惠特尼连通性定理

图论中，惠特尼连通性定理（），简称惠特尼定理（），是美國數學家哈斯勒·惠特尼于1932年提出的关于2连通图等价性质的定理，该定理提供了关于2连通图的不同点对之间的连通性质刻画，描述了2连通图的特殊性质。

 定理陈述 
对一个图，若至少存在3个点，则是2连通的当且仅当对中任意两个点，中至少存在连接的2条内部不相交路径，即除首尾相同（皆為）外，沒有其他公共頂點的路徑。

 定理证明 

 必要性 
因为任意两点之间均存在路径，于是是连通的。

进一步，对于任意两点之间有至少存在两条内部不相交路径，所以考虑删除中任意一点，其均不会造成不连通。于是是2连通的。

 充分性 
是2连通的，希望证明对于任意两点，能找到至少两条连接的内部不相交路径。

下面通过对之间的距离进行归纳来由数学归纳法证明：

 对于，此时是的一条边。而由于，根据惠特尼不等式，，于是。那么至少需要删两条边才会导致不连通，于是删一条边之后仍然还是连通的。则考虑，其仍然是连通图，于是对于，仍然存在一条路径连接。于是中至少存在两条连接的内部不相交路径。
 假设对于，中都存在至少两条连接的内部不相交路径，则考虑；
 由于之间距离为，则中一定存在一条连接的路径，且的长度（其包含的边的数量）为，如图1所示。此时考虑中的邻居，一定满足。这是因为对于在中已经有到长度为的路径，而如果还存在其他路径长度小于，那么也存在到的路径长度小于，与矛盾。于是对于，根据归纳假设，存在至少2条连接的内部不相交路径。于是构成了一个环，如图2所示。替代=充分性的归纳证明|缩略图|310x310像素|充分性的归纳证明
 如果，即已经在这个环上，如图3所示，则对于与这两个环上的点，它们之间也存在环上两条相反的绕行方向的路径，于是与存在两条内部不相交的路径。
 如果，那么由于是2连通的，则考虑，其仍然是连通的。那么对于，此时存在另一条连接的路径。此时，如果与以及除了之外没有其他交点，如图4所示，则显然与就构成了连接的两条内部不相交路径；否则，令为与相交的最后一个交点，根据的对称性，不妨假设就在上，如图所示。那么考虑和，这两条路径则构成了连接的内部不相交路径。
 于是无论如何，当时，均能至少找到连接的两条内部不相交路径。

于是根据数学归纳法，当是2连通图时，对于任意两点，能找到至少两条连接的内部不相交路径。

 推论 
根据惠特尼定理的结论，可以得到关于2连通图的等价描述的推论：

 图是连通且没有割点（即图是2连通的）；
 对于图中任意两点，中存在至少两条连接的内部不相交路径；
 对于图中任意两点，中存在一个环且均在上；
 图的最小度至少为1，且对于图中的任意两条边，中存在一个环且均在上。

 推论证明 

 描述1描述2：直接运用惠特尼定理即可。
 描述2描述3：关系是显然的。若这两点之间存在至少两条连接它们的内部不相交路径，则这两条内部不相交路径的并形成了环且这两点在环上；若存在这两点同时位于环上，则这两点之间在环上的不同绕行方向的路径形成了连接它们的两条内部不相交路径。
 描述4描述3：对任意的两点，由于，则均存在邻居，。考察，
 若即两条边完全分离，则由于任意两条边均位于一个环上，于是位于同一个环上，于是也位于该环上。
 若即两条边有一个公共点，此时仍然是两条不同的边，则同样由于任意两条边均位于一个环上，于是位于同一个环上，于是也位于该环上。
 若即实际上只是一条边，此时与其他任意一条边仍然位于同一个环上，所以仍然位于环上。
 描述123描述4：首先根据描述1，图是连通的，所以。其次，对于图中的任意两条边，下面证明它们位于同一个环上。

替代=向G中加入两个辅助点w,z|左|缩略图|向中加入两个辅助点
令。首先仍然是2连通的，这是因为，的构造过程是加入两个点且两个点均与原图中两个点相连，则考虑中的割集。若割集中含有新加入的点，则除去新加入的点，是原图的割集，而根据描述1，本是2连通的，则或；若割集中不含有新加入的点，如果割集取自，则，否则实际上是原图的割集，所以同样，。所以无论如何，对于的任意割集，其大小至少为2，故仍然是2连通的。实际上，关于向-连通图加入辅助点的更一般的结论称为「扩展引理」（），它也在证明门格尔定理中发挥了作用。

那么根据描述3，对于，一定存在环，均位于上。而的度均为2，所以也位于上，且的其他边均来自原图。于是可以将替换成，替换成，从而均位于原图中的一个环上。

 影响及意义 
惠特尼定理提供了对于2连通性的更具体的性质刻画，从而提供了另一种对于2连通性的具体证明方向。

 参考文献 




Category:图论
Category:组合数学
Category:理论计算机科学
Category:数学定理