22问答网
所有问题
G是n阶简单无向图,如果图G中任意两点的度数之和大于等于n-1,证明图G是连通图
如题所述
举报该问题
推荐答案 2008-11-12
假设G有两个连通分支G1和G2,那么取v1是G1中度数最小的顶点,v2是G2中度数最小的顶点,则d(v1)+d(v2)≤n-2(等号在G1和G2都是完全图时取到),这与条件矛盾。
温馨提示:答案为网友推荐,仅供参考
当前网址:
http://22.wendadaohang.com/zd/62f62TCS.html
相似回答
...
无向图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是连通图
?
答:
可以运用反证法证明:如果G的补图不
连通
,G必连通。如果G的补图不连通,则设G补可以分成n个连通子图,且n个连通子图间没有任何边。所以G(也就是G补的补图)中n部分必两两相连(即形成n部图),所以G连通。
大家正在搜
设G是任意6阶简单无向图
设n阶无向简单图G中
设G是具有m条边的n阶简单图
若一个简单无向图G与其补图
已知n阶无向图G中有m条边
n阶k正则图G的变数是
设G为有m条边的n阶无向图
简单图G至少有3个点
设G为p阶简单图
相关问题
证明:若n阶简单无向图G的任意两个结点的度数之和大于等于n-...
高等数学中说,n阶无向简单图中,任意两个顶点的度数之和大于n...
离散证明:一个图包含2n个结点,每个结点的度数大于等于n的简...
离散数学:一个n(n>=2)阶无向简单图G中,n为奇数,已知...
无论有向图还是无向图,顶点数n,边数e和度数之间有什么关系
设一个无向图G=(V,E)有n个顶点n+1条边,证明G中至少...
设一个无向图G=(V,E)有n个顶点n+1条边,证明G中至少...
设G是n>=3的连通图,证明若m>=0.5(n-...