四、连通度和匹配

本文主要是介绍四、连通度和匹配，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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)\ge 1$
\qquad 定理1：设$G=(V,E)$，令$\delta (G)$表示$G$中顶点的最小度，有$\kappa (G)\le \lambda (G)\le \delta (G)$.
\qquad 定理2：设$a,b,c$为正整数，且满足$a\le b\le c$，则存在$G$使得$\kappa (G)=a$, $\lambda (G)=b$, $\delta (G)=c$.
\qquad 定理3：设$G=(V,E)$是一个$(p,q)$图，若$\delta (G)\ge [\frac{p}{2}]$（$G$连通的充分条件），则$\lambda (G)\le \delta (G)$。

2、n - 连通

\qquad n-连通定义：设$G=(V,E)$，$n\ge 0$，若$\kappa (G)\ge n$，则称$G$为n-顶点连通；若$\lambda (G)\ge n$，则称$G$为n-边连通。
\qquad 定理4：令$G=(V,E)$，$|V|\ge 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)$，$S\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 在一个容量网络中，最大流的流量等于最小割的截量。

THE END

这篇关于四、连通度和匹配的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---