4
图论简介
•
1856 年，哈密顿在给格雷夫斯的信中提出一个游戏：用正十二面体
上 20 个顶点表示 20 个城市，要求游戏者沿着各边行走，走遍每个
城市一次且仅一次，最后回到原出发城市。这个游戏促使人们研究
如何判断一个图有无这一性质，如果有，则又如何确定这样的路径，
即称之为哈密顿图。这是一个至今尚未完全解决的问题。
•
1962 年，中国数学家管梅谷提出一个所谓“中国邮路问题”：邮递员
带着邮件从邮局出发，走遍他所管辖的每一条街道，最后回到邮局，
如何选择路线，使走的路程最短。 1967 年，埃德蒙兹给出中国邮
路问题一个好的解法。
•
图论虽有 200 年的历史 , 但受计算机科学发展的刺激 , 发展极其迅
速。上世纪 60 年代以来图论在各种学科领域中得到了广泛应用。图
论在理论上也得到了新的发展，如图特等发展了拟阵理论，贝尔热
等发展了超图理论，埃尔德什等发展了极图理论等。
•
本书介绍图的基本概念、路与回路、图的矩阵表示、欧拉图与汉密
尔顿图、平面图、对偶图与着色、树与生成树、根树及其应用、二
部图、匹配等。各章节主要知识点关联如图 4.0.0 所示。
