离散数学 · 图论 · 速览

离散数学目录阅读详版下载 Markdown

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)$.