kConnected

定义

称两条 $u,v$ -path 内部不相交, 当且仅当除了端点外没有公共点.

定理 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$ .

引理

若 $G$ k-连通, 设 $G'$ 是由 $G$ 添加一个新节点 $y$ , 并且 $y$ 至少有 $k$ 个邻居, 那么 $G'$ 是 k-连通的.

证明

考虑 $G'$ 的分割集.

定理

2-连通的几个等价条件:

A \item[B]
C \item[D]

定义

细分 (subdivision): 对于一条边的定义. 细分一条边 $uv$ 是指将 $uv$ 通过一个新的点 $w$ , 将其替换为路径 $u,w,v$ .

推论

如果 $G$ 2-连通, 那么 $G$ 细分一条边得到的新图 $G'$ 也是 2-连通的.

定义

耳 (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$ 的耳.

注

上述耳分解对于 $P_i$ 来说其内部的点在 $P_0\cup P_1\cup\cdots\cup P_i$ 中的度数为 2, 而不是在 $G$ 中的度数为 2.

定理 Whitney

图 $G$ 是 2-连通的当且仅当它有一个耳分解.

更进一步的, $G$ 中的每一个环一定可以作为某些耳分解的初始环.

定义

闭耳 (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$ 的耳或闭耳.

定理

图 $G$ 是 2-边连通图当且仅当它有一个闭耳分解.

更进一步分, $G$ 中的每一个环一定是某些闭耳分解的初始环.

定理 Robbins

图 $G$ 有强定向当且仅当它是 2-边连通.

注

强定向: 给每条边定方向后整个图是强连通的有向图.

定义

$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 数量.

定理 Menger

只要 $x,y$ 之间没有边, 那么 $\kappa(x,y)=\lambda(x,y)$ .

定义

线图 (line graph) $L(G)$ : $L(G)$ 中的顶点对应 $G$ 中的边, $ef\in E(L(G))\Leftrightarrow e,f$ 在 $G$ 中有公共端点.

定义

类似的对边连通定义

$\kappa'(x,y)$

$\lambda'(x,y)$

定理

$\forall x\neq y$ , $\kappa'(x,y)=\lambda'(x,y)$ .

k-Connected graphs #

评论