已知图G不是连通的,求证它的补图必为连通的谁会啊

已知图G不是连通的,求证它的补图必为连通的谁会啊
已知图G不是连通的,求证它的补图必为连通的
谁会啊

已知图G不是连通的,求证它的补图必为连通的谁会啊
如果图G(V,E)不连通的话,它的顶点可以分为两个非空集合A,B,其中对于任意在A中的点P和任意在B中的点Q都没有PQ这条边.
这样的话,取其补图G',则对于任意在A中的点P和任意在B中的点Q都有PQ这条边.这样的话,对于任意两点P,Q,如果它们分别处于A,B的话,它们之间就有边相连；否则,不失一般性设它们都在A中,由于B非空,我们可以在B中任取一点R,我们知道PR和QR这两条边都是存在的,所以P,Q是连在一起的.
综上,知G'连通.

在B中的点Q都没有PQ这条边。
这样的话，取其补图G'，则对于任意在A中的点P和任意在B中的点Q都有PQ这条边。这样的话，对于任意两点P,Q，如果它们分别处于A,B的话，它们之间就有边相连；否则，不失一般性设它们都在A中，由于B非空，我们可以在B中任取一点R，我们知道PR和QR这两条边都是存在的，所以P,Q是连在一起的。...

全部展开

在B中的点Q都没有PQ这条边。
这样的话，取其补图G'，则对于任意在A中的点P和任意在B中的点Q都有PQ这条边。这样的话，对于任意两点P,Q，如果它们分别处于A,B的话，它们之间就有边相连；否则，不失一般性设它们都在A中，由于B非空，我们可以在B中任取一点R，我们知道PR和QR这两条边都是存在的，所以P,Q是连在一起的。

收起