图论与组合：连通性 / kConnected

迁移来源

旧站标题：kConnected

新站标题：图论与组合：连通性 / kConnected

旧站路径：/math/课程/图论与组合/chapters/连通性/kconnected/

旧页面 ID：358

k-Connected graphs #

definition

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

tip

一个至少三个点的 2-连通图当且仅当任意两个点 $u,v$ 之间存在两条内部不相交的 $u,v$ -path.

note

” $\Rightarrow$ :” 数学归纳法

$d(u,v)=1$ . 由 $\kappa(G)\leqslant\kappa'(G)$ , 删除 $uv$ 后仍连通, 所以存在另一条 $u,v$ -path.

对 $d(u,v)=k$ .

tip

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

note

考虑 $G'$ 的分割集.

tip

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

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

definition

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

tip

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

definition

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

info

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

tip

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

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

对于边连通同样有类似定理.

definition

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

tip

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

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

tip

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

info

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

definition

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

tip

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

definition

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

definition

类似的对边连通定义

$\kappa'(x,y)$

$\lambda'(x,y)$

tip

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

k-Connected graphs #

评论