Graphs and trees: the structure that both search and neural networks stand on

Let V be a finite non-empty set; we call its elements vertices.

1. An undirected graph is a pair G = (V, E), where E ⊆ {{u, v} : u, v ∈ V, u ≠ v}; the elements of E are edges — two-element subsets of V. Vertices u, v are adjacent if and only if {u, v} ∈ E.
2. A directed graph is a pair G = (V, E), where E ⊆ V × V; an edge is an ordered pair (u, v) — an arrow from u to v. A directed graph is therefore a relation on V (see the part Sets and relations).
3. A weighted graph is a triple G = (V, E, w), where (V, E) is a graph as in 1 or 2 and w : E → ℝ is a function that assigns each edge e ∈ E a weight w(e) (length, cost, time).

Unless stated otherwise, a graph in this part is undirected.

Let G = (V, E) be an undirected graph and v ∈ V. The degree of the vertex v is the number of edges that contain it (that leave it):

deg(v) = |{e ∈ E : v ∈ e}|.

Theorem (handshaking lemma). Let G = (V, E) be an undirected graph. Then

∑_{v ∈ V} deg(v) = 2 |E|.

In particular, the sum of the degrees in every undirected graph is an even number.

Theorem. Let G = (V, E) be an undirected graph and L = {v ∈ V : deg(v) is odd} the set of its vertices of odd degree. Then |L| is an even number.

Proof. Split the sum of the degrees into vertices of even and of odd degree: ∑_{v ∈ V} deg(v) = ∑_{v ∈ V ∖ L} deg(v) + ∑_{v ∈ L} deg(v). By the handshaking lemma the left-hand side is 2|E|, which is even; the first sum on the right is a sum of even numbers, hence even. So the second must be even too — and a sum of |L| odd numbers is even if and only if |L| is even. ∎

That is why you cannot draw a graph with five vertices each of which has degree 3: the sum 15 would be odd.

Let G = (V, E, w) be a weighted undirected graph with non-zero weights (w(e) ≠ 0 for all e ∈ E) and n = |V| vertices, which we number: V = {v₁, …, v_n}. The adjacency matrix of the graph G is the square matrix A ∈ ℝ^n×n with entries (for i, j = 1, …, n)

A_ij = w({v_i, v_j}) if {v_i, v_j} ∈ E;   otherwise A_ij = 0.

The weights must be non-zero so that an edge can be told apart from a missing edge. For an unweighted graph we write 1 instead of the weight. Since {v_i, v_j} = {v_j, v_i}, an undirected graph has A_ij = A_ji, that is A = A^T.

For v ∈ V let N(v) denote the set of its neighbours:

N(v) = {u ∈ V : {u, v} ∈ E}.

The adjacency list is the mapping that assigns each vertex v ∈ V the set N(v), for a weighted graph together with the weights: {(u, w({u, v})) : u ∈ N(v)}. We have |N(v)| = deg(v).

The city graph: the matrix has 7 · 7 = 49 cells, of which only 24 are non-zero (each road twice, above and below the diagonal). The adjacency lists have ∑ deg(v) = 2 · 12 = 24 entries in total (colours as in the handshaking lemma above). Row B of the matrix is (4, 0, 5, 3, 7, 0, 0) — four non-zero numbers, because deg(B) = 4.

A road network with a million junctions, with 3 roads leaving each on average: |E| = 10⁶ · 3/2 = 1.5 · 10⁶. The matrix has (10⁶)² = 10¹² cells, the lists only 2 · 1.5 · 10⁶ = 3 · 10⁶ entries — more than three hundred thousand times fewer.

Let G = (V, E) be an undirected graph and u, v ∈ V.

1. A path from u to v is a sequence of vertices (v₀, v₁, …, v_k), k ≥ 0, such that v₀ = u,   v_k = v,   v_i ≠ v_j for i ≠ j,   {v_i−1, v_i} ∈ E for i = 1, …, k. Its length is k (the number of edges); in a weighted graph (V, E, w) it is the sum of the weights ∑_i=1^k w({v_i−1, v_i}).
2. A cycle is a sequence of vertices (v₀, v₁, …, v_k) with k ≥ 3 in which v₀, …, v_k−1 are pairwise distinct, v_k = v₀ and {v_i−1, v_i} ∈ E for i = 1, …, k — a path that returns to its starting vertex after at least three edges.
3. G is connected if and only if ∀u, v ∈ V there is a path from u to v.
4. Define a relation ∼ on V: u ∼ v if and only if there is a path from u to v. It is an equivalence (reflexive thanks to the path of length 0, symmetric by reversing the path, transitive because a path can be chosen from the concatenation of two paths). Its equivalence classes are the connected components of G; they therefore form a partition of V (see the part Sets and relations).

A graph is therefore connected if and only if it has a single connected component.

Let G = (V, E, w) be a weighted undirected graph with non-negative weights, w : E → [0, ∞), and u, v ∈ V. For a path π let w(π) = ∑_{e ∈ π} w(e) denote its length (the sum of the weights of its edges). The distance of the vertices u and v is

d(u, v) = min {w(π) : π is a path from u to v}   if at least one such path exists; otherwise d(u, v) = ∞.

The minimum exists because a finite graph has finitely many paths. For an unweighted graph we take w(e) = 1 for all e ∈ E; the distance is then the smallest number of edges of a path from u to v.

Theorem. Let G = (V, E, w) be a weighted graph with non-negative weights, w : E → [0, ∞), start ∈ V the starting vertex and d[·] the estimates of Dijkstra’s algorithm run from the start (described above). Then for every vertex u, at the moment the algorithm closes it,

d[u] = d(start, u).

Why: every other path to u must leave the set of closed vertices for the first time somewhere, through a vertex x whose estimate is ≥ d[u] (otherwise we would have picked x, not u). The rest of the path from x to u has non-negative length, so the whole path is not shorter than d[u]. ∎

With a negative edge this argument breaks down — “the rest of the path” could make the length shorter. Negative weights therefore need a different algorithm (Bellman–Ford).

Let G = (V, E) be an undirected graph.

1. G is a forest if and only if it contains no cycle (each of its connected components is then a tree).
2. G is a tree if and only if it is connected and contains no cycle.

Theorem. Let G = (V, E) be an undirected graph with n = |V| ≥ 1 vertices. Then the following statements are equivalent:

1. G is a tree;
2. G is connected and |E| = n − 1;
3. G contains no cycle and |E| = n − 1;
4. ∀u, v ∈ V there is exactly one path from u to v.

A rooted tree is a pair (T, r), where T = (V, E) is a tree and r ∈ V a marked vertex, the root. For v ∈ V:

1. the depth h(v) is the length (number of edges) of the unique path from r to v; in particular h(r) = 0;
2. the children of the vertex v are its neighbours in the direction away from the root, i.e. the vertices of the set {u ∈ N(v) : h(u) = h(v) + 1}; v is their parent;
3. v is a leaf if and only if it has no child.

Theorem. Let T = (V, E) be a tree with n = |V| ≥ 1 vertices. Then |E| = n − 1.

Lemma: let T be a tree with at least two vertices. Then T has a leaf, i.e. a vertex of degree 1. Proof of the lemma: take the longest path in the tree; its end vertex cannot have another neighbour off the path (the path could be extended) or on the path (a cycle would arise) — so it has degree 1.

Proof of the theorem by induction on n. Base case: a tree with 1 vertex has 0 edges. Inductive step: in a tree with n + 1 vertices remove a leaf together with its only edge. The rest is still connected and without cycles, hence a tree with n vertices, and by the induction hypothesis it has n − 1 edges. The original tree had one more, n. ∎

Let G = (V, E, w) be a connected weighted undirected graph.

1. A spanning tree of the graph G is a graph T = (V, F) with F ⊆ E that is a tree — it contains all vertices of G and only some of its edges.
2. The weight of a spanning tree is w(T) = ∑_{e ∈ F} w(e).
3. A spanning tree T is minimum if and only if w(T) ≤ w(T′) for every spanning tree T′ of the graph G.

Kruskal’s algorithm.

• Input: a connected weighted undirected graph G = (V, E, w) with m = |E| edges.
• Output: a set of edges F ⊆ E such that (V, F) is a minimum spanning tree of G.

1. Sort the edges by weight in ascending order: e₁, …, e_m with w(e₁) ≤ … ≤ w(e_m).
2. Set F := ∅.
3. For i = 1, …, m: if the graph (V, F ∪ {e_i}) contains no cycle, set F := F ∪ {e_i}; otherwise skip the edge e_i.
4. Return F.

Termination: the algorithm stops after going through all m edges (it may stop earlier, as soon as |F| = |V| − 1). It is a greedy algorithm — at every step it takes the lightest admissible edge and never revises the decision — and yet it always finds a minimum spanning tree (theorem below).

The edges sorted by length (accepted ones in bold): A–C (2), D–E (2), B–D (3), E–G (3), A–B (4), D–F (4), B–C (5), F–G (5), C–D (6), E–F (6), B–E (7), C–F (8).

The first six edges are accepted: A–C and D–E join pairs, B–D adds B to D–E, E–G adds G and A–B connects the group {A, C} with the group {B, D, E, G}. D–F attaches the last vertex F. Now all vertices are in a single component, so every further edge would join two vertices of the same component — it would close a cycle and the algorithm rejects it.

Length of the spanning tree: 2 + 2 + 3 + 3 + 4 + 4 = 18.

Let G = (V, E, w) be a connected weighted undirected graph. A cut is a division of the vertices into two non-empty parts S and V ∖ S, where ∅ ≠ S ⊊ V. An edge {u, v} ∈ E crosses the cut if and only if |{u, v} ∩ S| = 1 (one end in S, the other outside).

Theorem. Let (S, V ∖ S) be a cut of the graph G and e an edge that crosses the cut and has the smallest weight of all edges crossing this cut. Then there is a minimum spanning tree of G that contains the edge e.

Proof: take any minimum spanning tree T; if it contains e, we are done. Otherwise consider T without e. Adding e creates a cycle, and that cycle must cross the cut once more, through some edge f. Removing f gives a spanning tree again, with weight w(T) + w(e) − w(f) ≤ w(T), because w(e) ≤ w(f). So it is also minimum and contains e. ∎

Kruskal accepts an edge only when it joins two different components — and it is the lightest edge across the cut “one of those components against the rest”, because it has already processed all the lighter ones.

Let G = (V, E) be a directed graph, E ⊆ V × V, with n = |V| vertices.

1. A directed cycle is a sequence of vertices (v₀, v₁, …, v_k), k ≥ 1, such that (v_i−1, v_i) ∈ E for i = 1, …, k and v_k = v₀ — following the arrows you can return to the starting vertex.
2. G is a directed acyclic graph (DAG) if and only if it contains no directed cycle.
3. A topological ordering of the graph G is a bijection π : V → {1, …, n} (an order of the vertices) such that ∀(u, v) ∈ E : π(u) < π(v), i.e. every edge goes from left to right — u comes before v in the order.

Theorem. Let G = (V, E) be a directed graph. Then G has a topological ordering if and only if it is acyclic.

Inputs x = 2, w = 0.5, b = −1, correct answer y = 1, loss L = (ŷ − y)², σ(z) = 1/1 + e^−z.

Forward (in topological order): w · x = 1; z = 1 + (−1) = 0; ŷ = σ(0) = 0.5; L = (0.5 − 1)² = 0.25.

Backward (in reverse order; colours as in the breakdown of the chain rule below): ∂L/∂ŷ = 2(ŷ − y) = −1; ∂ŷ/∂z = σ(z)(1 − σ(z)) = 0.25; ∂L/∂z = −1 · 0.25 = −0.25; ∂L/∂b = ∂L/∂z · 1 = −0.25; ∂L/∂w = ∂L/∂z · ∂z/∂w = −0.25 · 2 = −0.5 (∂z/∂w = x = 2).

Both derivatives are negative: increasing w and b decreases the loss — the network moves towards the answer 1.