22问答网
所有问题
离散证明:一个图包含2n个结点,每个结点的度数大于等于n的简单图是连通的
如题所述
举报该问题
其他回答
第1个回答 2019-09-02
假设不连通。有如下两种情况:
1.最小连通分量有n个结点:此时共两个连通分量,每个分量n个结点。对于任一点,它的度至多是n-1,矛盾。
2.最小连通分量小于n个结点:该分量中任一点的度不超过n,矛盾。
第2个回答 2020-04-22
假设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有
2n个
顶点
,每个
顶点
的度数
至少为
n证明
此
图是连通
图。
答:
【答案】:[证明]用反证法,设图G不
是连通
图,不妨设图G有两个连通分支G1和G2构成,其中G1含有k个顶点(1≤k<n),G2含有2n-k个顶点。在连通分支G1中任取一点v1,在连通分支G2中任取一点v2。由于图G是
简单图,
所以G1和G2也是简单图,于是有deg(v1)≤k-1deg(v2)≤2n-k-1由此可得de...
证明:
在两个或两个以上
结点的简单图
中,至少有两
个结点的度数
相同。
答:
在n阶
简单图
中,点
的度数
在必然在0~n-1之间,共n个不同的度数。假设: 没有两个点度数相同,即:0~n-1这n个度数必然对应n个点。
证明:1
.若最小度为0,则说明有一个点为孤立点,此时在剩下n-1个点中,最大的度数只能为n-1-1=n-2,0~n-2只对应n-1个点,故,与假设矛盾。2.若最...
大家正在搜
链表每个结点中都恰好包含一个指针
链表中每个节点都包含一个指针
每个节点包含两个域
包含节点abc的树有几个
链式存储结构中的节点包含
设置包含根节点的二叉树高度为0
建立有n个节点的单链表
设有n个节点的无向图
设有n个节点的完全二叉树