一、欧拉图
 欧拉(Euler)是个绝顶聪明的家伙，当他在1736年访问Konigsberg, Prussia(now Kaliningrad Russia)时，他发现当地的市民正从事一项非常有趣的消遣活动，Konigsberg城中有一条名叫Pregel的河流横经其中，在河上建有七座桥，他们在每个星期六作一次走过所有七座桥的散步，于是就热衷于这样一个问题，可不可以从一个起点出发，经过所有桥一次，最后又回到起点呢？这就是有名的七桥问题。
 图1： http://www.lmedu.com.cn/Img/Content/2004-4-20/20044209342.gif

 如果用结点表示四个位置，用弧表示七座桥，那就成了图论的一个问题：从任意一个结点出发，经过所有的弧一次且仅一次，最后又回到出发点，是否存在这样的环路？
 图2： http://www.lmedu.com.cn/Img/Content/2004-4-20/200442093412.gif

 欧拉为此想到了一个非常简单的方法，确定在什么样的条件下有上面那样的性质，这样的图也就叫欧拉图。
 无向图G(V,E)是欧拉图，当且仅当：
 1、图G所有结点强连通
 2、图G所有结点的度皆为偶数

 它的证明也非常简单，必要性很显然，充分性可以用数学归纳法，不多说了。

二、哈密顿图
 类似的问题还有哈密顿图问题，哈密顿图是这样的图，从任意一个结点出发，经过其它所有结点一次且仅一次，最后又回到出发点，是否存在这样的环路？这样的问题最开始叫做邮差问题，当邮差递信的时候，总是是希望走这样的环路而不重复去同一个地方，这样看上去简单的问题实际上并不简单。

 确定哈密顿图的充分必要条件到目前还没有，只有必要条件或充分条件（书上这么说的），这似乎是告诉学数学的人努力去找到这样一个充分必要条件，就像在数学分析里柯西为函数收敛找到的充要条件而成为收敛原理一样，从而更加深刻地认识这样的数学问题。但我有不同的想法，数学应该更注重美，从哈密顿图的定义看是非常简单的，现在有必要条件，那就是要了解它的性质，现在也有充分条件，那也可以用来判别哈密顿图，为什么要寻找形式上更加复杂的充要条件呢？给原本形式简单的数学问题套上复杂繁琐的面具。

 我按自己的理解，给出一个充分必要条件，但它看上去更像是定义，它是运用递归的形式给出的：
 无向图G(V,E)是哈密顿图，当且仅当：
 1、图G所有结点强连通
 2、图G所有结点的度大于等于2
 3、所有结点的度等于2，或者对于那些度大于2的结点，一定存在它的一条边，当从图G中去掉这条边后得到的图G'仍然是哈密顿图。

 说明一下，条件1、2是必要条件，这很显然，条件3是条件2的补充，同时也是充分条件，它实际上是给出了一种确定方法。：）
 笔者没给出证明，正确与否还不知道。

 另外还有一个非常有名的问题，即所谓的旅行商问题，用图论的形式表示就是求最小哈密顿环，如果给图中每个边加上一个权值，这个值表示连接两结点的‘代价’，比如交通图中两个城市之间的距离，那么问题就是对于任意一个哈密顿环，把它边上的权全加起来何时才能最小？这个问题目前还没有解决，同时也没有数学证明是不可能解决的。

评论