7-4欧拉图和汉密尔顿图 要求： 1、理解欧拉图、汉密尔顿图的定义。 2、掌握欧拉图的判定方法。 3、会判断一些图不是汉密尔顿图。

Presentation on theme: "7-4欧拉图和汉密尔顿图 要求： 1、理解欧拉图、汉密尔顿图的定义。 2、掌握欧拉图的判定方法。 3、会判断一些图不是汉密尔顿图。"— Presentation transcript:

1 7-4欧拉图和汉密尔顿图 要求： 1、理解欧拉图、汉密尔顿图的定义。 2、掌握欧拉图的判定方法。 3、会判断一些图不是汉密尔顿图。
4、熟悉一些欧拉图和汉密尔顿图。

2 一、欧拉图 1、哥尼斯堡七桥问题 A B C D

3 七桥问题等价于在图中求一条回路，此回路经过每条边一次且仅有一次。欧拉在1736年的论文中提出了一条简单的准则，确定了哥尼斯堡七桥问题是不能解的。

4 2、欧拉图(Euler) 1.定义 如果无孤立结点图G上有一条经过G的所有边一次且仅一次的路径，则称该路径为图G的欧拉路径（Euler walk）。如果图G上有一条经过G边一次且仅一次的的回路，则称该回路为图G的欧拉回路，具有欧拉回路的图称为欧拉图（Euler graph）。 2.定理 无向图G具有一条欧拉路，当且仅当G连通，并且有零个或两个奇数度结点。

5  证明思路：1) 先证必要性: G有欧拉路  G连通 且（有0个 或 2个奇数度结点） 设G的欧拉路是点边序列v0e1v1e2… ekvk，其中结点可能重复，但边不重复。因欧拉路经过（所有边）所有结点，所以图G是连通的。 对于任一非端点结点vi，在欧拉路中每当vi出现依次，必关联两条边，故vi虽可重复出现，但是deg(vi)必是偶数。对于端点,若v0=vk ，则deg(v0)必是偶数，即G中无奇数度结点 。若v0≠vk ，则deg(v0)必是奇数， deg(vk)必是奇数,即G中有两个奇数度结点 。必要性证完。

6 2)再证充分性:(证明过程给出了一种构造方法)
G连通且（有0个 或 2个奇数度结点） G有欧拉路 (1)若有 2个奇数度结点,则从其中一个结点开始构造一条迹,即从v0出发经关联边e1进入v1,若deg(v1)为偶数,则必可由v1再经关联边e2进入v2,如此下去,每边仅取一次,由于G是连通的,故必可到达另一奇数度结点停下,得到一条迹L1:v0e1v1e2… ekvk。若G中没有奇数度结点,则从任一结点v0出发,用上述方法必可回到结点v0,得到一条闭迹。 (2) 若L1通过了G的所有边, L1就是一条欧拉路。 (3) 若G中去掉L1后得到子图G’,则G’中每个结点度数都为偶数,因为原来的图G是连通的,故L1与G’至少有一个结点vi重合,在G’中由vi出发重复(1)的方法,得到闭迹L2。 (4)当L1与L2组合,若恰是G,得欧拉路,否则重复(3),可得闭迹L3,依此类推可得一条欧拉路。充分性证完 

7 3.定理7-4.1的推论 无向图G具有一条欧拉路，当且仅当G连通且所有结点度数皆为偶数。
由于有了欧拉路和欧拉回路的判别准则，因此哥尼斯堡七桥问题立即有了确切的否定答案，因为从图中可以看到deg(A)＝5，deg(B)＝deg(C)＝deg(D)=3，故欧拉回路必不存在。

8 (b)为欧拉回路，可以从任一结点出发，一笔画回到原出发点。
4、一笔画问题 要判定一个图G是否可一笔画出，有两种情况：一是从图G中某一结点出发，经过图G的每一边一次仅一次到达另一结点。另一种就是从G的某个结点出发，经过G的每一边一次仅一次再回到该结点。上述两种情况分别可以由欧拉路和欧拉回路的判定条件予以解决。 见303页图7- 4.3 (a)为欧拉路，有从v2到v3的一笔画。 (b)为欧拉回路，可以从任一结点出发，一笔画回到原出发点。 练习 311页（1）（3）

9 311页(3) 完全图Kn每个结点的度数为n-1，要使n-1为偶数，必须n为奇数。故当n为奇数时，完全图Kn有欧拉回路。

10 可以将欧拉路和欧拉回路的概念推广到有向图中。
5.定义7-4.2：给定有向图G，通过图中每边一次且仅一次的一条单向路（回路），称作单向欧拉路（回路）。 6.定理 有向图G为具有一条单向欧拉回路，当且仅当G连通，并且每个结点的入度等于出度。有向图G有单向欧拉路，当且仅当G连通，并且恰有两个结点的入度与出度不等，它们中一个的出度比入度多1，另一个入度比出度多1。 证明思路与定理7-4.1类似

11 例1有向欧拉图应用示例：计算机鼓轮的设计。
鼓轮表面分成24=16等份，其中每一部分分别用绝缘体或导体组成，绝缘体部分给出信号0，导体部分给出信号1，在下图中阴影部分表示导体，空白体部分表示绝缘体，根据鼓轮的位置，触点将得到信息4个触点a,b,c,d读出1101(状态图中的边e13),转一角度后将读出1010 (边e10)。 问鼓轮上16个部分怎样安排导体及绝缘体才能使鼓轮每旋转一个部分，四个触点能得到一组不同的四位二进制数信息。

12 d 1 1 1 1 1 1 c 1 b 1 1 1 a 1

13 设有一个八个结点的有向图，如下图所示。其结点分别记为三位二进制数{000，001，……，111}，
设ai{0,1}，从结点a1 a2 a3可引出两条有向边，其终点分别是a2 a30以及a2 a31。该两条边分别记为a1 a2 a30和a1 a2 a31。 按照上述方法，对于八个结点的有向图共有16条边，在这种图的任一条路中，其邻接的边必是a1 a2 a3a4和a2 a3a4a5的形式，即是第一条边标号的后三位数与第二条边的头三位数相同。 由于图中16条边被记为不同的二进制数，可见前述鼓轮转动所得到16个不同位置触点上的二进制信息，即对应于图中的一条欧拉回路。

14 e0=0000 a1 a2 a3 (=000) 1 a1 a2 a3 (=000) 0 000 a1 a2 a3 (=100) 0 e1=0001 e8=1000 a1 a2 a3 (=001) 1 e9=1001 001 100 010 e2=0010 e4=0100 e3=0011 e5=0101 e10=1010 e12=1100 101 e11=1011 e13=1101 011 110 e6=0110 a1 a2 a3 (=110) 0 e14=1110 e7=0111 a1 a2 a3 (=011) 1 111 a1 a2 a3 (=111) 0 a1 a2 a3 (=111) 1 e15=1111

15 所求的欧拉回路为： e0e1e2e4e9e3e6e13e10e5e11e7e16e14e12e8(e0) （从图示位置开始） e13e10e5e11e7e16e14e12e8e0e1e2e4e9e3e6 (e13) 所求的二进制序列为： (0) (1) （从图示位置开始） 上述结论可推广到鼓轮具有n个触点的情况。构造2n-1 个结点的有向图，每个结点标记为n-1位二进制数,从结点a1a2a3...an-1出发,有一条终点为a2a3...an-10的边,该边记为a1a2a3...an-10；还有一条终点标记为a2a3...an-11的边,该边记为a1a2a3...an-11 。邻接边的标记规则为：“第一条边后n-1位与第二条边前n-1位二进制数相同”。 哈密尔顿回路问题见图7-4.6。

16 二、汉密尔顿图 与欧拉回路类似的是汉密尔顿回路。它是1859年汉密尔顿首先提出的一个关于12面体的数学游戏：能否在图7-4.6中找到一个回路，使它含有图中所有结点一次且仅一次？若把每个结点看成一座城市，连接两个结点的边看成是交通线，那么这个问题就变成能否找到一条旅行路线，使得沿着该旅行路线经过每座城市恰好一次，再回到原来的出发地？他把这个问题称为周游世界问题。 1、定义7-4.3：给定图G，若存在一条路经过图中的每个结点恰好一次，这条路称作汉密尔顿路。若存在一条回路，经过图中的每个结点恰好一次，这条回路称作汉密尔顿回路。 具有汉密尔顿回路的图称作汉密尔顿图。

17 图7-4.6存在一条汉密尔顿回路，它是汉密尔顿图

18 C经过图G的每个结点恰好一次， C与G的结点集合是同一个，因此 C-S与G-S的结点集合是同一个，
2、定理 若图G＝<V，E>具有汉密尔顿回路，则对于结点集V的每个非空子集S均有W(G-S)≤|S|，其中W(G-S)是G-S的连通分支数。 证明 设C是G的一条汉密尔顿回路，对于V的任何一个非空子集S，在C中删去S中任一结点a1，则C-a1是连通的非回路， W(C- a1)=1， |S|≥1，这时 W(C-S)≤|S|。 若再删去S中另一结点a2，则W(C-a1-a2)≤2，而 |S|≥2，这时 W(C-S)≤|S|。由归纳法可得：W(C-S)≤|S|。同时C-S是G-S的一个生成子图，因而W(G-S)≤W(C-S)，所以W(G-S)≤|S|。 C经过图G的每个结点恰好一次， C与G的结点集合是同一个，因此 C-S与G-S的结点集合是同一个，

19 此定理是必要条件，可以用来证明一个图不是汉密尔顿图。
如右图，取S={v1,v4}，则G-S有3个连通分支， 不满足W(G-S)≤|S|，故该图不是汉密尔顿图。

20 说明：此定理是必要条件而不是充分条件。有的图满足此必要条件，但也是非汉密尔顿图。
所以用此定理来证明某一特定图是非汉密尔顿图并不是总是有效的。例如，著名的彼得森(Petersen)图，在图中删去任一个结点或任意两个结点，不能使它不连通；删去3个结点，最多只能得到有两个连通分支的子图；删去4个结点，只能得到最多三个连通分支的子图；删去5个或5个以上的结点，余下子图的结点数都不大于6，故必不能有5个以上的连通分支数。所以该图满足W(G-S)≤|S|，但是可以证明它是非汉密尔顿图。

21 下面的定理给出一个无向图具有汉密尔顿路的充分条件。
3.定理 设图G具有n个结点的简单图,如果G中每一对结点度数之和大于等于n-1,则G中存在一条汉密尔顿路。  证明思路：1) 先证G连通: 若G有两个或多个互不连通的分支,设一个分图有n1个结点,任取一个结点v1,另一分图有n2个结点,任取一个结点v2,因为deg(v1)≤n1-1, deg(v2)≤n2-1, deg(v1)+ deg(v2)≤n1+n2-2<n-1 ,与假设矛盾, G是连通的。

22 2) 先证(构造)要求的汉密尔顿路存在: 设G中有p-1条边的路,p<n,它的结点序列为v1, v2,…, vp。如果有v1或vp邻接于不在这条路上的一个结点,立刻扩展该路,使它包含这个结点,从而得到p条边的路。否则v1和vp都只邻接于这条路上的结点,我们证明在这种情况下,存在一条回路包含结点v1, v2,…, vp。 若v1邻接于vp,则v1, v2, …, vp即为所求。 若v1邻接于结点集{vl,vm,…,…,vj,…,vt}中之一,这里2≤l,m,...,j,...,t≤p-1,如果vp是邻接于vl-1,vm-1,…,…, vj-1, …,vt-1中之一,譬如是vj-1,则v1v2…vj-1vpvp-1...vjv1 是所求回路（如图7-4.9(a)所示）。 如果vp不邻接于vl-1,vm-1,…,…,vj-1, …,vt-1中任一个,则vp最多邻接于p-k-1个结点, deg(vp)≤p-k-1, deg(v1)=k,故deg(vp)+deg(v1)≤p-k-1+k<n-1,即v1与 vp 度数之和最多为n-2，得到矛盾。

23 至此，已经构造出一条包含结点v1,v2,…,vp的回路,因为G是连通的,所以在G中必有一个不属于该回路的结点vx与回路中某一结点vk邻接,如图7-4.9(b)所示, 于是就得到一条包含p条边的回路(vx,vk,vk+1,…,vj-1,vp,vp-1,…, vj,v1, v2 , …, vk-1),如图7-4.9(c)所示,重复前述构造方法，直到得到n-1条边的路。  说明：该定理的条件是充分条件但不是必要条件。见308页图7-4.10。 n=6，每一对结点度数之和等于4，小于n-1，但在G中存在一条汉密尔顿路。

24 例 某地有5个风景点，若每个景点均有两条道路与其他景点相通，问是否可经过每个景点一次而游完这5处。
解 将景点作为结点，道路作为边，则得到一个有5个结点的无向图。 由题意，对每个结点vi(i=1,2,3,4,5)有 deg(vi)=2。 则对任两点和均有 deg(vi) + deg(vj)=2 + 2 =4 = 5 – 1 所以此图有一条汉密尔顿回路。即经过每个景点一次而游完这5个景点。

25 例：在七天内安排七门课程的考试，使得同一位教师所任的两门课程不排在接连的两天中，试证明如果没有教师担任多于四门课程，则符合上述要求的考试安排总是可能的。
证明：设G为具有七个结点的图，每个结点对应于一门课程考试，如果这两个结点对应的课程考试是由不同教师担任的，那么这两个结点之间有一条边，因为每个教师所任课程数不超过4，故每个结点的度数至少是3，任两个结点的度数之和至少是6，故G总是包含一条汉密尔顿路，它对应于一个七门考试课程的一个适当的安排。

26 4.定理7-4.5 设图G具有n个结点的简单图,如果G中每一对结点度数之和大于等于n,则G中存在一条汉密尔顿回路。
 证明思路：由定理7-4.4知,必有一条汉密尔顿路,设为v1,v2,…,vn,若v1与vn邻接,则定理得证。 若v1与vn不邻接,假设v1邻接于{ vi1,vi2,…,vik}, 2≤ij≤n-1, vn必邻接于vi1-1,vi2-1,…,vik-1中之一。若vn不邻接于vi1-1,vi2-1,…,vik-1中之一,则vn至多邻接于n-k-1个结点,因而, deg(vn)≤n-k-1,而 deg(v1)=k, deg(v1)+ deg(vn)≤n-k-1+k=n-1 ,与假设矛盾, 所以必有一条汉密尔顿路v1v2…vj-1vnvn-1 …vjv1,如图7-4.11所示。 

27 在这个例子中C(G)是完全图，一般情况下， C(G)也可能不是完全图。
5、图的闭包 定义7-4.4：给定图G=<V，E>有n个结点，若将图G中度数之和至少是n的非邻接结点连接起来得图G’，对图G’重复上述步骤，直到不再有这样的结点对存在为止，所得到的图，称为是原图G的闭包，记作C(G)。 在这个例子中C(G)是完全图，一般情况下， C(G)也可能不是完全图。 构造310页图7-4.12(a)的闭包。

28 6、定理7-4.6：当且仅当一个简单图的闭包是汉密尔顿图时，这个简单图是汉密尔顿图。
7、推论：n3的有向(无向)完全图Kn为汉密尔顿图。

29 关于图中没有汉密尔顿路的判别尚没有确定的方法，下面通过一个例子，介绍一个判别汉密尔顿路不存在的标号法。
例 证明下图没有汉密尔顿路。

30 证明 任取一结点如v1,用A标记，所有与它邻接的结点标B。
继续不断地用A标记所有与B邻接的结点，用B标记所有与A邻接的结点，直到图中的所有结点全部标记完毕。

31 遇到相邻结点出现相同标记，可在此对应边上增加一个结点，并标上相异标记。见图7-4.14
再看310页例题2 如果图中有一条汉密尔顿路，则必交替通过结点A和B。因此或者结点A和B数目一样，或者两者相差1个。 而本题有3个结点标记A，5个结点标记B，它们相差2个，所以该图不存在汉密尔顿路。 遇到相邻结点出现相同标记，可在此对应边上增加一个结点，并标上相异标记。见图7-4.14

32 练习 311页（7）

33 有7个结点标记A，6个结点标记B，所以该图不存在一条汉密尔顿回路。

34 在无孤立结点图G中，经过图中每条边一次且仅有一次的一条回路，称为欧拉回路。
311页（6） a)画一个有一条欧拉回路和一条汉密尔顿回路的图。 给定图G，经过图中每个结点恰好一次的回路称作汉密尔顿回路。

35 b)画一个有一条欧拉回路，但没有一条汉密尔顿回路的图。

36 c)画一个没有一条欧拉回路，但有一条汉密尔顿回路的图。

37 无向图G具有一条欧拉回路，当且仅当G是连通的，并且所有结点度数全为偶数。下面的图中所有结点度数全为偶数，所以都是欧拉图。
311页（2）构造一个欧拉图，其结点数v和边数e满足下述条件 a)v，e的奇偶性一样。 b) v，e的奇偶性相反。 如果不可能，说明原因。 无向图G具有一条欧拉回路，当且仅当G是连通的，并且所有结点度数全为偶数。下面的图中所有结点度数全为偶数，所以都是欧拉图。 v=3,e=3 v=4,e=4 v=4,e=6 v=5,e=5 v=6,e=7 v=7,e=8