Graph Theory Matús Mihalák
General graphs
A graph G has vertices V and edges E, notation: G = (V, E).
• ∑𝑣∈𝑉 𝑑(𝑣) = 2|𝐸| (sum of all degrees of vertices is equal to twice the number of edges)
• 𝛿(𝐺): minimum degree of G → vertex with the minimum degree (𝛿(𝐺) ≤ 𝑛 − 1)
• ∆(𝐺): maximum degree of G → vertex with the maximum degree
∑𝑣∈𝑉 𝑑(𝑣)
• 𝑑(𝐺): average degree of G ( )
|𝑉|
• Isomorphism: graphs that have the same number of vertices and edges and the same
edge connectivity (same vertices must be connected to each other).
Both graphs should have:
- Same |V| and |E|
- Same degree at every edge
- Same length of cycles
• Complete graph: every vertex is connected to every other vertex.
• Simple graph: unweighted, undirected graph containing no loops or multiple edges.
Vertices
• Number of vertices = |V| = n.
• Degree of a vertex = d(v).
• Vertices u and v are adjacent (neighbours) if there exists an edge with vertices u and v
and endpoints in E ( {𝑢, 𝑣} ∈ 𝐸 ).
• For an edge e= {u, v}, u and v are endpoints or end-vertices of edge e.
• Neighbourhood of a vertex v in a graph G= (V, E) is a set of all vertices that are connected
by edges to vertex v: 𝑁𝐺 (𝑣) = {𝑢|𝑢 ∈ 𝑉 ∧ {𝑢, 𝑣} ∈ 𝐸}
• A vertex with degree 1 is a leaf (especially makes sense in a tree).
Edges
• Number of edges = |E| = m.
• Edge e is incident to vertex v if there exists an edge e in E that has v as an endpoint.
A clique is a subset of vertices such that every vertex is connected to every other vertex in the
clique, meaning the subgraph (clique) is complete.
𝑉 ′ ⊆ 𝑉 such that ∀ 𝑢, 𝑣 ∈ 𝑉 ′ : {𝑢, 𝑣} ∈ 𝐸
Tours
Path: a set of vertices and a set of edges that connect every vertex to the next vertex in the set.
So it is a non-empty graph P= (V, E) of the form V= {x0, x1, …, xk}, E= {x0x1, x1x2, …, xk-1xk} and every
xi,xj (i≠j) are distinct vertices.
• Length of a path P is the number of edges of P (|E|)
• Pxi: x0,x1,…,xi
xiP: xi,xi+1,…,xk
xiPxj: xi,…,xj
• Two paths P and P’ are independent if none of the paths contains an inner vertex of the
other path, but they may contain end-vertices of the other path.
, • d(u, v): distance between vertices u and v is the length of the shortest path from u to v.
If no path exists, then d(u, v) = ∞.
• Shortest path
- dk[u]: weight of shortest s-u path using ≤ k edges
- Computing this u-v path by Dijkstra’s algorithm for positive weights (O(n
Log(n)+m)):
▪ Greedy algorithm
▪ Maintain d[v] for all v in V, upper-bound on d (u,v)= ∞
▪ D[v]=0 and S=∅
▪ Step-by-step, d[v] becomes d(u,v):
WHILE S≠V DO
u⟵arg minv⊆V\S d[v] (minimum of d[v]-list)
S⟵ S ∪ {u}
∀ edges (u,x) ∈ E:
IF d[x]>d[u]+w(u,x)THEN
d[x]:= d[u]+w(u,x)
▪ Keeps S⊆V, a set of “fixed” vertices for which d[v]=dist(u,v)
- Bellman-Ford algorithm (O(nm)):
▪ D[v]:= ∞, 𝜋[v]=NIL (undefined)
▪ D[s]=0, 𝜋[s]=s
▪ FOR k=1 to n-w DO
• ∀ edges (u,v) ∈E
o IF d[v]>d[u]+w(u,v) THEN
D[v]:= d[u]+w(u,v)
𝜋[v]=u
▪ After round i: d[v1] = d(s, vi)
▪ There is a negative cycle in G if and only if ∃ edge (u, v) ∈ E:
𝑑[𝑣] > 𝑑[𝑢] + 𝑤(𝑢, 𝑣). So, using n edges to get cheaper to v means there
is a negative cycle.
- Path P from s-t is a shortest path, then ∀ u, v ∈ P, uPv is a shortest u-v path in G (if
no negative weighted cycles in G).
▪ Keep d[v] upper-bound on d(s,v)
▪ Keep 𝜋[v] predecessor of v on a shortest s-v path
▪ Compute shortest s-v paths using at most k
edges (k=0,1,…,n-1)
▪ Example:
• K=0 d[s]=0 - d[v1] = d[v2] = d[v3] = d[t]= ∞
• K=1 d[s]=0 - d[v1]=11 - d[v2]=8 - d[v3]= ∞ - d[t]=10
• K=2 d[s]=0 - d[v1]=11 - d[v2]=8 - d[v3]=10 - d[t]=9
• K=3 d[s]=0 - d[v1]=11 - d[v2]=8 - d[v3]=10 - d[t]=7
• diam(G): diameter is the largest distance between any two vertices u and v (so the largest
shortest path!)
• G is disconnected if there exists u and v such that there is no path from u to v.
• Alternating path: a path in G starting with an unmatched vertex and edges on the path
alternate with “∉ 𝑀” and “∈ 𝑀”.
• Augmenting path is a path P in a graph G= (V, E) with a matching M (improved idea of the
maximum matching algorithm).
- It starts and ends with an unmatched vertex.
- Every second edge in P is ∈ M.
- Then, augment matching along path P, i.e. flipping.
• The algorithm returns a maximum matching, because for any matching M of graph G:
General graphs
A graph G has vertices V and edges E, notation: G = (V, E).
• ∑𝑣∈𝑉 𝑑(𝑣) = 2|𝐸| (sum of all degrees of vertices is equal to twice the number of edges)
• 𝛿(𝐺): minimum degree of G → vertex with the minimum degree (𝛿(𝐺) ≤ 𝑛 − 1)
• ∆(𝐺): maximum degree of G → vertex with the maximum degree
∑𝑣∈𝑉 𝑑(𝑣)
• 𝑑(𝐺): average degree of G ( )
|𝑉|
• Isomorphism: graphs that have the same number of vertices and edges and the same
edge connectivity (same vertices must be connected to each other).
Both graphs should have:
- Same |V| and |E|
- Same degree at every edge
- Same length of cycles
• Complete graph: every vertex is connected to every other vertex.
• Simple graph: unweighted, undirected graph containing no loops or multiple edges.
Vertices
• Number of vertices = |V| = n.
• Degree of a vertex = d(v).
• Vertices u and v are adjacent (neighbours) if there exists an edge with vertices u and v
and endpoints in E ( {𝑢, 𝑣} ∈ 𝐸 ).
• For an edge e= {u, v}, u and v are endpoints or end-vertices of edge e.
• Neighbourhood of a vertex v in a graph G= (V, E) is a set of all vertices that are connected
by edges to vertex v: 𝑁𝐺 (𝑣) = {𝑢|𝑢 ∈ 𝑉 ∧ {𝑢, 𝑣} ∈ 𝐸}
• A vertex with degree 1 is a leaf (especially makes sense in a tree).
Edges
• Number of edges = |E| = m.
• Edge e is incident to vertex v if there exists an edge e in E that has v as an endpoint.
A clique is a subset of vertices such that every vertex is connected to every other vertex in the
clique, meaning the subgraph (clique) is complete.
𝑉 ′ ⊆ 𝑉 such that ∀ 𝑢, 𝑣 ∈ 𝑉 ′ : {𝑢, 𝑣} ∈ 𝐸
Tours
Path: a set of vertices and a set of edges that connect every vertex to the next vertex in the set.
So it is a non-empty graph P= (V, E) of the form V= {x0, x1, …, xk}, E= {x0x1, x1x2, …, xk-1xk} and every
xi,xj (i≠j) are distinct vertices.
• Length of a path P is the number of edges of P (|E|)
• Pxi: x0,x1,…,xi
xiP: xi,xi+1,…,xk
xiPxj: xi,…,xj
• Two paths P and P’ are independent if none of the paths contains an inner vertex of the
other path, but they may contain end-vertices of the other path.
, • d(u, v): distance between vertices u and v is the length of the shortest path from u to v.
If no path exists, then d(u, v) = ∞.
• Shortest path
- dk[u]: weight of shortest s-u path using ≤ k edges
- Computing this u-v path by Dijkstra’s algorithm for positive weights (O(n
Log(n)+m)):
▪ Greedy algorithm
▪ Maintain d[v] for all v in V, upper-bound on d (u,v)= ∞
▪ D[v]=0 and S=∅
▪ Step-by-step, d[v] becomes d(u,v):
WHILE S≠V DO
u⟵arg minv⊆V\S d[v] (minimum of d[v]-list)
S⟵ S ∪ {u}
∀ edges (u,x) ∈ E:
IF d[x]>d[u]+w(u,x)THEN
d[x]:= d[u]+w(u,x)
▪ Keeps S⊆V, a set of “fixed” vertices for which d[v]=dist(u,v)
- Bellman-Ford algorithm (O(nm)):
▪ D[v]:= ∞, 𝜋[v]=NIL (undefined)
▪ D[s]=0, 𝜋[s]=s
▪ FOR k=1 to n-w DO
• ∀ edges (u,v) ∈E
o IF d[v]>d[u]+w(u,v) THEN
D[v]:= d[u]+w(u,v)
𝜋[v]=u
▪ After round i: d[v1] = d(s, vi)
▪ There is a negative cycle in G if and only if ∃ edge (u, v) ∈ E:
𝑑[𝑣] > 𝑑[𝑢] + 𝑤(𝑢, 𝑣). So, using n edges to get cheaper to v means there
is a negative cycle.
- Path P from s-t is a shortest path, then ∀ u, v ∈ P, uPv is a shortest u-v path in G (if
no negative weighted cycles in G).
▪ Keep d[v] upper-bound on d(s,v)
▪ Keep 𝜋[v] predecessor of v on a shortest s-v path
▪ Compute shortest s-v paths using at most k
edges (k=0,1,…,n-1)
▪ Example:
• K=0 d[s]=0 - d[v1] = d[v2] = d[v3] = d[t]= ∞
• K=1 d[s]=0 - d[v1]=11 - d[v2]=8 - d[v3]= ∞ - d[t]=10
• K=2 d[s]=0 - d[v1]=11 - d[v2]=8 - d[v3]=10 - d[t]=9
• K=3 d[s]=0 - d[v1]=11 - d[v2]=8 - d[v3]=10 - d[t]=7
• diam(G): diameter is the largest distance between any two vertices u and v (so the largest
shortest path!)
• G is disconnected if there exists u and v such that there is no path from u to v.
• Alternating path: a path in G starting with an unmatched vertex and edges on the path
alternate with “∉ 𝑀” and “∈ 𝑀”.
• Augmenting path is a path P in a graph G= (V, E) with a matching M (improved idea of the
maximum matching algorithm).
- It starts and ends with an unmatched vertex.
- Every second edge in P is ∈ M.
- Then, augment matching along path P, i.e. flipping.
• The algorithm returns a maximum matching, because for any matching M of graph G:
