e图和h图ppt课件

《e图和h图ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第十章E图和H图1§10.1七桥问题与E图历史上的哥尼斯堡七桥问题是著名的图论问题。问题是这样的：18世纪的东普鲁士有个哥尼斯堡城，在横贯全城的普雷格尔河两岸和两个岛之间架设了7座桥，它们把河的两岸和两个岛连接起来。每逢假日，城中居民进行环城游玩，人们对此提出了一个“遍游”问题，即能否有这样一种走法，使得从某地出发通过且只通过每座桥一次后又回到原地呢？2ABCD用顶点表示陆地，边表示陆地之间的桥。则问题等价于“能否一笔画出右图？”，即找经过每条边一次且仅一次的回路。Euler证明了，七桥问题是无解的。E图定义10.1

2、.1：设G是一个图，经过G的每一条边的链称为E链；闭的E链称为E闭链。如果G中存在E链，称G为半E图；如果G中存在E闭链，称G为E图（欧拉图）。3问题：对于一个图G，如何判定它是否为E图、半E图呢？还记得我们第一次课的手机解锁图吗？手机解锁图下面的讨论中设G是非平凡的连通图。E图半E图都不是无奇点的连通图是E图引理10.1.1：连通图G中无奇点，则G是E图。证明：（反证法）设G是无奇点的连通图且G不是E图。（构造反例：G中有闭链，且是E链）在所有连通无奇点的非E图中，选一个边最少的图G。因G的每个顶点的度至少是2，从

3、而G必含闭链。5若G不含回路，则G是树。我们知道树中至少有两个悬挂点（奇点），矛盾。所以G中一定含有回路。而回路就是闭链。所以G中必含闭链。设C是G中最长的闭链，由假设C不是E闭链。（下面推出矛盾）。为什么？半E图中最多有两个奇点推论10.1.1G是半E图当且仅当G中最多有两个奇点。证明：(充分性)设G是半E图，C是G的一条E链。除起点与终点外，C中每个顶点的度均为偶数。又因G连通，故G最多有两个奇点。(必要性)设G最多只有两个奇点。若G无奇点，则由定理10.1.1知，G为E图，亦为半E图；若G有两个奇点，设为u和v

4、,则在G中加入e=uv的边，使G中无奇点。由定理10.1.1知，G+e为E图，即G+e含E闭链C，于是C–e构成G的一条E链，所以G是半E图。8为什么不要证明G中只有一个奇点的情况？因为任何一个图的奇点个数必为偶数。练一练哥尼斯城堡桥不是E图10“一笔画”游戏攻略我国民间很早就流传一种“一笔画”游戏，由刚才所学的定理，你能给出游戏攻略吗？如何判定，如何画？如果图中所有结点是偶点，则可以任选一点作为始点一笔画完；如果图中只有两个奇点，则可以选择其中一个奇点作为始点也可一笔画完。其余情况则不能一笔画完。应用题例：下图是一

5、幢房子的平面图形，前门进入一个客厅，由客厅通向4个房间。如果要求每扇门只能进出一次，现在你由前门进去，能否通过所有的门走遍所有的房间和客厅，然后从后门走出？§10.2周游世界问题与H图周游世界问题:用一个正十二面体的二十个顶点来代表二十个城市，要求从其中任一顶点出发，沿着这个正十二面体的棱走遍这二十个顶点，且每个城市只经过一次，最后回到起点。该问题等价于“能否从下图找一条含所有顶点的回路？”13H图定义10.2.1：设G是一个图，含G的每个顶点的通路称为H通路；起点与终点重合的H通路称为H回路；如果G中存在H回路，称

6、G为H图（汉密尔顿图）；若G中存在H通路，称G为半H图。显然，H图必是半H图，反之不然。14Herschel图该图是半H图。15因为它是一个具有奇数个顶点的二分图。所以不可能有H回路。因为二分图中的回路一定是偶数条边。(定理7.5.2)为什么？H图的判定问题：对于一个图G，如何判定它是否为H图、半H图呢？尽管H回路与E回路问题在形式上极为相似，但是到目前为止还不知道一个图为H图的充要条件，寻找该充要条件仍是图论中尚未解决的主要问题之一。下面先给出一个简单而有用的必要条件。H图的一个必要条件定理10.2.1如果G是一个

7、H图，则对V(G)的任何非空真子集S，均成立：(G–S)

8、S

9、证明：设C是G的H回路(G的所有顶点都在C上)，S是V(G)的任一非空子集。则显然在G－S中，C最多被分为

10、S

11、段，所以W（G－S）≤

12、S

13、17定理10.2.1证明图示18G(H图)C(H回路）一个非H图的判定取S为红色点集。

14、S

15、=5。(G–S)=6＞

16、S

17、根据定理10.2.1，此图不是H图。试一试你能判别下图是否为H图吗？必要条件仅可判定非H图注意定理10.2.1只是判断H图的必要条件，有的图虽然满足条件，却不是H图。(满足的不一定是，不满足的一

18、定不是）。21Peterson图Peterson图是半H图而不是H图。如下面的Peterson图不是H图。可是它却满足定理10.2.1的条件。H图的充分条件问题：满足什么条件的图一定为H图、半H图呢？判断H图、半Ｈ图的充分条件很多，我们逐一介绍。H图的一个充分条件定理10.2.2设G是p(3)阶简单图。如果G中任何两个不邻接的顶点u和v均满足