如何解“设G是n>=3的连通图,证明若m>=(n-1)(n-2)/2+2,则G存在哈密顿回路”?
人气:300 ℃ 时间:2020-04-24 12:53:40
解答
一定存在一个度数至少为n-2的点v.否则的话,每个点的度数不超过n-3,那么边数最多只有n*(n-3)/22.如果v的度数是n-2,那么把v从图中去掉,剩余子图含有n-1个点以及至少(n-2)(n-3)/2+2条边.由归纳假设,子图中有HC(Hamilton Circuit):u1-u2-.-u(n-1)-u1.从这n-1个点里任取两个与v相连的,比如ui与uj.那么原图的HC就是u1-u2-.-ui-v-uj-.-u(n-1)-u1.3.如果v的度数是n-1,那么把v从图中去掉,剩余子图有至少(n-2)(n-3)/2+1条边.在子图里任意加上一条边,使得边数达到(n-2)(n-3)/2+2,再用归纳假设,得到一个HC.如果HC中不包含新加的边,用2的方法构造新HC;如果包含,那么把这条ui-uj边替换成两条ui-v-uj.
推荐
- 证明n个顶点k条边的简单图G,若k>1/2(n-1)(n-2),则图G是连通的.
- 设无向连通图G有n个顶点,证明G至少有(n-1)条边.
- 证明:G连通不含回路推出G无回路且n=m+1
- 设G是有n个结点n条边的简单连通图,且G中存在度数为3的结点,证明G中至少有一个度数为1的结点
- 设无向图G中有n个结点,n-1条边,用归纳法于n,证明G是连通图则G中无回路.
- 张岱《湖心亭看雪》中“痴”字的含义,舟子为什么要说他痴,他是怎么想的
- make up one's mind to do sth.make a decision to do sth.
- 在平面上,将硬币竖直,沿直线滚动一周,则边缘上一点一周内的路程和位移是?
猜你喜欢
- 用六个边长是5分米的正方体拼成一个大的长方体,长方体的占地面积最少是多少?
- 就一题.说明理由.
- “秦王怫然怒”中的“怫”、“然”、“
- 10的负6次方的平方根和10的负4次方的算术平方根是什么
- 你假期有什么计划,用英文怎么说
- 请告知关于some,other,others,another,一些相关的结构的用法
- 90°-18°17′,21°15′x6,173°12′除以3,23°35′+57°23′,180°-138°47′,15°15′x6,72°12′
- what does Mary think of God is?He is a real man.翻译