对于一个连通图，如果任意两点至少存在两条“点不重复”的路径，则说这个图是点双连通的（一般简称双连通，biconnected），特别的，只有两个点一条边的图也是双连通图。
注：下面提到的G均是无向图
命题1 G是双连通图的充要条件是G的任意两条边都在同一个简单环内。
证
充分性。对于G中任意两点u v，取任意两条分别以它们为端点的边，它们在一个简单环内，从而u到v有两条点不重路径。
必要性。G是双连通的，假设存在边u1-v2和边u2-v2不同时存在于任何一个简单环内，那么u1到u2的每一条路径与v1到v2的每一条路径必两两有交。由于G双连通，v1到v2存在不交的两条路径p q，则u1到u2的每一条路径都与p q有交，如此从u1出发必然存在某条路径在不经过q（p）的情况下到达p（q），从u2出发也是同理，那么所有的情况见下图，我们发现，总能够找到一个同时包含u1-v1 u2-v2的简单环。
命题2 G是双连通图的充要条件是G中无割顶（割点）。
证
必要性显然。
充分性。要证明G中无割点则G双连通，只需证若G不双连通，则G有割点。若G不是双连通的，那么存在两点u v使得每一条u到v的路径两两有交，我们证明这些交点中，必有一个是所有这些路径的公共交点。
对u v之间所有路径产生的交点总个数n进行归纳。
①若n=1，那么这唯一的一点就是所有路径的公共点。
②假设n=k时命题成立。考虑n=k+1的情形：任选一个交点x，如若它是所有路径的公共点，那么命题成立，否则至少存在一条u v间路径p不经过x，现将x从每一条u v间路径中删去，再添加一些边，使得每一条路径上x前后的两个点直接相连，如果这样处理后，所有的路径两两都有交，那么根据归纳假设，必存在一个公共点，若不是两两路径都有交，则至少存在两条路径h1、h2无交点，这说明x是h1和h2唯一的交点。现在我们考虑p、h1、h2这三条路径。由于p不经过x，那么p中必然有一段p*连接了x左右两边，且这一段本身不和h1或h2相交，那么所有情况如下图所示，如此我们总能找到两条完全不交的u v路径，这与我们的假设“u v间任意路径两两相交”是矛盾的。至此我们分析了所有的分支，这些分支要么能推出命题成立，要么自相矛盾，从而我们证明了对于n=k+1命题也成立。
命题3 G是双联通图的充要条件是对于G中任意三点a b c都存在一条a出发c结束中间经过b的简单路径。
证
充分性。对于G中任意两点u v，再取与u相邻的一个点a，则存在a出发u结束中间经过v的简单路径a-p1-v-p2-u，p1和p2分别是一条路径，那么u-a-p1-v和u-p2-v显然是两条不相交的u v路径。
必要性证明同命题1，略。
命题4 G的两个bcc（biconnected component，双连通分量）最多只有一个公共点，且这个点是割顶。
证
若G的两个bcc有两个或以上的公共点，那么这些公共点必不是割顶，根据命题2，这两个bcc的并也是一个bcc，因为其中不含割顶。如果它们的唯一公共点不是割顶，那么也可以合并。
命题5 G的每一条边恰好属于一个bcc。
证
对于任意边e，由命题4知它不可能属于多个bcc，如若它不属于任何一个包含更多边的bcc，那么根据定义，它自己也是一个bcc。
命题6 连通图G的所有bcc以树的形式连接起来。
证
假设G含有n个bcc，将每个bcc视为结点，将连接两个bcc的割顶视为边得到图G，G显然是连通的，且无环，否则环上的割顶在G中也必成环，这是不可能的，因而G*无环连通，是一棵树。
网友评论