问题标题：
问一道缺了德的数学题某城市有10条公共汽车线路,现知沿其中9条线路可走遍所有车站,但沿其中任何8条线路不能走遍所有车站,问至少有多少个不同的车站?
问题描述：
问一道缺了德的数学题
某城市有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顶点
查看更多
