离散数学7欧拉图与汉密尔顿图(ppt文档).ppt

7.欧拉图与汉密尔顿图一.欧拉图:
1.欧拉路:在无孤立结点的图G中,如果存在一条路,它经过图中每条边一次且仅一次,称此路为欧拉路.
2.欧拉回路:在无孤立结点的图G中,若存在一条回路,它经过图中每条边一次且仅一次,称此回路为欧拉回路.
称此图为欧拉图,或E图.(Euler)
在G1中:有欧拉路:
acbefgdcfh
在G2中:有欧拉回路:
v1v2v3v4v5v2v4v6v5v3v1

如何判定一个图中是否有
欧拉路,或有欧拉回路?3.有欧拉路与有欧拉回路的判定:
定理8-5.1:无向图G具有欧拉路,当且仅当G是连通的,且有
零个或两个奇数度的结点.
*证明:必要性,设G有欧拉路.(自行尝试证明)
充分性,(证明的过程就是一个构造欧拉路的过程)
如果G有两个奇数度结点:就从一个奇数度结点出发,每
当到达一个偶数度结点,必然可以再经过另一条边离开此
结点,如此重复下去,经过所有边后到达另一个奇数度结点
如果G无奇数度结点,则可以从任何一个结点出发,去构
造一条欧拉路.

推论:无向图G具有欧拉回路,
当且仅当G是连通的,且所有结点的度都是偶数.从此推论得知,七桥问题的图不是欧拉图.
4.求欧拉回路的算法:

用上述算法求右图中欧拉回路.
此图中所有结点度均为偶数,
所以有欧拉回路.
a)选以1为起点的闭迹E1:1261
b)E1不包含所有边.
c)在G-E1中找新闭迹E2:6356(6是E1与E2的公共点)
d)以公共点6为起点,对E1∪E2中的边排序:C=6356126
e)E1:=C
f)E1不包含所有边.
g)在G-E1中找新闭迹E2:52345(5是E1与E2的公共点)
h)以公共点5为起点,对E1∪E2中的边排序:
C=52345612635
i)E1:=C
j)E1包含所有边.k)打印E1=52345612635l)停止.欧拉路与欧拉回路问题,也称一笔画问题.

5.欧拉图的应用----计算机鼓轮的设计
早期向计算机输入数据,为简单,以输入八进制数为例
(0,1,2,3,4,5,6,7,即000,001,010,011,100,101,110,111)
鼓轮表面分成23等分,每一等分分别用绝缘体或导体组成,
绝缘部分输出0,导体部分输出1.有三个触点分别与三个
部分接触,以读取三个数字.
转动鼓轮,分别输出8个数:
000,001,010,011,100,101,110,111
下面介绍此鼓轮的设计过程:此轮的设计:以两位二进制数
V={00,01,10,11}为结点,画带
权图(即边上标有数字--称为
边的权),从任何a1∈V结点
画2条有向边,标权0(或1),
该边指向结点a2,于是构成
边a10,(或a11),这八条边分别
表示八个二进制数:
000,001,010,011,100,101,110,111
从此图上取一个欧拉回路:e0e1e2e5e3e7e6e4
将上述各边的末位数字写成序列:01011100,
于是就按照此序列将鼓轮进行加工,标0部分
用绝缘体,标1部分用导体.思考题：
上面的“计算机鼓轮设计问题”里，用到的是有向图欧拉回路。而有向图何时具有欧拉回路，其判定方法与无向图不同。具体会是怎样的呢？请同学们在课余时间自行搜索资料。
另外，上面设计有向图的边，也缺乏唯一性和确定性。是不是随便设计边就可以呢？请大家举例尝试自行设计计算机鼓轮的编码。
实际上，该编码不能任意设计，也就是说有向图是应该有确定的设计规则的。具体规则又会是什么呢？
同样，请同学在课余时间思考。
一般，将如此设计好的{0，1}序列，叫做布鲁因（DeBrujin）序列。该序列长度并不局限于8位，同样有16位，32位等任意2n长度的布鲁因序列。二.汉密尔顿图(H图)(Hamilton图)
Hamilton是英国数学家,在1959年,他提出Hamilton回路.
H图起源于一种游戏,这个游戏就是所谓周游世界问题.
例如,某个城市的街道如图所示:
该城市的所有交叉路口都有形象各
异的精美的雕塑,吸引着许多游客,
人人都想找到这样的路径:游遍各
个景点再回到出发点----H回路.
1.定义:设G=<V,E>是个无向有限图,
汉密尔顿路:通过G中每个结点恰好一次的路.
汉密尔顿回路(H回路):通过G中每个结点恰好一次的回
路.
汉密尔顿图(H图):具有汉密尔顿回路(H回路)的图.
例如右图中,就是H图,因为它有H回路:1234561
2.汉密尔顿图的判定:
到目前为止并没有判定H图的充分和必要条件.
定理8-5.2(充分条件):G是完全图,则G是H图.
证明:略

定理8-5.3(充分条件)设G是有n个结点的简单图,若G中每对结点度数之和大于等于n-1(n),则G有一条H路(H回路)
证明:先证