若图G是不连通的 证明：G的补图是连通的．
已帮助 人
若图G是不连通的，证明：G的补图是连通的．
热搜：单连通域和多连通区域区别
-
若图G=(V，E)是不连通的，可设图G的连通分支是G(V1)，G(V2)，…，G(Vm)(m≥2)．由于任意两个连通分支G(Vi)与G(Vj)(i≠j)之间不连通，因此两个结点子集Vi与Vj之间的所有连线都在图G的补图中．任取两个结点u和v，有如下两种情形：
①u和v分别属于两个不同结点子集Vi与Vj．由于G包含边(u，v)，故u和v在G中是连通的．
②u和v属于同一个结点子集Vi．可在另一个结点子集Vj中取一个结点ω，由于边(u，ω)及边(v，ω)均在中，故邻接边(u，ω)和(ω，v)组成的路连接结点u和v，即u和v在补图中也是连通的．
由此可知，当图G不是连通图时，G的补图必是连通图．