图的连通性 connectivity

基本定理(Menger, 1927)
(1)[vertex form] 设s, t为图G中两个不相邻的顶点，则分离s, t的最少顶点数 = 连接s, t的独立道路的最大数目。
(2)[edge form] 设s, t为图G中两个不同的顶点，则分离s, t的最少边数 = 连接s, t的不相交道路的最大数目。

定理中术语的解释。

s, t为不相邻的顶点是指没有直接连接s, t的边。

所谓分离s, t的顶点集合S, 是指s, t都不在S中，且在原图中去掉S中的顶点，则s, t在剩下的图中不能相互连接。亦即，任意连接s, t的道路至少通过S中的一个顶点。

连接s, t的道路是指，一些首尾相接的边sa, ab, bc, …, xy, yt, 并且所有的顶点互不相同。例如sa, ab, bc, cd, da, at不是一条道路。

两条连接s, t的道路称为独立的，若这两条道路的公共点只有s, t.

不相交的道路，是指这些道路没有相同的边，但是可以有共同的顶点。

证明。
(1) 由图G构造一个相应的定向图，将图G中的每一条边xy都换作两条定向边xy及yx, 在 除开s,t 以外的每个顶点上赋予容量1.　由此限定的流在每条边上的流量只能为０或者１.　将顶点s, t看作source和sink. 于是由整性最大流最小割定理，可知存在一个具有最大流量的整数流。容易看出：连接s, t的独立道路的最大数目 = 最大流量 = 分离s, t需要的最少顶点数。
(2) 类似(1). 只需将其中对于顶点的容量限制改换为对于边的容量限制即可。
证毕。

若图中任意两个顶点都可以用一些边连接起来，则称这个图为连通的。

G为连通图，则G称为k-连通的，k-connected, 若
当Gz中顶点个数为(k+1)时，G为完全图，亦即任意两个顶点之间都有边相连接。
当G中的顶点个数至少为(k+2)时，去掉其中的任意(k-1)个顶点，所得到的图仍然连通。

注意，连通图可以看作1-连通的。

一个图称为k-edge-connected, 若去掉其中的任意(k-1)条边，剩下部分仍然连通。

使得图G为k-连通的最大数字k称为图G的连通度，connectivity.
使得图G为k-edge-connected的最大数字k称为图G的edge-connectivity.
约定，不连通的图，其两种连通度都规定为0.

Menger定理的推论：
(1) 图G是k-connected的 iff 对于图G中任意两个顶点，至少有k条独立的道路连接这两个顶点。
(2) 图G是k-edge-connected的 iff 对于图G中任意两个顶点，至少有k条不相交的道路连接这两个顶点。

Menger定理是在1927年证明的，而max-flow min-cut定理则是在1962年证明的。我们是由max-flow min-cut定理证明Menger定理。反过来，也可以用Menger定理证明max-flow min-cut定理。因而人们通常这样叙述：Menger定理与max-flow min-cut定理是等价的。两个数学定理等价，这个说法多少有点古怪：两个都正确的命题之间是等价的。这两个定理也都可以单独证明。

iff = if and only if, 这个简洁的用语充分的反映出来英语的某些优势。

另外Menger定理的结论“分离s, t的最少顶点数 = 连接s, t的独立道路的最大数目”用英文可以叙述为：The minimal number of vertices separate s from t = the maximal number of independent s-t paths. 似乎英文要简明一些。当然二者包含的信息还是相同的，用哪种语言并不能从本质上简化定理。