# 离散数学 · 图论 · 速览 > Arietids Learn · 个人课程复习笔记 > 在线阅读：https://learn.arietids.net/courses/discrete-math/chapter-01-quick/ ## Graphs and Degree - **Graph** $(V,E)$: $V$ vertices, $E$ edges; each edge has two **endpoints** (possibly identical) and **connects** them. - Three classification axes: directed/undirected; multiple edges（重边/平行边）or not; loops（自环）or not. - In an **undirected** graph: $u,v$ **adjacent** (neighbours) ⇔ some edge has endpoints $u,v$; that edge is **incident** with $u,v$; $\mathcal{N}(v)$ = all neighbours, $\mathcal{N}(A)=\bigcup_{v\in A}\mathcal{N}(v)$. - In an **undirected** graph: $\deg(v)$（度）= number of incident edges, **a loop counts twice**. - **Handshaking（握手定理）**: finite undirected ⇒ $2|E| = \sum_{v\in V}\deg(v)$ (proof: swap summation order over $v$ and $e$). ⇒ number of odd-degree vertices is **even**. - Directed edge $u \to v$: $u$ adjacent to $v$, $v$ adjacent from $u$; $u$ **initial**, $v$ **terminal** vertex; $\deg^-(v)$ in-degree, $\deg^+(v)$ out-degree; finite directed ⇒ $|E| = \sum\deg^+(v) = \sum\deg^-(v)$. - **Path** of length $n\geqslant 0$ from $u$ to $v$: edges $e_1,\ldots,e_n$ with vertices $u=x_0,\ldots,x_n=v$, endpoints of $e_i$ are $x_{i-1},x_i$ (directed: $e_i$ from $x_{i-1}$ to $x_i$); **simple** = no duplicate edges; **circuit** = path of **positive** length $u$ to $u$. ## Connectivity - $u,v$ **connected** ⇔ path from $u$ to $v$; connectivity holds to itself, is symmetric and transfers along chains; **connected graph（连通图）** ⇔ every pair connected. - **Subgraph（子图）**: $V'\subseteq V$, $E'\subseteq E$; **proper** if $\neq G$; **induced（导出子图）** by $W$: all vertices of $W$ + all edges with both endpoints in $W$. - A path induces a connected subgraph; two connected subgraphs sharing a vertex have a connected union. - **Connected component（连通块）** = connected subgraph not a proper subgraph of another connected subgraph; each is an induced subgraph of $\{v : v \text{ connected to } u\}$. - **Strongly connected（强连通）** directed graph: paths both ways for every pair; **strongly-connected component（强连通块）** = strongly-connected subgraph not a proper subgraph of another one, each an induced subgraph of $\{v : v \text{ mutually reachable from } u\}$; mutual reachability holds reflexively, symmetrically, transitively. - Between two strongly-connected components reachability is uniform ($v_1$ reachable from $u_1$ iff $v_2$ from $u_2$); a circuit's edges and vertices lie in one strongly-connected component. - Adding edge $e_0$ ($u$–$v$): never destroys connectivity; if $u,v$ already connected, connectivity unchanged; if not: $x$ connected to $u$ in $G'$ ⇔ to $v$ in $G'$ ⇔ to one of $u,v$ in $G$; any newly connected $x,y$ become connected together with $u,v$ in $G'$. ## Trees - **Tree** = connected nonempty undirected graph with **no simple circuits**; add edge between existing vertices ⇒ simple circuit; remove edge ⇒ disconnected; leaf (unrooted) = degree-$1$ vertex; $\geqslant 2$ vertices ⇒ $\geqslant 2$ leaves; $n$ vertices ⇒ $n-1$ edges. - **Six equivalent characterizations** of finite $G$: ① tree; ② connected ∧ $|E|=|V|-1$; ③ no simple circuits ∧ $|E|=|V|-1$; ④ connected ∧ every edge is a cut edge; ⑤ no simple circuits ∧ adding any edge between vertices of $G$ creates one; ⑥ unique simple path between any two vertices. ## Spanning Trees and MST - **Spanning tree**: subgraph that is a tree containing **every vertex**; graph connected ⇔ spanning tree exists (connected ⇒ exists: repeatedly delete one edge of a simple circuit until vertices = edges + 1). - **Weighted graph**: each edge gets a (real) number; **MST**: spanning tree with minimum total weight (finite connected weighted graph). - **Prim**: for a finite connected weighted graph, start from a singleton vertex $T_0$; repeatedly add the minimum-weight edge keeping $T_n + e'$ a tree (edge crosses $V_n$ to $V\backslash V_n$, vertex side added); after $|V|-1$ steps, MST. - **Kruskal**: for a finite connected weighted graph, start from $(V,\varnothing)$; repeatedly add the minimum-weight edge that creates **no simple circuit**; after $|V|-1$ steps, MST. - Correctness pattern (both): induction — there is always an MST $T^*$ containing the current partial graph; Prim's induction step is the **edge exchange**: a $T^*$-path between $e_{n+1}$'s endpoints must contain an edge $e^*$ leaving $V_n$; $w(e^*)\geqslant w(e_{n+1})$ (choice) and $w(e^*)\leqslant w(e_{n+1})$ ($T^*$ is minimum), so swapping keeps an MST; Kruskal's idea: $e_n$ is "necessary" — lighter edges cannot connect its endpoints without a simple circuit. ## Rooted Trees - **Rooted tree** = tree + designated **root** $r$; **level** of $v$ = length of unique simple path $r \to v$; **height** = max level; **parent** of $v\neq r$ = unique neighbour on the $r$–$v$ path, $v$ its **child**; **siblings** = same parent; **ancestors** of $v \neq r$ = vertices on the $r$–$v$ path excluding $v$, including $r$; **descendants** of $v$ = vertices with $v$ as ancestor. - Ancestor/descendant relations are transitive; $u$ is $v$'s ancestor ⇔ a parent chain $w_0=u,\ldots,w_k=v$ exists; the unique simple path between descendants of $u$ stays within $u$'s descendants and $u$. - Rooted-tree **leaf** = no children (≠ unrooted notion: degree $1$), otherwise **internal vertex**; **subtree** at $v$ = induced subgraph of $v$ + descendants (it is a tree). - **$m$-ary tree（$m$ 叉树）**: every internal vertex has $\leqslant m$ children (binary = 2-ary); height $h$ ⇒ **at most $m^h$ leaves**. ## Depth-First Search（深度优先搜索） - Procedure: fix a start vertex; **augment a simple path** until stuck; **trace back** to the deepest vertex with an augmentable edge; repeat. Moves are **forward / backward steps**; edge used by a forward move = **tree edge**, otherwise **back edge**. - Formal DFS conditions ($k$-th step $v_{k-1}\to v_k$ via $e_k$, start $u$): $v_0=u$; if an unvisited neighbour of $v_{k-1}$ exists, the move **must** be forward; forward steps reach only unvisited vertices; a backward step retraces the forward edge that first entered the current vertex ($v_k=v_{i-1}$, $e_k=e_i$). - Tree edges of a DFS on a connected graph form a **spanning tree** (rooted at the start vertex); a forward step goes to a child. - Each $v \neq u$ is a forward step's terminal **exactly once** and a backward step's start **exactly once**; with $n=|V|$, total: $n-1$ forward + $n-1$ backward steps. - Visited vertices split into three categories: the start vertex / entered (one forward terminal) but not yet left / entered and left (one backward start); a simple path $v_0 \to v_k$ uses only forward edges and passes exactly through the start and the not-yet-left vertices. - Between two visits of $u$ all visited vertices are $u$'s descendants or $u$ itself; a **back edge** always joins a vertex to an ancestor, a descendant, or itself. - **Tarjan bridges**: DFS computing $\mathrm{dfn}(u)$ (visit time) and $\mathrm{low}(u) = \min$ of own time, children's $\mathrm{low}$, and $\mathrm{dfn}$ of other neighbours (entering edge $e_0$ excluded); after recursing into child $v$: edge $u$–$v$ is reported as a **bridge** when $\mathrm{low}(v) = \mathrm{dfn}(v)$.