第10章几种典型图 图10.1.2
第10章 几种典型图 图 10.1.2 e10 e 1 e9 e 3 e4 e2 e5 e6 e7 e8 (a) (b) (c) 1 0 5 4 3 2
第10章几种典型图 当给定了一个欧拉图后,如何找出它的一条欧拉 回路?下面的 Fleury(于1921年提出)算法解决了这个 问题,这个算法的实质是“避桥” 设G是欧拉图。 (1)任选G的一个顶点v为起点,并设零条边的通 路为b=vo (2)设已选好的简单通路为l-=Vne1ve2v2,ev,则按 下述方法从E{e1,e2,…,e}中选取边e+1:
第10章 几种典型图 当给定了一个欧拉图后，如何找出它的一条欧拉 回路？下面的Fleury（于1921年提出）算法解决了这个 问题，这个算法的实质是“避桥” 。 设G是欧拉图。 （1）任选G的一个顶点v0为起点，并设零条边的通 路为l0 =v0。 （2）设已选好的简单通路为l i =v0e1v1e2v2…eivi，则按 下述方法从E-{e1，e2，…，ei}中选取边ei+1：
第10章几种典型图 ①er1与v,关联; ②2除非没有别的边可选择,否则e+1不是G=G- e1,e2,…,e;}的割边(桥)。 (3)当第(2)步不能继续进行时(所有的边已走 遍),算法终止
第10章 几种典型图 ①ei+1与vi关联； ② 除非没有别的边可选择，否则ei+1不是Gi =G- {e1，e2，…，ei}的割边（桥）。 （3）当第(2)步不能继续进行时（所有的边已走 遍），算法终止
第10章几种典型图 【例10.1.1】找出图10.12(a)所示图G的一条欧 拉回路。 解从v出发,先找到l3=ve1ve24e3l6,因为此时在 G3=G-{e1,e2,e3}中,关联v的边e和e10均是割边,所 以只能选取e4,继续下去,最后可得一条欧拉回路: VoeIvle,ve3vsevesvesv3e7v e&vleolse1ol
第10章 几种典型图 【例10.1.1】 找出图10.1.2（a）所示图G的一条欧 拉回路。 解 从v0出发，先找到l3 =v0e1v1e2v4e3v6，因为此时在 G3 =G-{e1，e2，e3}中，关联v6的边e9和e10均是割边，所 以只能选取e4，继续下去，最后可得一条欧拉回路： l=v0e1v1e2v4e3v5e4v2e5v4e6v3e7v2e8v1e9v5e10v0
第10章几种典型图 最后介绍一下“中国邮递员问题”( the chinese Postman problem)。我国数学家管梅谷于1962年首先 提出这个问题,并得到一些结果,得到世界同行们的 承认。该问题是说:邮递员从邮局出发在他的管辖区 域内投递邮件,然后回到邮局。自然,他必须走过他 所辖区域内的每一条街道至少一次。在此前提下,希 望找到一条尽可能短的路线
第10章 几种典型图 最后介绍一下“中国邮递员问题”（the Chinese Postman Problem）。我国数学家管梅谷于1962年首先 提出这个问题，并得到一些结果，得到世界同行们的 承认。该问题是说：邮递员从邮局出发在他的管辖区 域内投递邮件，然后回到邮局。自然，他必须走过他 所辖区域内的每一条街道至少一次。在此前提下，希 望找到一条尽可能短的路线