图论是数学的一个分支，它以图为研究对象。通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。
数学游戏，作为一种运用数学知识的大众化的智力娱乐活动，因其趣味性，往往容易激发人们的数学热情与兴趣，因而对普及数学而言是非常有益的。
另一方面，从历史角度看，数学游戏还曾对数学的发展起到过重要而积极的作用。特别是，它曾直接导致过新的数学分支图论的创立(游戏的发明者则是哈密顿)。
...
01 天赋超群的哈密顿的生平经历
哈密顿（1805～1865），爱尔兰数学家，数学史上诸多早熟的天才之一。他于1805年出生在都柏林。当他大约1周岁时，父母把他交给一位叔父抚养并进行教育。这位叔父是个语言学家，在他的培养下，天赋超群的哈密顿3岁时就能顺利地读英文；5岁就能读能译拉丁文、希腊文和希伯来文；8岁时又掌握了意大利文和法文；不到10岁就学阿拉伯文和梵文。14岁时他用波斯文写信给当时正在访问都柏林的波斯大使。15岁那年，一件偶然的事件改变了他的兴趣与生活道路。当时，一个美国青年科尔布恩在都柏林表演了他的快如闪电的计算能力。"后来很长一段时间"，哈密顿后来写道，"我喜欢心算很长的算术运算，开平方和开立方，以及每一件与数的性质有关的东西。"最后，他决心终身从事数学。他宣称："再没有比研究科学更能提高人的心灵，更能把一个人提高到众人之上的了。谁不愿意享有阿基米得的名声……呢？"
1823年，这位神童进入都柏林的三一学院。21岁时，他提交了一篇重要的有关光学的论文。1826年，尚未大学毕业的哈密顿当选三一学院天文学教授职位。1835年，哈密顿获爵士称号，两年后又当选为爱尔兰皇家科学院主席。
事业上的成功却没有给他带来个人生活的幸福。他于1833年结婚，妻子"极为羞怯，又极为纤弱"。在这个不幸的婚姻中，哈密顿夫人难以胜任家务且常常生病，结果导致悲惨的哈密顿食无定时，酗酒到危险的程度。当他去世后，人们看到他的工作房间因长期无人打扫而变得如猪圈一般：房间里堆满了像小山一样的纸张，而纸堆中竟然夹杂着大量的盘碟与剩下的饭菜。
...
02 发明周游世界游戏，播下了图论诞生与发展的种子。
哈密顿在数学方面主要研究代数，其最重要的贡献是在1843年发现了四元数。把他与图论联系在一起的是他提出的一个趣味问题：从正十二面体（共有20个顶点）的一个顶点出发，沿着边行进，把20个顶点无遗漏地全部通过，每一顶点只许过一次而回到原处。问这种走法是否存在。将这一问题略加转化，哈密顿于1857年发明了着名的周游世界游戏，并以25英镑把这个游戏卖给一家公司。后来，这一游戏还进入了市场。
游戏的道具由一个木制的正十二面体构成，正十二面体的每个棱角上标有一个当时非常有名的城市。游戏目的是环绕世界旅行，其要求是寻找一个环游路线，使得：沿正十二面体的棱，从一个"城市"出发，经过每个城市恰好一次，最后回到原出发点，并且经过的棱不许重复。
...
为了容易记住哪些城市已被游览过，在每个棱角上放一个钉子，再用一根线绕在那些旅游过的城市（钉子）上，由此就获得旅程的一个直观表示。后来，人们发现这个道具不好用，因而诞生了与正十二面体等价的平面木板状版本。可惜，这个游戏的商业运作是失败的，玩具商没有从这个游戏中赚到钱。但在数学史上，哈密顿周游世界的游戏和欧拉的七桥问题是两例标志性建筑，播下了图论诞生与发展的种子。
如下右图给出了这游戏的一种正确玩法。
...
让我们对照一下欧拉与哈密顿研究的问题。欧拉要求在一个图中寻找满足"从一个顶点出发，沿边行进，无遗漏走遍所有的边，每一边只许经过一次回到出发点"的路线，这样的路线后来在图论中被称为欧拉回路。而具有欧拉回路的图称为欧拉图。与之表面相似，实际完全不同的哈密顿问题则要求在一个图中寻找满足"从一个顶点出发，沿边行进，无遗漏地通过全部顶点，每一顶点只许过一次而回到出发点"的路线，这样的路线后来在图论中被称为哈密顿圈，而具有哈密顿圈的图称为哈密顿图或说图是哈密顿的。
欧拉问题与哈密顿问题已经成为现在图论的重要组成部分。令人感到惊奇的是，对欧拉问题，我们已经有了简单、漂亮的结果：一个连通图存在欧拉回路当且仅当它的所有顶点都是偶顶点。然而对哈密顿问题即"一个给定的连通图是否存在哈密顿回路"，至今仍然是图论中一个尚未解决的着名难题。数学家们经过努力得到了一些存在哈密顿回路的必要条件与充分条件，但至今还没有得到充要条件。
欧拉七桥问题与哈密顿周游世界游戏是两例标志性建筑，它们播下了图论诞生与发展的种子。这门一开始以游戏形式出现，而且此后也一直没有完全失去这一特点的数学分支，在20世纪得到迅速发展，已经成为十分有用的重要数学分支。
图论以图为研究对象。所谓图，就是一些点与某些点之间的连线（称为边）的集合。这里，我们仅介绍其中几个简单的名词。
如果e=uv是图的边，则称u和v是邻接的顶点，顶点u和v互称为邻点。一个点的相邻点的个数称为这个点的次数（或度）。如果一个图中，每一个顶点都可以通过边到达任何其他顶点，我们就称这个图是连通图。
如果一个图可以画在平面上使得其中各条连线彼此不相交，那么这个图叫做平面图。当然，有些图（如下面的左图）初看起来不是平面图，但经过适当的移动（将AB边拉出来，从外面走），就可以变成没有相交连线的平面图，这种图称为可平面化图，或者称为可以嵌入到平面的图。两个图的点数相同，边数相同，点与边的关系也相同，称为两个同构图。
还有的图无论怎么做都不能变成平面图，这种图称为不可平面化的图。最典型的不可平面化的图一个称为K5，一个称为K3，3，如下图所示。
1930年，波兰数学家库拉托夫斯基得出一个着名结论：图G可平面化当且仅当G不包含K5或K3，3的剖分图。所谓剖分图，就是在原图的边上任意添加一些顶点所得到的图。
...03 四色问题
图论中最着名和最具启发性的问题之一是四色问题:"平面上绘制的任何地图，其区域都可能被涂上四种颜色，以至于任何两个边界相同的区域都有不同的颜色，这是真的吗?"
这个问题最早是由弗朗西斯·格思里在1852年提出的，它的第一个书面记录是在同年德·摩根写给汉密尔顿的一封信中。提出了许多不正确的证明，包括Cayley、Kempe等人的证明。
...四色问题曾在近代图论发展中起过重要作用，那么这个地图染色问题是如何与图论联系起来的呢？为创建起图论与地图着色问题之间的联系，数学家引入了对偶图的概念。
...四色猜想是一个区域的染色问题，它可以看做是图的面染色。对此问题可以换一种角度考虑：在地图的每一个区域内取一点，为了形象，不妨设想这点是区域的首都，然后将有公共边界国家的首都用线联结，由此得到一个由点与线构成的新图。每张地图都有的这个与之关联的图称为其对偶图。图中的点称为顶点，图中的线称为边。图中右边相连的两点称为相邻点。显然，一地图中两个顶点是相邻点当且仅当它们所对应的区域有公共边界。
地图的对偶图具有一个特点：其边除了可能在顶点上相交外，都无其他交点。用我们上面刚引入的术语来说，就是每张地图的对偶图都是平面图。反之，每个连通的平面图都是某个地图的对偶图。于是，在经过这种转化后，地图中的面着色问题等价于平面图中的顶点着色问题，而"有公共边界的国家着不同的颜色"变为"每条边的两个端点着不同的颜色"。而四色猜想在其对偶图中等价于：对一个平面图上的顶点染色，使相邻两顶点颜色相异，至多用四种颜色就够了。如果把平面图顶点染色所需要的最少颜色数称为平面图的色数，则四色猜想也等价于说：每个平面图的色数至多是4。
...在引入对偶图后，我们还可以做另一种转换。考虑对所得的平面图进行边染色。即让一个图的每边染一种颜色，并使有公共顶点的边（称为相邻边）有不同的颜色，这样的染色称为边染色。同样的，如果把平面图边染色所需要的最少颜色数称为边色数，则四色猜想等价于：每个平面图的边色数至多是4。
这样，四色问题被带进了图论领域，并转化为图论的着色问题。
...04 图论和应用非常广泛
虽然组成图的顶点和边看似十分简单，我们却可以用之模拟生活中很多的活动，包括人际关系，路线问题，通讯系统，计算机问题。通过图论，我们可以把顶点当做一个人，而连接两个顶点的边表示两个人是朋友，我们可以通过图论证明出拉姆西难题：在随意凑齐的六个人中，一定能找到彼此认识或者彼此不认识的三个人。通过图论，我们若将边加上重量，我们就可以用此模拟优化问题，这些问题在计算机中被称作货郎担问题，是计算机学科中经典的NP问题，正被无数数学和计算机学科中的精英研究着。
这就是图论的魅力了，你感受到了吗？
...图论是近年来发展十分迅速的一个应用数学分支。当前，图论在自身理论研究取得重大进展的同时，也成为解决数学其它领域问题的重要手段，作用日益凸显。此外，作为网络建模的基本理论与方法。
今天，图论已广泛应用在计算机科学、运筹学、控制论、信息论等学科中，成为对现实世界进行抽象的一个强有力的数学工具。数学问题的提出与解决，推动了数学的发展。我们今天学习欧拉的成果不应是单纯把它作为数学游戏看待，重要的是应该知道他是怎样把一个实际问题抽象为数学模型，然后用数学的方法研究它，再用来解决实际问题。这样循环往复，螺旋上升，永无止境。
...