设无向图G中有n个结点,n-1条边,用归纳法于n,证明G是连通图则G中无回路.
人气:163 ℃ 时间:2020-07-29 07:48:28
解答
假设这个无环图是不连通的,则设图G有k个连通分支G1,G2,…,Gk(k≥2),设G1有x1个结点,G2有x2个结点,G3有x3个结点……Gk有xk个结点,则有x1+x2+x3+……+xk=n,又因为Gi有xi-1条边,所以图G有(x1-1)+(x2-1)+(x3-1)+……+(...
推荐
- 设无向连通图G有n个顶点,证明G至少有(n-1)条边.
- 设G为一n阶简单无向图,证明以下结论:1:若G不联通,则G的补图联通 2:若G至少具有(n-1)*(n-2)/2 +2
- 证明n个顶点k条边的简单图G,若k>1/2(n-1)(n-2),则图G是连通的.
- 图G无向连通图,G中有割点或桥,则无汉密尔顿图,怎么证明
- 如何解“设G是n>=3的连通图,证明若m>=(n-1)(n-2)/2+2,则G存在哈密顿回路”?
- 如果a,b互为相反数,c,d互为倒数,m的绝对数为2,求式子a+b+c分之a+b +m-cd的值 两种结果都写过程
- X染色体和Y染色体的区别?
- 【我们是一对蝴蝶】 用英语怎么说
猜你喜欢
- 100ml溶液稀释10倍后pH是12.5,原溶液pH是多少呀!
- Let the cat _____ up the tree.(climb) 用所给动词的适当形式填空?
- 有谁看得懂等高线地形图?
- 多项式3十(x一1)的平方取最小值
- 甲,乙,丙3人,甲每分钟行走60米,乙每分钟行走67.5米,丙每分钟行走75米,如果甲乙2人在东村,丙在西村,他们3人同时由两村相向而行,丙遇到乙后,继续走1分钟才遇到甲.问:东西两村相距多少米?
- 韩琦写的《郡圃春晚》译文
- 5月24日英语怎么读
- 数学题之190