已知图G不是连通的,求证它的补图必为连通的谁会啊
来源:学生作业帮助网 编辑:作业帮 时间:2024/07/11 22:06:00
![已知图G不是连通的,求证它的补图必为连通的谁会啊](/uploads/image/z/12500538-42-8.jpg?t=%E5%B7%B2%E7%9F%A5%E5%9B%BEG%E4%B8%8D%E6%98%AF%E8%BF%9E%E9%80%9A%E7%9A%84%2C%E6%B1%82%E8%AF%81%E5%AE%83%E7%9A%84%E8%A1%A5%E5%9B%BE%E5%BF%85%E4%B8%BA%E8%BF%9E%E9%80%9A%E7%9A%84%E8%B0%81%E4%BC%9A%E5%95%8A)
xRNQ&'I
i`"7%AU(>gyAS}1kTnc*bErLXLS+_!4wK- h?f"k
;ɈZE}\d6Uxzt`r瘌q_A6YQ2;G
TiΣƨAj<D:!eϣ{-}Pbs49fr>8D,+jesdQ#?Y~\ӥ6VyiZVK
ۺooT4
3ooT 㛜l@ HK Or" ;IE.h\ƪ&8Rs#ͫm{5Z^6x$;wc2AYx1i9$%Y6;M&{V#s3
N Go&Y{툧'vr
已知图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是连在一起的。
收起