西安电子科技大学S6.2.2无向图的连通性软件学院茶家家教家【例题】证明一个简单无向图若不是连通的，则它的补图一定连通证明：设G=<V，E>是一个非连通的简单无向图，那么有G至少有两个以上的连通分支。任取G中的两个结点vi和vi(i）如果vi和vi在不同的连通分支中，那么(vi，vi)必不是图G中的边，所以(vi，vi)是G的补图G”中的边。因此，在G中vi和vj是连通的。（ii）如果vi和vi在同一个连通分支中，那么任取G的另外一个连通分支中的结点vk，由（i）知(vi，vk)和(vj，vk是G’中的边，因此vivkvj是从结点vi到vj的一条路径。因此，在G”中vi和vi是连通的。故一个简单无向图G若不是连通的，则它的补图G”一定连通。西安电子科技大学 §6.2.2 无向图的连通性 软件学院 证明：设G=<V, E>是一个非连通的简单无向图，那么有 G至少有两个以上的连通分支。任取G中的两个结点vi和vj （i）如果vi和vj在不同的连通分支中，那么(vi, vj)必 不是图G中的边，所以(vi, vj)是G的补图G’中的边。因 此，在G’中vi和vj是连通的。 （ii）如果vi和vj在同一个连通分支中，那么任取G的 另外一个连通分支中的结点vk，由（i）知(vi, vk)和(vj, vk) 是G’中的边，因此vi vkvj是从结点vi到vj的一条路径。因 此，在G’中vi和vj是连通的。 故一个简单无向图G若不是连通的，则它的补图G’ 一定连通