图论：证明若G不连通，则G的补图连通。

如题所述

举报该文章

相关建议 2018-06-26

温馨提示：内容为网友见解，仅供参考

当前网址：https://aolonic.com/aa/k351aknw34ddw3g4w1.html

其他看法

第1个回答 2014-01-01

归纳法，设n=k成立，对n=k+1，G里先选k个点，不妨设此k点子图G'本身联通，剩下一点a若和G'里的任意点相连，则已证明。若否，则a与G'里的点都不相连，则G的补图已经自然联通了：通过a，2步以内即可从一点到任意一点。

第2个回答 2020-04-21

之前大佬们的回答都没写出详细过程，我写了一下，请采纳

图论:证明若G不连通,则G的补图连通。
可以运用反证法证明：如果G的补图不连通，G必连通。如果G的补图不连通，则设G补可以分成n个连通子图，且n个连通子图间没有任何边。所以G（也就是G补的补图）中n部分必两两相连（即形成n部图），所以G连通。

图论:证明若G不连通,则G的补图连通。
这个很简单的，根据补图的定义就可以了，u，v在G中不相邻，那么根据补图的定义在补图的中式相邻的。

图论:证明若G为简单连通图,且G中任意一对不相邻顶点u和v满足:d(u)+d...
http:\/\/web.nuist.edu.cn\/courses\/lssx\/longtime\/part4\/chapter15\/15_02_03_01.htm 记得采纳啊

哈斯勒·惠特尼是做什么的
惠特尼一生对四色问题感兴趣,他最早和最后的数学论文都是关于四色问题的.他给出四色问题的等价命题并研究可约性问题.从四色问题出发他研究一般图论,特别是得出两图同胚的条件:如G和G’是两连通图,均不包含三个形如ab,ac,ad的弧.若存在任意具有公共顶点的两弧到另一图的具有公共顶点的两弧之间的一一对应,则两图...

...G中任意两点的度数之和大于等于n-1,证明图G是连通图
先假设G不是连通的，则G至少有两个连通分支G1和G2,有 |G1|+|G2| ≤ |G| = n；任取G1中一点v1,G2中一点v2，则d(v1)≤|G1|-1,d(v2)≤|G2|-1；d(v1)+d(v2) ≤ |G1|+|G2|-2 ≤ n-2，与条件矛盾，故G只能是连通图。在图论中，连通图基于连通的概念。在一个无向...

高随祥《图论与网络流理论》习题参考答案(第三章)
3.1部分，问题(1)探讨了图G的连通性与结构。若G为若干个独立的顶点集合组成的连通图，则G自身构成一个连通的简单路径或简单循环。问题(2)则延伸了这一思考，强调在最长路P的端点u与v间，任何相邻边均不与P内边或端点边重叠，从而确保路径的唯一性或形成路或圈的结构。3.2部分，问题(1)深入探讨...

图论:证明若G为简单连通图,且G中任意一对不相邻顶点u和v满足d(u)+d...
跟O.Ore1960的一个定理有点像，可能证明方式会有参考吧http:\/\/wenku.baidu.com\/view\/1c8a3aa6f524ccbff1218497.html

欧拉定理的拓扑公式
欧拉定理的拓扑公式是：对于任何连通的无向图G，如果V表示G的顶点数，E表示G的边数，则G的边数E满足E = V - 1 + k，其中k是G中连通分量的个数。若G是连通图，则k=1，此时公式简化为E = V - 1。欧拉定理的拓扑公式是图论中的一个基本定理，它建立了图的顶点数、边数和连通分量数之间的...

如何判别强连通、单向连通、弱连通、不连通?
连通分量：无向图 G的一个极大连通子图称为 G的一个连通分量（或连通分支）。连通图只有一个连通分量，即其自身；非连通的无向图有多个连通分量。强连通图：有向图 G=(V,E) 中，若对于V中任意两个不同的顶点 x和 y，都存在从x到 y以及从 y到 x的路径，则称 G是强连通图。相应地有强...

连通图是什么概念?
1. 连通图定义：在图论中，连通图是基于连通概念的图。对于无向图G，若任意两个顶点之间都存在路径，则G是连通的。2. 连通图的性质：在有向图中，若任意两个顶点之间的路径中的所有边都具有相同的方向，则G被称为连通图。图的连通性是其基本属性。3. 单向连通图：对于有向图G，如果顶点u到顶点...

相似回答

大家正在搜