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

已知图G不是连通的,求证它的补图必为连通的
谁会啊
粉丝921 1年前 已收到2个回答 举报
赞

那年的雪哦 幼苗

共回答了16个问题采纳率：100% 举报

如果图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'连通.

1年前

9

水草10 幼苗

共回答了39个问题 举报

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

1年前

1
可能相似的问题

你能帮帮他们吗

精彩回答

Copyright © 2024 YULUCN.COM - 雨露学习互助 - 17 q. 0.021 s. - webmaster@yulucn.com