Graphs, Networks & Algorithms Flashcards
Adjacent vertices
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
Describe A_n graphs
straight line of n vertices
Describe D_n graphs
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)
Describe E_n graphs
(n≥6)
straight line of n-1 vertices, with an extra vertex connected to the third left most vertex
Circuit/cycle
a path begins and ends at the same vertex
Eulerian Path
Paths that use every edge in the graph precisely once
Power set of V [P(V) and P_n(V)]
P(V)
the set of all subsets of V
P_n(V)
the set of subsets of V containing n elements
Finite Graph
(V,E,ε)
V and E are finite sets
Loop free graph
(V,E,ε)
Im(ε) ⊂ P_2(V)
Simple graph
Loop free, and ε injective
There is at most one edge between 2 vertices
Complete graph (K_n)
Simple, and Im(ε)=P_2(V)
(No loops, and there is exactly one edge between each pair of vertices
Automorphism
of graph G is an isomorphism G->G
Define cardinality
the number of elements in a set
Define Injective function
(one-to-one function)
each element of the codomain (ouptput) is mapped to by at most one element of the domain (input)
Define surjective function
each element of the codomain (output) is mapped to by at least one element of the domain
Define Bijective function
Injective and surjective
each element of the codomain is mapped to by exactly one element of the domain
What is the relation between morphisms and cycles?
Morphisms of graphs must take cycles of a given length to cycles of the same length.
Another term for a homomorphism
morphism
Directed graph
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
Inverse to an isomorphism (Ф,ψ)
( Ф^(-1), ψ^(-1) )
Chromatic number?
give a practical definition
The smallest number of colours needed to colour the vertices in such a way that adjacent vertices have distinct colours.
Relation between chromatic number and chromatic polynomial
By definition, the chromatic number is the smallest natural number n s.t. P_G(n) is non zero
The chromatic polynomial for the complete graph K_r
P_G(n) = n(n-1)(n-2)…(n-r+1)
Simple definition of an algorithm
A set of rules by which the answer to a problem can be found
Attributes of an algorithm
Finiteness Definiteness Input Output Effectiveness
Simple definition for the complexity of an algorithm
The time taken for the algorithm to terminate as a function of its inputs
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
Polynomial-Time problem
Can be solved by a polynomial-time algorithm
on a deterministic Turing Machine
What is a non-deterministic Turing machine?
Hypothetical machine that follows instructions
But is allowed to make guesses
And always guesses correctly
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
Δ(G)
Maximum degree of graph G
max v∈V, deg(v)
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) ≥ … .
Define the degree of a vertex
The degree of vertex v, deg(v), is the number of edges that contain v as an endpoint
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
Kuratowski’s Theorem
A graph is planar iff it does not contain K5 or K3,3 as a minor
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
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)
The surface of genus 0
sphere
plane
Practical explanation of genus in relation to surface
The genus counts the number of ‘holes’ in the surface
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)
Ribbon graph
Is a graph defined as a quadruple (V, H, τ, w)
AND
a cyclic ordering of the half-edges at each vertex
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
What is the maximum number of vertices of a graph to guarantee it is planar?
4
Do loops and multiple edges affect planarity?
No
The Graph Minor Theorem
In any infinite list of graphs, some graph is a minor of another
Every planar map can be coloured using no more than … colours
6
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
Thickness of graph G, i.e. t(G)
smallest number of disjoint edge sets Ei
required in planar decomposition of G
Connected graph G
For any distinct vertices v=/=u
there is a path in G from v to u
A is the adjacency matrix What does (A^n)_i,j denote
The number of paths of length n from vertex i to j
Non-trivial cycle in G
A cycle in which each edge is used no more than once
Tree
A finite, connected graph
that contains NO non-trivial cycles
Complexity of Kruskal’s Algorithm
O( |E| ⋅ log|E| )
Complexity of Prim’s Algorithm
O( |V| |E| )
Complexity of Dijkstra’s Algorithm
O( |V|^2 )
What is the type of graph that can be used in Kruskal’s/Prim’s algorithm?
Finite, connected, metric graph
G=(V,E,ε,μ)
Define metric graph
A graph together with a metric
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)
Define a metric on G
Function μ:E→ℝ+
assigning a strictly positive number to each edge of G
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
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’
Describe a graph in terms of ‘connected components’
A graph is a disjoint union of its connected components
s and t in a directed graph
s ~ source
t ~ sink
Another name for ‘feasilble flow’
flow
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)
Define the value of a flow
v(f)
net flow into the sink t
What is the aim of the Ford-Fulkerson algorithm?
Computes a maximal flow
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)
If A is symmetric, what other assumptions can you make about A?
eigenvalues of A are real
A is diagonisable
Spectrum of A
The set of eigenvalues of A
Represented as an increasing sequence of (real) numbers
Heuristic method
An algorithm that produces a good solution, with no guarantee of optimality.
Sensitivity analysis
Analysing the behaviour of an algorithm as we change some input
Fixed point free graph
E.g. τ(h) ≠ h
Involution graph
The graph composed with itself is the identity function
Combinatorial metric
every edge is given length 1
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
Acyclic graph
Graph that contains no cyclic subgraphs
Maximal flow
feasible flow
v(f) >= v(f’) for feasible flows f’
Flow augmenting chain
A path along which the flow can be increased
