Graph Theory Flashcards
What is a graph?
Pair of sets (V(G),E(G)), where each element of E consists of a pair of elements of V
What is a walk in a graph G?
A sequence of vertices v_1 v_2 … v_n such that {v_i, v_i+1} is in E(G) for 1 <= i < n
What is a path in a graph G?
A walk where all the vertices are distinct
What is a cycle?
A closed walk of at least 3 vertices with otherwise distinct vertices
What does is mean for a graph G to be connected?
For any two vertices x,y in V(G), there is an xy-walk in G
What does it mean for two vertices x,y to lie in the same component?
They are joined by an xy-walk
What is a tree?
A minimally connected graph
Prove that any tree is acyclic
- SFAC there is a cycle in T
- Remove some edge e in this cycle
- Then we obtain a path, P
- Take two vertices x,y in T
- Since T is connected, there is an xy-walk between them
- If this walk used the edge we removed, replace it with the path P
- This is still an xy-walk
- So T-{e} is connected
- Contradicts minimality of T
- So T is acyclic
Prove that a connected & acyclic graph G is a tree
- SFAC G - {e} is connected for some e = xy in G
- Let W be a shortest xy-walk in G-{e}
- Then W must be an xy-path (otherwise it wouldn’t be the shortest)
- So if we add e back in, we get a cycle, but G was acyclic, contradiction
Prove that any two vertices in a tree are joined by a unique path
- SFAC this isn’t true
- i.e. there are two distinct xy-paths in T, P_1 and P_2
- Suppose P_1 is the shortest over all such choices of x and y
- Then P_1 and P_2 intersect only at x and y
- But this is a cycle, contradiction
Prove that any tree with at least two vertices has at least two leaves
- Let P be a longest path in T
- If the start / end of P had another neighbour in V(T)/V(P), we could make the path longer
- If the start / end of P had another neighbour in V(P) other than the next in the sequence P, we would have a cycle
- So the two ends of P must be leaves.
What is a leaf?
A vertex of degree 1
Prove that if T is a tree and v is a leaf, then T-v is a tree
- Suffices to show T-v is connected & acyclic
- Know T is acyclic, and we can’t create a cycle by removing an edge, so T-v is acyclic
- Know T is connected
- For any x,y in T-v, the unique xy-path in T is contained in T-v
- So T-v is a tree
Prove that any tree on n vertices has n-1 edges
- By induction
- A tree with 1 vertex has 0 edges
- Consider a tree T on n vertices
- Know T has a leaf v
- Know T-v is a tree
- T-v has n-1 vertices and n-2 edges by induction hypothesis
- So T has n vertices & n-1 edges
What is a spanning tree?
Minimally connected subgraph of the same vertex set
Prove that a connected graph with n-1 edges and n vertices is a tree
- Let H be a spanning tree of G
- H has n vertices and n-1 edges
- so H=G, i.e. G is a tree
What is a minimum cost spanning tree of G?
A spanning tree T of G such that for any other spanning tree T’, C(T’) >= C(T)
Describe Kruskal’s algorithm
- A_0 = {}
- Check if there is an edge e in G / A_i such that (V(G), A_i U {e}) is acyclic
- If not, output A = A_i and stop
- If there is, set A_i+1 = A_i ∪ {e} for one such e such that c(e) is minimal, then increase i by 1
Prove that Kruskal’s algorithm produces a minimum cost spanning tree of G
[CONTINUE]
What is an Euler trail?
A walk such that every edge in a graph appears exactly once
What is an Euler tour?
A closed Euler trail
What is an Eulerian graph?
A graph where every edge is of even degree (in an Euler tour, we use one edge to enter a vertex, and a different edge to leave).
What is Eulers theorem?
a connected Eulerian graph has an Euler Tour
Prove Eulers theorem
- Will prove that Fleury’s algorithm produces an Euler tour.
- [CONTINUE]
Describe Fleury’s Algorithm
- Start at any vertex
- Follow a walk, deleting each edge after it is used
- At each step, ensure that after any isolated vertices are removed the graph is still connected, and that we do not run along an edge to a leaf, unless that is the only option.
Prove that in any graph there are an even number of vertices of odd degree
- The sum of the degrees of all the vertices in a graph is equal to 2 x no. of edges (since each edge connects to two vertices).
- So the sum of the degrees of the vertices must be even
- So there must be an even number of odd degree vertices
What is a Hamiltonian cycle?
A closed walk that visits every vertex exactly once
What is a hamiltonian graph?
A graph that contains a Hamiltonian cycle
State Ore’s theorem
- G a connected graph with n >= 3 vertices
- For every pair of non-adjacent vertices x & y, d(x) + d(y) >= n
- Then G is hamiltonian
State Dirac’s theorem
- G connected graph with n>= 3 vertices
- For ever vertex v, d(v) >= n/2
- Then G is Hamiltonian
Prove that if G is connected an non-hamiltonian, then the length of the longest path is at least as long as the longest cycle
- Let C be a longest cycle with length L
- Since G is not hamiltonian, there is some vertex not in C.
- Since G is connected, there is some edge vu with u in C and v not in C
- Remove an edge of C that contains u and replace it with uv
- This gives a path of length L
Prove ore’s theorem
- SFAC G is not hamiltonian
- Let P = x1 x2 … xk be a longest path in G
- P has length k-1
- So G doesn’t have a cycle of length k (length of longest path >= length of longest cycle)
- So x1 and xk are not adjacent
- So d(x1) + d(xk) >= n
- [CONTINUE]
What is an L-shortest xy-path?
An xy-path P that minimises L(P)
Describe Dijkstra’s algorithm
- Goal: Find an L-shortest xy-path
- Set U = V(G), D(x) = 0, D(v) = infinity for v != x
- If U is empty, stop
- Otherwise:
- Pick u in U with D(u) minimal
- Delete u from U
- For any v in U that is adjacent to u, with D(v) > D(u) + L(uv), replace D(v) by D(u) + L(uv)
- Repeat
What is an L-shortest paths tree rooted at x of a graph G?
- A spanning tree T
- For any y in V(G), the unique xy path in T is an L-shortest xy-path in G.
Wrt Dijkstra’s, what is the parent of a vertex v?
The last vertex u such that we replaced D(v) by D(u) + L(uv)
How would you use Dijkstra’s to get an L-shortest paths tree rooted at x?
- Run the algorithm
- Determine the parent of each vertex
- Draw an edge from each vertex to its parent
What is a matching?
A subset of the edge set M such that the edges in M are pairwise disjoint.
What is a perfect matching?
A matching M such that every vertex of the graph belongs to some edge of M
What is a bipartite graph G?
A graph such that V(G) can be partitioned into two sets A, B so that every edge of G crosses between A and B
If M is a matching and P is a path, what does it mean for P to be an M-alternating path?
Every other edge of P is in M
If M is a matching and P is a path, what does it mean for P to be an M-augmenting path?
Every other edge of P is in M and it’s end vertices are not in any edge of M
If M is a matching in G, prove that M is not of maximum size if and only if there is an M-augmenting path in G
- If there is an M-augmenting path in P, we can create a larger matching by “flipping” every edge of P (replace M by M \ (M ∩ E(P)) ∪ (E(P) \ M))
- Suppose M* is a matching with more edges than M
- Let H = M U M*
- Every vertex has degree at most 2 in H
- So each component of H is an edge, path or cycle
- The edge components consist of M ∩ M*
- The edges in path and cycle components alternate between M and M*
- As |M| > |M| we can find a path component with more edges of M
than M - This is an M-augmenting path in G.
Describe the Hungarian algorithm for finding a maximum matching in G
What is a cover of G?
A set of vertices C such that every edge contains at least one vertex of C
What is the relationship between the size of a matching and the size of a cover?
|M| <= |C|
What is Konig’s theorem?
In any bipartite graph, the size of a maximum matching equals the size of a minimum cover
Prove Konig’s theorem
For a bipartite graph with parts A,B and a set S, a subset of A, what is the neighbourhood of S?
N(S) = ∪a∈S{b : ab ∈ E(G)}
i.e. the set of vertices in B that are joined by an edge to a vertex in S
What is Hall’s theorem?
- Let G be a bipartite graph with parts A,B
- Then G has a matching covering A if and only if every S a subset of A has |N(S)| >= |S|
Prove Hall’s theorem
What is a postman walk in G?
A walk that uses every edge in G at least once
Describe Edmond’s algorithm for the chinese postman problem
For a graph H in which not all degrees are even, prove there is a path in H such
that both ends have odd degree
Prove that Edmonds’ Algorithm finds a minimum length postman walk.
What is the chinese postman problem?
The problem of finding the shortest postman walk - a walk that uses every edge of G at least once
