四、连通度和匹配

文章目录

1、连通度
2、n - 连通
- 2.1 门格尔定理
- 2.2 柯尼希定理
3、网络流问题
- 3.1 增光路定理
- 3.2 最大流-最小割定理
THE END

1、连通度

$\qquad$ 顶点(边)连通度：定义一个图 $G = (V, E)$ ，若想将 $G$ 变成一个不连通图或者平凡图所需要去掉的最少的顶点(边)数称为 $G$ 的顶点(边)连通度，记为： $\kappa(G), \lambda(G)$ . 连通度有以下性质：
$\qquad$ 不连通的图或者平凡图的 $\kappa(G) = \lambda(G) = 0$
$\qquad$ 树的 $\kappa(G) = \lambda(G) = 1$
$\qquad$ 有割点的图 $\kappa(G) = 1$
$\qquad$ 有桥的图 $\lambda(G) = 1$
$\qquad$ 完全( $p, q$ )图的 $\kappa(G) = \lambda(G) = p-1$
$\qquad$ 图 $G$ 连通，则 $G$ 的 $\kappa(G) \geq 1$
$\qquad$ 定理1：设 $G = (V, E)$ ，令 $\delta(G)$ 表示 $G$ 中顶点的最小度，有 $\kappa(G)\leq \lambda(G)\leq \delta(G)$ .
$\qquad$ 定理2：设 $a, b, c$ 为正整数，且满足 $a\leq b \leq c$ ，则存在 $G$ 使得 $\kappa(G)=a$ , $\lambda(G)=b$ , $\delta(G)=c$ .
$\qquad$ 定理3：设 $G = (V, E)$ 是一个 $(p, q)$ 图，若 $\delta(G) \geq [\frac{p}{2}]$ （ $G$ 连通的充分条件），则 $\lambda(G) \leq \delta(G)$ 。

2、n - 连通

$\qquad$ n-连通定义：设 $G = (V, E)$ ， $\geq 0$ ，若 $\kappa(G) \geq n$ ，则称 $G$ 为n-顶点连通；若 $\lambda(G) \geq n$ ，则称 $G$ 为n-边连通。
$\qquad$ 定理4：令 $G = (V, E)$ ， $\geq 3$ ，称 $G$ 是2-顶点连通的，当且仅当 $G$ 的任意两个不同的顶点 $u$ 和 $v$ 在 $G$ 的同一个圈上。
$\qquad$ 定理5：令 $G = (V, E)$ ，称 $G$ 是n-边连通的，当且仅当：不存在 $V$ 的真子集 $A$ ，使得联结 $A$ 中一个节点和 $V / A$ 中一个节点的边数少于 $n$ 。

2.1 门格尔定理

$\qquad$ 引入分离的概念：令 $G = (V, E)$ ， $\subseteq A，s, t \in A$ ，若在 $G - S$ 中， $s, t$ 属于不同的支，则称 $S$ 分离了 $s$ 和 $t$ 。
$\qquad$ 明格尔定理： 分离 $s$ 和 $t$ 所需要去掉的最少得顶点数等于 $s$ 和 $t$ 之间不相交路(独立轨)的最大条数。

2.2 柯尼希定理

$\qquad$ 每一个正则二部图有一个1度因子；每一个k-正则二部图可以分解出k个1度因子。

3、网络流问题

$\qquad$ 在一个有向图 $D = (V, A, w)$ 中， $w ： A \to R$ 表示弧的容量；流量表示弧上实际的流值；网络流表示所有弧上流值的集合；可行流表示每一条弧上的流量不超过这条弧的容量，且从源点 $s$ 流出的流和流入汇点 $t$ 的流量之和相等；最大流表示可行流的流量之和最大；饱和弧表示弧上的流量等于其容量；链表示图 $D$ 中不考虑方向的路；增广路表示满足下述条件的链：前向弧不饱和，后向弧不为零；最小割表示将源点和汇点分离的割边中，容量最小的割边组成的割；

3.1 增光路定理

$\qquad$ 在一个容量网络中，一个可行流 $f$ 是最大流的充要条件为：容量网络中不存在增光路。

3.2 最大流-最小割定理

$\qquad$ 在一个容量网络中，最大流的流量等于最小割的截量。