ExcelHome技术论坛

 找回密码
 免费注册

QQ登录

只需一步,快速开始

EH搜索     
EH云课堂-专业的职场技能充电站 妙哉!函数段子手趣味讲函数 Excel服务器-会Excel,做管理系统 Excel Home精品图文教程库
Excel不给力? 何不试试FoxTable! Excel 2016函数公式学习大典 EH云课堂直播课程免费学 打造核心竞争力的职场宝典
300集Office 2010微视频教程 Tableau-数据可视化工具 精品推荐-800套精选PPT模板,点击获取 ExcelHome出品 - VBA代码宝免费下载
你的Excel 2010实战技巧学习锦囊 欲罢不能, 过目难忘的 Office 新界面 Excel VBA经典代码实践指南
查看: 4119|回复: 5

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

[复制链接]

TA的精华主题

TA的得分主题

发表于 2013-11-28 12:24 | 显示全部楼层 |阅读模式
本帖已被收录到知识树中,索引项:
本帖最后由 lee1892 于 2013-11-28 13:29 编辑

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

一、七桥问题

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

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

欧拉在第二年发表论文,证明了符合条件的走法不存在,并顺带提出和解决了一笔画问题。应该说这是图论史上第一篇重要文献。欧拉把实际的抽象问题简化为平面上的点与线组合,每一座桥视为一条线,桥所连接的地区视为点。这样若从某点出发后最后再回到这点,则这一点的线数必须是偶数,这样的点称为偶顶点。相对的,连有奇数条线的点称为奇顶点。欧拉论述了,由于柯尼斯堡七桥问题中存在4个奇顶点,它无法实现符合题意的遍历。
220px-Konigsberg_bridges.png 179px-7_bridges.svg.png 180px-Konigsburg_graph.svg.png
欧拉把问题的实质归于一笔画问题,即判断一个图是否能够遍历完所有的边而没有重复,而柯尼斯堡七桥问题则是一笔画问题的一个具体情境。欧拉最后给出任意一种河、桥图能否全部走一次的判定法则,从而解决了“一笔画问题”。对于一个给定的连通图,如果存在两个以上(不包括两个)奇顶点,那么满足要求的路线便不存在了,且有n个奇顶点的图至少需要n/2笔画出。如果只有两个奇顶点,则可从其中任何一地出发完成一笔画。若所有点均为偶顶点,则从任何一点出发,所求的路线都能实现,他还说明了怎样快速找到所要求的路线。

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

(以上来自中文WiKi)

TA的精华主题

TA的得分主题

 楼主| 发表于 2013-11-28 13:00 | 显示全部楼层
本帖最后由 lee1892 于 2013-11-28 13:01 编辑

二、图论中的基本概念

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

另外在图论中还有一个重要的概念,度(Degree)。一个顶点的度是指联结到该顶点的边的数量,且对于直接联结回到该顶点的边(一个回路,如下图中度为5的顶点)则要计两次。下图显示的图中,每个顶点的度标识在该顶点的圆圈内。
220px-UndirectedDegrees_(Loop).svg.png

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

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

220px-Depth-first-tree.png

关于度的一个定理:握手定理(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 的两倍。
250px-6n-graf.svg.png
(以上来自英文WiKi)

TA的精华主题

TA的得分主题

 楼主| 发表于 2013-11-28 13:26 | 显示全部楼层
本帖最后由 lee1892 于 2013-11-28 13:28 编辑

三、欧拉路径

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


1、一个无向图存在欧拉回路的充要条件是:每一个顶点的度为偶数,并且所有度非零的顶点都属于同一个连通分量(Connected Component,一个图可能由数个互不联通的部分构成)。
240px-Pseudoforest.svg.png
2、一个无向图存在欧拉路径的充要条件是:最多只有两个顶点的度为奇数,并且所有度非零的顶点都属于同一个连通分量。
3、一个有向图存在欧拉回路的充要条件是:每一个顶点的进入度和离开度相等,并且所有度非零的顶点都属于同一个强连通分量(Strong Connected Component,每一个顶点都可以经由边到达其他的每一个顶点的图为强连通图)。
220px-Scc.png
4、一个有向图存在欧拉路径的充要条件是:最多有一个顶点的度 为 (离开度 - 进入度 = 1),并且最多有一个顶点的度 为 (进入度 - 离开度 = 1),其它的顶点有着相等的进入度和离开度,并且所有的度非零的顶点属于同一个连通分量。

TA的精华主题

TA的得分主题

发表于 2014-1-21 22:58 | 显示全部楼层
lee1892 发表于 2013-11-28 13:26
三、欧拉路径

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

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

TA的精华主题

TA的得分主题

发表于 2014-11-11 21:03 | 显示全部楼层
lee1892 发表于 2013-11-28 13:26
三、欧拉路径

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

lee1892老师太高深了!

TA的精华主题

TA的得分主题

发表于 2019-8-20 22:54 | 显示全部楼层
这个问题是否有任何代码或解决方案文件?Excel  vba?

我对这种数学一无所知
您需要登录后才可以回帖 登录 | 免费注册

本版积分规则

关闭

最新热点上一条 /1 下一条

关注官方微信,每天学会一个新技能

手机版|关于我们|联系我们|ExcelHome

GMT+8, 2020-2-26 09:31 , Processed in 0.379221 second(s), 18 queries , Gzip On, MemCache On.

Powered by Discuz! X3.4

© 1999-2020 Wooffice Inc.

   

沪公网安备 31011702000001号 沪ICP备11019229号

本论坛言论纯属发表者个人意见,任何违反国家相关法律的言论,本站将协助国家相关部门追究发言者责任!     本站特聘法律顾问:徐怀玉律师 李志群律师

快速回复 返回顶部 返回列表