一个图含有两个度数为奇数的顶点,它们之间是否一定存在一条路?证明或给出反例.
人气:253 ℃ 时间:2020-04-23 18:24:03
解答
如果你说的是这个图只含有两个度数为奇数的顶点
那么答案是肯定
证明方法是,从其中一个度数为奇数的顶点开始,用可以重复经过顶点,但不重复经过边的方法随意走,当无路可走时,一定是走到了另一个度数为奇数的顶点,即它们之间一定存在一条路
如果不止两个就不一定了,因为可能不在同一连通域
其实反过来说,因为只有2个奇度数点时它们属于同一连通域,所以之间一定有路
推荐
- “在顶点个数不少于2的简单无向图中,必有度数相同的顶点”的证明过程?
- 图论:证明树是二分图
- 图论证明,图G带v个顶点,e条边的连通平面图简单图,其中v大于等于3且圈的长度为L.
- 1.证明在具有n个顶点的简单无向图G中,至少有两个顶点的度数相同.
- 证明:N个顶点的简单图最少有2个顶点度数一样
- 现在有鸡、兔共居一笼,鸡头和兔头一共有15个,鸡脚和兔脚共有44只,问鸡、兔各有几只?
- 求助-翻译-巴西人的邮件---thanks
- 若(x^m÷x^2n)^3÷x^m-n与-1/4x^2为同类项,且2m+5n=7,求25n^2-4m^2的值
猜你喜欢