图论算法基础 之 七桥问题与欧拉路径

lee1892

相关帖子：
计算两点间最短路径（三种算法的介绍）
浅谈骑士巡逻问题（神经网络算法）与哈密顿路径

一、七桥问题

又被称为柯尼斯堡七桥问题（Seven Bridges of Koenigsberg *） * 德语的 o 上带两点的字母表达为英文时为 oe

大数学家欧拉同学在1735年提出这个问题：在下图中有两个岛及七座桥，在所有桥都只能走一遍的前提下，如何才能把这个地方所有的七座桥都走遍。

欧拉在第二年发表论文，证明了符合条件的走法不存在，并顺带提出和解决了一笔画问题。应该说这是图论史上第一篇重要文献。欧拉把实际的抽象问题简化为平面上的点与线组合，每一座桥视为一条线，桥所连接的地区视为点。这样若从某点出发后最后再回到这点，则这一点的线数必须是偶数，这样的点称为偶顶点。相对的，连有奇数条线的点称为奇顶点。欧拉论述了，由于柯尼斯堡七桥问题中存在4个奇顶点，它无法实现符合题意的遍历。

→

→

欧拉把问题的实质归于一笔画问题，即判断一个图是否能够遍历完所有的边而没有重复，而柯尼斯堡七桥问题则是一笔画问题的一个具体情境。欧拉最后给出任意一种河、桥图能否全部走一次的判定法则，从而解决了“一笔画问题”。对于一个给定的连通图，如果存在两个以上（不包括两个）奇顶点，那么满足要求的路线便不存在了，且有n个奇顶点的图至少需要n/2笔画出。如果只有两个奇顶点，则可从其中任何一地出发完成一笔画。若所有点均为偶顶点，则从任何一点出发，所求的路线都能实现，他还说明了怎样快速找到所要求的路线。

不少数学家都尝试去解析这类事例。而这些解析，最后发展成为了数学中的图论。

（以上来自中文WiKi）

lee1892

二、图论中的基本概念

注意前贴中最右侧的那个抽象图中，在图论里，称蓝色的圆点为顶点（Vertex），联结顶点的黑线则成为边（Edge）。

另外在图论中还有一个重要的概念，度（Degree）。一个顶点的度是指联结到该顶点的边的数量，且对于直接联结回到该顶点的边（一个回路，如下图中度为5的顶点）则要计两次。下图显示的图中，每个顶点的度标识在该顶点的圆圈内。


至此，我们讨论到的是无向图（Un-directed Graph），即边是没有方向限制的。图论中，还有一个概念对应的称为有向图（Directed Graph），即边是有方向限制的。那么对于有向图而言，一个顶点度就存在两种：进入度（In-Degree）和离开度（Out-Degree）。

度的一些特殊值：

• 一个顶点的度如果是0，则被称为孤立顶点（Isolated Vertex）
• 一个顶点的度如果是1，则可以被称为叶子顶点（Leaf Vertex）或是末端顶点（End Vertex），如下图中的树
• 对于有 n 个顶点的图，如果某个顶点有 n-1 的度，则该顶点就被称为控制顶点（Dominating Vertex）
  

关于度的一个定理：握手定理（Handshaking Lemma）
对于任何一个有限的无向图，度为奇数的顶点数量是偶数。更为通俗的说法，在一群人中，一部分人互相握手，握了奇数个其他人的手的人数为偶数（In a party of people some of whom shake hands, an even number of people must have shaken an odd number of other people's hands）。该定理可由图的总度数计算公式推导，图总度数是其边的数量的两倍。如下图中，顶点2、4、5、6的度为奇数，而图的总度数则为 2+3+2+3+3+1=14（由1至6），为边的数量 7 的两倍。

（以上来自英文WiKi）

lee1892

三、欧拉路径

对于前述的七桥问题，将桥所连接的地区视为顶点，而每座桥视为边，就可以用图论术语来描述：对于一个有着四个顶点和七条边的无向图，是否能找到一个恰好包含了所有的边并且没有重复的路径。推而广之对于任意一个图而言，是否能够判断存在与否这样能包含所有的边且不重复的路径，或更为术语化的：能够便利完所有的边而没有重复。这样的路径在图论中被称为欧拉路径（Eulerian Path），如果路径的起始顶点和结束顶点为同一个的话，则被称为欧拉回路（Eulerian Cycle）。而存在欧拉路径的图则可被称为欧拉图（Eulerian Graph）。


1、一个无向图存在欧拉回路的充要条件是：每一个顶点的度为偶数，并且所有度非零的顶点都属于同一个连通分量（Connected Component，一个图可能由数个互不联通的部分构成）。

2、一个无向图存在欧拉路径的充要条件是：最多只有两个顶点的度为奇数，并且所有度非零的顶点都属于同一个连通分量。
3、一个有向图存在欧拉回路的充要条件是：每一个顶点的进入度和离开度相等，并且所有度非零的顶点都属于同一个强连通分量（Strong Connected Component，每一个顶点都可以经由边到达其他的每一个顶点的图为强连通图）。

4、一个有向图存在欧拉路径的充要条件是：最多有一个顶点的度 为 （离开度 - 进入度 = 1），并且最多有一个顶点的度 为 （进入度 - 离开度 = 1），其它的顶点有着相等的进入度和离开度，并且所有的度非零的顶点属于同一个连通分量。

aoe1981

lee1892 发表于 2013-11-28 13:26
三、欧拉路径

对于前述的七桥问题，将桥所连接的地区视为顶点，而每座桥视为边，就可以用图论术语来描述 ...

毫无疑问，欲做计算机大家者，必是数学狂人，数学是基础性的学科，在很多时候，掌握数学知识的深度与广度决定了各种应用的深度与广度！一门学科或技术，只有广泛而深入地应用着数学的原理与技巧时，才是蓬勃而成熟的。。。楼主大才，长期坚持，必有大成！

EXCEL江湖

lee1892 发表于 2013-11-28 13:26
三、欧拉路径

对于前述的七桥问题，将桥所连接的地区视为顶点，而每座桥视为边，就可以用图论术语来描述 ...

lee1892老师太高深了！

xman2000

这个问题是否有任何代码或解决方案文件？Excel  vba?

我对这种数学一无所知