k-Connected graphs
📝定义 5.2.1
称两条 $u,v$-path 内部不相交, 当且仅当除了端点外没有公共点.
💡定理 5.2.2 Whitney
一个至少三个点的 2-连通图当且仅当任意两个点 $u,v$ 之间存在两条内部不相交的 $u,v$-path.
📝证明
"
$\Rightarrow$:" 数学归纳法
$d(u,v)=1$. 由 $\kappa(G)\leqslant\kappa'(G)$, 删除 $uv$ 后仍连通, 所以存在另一条 $u,v$-path.
对 $d(u,v)=k$.
💡引理 5.2.3
若 $G$ k-连通, 设 $G'$ 是由 $G$ 添加一个新节点 $y$, 并且 $y$ 至少有 $k$ 个邻居, 那么 $G'$ 是 k-连通的.
📝证明
考虑 $G'$ 的分割集.
💡定理 5.2.4
2-连通的几个等价条件:
- A \item[B]
- C \item[D]
📝定义 5.2.5
细分 (subdivision): 对于一条边的定义. 细分一条边 $uv$ 是指将 $uv$ 通过一个新的点 $w$, 将其替换为路径 $u,w,v$.
💡推论 5.2.6
如果 $G$ 2-连通, 那么 $G$ 细分一条边得到的新图 $G'$ 也是 2-连通的.
📝定义 5.2.7
耳 (ear): 图
$G$ 的耳是一条极大的路径, 满足路径内部的点在
$G$ 中的度数均为 2 且整个路径包含在一个环中.
耳分解 (ear decomposition): $P_0,P_1,\cdots,P_n$, 其中 $P_0$ 是一个环, $P_i$ 是 $P_0\cup P_1\cup\cdots\cup P_i$ 的耳.
ℹ️注 5.2.8
上述耳分解对于 $P_i$ 来说其内部的点在 $P_0\cup P_1\cup\cdots\cup P_i$ 中的度数为 2, 而不是在 $G$ 中的度数为 2.
💡定理 5.2.9 Whitney
图
$G$ 是 2-连通的当且仅当它有一个耳分解.
更进一步的, $G$ 中的每一个环一定可以作为某些耳分解的初始环.
对于边连通同样有类似定理.
📝定义 5.2.10
闭耳 (closed ear): 除了一个点之外其余所有点在
$G$ 中度数都为 2 的环.
闭耳分解: $P_0,P_1,\cdots,P_n$, 其中 $P_0$ 是一个环, $P_i$ 是 $P_0\cup P_1\cup\cdots\cup P_i$ 的耳或闭耳.
💡定理 5.2.11
图
$G$ 是 2-边连通图当且仅当它有一个闭耳分解.
更进一步分, $G$ 中的每一个环一定是某些闭耳分解的初始环.
💡定理 5.2.12 Robbins
图 $G$ 有强定向当且仅当它是 2-边连通.
ℹ️注 5.2.13
强定向: 给每条边定方向后整个图是强连通的有向图.
📝定义 5.2.14
$x,y$-分离子 (
$x,y$-separator) 或
$x,y$-割 (
$x,y$-cut): 点集
$S\subset V(G)-\{x,y\}$, 且 x,y 在 G-S 中连不联通.
称 $\kappa(x,y)$ 为上述最小的 $S$ 大小.
定义 $\lambda(x,y)$ 为最多的两两内部不相交的 $x,y$-path 数量.
显然有 $\kappa(x,y)\geqslant\lambda(x,y)$.
💡定理 5.2.15 Menger
只要 $x,y$ 之间没有边, 那么 $\kappa(x,y)=\lambda(x,y)$.
📝定义 5.2.16
线图 (line graph) $L(G)$: $L(G)$ 中的顶点对应 $G$ 中的边, $ef\in E(L(G))\Leftrightarrow e,f$ 在 $G$ 中有公共端点.
📝定义 5.2.17
类似的对边连通定义
$\kappa'(x,y)$
$\lambda'(x,y)$
💡定理 5.2.18
$\forall x\neq y$, $\kappa'(x,y)=\lambda'(x,y)$.