Brainscape's Knowledge GenomeTM


Top Flashcards (Certified)
All Flashcards

Uni Maths > Graphs, Networks & Algorithms > Flashcards

Graphs, Networks & Algorithms Flashcards

(79 cards)

Start Studying
1
Q

Adjacent vertices

A

Two vertices are adjacent if they are connected by an edge. If vertex i is adjacent to vertex j, we write i ∼ j.
{i,j} = ε(e) for some edge e ∈ E

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Describe A_n graphs

A

straight line of n vertices

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Describe D_n graphs

A

n≥4
Straight line of of n-2 vertices, with an extra 2 vertex connected to the leftmost vertex
(Or a straight line of n-1 vertices, with an extra vertex connected to the second left most vertex)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Describe E_n graphs

A

(n≥6)

straight line of n-1 vertices, with an extra vertex connected to the third left most vertex

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Circuit/cycle

A

a path begins and ends at the same vertex

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Eulerian Path

A

Paths that use every edge in the graph precisely once

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Power set of V [P(V) and P_n(V)]

A

P(V)
the set of all subsets of V
P_n(V)
the set of subsets of V containing n elements

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Finite Graph

A

(V,E,ε)

V and E are finite sets

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Loop free graph

A

(V,E,ε)

Im(ε) ⊂ P_2(V)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Simple graph

A

Loop free, and ε injective

There is at most one edge between 2 vertices

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Complete graph (K_n)

A

Simple, and Im(ε)=P_2(V)

(No loops, and there is exactly one edge between each pair of vertices

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Automorphism

A

of graph G is an isomorphism G->G

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Define cardinality

A

the number of elements in a set

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Define Injective function

A

(one-to-one function)

each element of the codomain (ouptput) is mapped to by at most one element of the domain (input)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Define surjective function

A

each element of the codomain (output) is mapped to by at least one element of the domain

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Define Bijective function

A

Injective and surjective

each element of the codomain is mapped to by exactly one element of the domain

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

What is the relation between morphisms and cycles?

A

Morphisms of graphs must take cycles of a given length to cycles of the same length.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Another term for a homomorphism

A

morphism

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Directed graph

A

Digraph/Quiver.
Edges are allocated one direction of travel

Quadruple (V,E,h,t)
V vertices
E edges/ARROWS
h,t: E → V declaring the head and tail of each arrow respectively

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Inverse to an isomorphism (Ф,ψ)

A

( Ф^(-1), ψ^(-1) )

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Chromatic number?

give a practical definition

A

The smallest number of colours needed to colour the vertices in such a way that adjacent vertices have distinct colours.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

Relation between chromatic number and chromatic polynomial

A

By definition, the chromatic number is the smallest natural number n s.t. P_G(n) is non zero

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

The chromatic polynomial for the complete graph K_r

A

P_G(n) = n(n-1)(n-2)…(n-r+1)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

Simple definition of an algorithm

A

A set of rules by which the answer to a problem can be found

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Attributes of an algorithm
``` Finiteness Definiteness Input Output Effectiveness ```
26
Simple definition for the complexity of an algorithm
The time taken for the algorithm to terminate as a function of its inputs
27
What do P and NP stand for?
``` P: The class of all polynomial-time problems NP: The class of all non-deterministic polynomial-time problems ```
28
Polynomial-Time problem
Can be solved by a polynomial-time algorithm | on a deterministic Turing Machine
29
What is a non-deterministic Turing machine?
Hypothetical machine that follows instructions But is allowed to make guesses And always guesses correctly
30
What do P and NP stand for?
``` P: The class of all polynomial-time problems NP: The class of all non-deterministic polynomial-time problems ```
31
Δ(G)
Maximum degree of graph G | max v∈V, deg(v)
32
Additional step to make the greedy colouring algorithm the Welsh-Powell algorithm?
[Given a non-empty loop-free graph G=(V,E,ε).] | Sort the vertices into order of decreasing vertex degrees deg(v1) ≥ deg(v2) ≥ ... .
33
Define the degree of a vertex
The degree of vertex v, deg(v), is the number of edges that contain v as an endpoint
34
Planar Graph
The graph can be drawn in the plane in such a way that the vertices are distinct points and edges only meet at incident vertices
35
Kuratowski's Theorem
A graph is planar iff it does not contain K5 or K3,3 as a minor
36
Equation satisfied by a SIMPLE, PLANAR, CONNECTED graph
3f ≤ 2e [f ≤ 2e/3] Every edge bounds 2 faces Every face has at least 3 edges bounding it
37
Graph G is a minor of G' if ...
``` G can be obtained from G' by deleting edges deleting vertices (and incident edges) contracting edges (removing an edge while simultaneously merging the two vertices that it joined) ```
38
The surface of genus 0
sphere | plane
39
Practical explanation of genus in relation to surface
The genus counts the number of 'holes' in the surface
40
Leg(u)
u is vertex Leg(u) = w^(-1)(u) The set of half-edges incident/attached to u Cardinality of Leg(u) = size of set Leg(u) = deg(u)
41
Ribbon graph
Is a graph defined as a quadruple (V, H, τ, w) AND a cyclic ordering of the half-edges at each vertex
42
What makes 2 RIBBON graphs the 'same' i.e. isomorphic
The graphs are isomorphic | Ordering of edges around each vertex coincides under the graph isomorphism
43
What is the maximum number of vertices of a graph to guarantee it is planar?
4
44
Do loops and multiple edges affect planarity?
No
45
The Graph Minor Theorem
In any infinite list of graphs, some graph is a minor of another
46
Every planar map can be coloured using no more than ... colours
6
47
Planar decomposition of a graph (V,E,ε)
A partition of the edge set E in such a way that each induced subgraph Gi=( V, Ei, ε|_(Ei) ) is PLANAR
48
Thickness of graph G, i.e. t(G)
smallest number of disjoint edge sets Ei | required in planar decomposition of G
49
Connected graph G
For any distinct vertices v=/=u | there is a path in G from v to u
50
``` A is the adjacency matrix What does (A^n)_i,j denote ```
The number of paths of length n from vertex i to j
51
Non-trivial cycle in G
A cycle in which each edge is used no more than once
52
Tree
A finite, connected graph | that contains NO non-trivial cycles
53
Complexity of Kruskal's Algorithm
O( |E| ⋅ log|E| )
54
Complexity of Prim's Algorithm
O( |V| |E| )
55
Complexity of Dijkstra's Algorithm
O( |V|^2 )
56
What is the type of graph that can be used in Kruskal's/Prim's algorithm?
Finite, connected, metric graph | G=(V,E,ε,μ)
57
Define metric graph
A graph together with a metric
58
Spanning tree of G=(V,E,ε)
``` G is a finite connected graph A spanning tree of a G is a subgraph T=(V_T, E_T, ε_T) of G s.t. T is a tree, and V_T=V (T contains every vertex in V) ```
59
Define a metric on G
Function μ:E→ℝ+ | assigning a strictly positive number to each edge of G
60
Length of a graph H=(V_H, E_H, ε_H) | l(H)
l(H) = l(E_H) | The sum of all the metrics of all the edges in the set E_H
61
Length of a set of edges E' | l(E')
G=(V,E,ε,μ) E'⊂E finiite subset of the edges in G l(E') = Σe∈E μ(e) i.e. the sum of all the metrics of all the edges in the set E'
62
Describe a graph in terms of 'connected components'
A graph is a disjoint union of its connected components
63
s and t in a directed graph
s ~ source | t ~ sink
64
Another name for 'feasilble flow'
flow
65
Define a feasible flow
function f:E→ℝ+ satisfying 1) 0 ≤ f(e) ≤ c(e) ∀e∈E 2) Outflow at each vertex = inflow (except s & t)
66
Define the value of a flow
v(f) | net flow into the sink t
67
What is the aim of the Ford-Fulkerson algorithm?
Computes a maximal flow
68
Max-flow Min-cut theory
The maximal flow value from s to t = the minimum of the capacities of the cuts separating s from t (if a network is operating to capacity then a bottle neck is guaranteed)
69
If A is symmetric, what other assumptions can you make about A?
eigenvalues of A are real | A is diagonisable
70
Spectrum of A
The set of eigenvalues of A | Represented as an increasing sequence of (real) numbers
71
Heuristic method
An algorithm that produces a good solution, with no guarantee of optimality.
72
Sensitivity analysis
Analysing the behaviour of an algorithm as we change some input
73
Fixed point free graph
E.g. τ(h) ≠ h
74
Involution graph
The graph composed with itself is the identity function
75
Combinatorial metric
every edge is given length 1
76
Key difference between Kruskal's and Prim's
Kruskal's: add edges of lowest weight unless they make a non trivial cycle Prim's: start with a vertex, and add shortest edges from that vertex and the following corresponding vertices added unless they make a non trivial cycle
77
Acyclic graph
Graph that contains no cyclic subgraphs
78
Maximal flow
feasible flow | v(f) >= v(f') for feasible flows f'
79
Flow augmenting chain
A path along which the flow can be increased

Uni Maths (10 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2025 Bold Learning Solutions. Terms and Conditions