G是n阶简单无向图，如果图G中任意两点的度数之和大于等于n-1，证明图G是连通图
发布网友
发布时间：2022-11-27 01:20
共3个回答
热心网友
时间：2023-10-13 06:40
先假设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只能是连通图。
在图论中，连通图基于连通的概念。在一个无向图 G 中，若从顶点i到顶点j有路径相连（当然从j到i也一定有路径），则称i和j是连通的。如果 G 是有向图，那么连接i和j的路径中所有的边都必须同向。如果图中任意两点都是连通的，那么图被称作连通图。
如果此图是有向图，则称为强连通图。而无向图中，如果任意两个顶点之间都能够连通，则称此无向图为连通图。
扩展资料：
连通图性质
一个无向图 G=(V,E) 是连通的，那么边的数目大于等于顶点的数目减一：|E|>=|V|-1，而反之不成立。
如果 G=(V,E) 是有向图，那么它是强连通图的必要条件是边的数目大于等于顶点的数目：|E|>=|V|，而反之不成立。
没有回路的无向图是连通的当且仅当它是树，即等价于：|E|=|V|-1。
参考资料：百度百科-连通图
热心网友
时间：2023-10-13 06:41
假设G有两个连通分支G1和G2，那么取v1是G1中度数最小的顶点，v2是G2中度数最小的顶点，则d(v1)+d(v2)≤n-2（等号在G1和G2都是完全图时取到），这与条件矛盾。
热心网友
时间：2023-10-13 06:41
