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.
