世界杯预选赛亚洲区_高达世界杯 - fzxzyy.com

连通性的定义

设 u 和 v 是图 G {\displaystyle G} 的顶点。

如果在 G {\displaystyle G} 中存在一条 u − v {\displaystyle u-v} 路径，则称 u {\displaystyle u} 和 v {\displaystyle v} 是连通的。

如果对于 G {\displaystyle G} 中的每一对顶点 u {\displaystyle u} 和 v {\displaystyle v} 都存在一条 u − v {\displaystyle u-v} 路径，则称 G {\displaystyle G} 是连通的，或称连通图。

边连通度

从图 G {\displaystyle G} 中删除使其断开的边数的最小值 lambda( G {\displaystyle G} )，也称为线连通度。断开图的边连通度为 0，而具有图桥的连通图的边连通度为 1。

顶点连通度

从图 G {\displaystyle G} 中删除使其断开的顶点数的最小值 kappa( G {\displaystyle G} )。

设 lambda( G {\displaystyle G} ) 是图 G {\displaystyle G} 的边连通度，delta( G {\displaystyle G} ) 是其最小度，那么对于任何图，kappa( G {\displaystyle G} ) ≤ lambda( G {\displaystyle G} ) ≤ delta( G {\displaystyle G} )

k-连通图

k-边连通图

如果一个图的最小割集包含k条边，并且删除这些边会导致图断开连接，那么该图的边连通度为k。

k-顶点连通图

如果一个图的最小割集包含k个顶点，并且删除这些顶点会导致图断开连接，那么该图的顶点连通度为k。1-连通图被称为连通图；2-连通图被称为双连通图；3-连通图被称为三连通图。

门格尔定理

边连通度

对于 u {\displaystyle u} 和 v {\displaystyle v} ，最小边割集的大小（即删除最少数量的边会导致 u {\displaystyle u} 和 v {\displaystyle v} 断开连接）等于从 u {\displaystyle u} 到 v {\displaystyle v} 的成对边不相交路径的最大数量。

顶点连通度

对于 u {\displaystyle u} 和 v {\displaystyle v} ，最小顶点割集的大小（即删除最少数量的顶点会导致 u {\displaystyle u} 和 v {\displaystyle v} 断开连接）等于从 u {\displaystyle u} 到 v {\displaystyle v} 的成对顶点不相交路径的最大数量。（边割集是指删除这些边会导致图断开的边集；顶点割集或分离集是指删除这些顶点会导致图断开的顶点集。）

最大流 (maximum flow) 最小割 (minimum cut) 定理

图 G {\displaystyle G} 中顶点 u {\displaystyle u} 和 v {\displaystyle v} 之间的最大流量，恰好等于断开 G {\displaystyle G} 连接并使 u {\displaystyle u} 和 v {\displaystyle v} 位于不同连通分量的最小边集的权重。

最大流：图 G {\displaystyle G} 中顶点 u {\displaystyle u} 和 v {\displaystyle v} 之间的最大流量

最小割集：断开 G {\displaystyle G} 中 u {\displaystyle u} 和 v {\displaystyle v} 所在的不同连通分量的最小边集。