当前位置 :
问一道缺了德的数学题某城市有10条公共汽车线路,现知沿其中9条线路可走遍所有车站,但沿其中任何8条线路不能走遍所有车站,问至少有多少个不同的车站?
1人问答
问题描述:

问一道缺了德的数学题

某城市有10条公共汽车线路,现知沿其中9条线路可走遍所有车站,但沿其中任何8条线路不能走遍所有车站,问至少有多少个不同的车站?

戴亚康回答:
  10个,参考图论Hamilton   9条线路可走遍所有车站,说明图中有N个点(未知),通常9条边连通   任何8条线路不能走遍所有车站,则图论中的定理,可推知这9条边是连通图的Hamilton路,(这个定理相当有深度呃,自己证当然缺德了咯)   9条边的Hamilton路共10个顶点   或者(这个可能浅一点):   有9条边,说明图中至多10个顶点连通(即10个车站),以9条边及相应端点可排列出一条链路(v1,e12,v2,e23,v3...)(v是点,e为边)   现在用反证法   如果图中少于10个顶点,说明图中有圈,(圈的概念是链路的起点和终点相同,比如说(v1,e12,v2,e23,v3,e31,v1)).   我们知道,在圈中删去任一边,图仍然保持连通(可到达)   所以如果图中有圈的话,可删去圈中任一边成为8条路,仍连通(可到达),与题目矛盾   所以图中恰有10顶点
数学推荐
最新更新
优秀数学推荐
PC端 | 移动端 | mip端
字典翻译(zidianfy.com)汇总了汉语字典,新华字典,成语字典,组词,词语,在线查字典,中文字典,英汉字典,在线字典,康熙字典等等,是学生查询学习资料的好帮手,是老师教学的好助手。
声明:本网站尊重并保护知识产权,根据《信息网络传播权保护条例》,如果我们转载的作品侵犯了您的权利,请在一个月内通知我们,我们会及时删除。
电话:  邮箱:
Copyright©2009-2021 字典翻译 zidianfy.com 版权所有 闽ICP备2022014709号-7
lyric 頭條新聞