Graph Theory Flashcards
Formal definition of a graph
A graph G is a pair (V(G), E(G)) where V(G) is a nonempty set of vertices/nodes and E(G) is a set of unordered pairs {u, v} where u, v ∈ V(G) and u =/= v, indicating there is an edge between u and v
V(G) and E(G) are often written as V and E, and {u, v} is written as uv
Digraph
Directed graph - edges can have directions
Multi-graph
Multiple edges allowed between two vertices
Pseudo-graph
Edges of the form uu (loops) are allowed
Weighted graphs
Vertices and edges can have weights
Neighbourhood of a vertex
N(v) is the set of neighbours of v, i.e. N(v) = {u ∈ V : uv ∈ E}
Degree of a vertex
deg(v) is the number of neighbours of v, i.e. the size of N(v)
δ(G) is the smallest degree in G
∆(G) is the largest degree in G
degree 0 = isolated vertex
degree 1 = end/pendant vertex
Subgraph
A subgraph G’ = (V’, E’) of G = (V, E) is a graph with V’ ⊆ V and E’ ⊆ E
It’s proper if G’ =/= G, and spanning if V’ = V (it has all the vertices of the original)
Induced subgraph
A subgraph that is made by just removing some vertices and their edges (no edges are removed unnecessarily)
Handshaking Lemma
In a graph G = (V, E): the sum of the degrees of the vertices is twice the number of edges
Proof: Every edge has two endpoints and contributes one to each of their degrees, so it contributes two to the sum of the degrees of the vertices
Path
Denoted by P_n, the graph with vertex set V = {v1, v2, …, v_n} and edge set E = {v1v2, v2v3, …, v_n-1 v_n}
Straight line of vertices
n-1 edges
Cycle
Denoted by C_n
The same as P_n but with an extra edge linking v_n and v_1
n edges
Length = number of edges
Complete bipartite graph
Denoted by K_p,q
A graph consisting of two sets of vertices (sizes p and q) connected in all possible ways (members of the same set are not connected)
pq edges
Complete graph
Denoted by K_n
A graph which contains all the possible edges between pairs of vertices
0.5n(n-1) edges
n-dimensional hypercube
A graph whose vertex set is {0, 1}^n (2^n vertices), and with an edge between vertices x and y if and only if they differ in exactly one bit.
Proof that an n-dimensional hypercube is bipartite
Let V1 contain all the vertices with an odd number of 1s
Let V2 contain all the vertices with an even number of 1s
This is a partition of V into two disjoint sets
Connected graph
Formal definition: Graph where any two vertices are connected by a path
Informal definition: A graph which is all in one piece, without any disconnected floating parts
What is an Eulerian circuit?
A circuit which traverses each edge exactly once and ends where it started
What is a Hamiltonian cycle?
A cycle which visits each vertex exactly once and ends where it started
Circuit vs cycle vs path
All types of walk
Path = Does not repeat vertices or edges
Cycle = Does not repeat vertices or edges, starts and ends on the same vertex
Circuit = Repeats vertices but not edges
Length = number of edges
Eulerian circuit theorem
A connected graph with at least two vertices has an Eulerian circuit if and only if each of its vertices has an even degree
Using the TSP to detect Hamiltonian cycles
For each vertex v, create a city c_v
For each pair of distinct u, v ∈ V, set the distance between c_u and c_v to 1 if uv ∈ E, and 2 otherwise
If G has a Hamiltonian cycle, then it’s a route of cost n. This is because if there’s a route of cost n then it can’t use pairs with cost 2, so it must go through all edges of G.
Therefore the problem of finding a Hamiltonian cycle has been reduced to a TSP.
Forests and trees
A forest is an acyclic graph (one without cycles)
A tree is a connected forest (i.e. a connected graph without cycles)
Spanning trees
A subgraph of a graph is spanning if it has the same set of vertices
Spanning trees theorem
Every connected graph contains a spanning tree (a spanning subgraph that is a tree)
Proof of the spanning trees theorem
Let G be a connected graph
If G has no cycles, it is a tree and therefore a spanning tree of itself
If it has a cycle, we can remove an edge from this cycle and the new graph will still be connected. We can repeat this until all cycles are destroyed and we have a spanning tree.
Therefore trees are the smallest connected structures.
Leaves in trees
A leaf is a vertex of degree 1
Leaf lemma
Every tree on at least two vertices contains a leaf
Proof of leaf lemma
By contradiction:
Assume that every vertex does not have degree 1
If a vertex has degree 0 then the graph is not connected and is therefore not a tree
If every vertex has degree 2+, then we can start at a vertex and go to one of its neighbours, and from there go to another neighbour until we encounter a vertex we’ve already visited. This implies that the graph contains a cycle and is therefore not a tree.
Edges of trees theorem
A connected graph on n vertices is a tree if and only if it has n-1 edges
What is a walk
A sequence of edges v0v1, v1v2, v2v3, …, v_n-1 v_n
v0, v1, …, v_n is also a walk in G
Closed walk = ends on the same vertex it started on
Distance between vertices
The length of a shortest path from u to v if a path exists, infinity otherwise
Diameter of a graph
Largest distance between two vertices
What is a connected component
A connected subgraph which is not part of any larger connected subgraph. Every graph contains at least |V| - |E| connected components
What does it mean if a directed graph G is weakly connected?
The graph obtained from G by removing directions is connected
What does it mean if a directed graph G is strongly connected?
Any two distinct vertices are connected by directed paths in both directions
What is a strongly connected component of a digraph?
A strongly connected subgraph which is not part of any larger strongly connected subgraph.
Unique path lemma
If T is a tree containing two distinct points u and v, there is only one path between u and v
This is because if there were two paths, then those paths would form a cycle, which violates the definition of a tree
What is a rooted tree
A tree in which one vertex is fixed as the root, and every edge is directed away from it.
If a vertex in a rooted tree has children, it’s an internal vertex
Number of leaves in a tree on at least 2 vertices where at least n vertices have degree at least 3
n + 2
Isomorphic graphs
Two graphs are isomorphic if there exists a bijective function f: V => V’ such that for every u, v ∈ V we have: uv ∈ E if and only if f(u)f(v) ∈ E’
Then we write: G ~= G’
Essentially this means that the vertices in G’ can be renamed to make it coincide with G
Isomorphic graphs share all their structural characteristics
Isomorphism on rooted trees
In a rooted tree T with root r, the level L(i) is the set of vertices at distance i from the root r
Determining if two rooted trees T1 and T2 are isomorphic
If r is a leaf of T1 then label it 10
Otherwise recurse into every child of r
Sort the labels of the children of r in decreasing order
Label the root “1” + all the labels of its children + “0”
Repeat this process for T2
m-ary tree
A rooted tree where each internal vertex has at most m children. It is a full m-ary tree if each internal vertex has exactly m children.
2-ary trees = binary trees
A full m-ary tree with i internal nodes has n = mi + 1 vertices
Balanced m-ary tree
All leaves in it have height h-1 or h
Adjacency list of a graph
For each vertex v, list all the vertices adjacent to it
Adjacency matrix of a graph
The entry in row i column j is 1 if vertex j shares an edge with vertex i, and 0 otherwise
Breadth-first Search
Create a queue which contains vertices which have been discovered but are waiting to be processed. Colour the vertices: white = undiscovered, grey = discovered and unprocessed, black = processed
Create an array d (distance from source s). If we discover a new vertex v while processing u, set d[v] = d[u] + 1
Add source vertex to queue
While the queue is not empty, remove the first vertex from the queue (oldest), change it to black and add its white neighbours to the queue and distance array (also change them to grey)
BFS analysis
Initialisation = O(V)
All queuing operations = O(V)
Each adjacency list is read once, their combined length is O(E)
Total running time is O(V+E)
Breadth-first tree
All the edges used to discover other vertices. A path from s to another vertex v through the tree is the shortest path between s and v. We can build up this tree by recording all the predecessors as we do the BFS.
Distance of two vertices in a graph
The length of the shortest path which connects them
Depth-first search
DFS(G, n)
Mark n as grey (visited)
Increment time by 1
Time when n was discovered := time
For each white (unvisited) node n’ adjacent to n: add n’ to predecessor array, DFS(G, n’)
Mark n as black
Time when n was finished := time
BFS vs DFS
BFS: searches layer-by-layer, computes shortest paths, removes the element which has been in S the longest (queue/FIFO)
DFS: digs deeper until no longer possible, removes the element which has been in S the shortest (queue/LIFO), mainly used for connectivity-type problems (i.e. reachability problems)
Both appropriate for graph exploration, linear time (very fast), list all vertices reachable from start vertex
DFS analysis
Initialisation takes time O(V)
O(V) is spent on incrementing time, updating d and f, and colouring vertices
O(E) is spent considering each vertex in each adjacency list
Overall time = O(V+E)
Depth-first forest
The predecessor subgraph, which has the same vertex set as the graph, is a depth-first forest
In the original graph:
- Tree edges are edges which are also in the DFS forest
- Back edges are edges that join a vertex to an ancestor
- Forward edges are edges not in the forest which join a vertex to its descendant
- Cross edges are all other edges
In an undirected graph, every edge is a tree edge or a back edge
