# 离散数学 · 图论 > Arietids Learn · 个人课程复习笔记 > 在线阅读：https://learn.arietids.net/courses/discrete-math/chapter-01/ ## 1 Graphs and Basic Definitions ### 1.1 Graph - **Graph**: a *graph* is an ordered pair $(V, E)$ where $V$ is a set of **vertices** and $E$ is a set of **edges**. - Every edge has two vertices associated with it, called its **endpoints**; these two vertices can be different or identical; an edge is said to **connect** its endpoints. - Remark: $V$ and $E$ can be infinite, but the course focuses on finite cases. ### 1.2 Different kinds of graphs Graphs are classified along three axes: - **Directed / Undirected**; - with or without **multiple edges**（重边，a.k.a. parallel edges，平行边）; - with or without **loops**（自环）. ## 2 Degree ### 2.1 Adjacency, incidence, neighbourhood, degree (undirected) - **Adjacency**: if $G=(V,E)$ is an undirected graph, two vertices $u,v \in V$ are **adjacent** (or **neighbours**) in $G$ if there is an edge $e \in E$ such that the endpoints of $e$ are $u, v$. - **Incidence**: if the endpoints of an edge $e$ are $u, v$, then $e$ is **incident** with $u, v$. - **Neighbourhood**: $\mathcal{N}(v)$ is the set of all neighbours of $v$; for a vertex set $A \subseteq V$, $\mathcal{N}(A) := \bigcup_{v \in A} \mathcal{N}(v)$. - **Degree（度）**: for an undirected graph $G=(V,E)$, the **degree** of a vertex $v \in V$ is the number of edges incident with it, **where a loop associated with $\{v,v\}$ contributes twice** to the degree of $v$: $$ \deg(v) = \big|\{e \mid v \text{ is } e\text{'s first endpoint}\}\big| + \big|\{e \mid v \text{ is } e\text{'s second endpoint}\}\big| = \sum_{v \text{ is } e\text{'s first endpoint}} 1 + \sum_{v \text{ is } e\text{'s second endpoint}} 1 $$ ### 2.2 The Handshaking Theorem（握手定理） - **Handshaking Theorem**: if $G=(V,E)$ is a **finite undirected** graph, then $2 \cdot |E| = \sum_{v \in V} \deg(v)$. - Proof idea (double counting by exchanging summation order — in the first two lines the inner sums run over edges $e$, after the exchange the inner sums run over vertices $v$): $$ \sum_{v \in V} \deg(v) = \sum_{v \in V}\Big(\sum_{\mathrm{first}(e)=v} 1 + \sum_{\mathrm{second}(e)=v} 1\Big) = \sum_{v}\sum_{\mathrm{first}(e)=v} 1 + \sum_{v}\sum_{\mathrm{second}(e)=v} 1 = \sum_{e}\sum_{\mathrm{first}(e)=v} 1 + \sum_{e}\sum_{\mathrm{second}(e)=v} 1 = \sum_e 1 + \sum_e 1 = 2 \cdot |E| $$ - **Corollary**: an undirected graph has an **even number of vertices of odd degree**. ### 2.3 Directed edges, in-degree and out-degree - **Directed edges**: if $G=(V,E)$ is a directed graph and $e \in E$ is from $u$ to $v$, then: $u$ is **adjacent to** $v$, and $v$ is **adjacent from** $u$; $u$ is the **initial** vertex of the edge, while $v$ is the **terminal** (or **end**) vertex of the edge. - **In-degree / out-degree**: if $G=(V,E)$ is a directed graph and $v \in V$: - $\deg^-(v) := |\{e \in E \mid e \text{ is associated with } (u',v') \text{ and } v = v'\}|$ (**in-degree**); - $\deg^+(v) := |\{e \in E \mid e \text{ is associated with } (u',v') \text{ and } v = u'\}|$ (**out-degree**). - **Degree sum of directed graphs**: if $G=(V,E)$ is a finite directed graph, then $|E| = \sum_{v \in V} \deg^+(v) = \sum_{v \in V} \deg^-(v)$. ## 3 Paths and Circuits - **Path (undirected)**: for an undirected graph $G=(V,E)$ and $u,v \in V$, a **path** of length $n$ ($n \geqslant 0$) from $u$ to $v$ in $G$ is a finite sequence $e_1,\ldots,e_n$ of edges in $E$ such that there exists a finite sequence of vertices $u = x_0,\ x_1,\ \ldots,\ x_{n-1},\ x_n = v$ such that the endpoints of each $e_i$ are $x_{i-1}, x_i$. - The path $e_1,\ldots,e_n$ is **simple** if it does not contain duplicate edges. The path **traverses** these edges and **passes through** the vertices $x_1,\ \ldots,\ x_{n-1}$. - **Notation**: we write the path $e_1,\ldots,e_n$ as $x_0, x_1, \ldots, x_{n-1}, x_n$ if $G$ is simple. - **Circuit (undirected)**: a path of **positive** length from $u$ to $u$ is a **circuit**. The circuit is **simple** if it does not contain duplicate edges. - **Path (directed)**: for a directed graph $G=(V,E)$ and $u,v \in V$, a **path** of length $n$ ($n \geqslant 0$) from $u$ to $v$ is a finite sequence $e_1,\ldots,e_n$ of edges in $E$ such that there exists a finite sequence of vertices $u = x_0,\ x_1,\ \ldots,\ x_{n-1},\ x_n = v$ such that each $e_i$ is **from $x_{i-1}$ to $x_i$**; *simple*, *traverses* and *passes through* are defined in the same way as in the undirected case. - **Notation**: we write the path $e_1,\ldots,e_n$ as $x_0, x_1, \ldots, x_{n-1}, x_n$ if $G$ is a simple directed graph. - **Circuit (directed)**: a path of **positive** length from $u$ to $u$ is a **circuit**; it is **simple** if it does not contain duplicate edges. ## 4 Connectivity of Undirected Graphs ### 4.1 Connected vertices and connected graphs - **Connected vertices**: in an undirected graph $G=(V,E)$, two vertices $u, v \in V$ are **connected** if there is a path from $u$ to $v$ in $G$. - Basic properties of connectivity in an undirected graph $G=(V,E)$: - for any $u \in V$, $u$ is connected to itself; - for any $u, v \in V$, if $u$ is connected to $v$, then $v$ is connected to $u$; - for any $u, v, w \in V$, if $u$ is connected to $v$ and $v$ is connected to $w$, then $u$ is connected to $w$. - **Connected graph（连通图）**: an undirected graph $G=(V,E)$ is **connected** if every pair of vertices in $V$ is connected; otherwise it is **disconnected**. ### 4.2 Subgraphs and connected components - **Subgraph（子图）**: a **subgraph** of a graph $G=(V,E)$ is a graph $G'=(V',E')$ such that (i) $V' \subseteq V$ and (ii) $E' \subseteq E$. A subgraph $G'$ of $G$ is **proper** if $G \neq G'$. - A path induces a connected subgraph: if $G=(V,E)$ is an undirected graph and $e_1, e_2, \ldots, e_n$ is a path in $G$ from $u$ to $v$ that traverses $u = x_0, x_1, \ldots, x_{n-1}, x_n = v$, then $G'=(V',E')$ with $V' = \{x_0, x_1, \ldots, x_n\}$ and $E' = \{e_1, \ldots, e_n\}$ is a connected subgraph of $G$. - Union of overlapping connected subgraphs: if $G=(V,E)$ is an undirected graph, $G'=(V',E')$ and $G''=(V'',E'')$ are two connected subgraphs of $G$, and $V' \cap V'' \neq \varnothing$, then $(V' \cup V'',\ E' \cup E'')$ is also a connected subgraph of $G$. - **Induced subgraph（导出子图）**: for $W \subseteq V$, the subgraph **induced** by $W$ consists of all the vertices from $W$ and all the edges from $E$ whose endpoints both lie in $W$. - **Connected component（连通块）**: a **connected component** of an undirected graph $G$ is a connected subgraph of $G$ that is **not a proper subgraph of another connected subgraph** of $G$. - **Structure of connected components**: if $G$ is a nonempty undirected graph, then $G$'s connected components are **induced subgraphs** of $V$'s subsets of the form $\{v \in V : v \text{ is connected to } u\}$ for some $u \in V$. - Proof structure (two directions, four obligations): - 1\) Suppose $G'=(V',E')$ is a connected component of $G$: (1a) prove that if $u \in V'$, then $V' = \{v \in V : v \text{ is connected to } u\}$; (1b) prove that $E'$ are all edges between two vertices in $V'$. - 2\) Suppose $V' = \{v \in V : v \text{ is connected to } u\}$ and $E'$ are all edges between two vertices in $V'$: (2a) prove that $G'=(V',E')$ is a connected graph; (2b) prove that $G'$ is not a proper subgraph of another connected subgraph of $G$. ## 5 Reachability of Directed Graphs - **Strongly-connected directed graph（强连通图）**: a directed graph $G=(V,E)$ is **strongly connected** if for every pair of vertices $(u,v)$, there is a path from $u$ to $v$ **and** a path from $v$ to $u$. - **Strongly-connected component（强连通块）**: a **strongly-connected component** of a directed graph $G$ is a strongly-connected subgraph of $G$ that is not a proper subgraph of another strongly-connected subgraph of $G$. - **Reachability**: a vertex $v \in V$ is **reachable** from $u \in V$ if there is at least a path from $u$ to $v$ in $G$. - **Mutual reachability**: two vertices $u, v \in V$ are **mutually reachable** if there are paths both from $u$ to $v$ and from $v$ to $u$ in $G$. - Basic properties of mutual reachability in a directed graph $G$: - for any $u \in V$, $u$ and itself are mutually reachable; - for any $u, v \in V$, if $u$ and $v$ are mutually reachable, then $v$ and $u$ are mutually reachable; - for any $u, v, w \in V$, if $u$ and $v$ are mutually reachable, and $v$ and $w$ are mutually reachable, then $u$ and $w$ are mutually reachable. - **Structure of strongly-connected components**: given a nonempty directed graph $G$, its strongly-connected components are **induced subgraphs** of $V$'s subsets of the form $\{v \in V : v \text{ is mutually reachable from } u\}$ for some $u \in V$. - **Reachability between components is uniform**: if $G'=(V',E')$ and $G''=(V'',E'')$ are two strongly-connected components of $G$, then for any $u_1, u_2 \in V'$ and $v_1, v_2 \in V''$: $v_1$ is reachable from $u_1$ iff $v_2$ is reachable from $u_2$. - **Circuits live inside one component**: if $e_1, e_2, \ldots, e_n$ is a circuit of a directed graph $G$ passing through $x_1, x_2, \ldots, x_n$, then $e_1, \ldots, e_n$ and $x_1, \ldots, x_n$ belong to the same strongly connected component. ## 6 Connectivity against Edge Addition / Removal - Setting: $G=(V,E)$ and $G'=(V, E \cup \{e_0\})$ are two undirected graphs, where $e_0 \notin E$ is an additional edge connecting $u$ and $v$. Then: - For any $x, y \in V$: if $x$ and $y$ are connected in $G$, then $x$ and $y$ are still connected in $G'$ (adding an edge never destroys connectivity). - If $u$ **is** connected to $v$ in $G$, then: for any $x$ and $y$, $x$ and $y$ are connected in $G$ **iff** $x$ and $y$ are connected in $G'$. - If $u$ is **not** connected to $v$ in $G$, then: - for any $x \in V$: $x$ is connected to $u$ in $G'$, iff $x$ is connected to $v$ in $G'$, iff $x$ is connected to one of $u$ and $v$ in $G$; - for any $x$ and $y$: if $x$ and $y$ are not connected in $G$ but they are connected in $G'$, then $x$, $y$, $u$ and $v$ are all connected in $G'$. ## 7 Trees ### 7.1 Definition and basic properties - **Tree**: a **tree** is a **connected (nonempty) undirected graph without simple circuits**. - **Adding an edge**: if adding an edge between vertices of a tree, the new graph will have a simple circuit. - **Removing an edge**: if removing an edge from a tree, the new graph will be unconnected. - **Leaf (in an unrooted tree)**: a vertex is a **leaf** in a tree if its degree is $1$. - If a tree has at least two vertices, then it has at least one leaf; moreover it has at least two leaves. - **Edge count**: a tree with $n$ vertices has $n-1$ edges. - An undirected graph **with no simple circuit** is a tree if adding an arbitrary edge between vertices of the graph generates a simple circuit in the new graph. - A **connected** undirected graph is a tree if removing any edge makes the new graph disconnected. ### 7.2 Equivalent characterizations of trees All statements below about a finite undirected graph $G=(V,E)$ are equivalent: - $G$ is a tree, i.e. $G$ is connected but contains no simple circuits. - $G$ is connected and $|E| = |V| - 1$. - $G$ contains no simple circuits and $|E| = |V| - 1$. - $G$ is connected, but every edge in $E$ is a cut edge. - $G$ contains no simple circuits, and adding any edge between vertices of $G$ generates a simple circuit. - There is a unique simple path between any two of $G$'s vertices. ## 8 Spanning Trees and Minimum Spanning Trees ### 8.1 Spanning trees - **Spanning tree**: a **spanning tree** of an undirected graph $G$ is a subgraph of $G$ that is a tree **containing every vertex of $G$**. - **Existence**: an undirected graph is connected **if and only if** it has a spanning tree. - Proof: - ($\Leftarrow$) If a spanning tree exists, then there is a path in the spanning tree between any two vertices, so the graph is connected. - ($\Rightarrow$) Suppose $G_0 = G$ is connected. If $G_0$ contains a simple circuit, remove one edge from the simple circuit, generating $G_1$; $G_1$ must still be connected. Repeat this process to construct $G_2, G_3, \ldots$; the number of edges keeps decreasing, so there must be a natural number $k$ such that the number of vertices of $G_k$ is one more than its edges — that $G_k$ must be a tree. ### 8.2 Weighted graphs and minimum spanning trees - **Weighted undirected graph**: a graph $G = (V,E)$ with a function that assigns to each edge a (real) number. - **Minimum spanning tree**: for a **connected weighted** graph $G$, a **minimum spanning tree** of $G$ is a spanning tree whose sum of all weights in the tree is the minimum among all spanning trees. ### 8.3 Prim's Algorithm - Construct a minimum spanning tree of a finite connected weighted graph $G=(V,E)$ according to the following steps: 1. Choose the initial tree $T_0 = (V_0, E_0)$ as an arbitrary **singleton vertex with no edges**. 2. Construct $T_{n+1}$ from $T_n$ by adding an edge $e_{n+1}$ with **minimum weight** among all remaining edges $e'$ satisfying that the graph $T_n$ added with $e'$ **is a tree**. 3. Finally $T_{|V|-1}$ is a minimum spanning tree. - **Key step** — find $e_{n+1}$ such that: - $e_{n+1}$ connects two vertices $u_{n+1}$ and $v_{n+1}$, one of which (suppose it is $u_{n+1}$) is in $V_n$ and the other ($v_{n+1}$) is in $V \backslash V_n$; - if there are more than one minimum weighted edges, choose an arbitrary one; - $T_{n+1} = (V_{n+1}, E_{n+1})$ where $V_{n+1} = V_n \cup \{v_{n+1}\}$ and $E_{n+1} = E_n \cup \{e_{n+1}\}$. - **Correctness proof**: by induction on $n$ that **there exists a minimum spanning tree $T^*$ such that $T_n$ is a subgraph of $T^*$**. - When $n = 0$: choose an arbitrary minimum spanning tree as $T^*$. - When $n = |V|-1$: if there exists a minimum spanning tree $T^*$ such that $T_{|V|-1}$ is a subgraph of $T^*$, then $T^*$ must be $T_{|V|-1}$ itself — done. - Induction step: assume there exists a minimum spanning tree $T^*$ such that $T_n$ is a subgraph of $T^*$; show there also exists a minimum spanning tree (maybe different from $T^*$) such that $T_{n+1}$ is a subgraph of it. - Choose an arbitrary minimum spanning tree $T^*$ such that $T_n$ is a subgraph of $T^*$. If $T_{n+1}$ is a subgraph of $T^*$, we are done. - Otherwise (**edge exchange**): $e_{n+1}$ is not an edge in $T^*$. Because $T^*$ is a spanning tree, there is a path in $T^*$ between $u_{n+1}$ and $v_{n+1}$. On this path, there must be an edge $e^*$ **leaving $V_n$** ($e^*$ connects a vertex in $V_n$ and a vertex in $V \backslash V_n$) — otherwise there would be a path in $T_n$ between $u_{n+1}$ and $v_{n+1}$, which contradicts the fact that $T_n$ is a tree. - Because of the choice of $e_{n+1}$: $w(e^*) \geqslant w(e_{n+1})$. On the other hand, $T^* \backslash \{e^*\} \cup \{e_{n+1}\}$ is a tree; because $T^*$ is a minimum spanning tree: $w(e^*) \leqslant w(e_{n+1})$. - Thus, changing $e^*$ to $e_{n+1}$ in $T^*$ gives another minimum spanning tree containing $T_{n+1}$ as a subgraph. ### 8.4 Kruskal's Algorithm - Construct a minimum spanning tree of a finite connected weighted graph $G=(V,E)$ according to the following steps: 1. Choose the initial graph $G_0 = (V, E_0)$ where $E_0 = \varnothing$. 2. Construct $G_{n+1}$ from $G_n$ by adding an edge $e_{n+1}$ with **minimum weight** among all remaining edges $e'$ satisfying that the graph $G_n$ added with $e'$ **has no simple circuit**. (If more than one edge $e'$ has minimum weight, pick an arbitrary one.) 3. Finally, $G_{|V|-1}$ is a minimum spanning tree. - Here, $G_{n+1} = (V, E_{n+1})$ where $E_{n+1} = E_n \cup \{e_{n+1}\}$. - **Correctness proof's main idea**: $e_n$ is "necessary" — assume it connects $u_n$ and $v_n$; all edges with less weight than $e_n$ are not enough to connect $u_n$ and $v_n$, or else there will be a simple circuit in the new graph. - Formal proof: by induction on $n$ that there exists a minimum spanning tree $T^*$ such that $G_n$ is a subgraph of $T^*$. ## 9 Rooted Trees ### 9.1 Basic definitions - **Rooted tree**: a **rooted tree** is a tree with a designated vertex (as the **root**). - **Level and height**: in a rooted tree $G=(V,E)$ with root $r$: the **level** of a vertex $v$ is the length of the unique simple path from $r$ to $v$; the **height** of the tree is the maximal level of its vertices. - **Parent and child**: the **parent** of a vertex $v \neq r$ is the unique vertex $u$ such that $\{u,v\} \in E$ and this edge appears on the unique simple path between $r$ and $v$; $v$ is called a **child** of $u$. - **Siblings**: vertices $u, v$ are **siblings** if they have the same parent. - **Ancestors and descendants**: the **ancestors** of a vertex $v \neq r$ are the vertices on the simple path from $r$ to $v$, **excluding $v$ but including $r$**; the **descendants** of a vertex $v$ are all vertices that have $v$ as one of their ancestors. ### 9.2 Structural theorems - **Ancestor transitivity**: in a rooted tree $G$, if $u$ is an ancestor of $v$ and $v$ is an ancestor of $w$, then $u$ is also an ancestor of $w$. - Proof sketch: let the simple path from $v$ to the root be $v = x_n, x_{n-1}, \ldots, x_0 = r$ and the one from $w$ to the root be $w = y_m, y_{m-1}, \ldots, y_0 = r$. By definition $u = x_i$ for some $0 \leqslant i < n$ and $v = y_j$ for some $0 \leqslant j < m$. Then $v = y_j, y_{j-1}, \ldots, y_0 = r$ is also a simple path from $v$ to the root, so by uniqueness $j = n$ and $x_n = y_n, x_{n-1} = y_{n-1}, \ldots, x_0 = y_0$. Hence $u = x_i = y_i$ with $0 \leqslant i < n < m$, i.e. $u$ is $w$'s ancestor. - **Descendant transitivity**: if $u$ is a descendant of $v$ and $v$ is a descendant of $w$, then $u$ is also a descendant of $w$. - **Path extension lemma**: in a rooted tree $G$, if $u$ is the parent of $v$ and $u = x_n, x_{n-1}, \ldots, x_0$ is the simple path from $u$ to the root, then $v, u = x_n, x_{n-1}, \ldots, x_0$ is the simple path from $v$ to the root. - Proof sketch: let $v = y_m, y_{m-1}, \ldots, y_0$ be the simple path from $v$ to the root; by definition $u = y_{m-1}$, so $y_{m-1}, \ldots, y_0$ is the simple path from $u$ to the root, i.e. $n = m-1$ and $x_n = y_n, \ldots, x_0 = y_0$. - **Ancestors as parent-chains**: - if $u$ is $v$'s ancestor in $G$, then there exist $w_0, w_1, \ldots, w_k$ s.t. $w_0 = u$, $w_k = v$, and $w_0$ is $w_1$'s parent, $w_1$ is $w_2$'s parent, etc.; - conversely, if $w_0, w_1, \ldots, w_k$ satisfy $w_0 = u$, $w_k = v$ and $w_0$ is $w_1$'s parent, $w_1$ is $w_2$'s parent, etc., then $u$ is $v$'s ancestor in $G$. - **Paths inside a subtree**: in a rooted tree $G$, if $v$ is a descendant of $u$, then the unique simple path from $v$ to $u$ only passes through $u$'s descendants and $u$. - Proof sketch: the simple path from $v$ to the root is $v = x_n, \ldots, x_0 = r$ with $u = x_m$ for some $0 \leqslant m < n$, so the simple path from $v$ to $u$ is $v = x_n, x_{n-1}, \ldots, x_m = u$; for any $i$ with $m < i \leqslant n$, $x_i, x_{i-1}, \ldots, x_0 = r$ is a subpath and hence the unique simple path from $x_i$ to the root; since $u = x_m$ is on this path, $x_i$ is a descendant of $u$. - **Corollary**: in a rooted tree $G$, if $v_1$ and $v_2$ are both $u$'s descendants, the unique simple path from $v_1$ to $v_2$ only passes through $u$'s descendants and $u$. ### 9.3 Leaves, subtrees, m-ary trees - **Leaf / internal vertex (rooted-tree context)**: in a rooted tree, a vertex is a **leaf** if it has **no children**; otherwise it is an **internal vertex**. - Note the two different leaf notions in this course: in an **unrooted** tree a leaf is a vertex of degree $1$; in a **rooted** tree a leaf is a vertex with no children. - **Subtree**: the **subtree** at a vertex $v$ is the induced subgraph of the vertex set consisting of the vertex $v$ (as its root) and all the descendants of $v$. - For any rooted tree $G=(V,E)$ and $v \in V$, the subtree at vertex $v$ is a tree. - **$m$-ary trees（$m$ 叉树）**: a rooted tree $G$ is **$m$-ary** if every internal vertex has **at most $m$ children**; $G$ is **binary** if it is $2$-ary. - **Leaf bound**: an $m$-ary tree of height $h$ has **at most $m^h$ leaves**. ## 10 Depth-First Search（深度优先搜索） ### 10.1 The DFS procedure (informal) - **DFS algorithm**: - Step 1: Fix an arbitrary starting vertex. - Step 2: Continuously **augment a simple path** until no edge is augmentable. - Step 3: **Trace back** to the deepest vertex from which some edge is augmentable and go back to Step 2. - Example graph used to illustrate DFS (11 vertices $a, b, \ldots, k$; edges read off the figure): $\{a,c\}, \{b,c\}, \{c,e\}, \{d,e\}, \{d,f\}, \{e,f\}, \{f,g\}, \{f,h\}, \{g,h\}, \{h,i\}, \{h,k\}, \{j,k\}$. ### 10.2 Describing a DFS process; tree edges and back edges - To describe a DFS process: we can say the $k$-th **move** is from vertex $u$ to vertex $v$ through edge $e$ as a **forward / backward step**; we can also say the $k$-th **forward move**. - **Tree edge / back edge**: in one DFS process, if there is a forward move through $e$, then $e$ is called a **tree edge**; otherwise $e$ is called a **back edge**. ### 10.3 Formal definition of a DFS process Given an undirected graph $G=(V,E)$ and a start point $u$, a DFS process (with $s$ steps) must satisfy the following conditions (assuming that the $k$-th step is from $v_{k-1}$ to vertex $v_k$ through edge $e_k$): - $v_0 = u$. - If there exists $e \in E$ and $w \in V$ s.t. $w \notin \{v_0, v_1, \ldots, v_{k-1}\}$ and $e$ connects $v_{k-1}$ and $w$, then the $k$-th move **must be forward** (i.e. go forward whenever an unvisited neighbour exists). - If the $k$-th move is a forward step, then $v_k \notin \{v_0, v_1, \ldots, v_{k-1}\}$ (forward steps only visit new vertices). - If the $k$-th move is a backward step and $v_{k-1} = v_i$, where $i \leqslant k-1$ and the $i$-th step is forward, then $v_k = v_{i-1}$ and $e_k = e_i$ (a backward step retraces the forward edge that first entered the current vertex). ### 10.4 Properties of DFS - **DFS yields a spanning tree**: all tree edges of a DFS process of a connected undirected graph $G$ form a **spanning tree** of $G$. - Proof scratch: 1) all vertices appear — if $v$ did not, we could construct a counterexample from a path connecting $u$ and $v$; 2) this subgraph is a tree — by induction over the steps, the subgraph with $\{v_0, v_1, \ldots, v_k\}$ and $\{e_1, e_2, \ldots, e_k\}$ is a tree, proved by case analysis on whether the $k$-th step is forward or backward. - Usually, we treat this tree as a **rooted tree** (the starting vertex is the root). - A forward step is from a vertex to **one of its children** (in the DFS tree). - Every vertex $v \neq u$ appears as a **forward step's terminal exactly once** in a DFS process of a connected undirected graph $G$ starting from $u$. - **Visited-vertices invariant**: for a **connected undirected** graph $G=(V,E)$ and a DFS process of $G$ with $s$ steps ($k$-th step from $v_{k-1}$ to $v_k$ through $e_k$) and every $k \leqslant s$, the set of "visited vertices" $\{v_0, v_1, \ldots, v_k\}$ can be divided into three categories: - the starting vertex; - the vertices which appear as exactly one forward step's termination and as **no** backward step's starting point in the first $k$ steps; - the vertices which appear as exactly one forward step's termination and as **exactly one** backward step's starting point in the first $k$ steps. - Moreover, one simple path from $v_0$ to $v_k$ satisfies the following properties (proof by induction over $k$): - it contains only forward edges: $e_{n_1}, e_{n_2}, \ldots, e_{n_l}$, where $1 \leqslant n_1 < n_2 < \cdots < n_l \leqslant k$; - it passes through vertices $v_{n_1-1},\ v_{n_1} = v_{n_2-1},\ v_{n_2} = v_{n_3-1},\ \ldots,\ v_{n_{l-1}} = v_{n_l-1},\ v_{n_l} = v_k$; - $\{v_0, v_{n_1}, v_{n_2}, \ldots, v_{n_l}\}$ are exactly all vertices in the first two categories above. - Every vertex $v \neq u$ appears as a **backward step's starting point exactly once** in a DFS process of a connected undirected graph $G$ starting from $u$. - A DFS process of a connected undirected graph with $n=|V|$ contains **$n-1$ forward steps and $n-1$ backward steps**. - Between two visits of $u$: if $G=(V,E)$ is a **connected undirected** graph and a DFS process of $G$ contains $s$ steps with the $k$-th step from $v_{k-1}$ to $v_k$ through $e_k$, and $v_i = v_j = u$ with $i < j$, then $v_k$ is $u$'s descendant or $u$ itself for every $i < k < j$. - **Back edge theorem**: a back edge is always from a vertex to one of its ancestors, one of its descendants, or itself. - Proof: consider an edge from $u$ to $v$. If one of them is the root, the statement is obviously true. Otherwise, consider the backward steps leaving $u$ and leaving $v$; suppose the backward step leaving $u$ is earlier. Then, right at the time of leaving $u$, $v$ must be visited (or else a forward step should happen). Since a backward step from $v$ had not yet happened, $v$ must be $u$'s ancestor. ### 10.5 Tarjan's Algorithm for Finding Bridges ```text Tarjan_Bridge(u, e0): time = time + 1; dfn(u) = time; low(u) = time; for every e ≠ e0 which is incident with u and another vertex v: if dfn(v) is uninitialized, then recursively run Tarjan_Bridge(v, e); low(u) = min(low(u), low(v)); if (low(v) = dfn(v)) then the edge connecting u and v is a bridge; else low(u) = min(low(u), dfn(v)); ``` - The recursion excludes the entering edge $e_0$ itself when scanning the edges incident with $u$; $\mathrm{dfn}(u)$ records the visiting time of $u$, and $\mathrm{low}(u)$ is updated by children's $\mathrm{low}$ values (after recursive calls) and by $\mathrm{dfn}(v)$ of already-visited neighbours; the bridge test is $\mathrm{low}(v) = \mathrm{dfn}(v)$.