PDF《图论中的经典问题简介》

0 或2. 这就是 一笔画 定理,也称为欧拉定理,经过每个 点恰好一次的回路也称为 欧拉回路 .欧拉通过对七桥问 题的研究,不仅圆满地回答了哥尼斯堡居民提出的问题,而 且由此开创了数学的两个新的分支――图论与拓扑. 随着时间的推移,图论不断发展,欧拉回路问题也有 所拓广.就这样到了二十世纪,又出现了一个新的问题 : 邮递员从邮局出发,每次要走遍他所负责街区的每一条道 路,投递完毕后仍须回到邮局,他应走什么路线才能使总 路程最短.这个问题就是著名的 中国邮路问题 (China Route Inspection Problem)或 中国邮递员问题 (Chinese Postman Problem) ,首先由我国数学家管梅谷教授于

1962 年提出,而美国国家标准和技术研究院(NIST)的Alan Goldman 首先将此问题命名为中国邮路问题. 若用顶点表示交叉路口,用边表示街道,那么邮递 员所管辖的范围可用一个赋权图来表示,其中边的权重 表示对应街道的长度.中国邮递员问题可以用图论语言 叙述为 :在一个具有非负权的赋权连通图中,找出一条 权最小的环游.这种环游称为最优环游.无向图的中国 邮路问题是容易解决的,而有向图的中国邮路问题是 NP 难问题.关于 NP 难的问题可参考任何一本组合优化或者 算法复杂性的教材,这里推荐李学良教授和史永堂博士 翻译的《组合优化》教材(高等教育出版社,2011) ,作者为William J. Cook, William H. Cunningham, William R. Pulleyblank, Alexander Schrijver. 2. 四色问题 印制地图时,为了便于区分,常把相邻(有公共边 界)的地区印成不同颜色.人们在实践中发现 :不论地 图上的行政区划多么复杂,最多使用四种颜色,一般都 能保证相邻地区使用不同颜色.实践中这样的结果,要 在理论上证明却不那么容易.这就是著名的四色问题―― 世界近代三大数学难题之一. 四色猜想的提出源自英国.1852 年,毕业于伦敦大学 的弗南西斯 ? 格思里(Francis Guthrie)工作时,发现了一 个有趣的现象 : 看来,每幅地图都可以用四种颜色着色,使 得有共同边界的国家着上不同的颜色.这个结论能不能从数 学上加以证明呢?他和在大学读书的弟弟格里斯决心试一 试.兄弟二人几经努力却没有进展.于是,他的弟弟就请教 他的老师、著名数学家德 ? 摩根,摩根也没找到解决途径, 于是写信向著名数学家哈密尔顿爵士请教.哈密尔顿接信后 开始研究,直到

1865 年逝世也没能解决.

1872 年,英国当时最著名的数学家凯利正式向伦敦 数学学会提出了这个问题,于是四色猜想成了世界数学界 关注的问题.世界上许多一流的数学家都纷纷参加了四色 猜想的大会战.1878-1880 年两年间,著名的律师兼数学 家肯普和泰勒两人分别提交了证明四色猜想的论文,宣布 证明了四色定理,大家都认为四色猜想从此也就解决了.

11 年后数学家赫伍德以自己的精确计算指出肯普的证明 是错误的.不久,泰勒的证明也被人们否定了.后来,越 来越多的数学家虽然对此绞尽脑汁,但一无所获. 于是,人们开始认识到这个貌似容易的题目并不简单. 进入

20 世纪以来,科学家们的证明基本上是按照肯普的想 法在进行.1913 年伯克霍夫在肯普的基础上引进了一些新 技巧,美国数学家富兰克林于

1939 年证明了

22 国以下的地 图都可以用四色着色.1960 年又推进到了