欧拉图与哈密顿ppt课件

1、第十五章第十五章 欧拉图与哈密顿图欧拉图与哈密顿图15.1 15.1 欧拉图欧拉图1736年数学家欧拉发表了第一篇图论论文，解诀了哥尼斯堡七桥问题。 定义欧拉通路和欧拉回路定义欧拉通路和欧拉回路 经过图无向图或有向图中一切边一次且仅一次行经过图无向图或有向图中一切边一次且仅一次行遍图中一切顶点的通路称为欧拉通路遍图中一切顶点的通路称为欧拉通路 经过图中一切边一次并且仅一次行遍一切顶点的回路经过图中一切边一次并且仅一次行遍一切顶点的回路称为欧拉回路称为欧拉回路 定义欧拉图和半欧拉图定义欧拉图和半欧拉图 具有欧拉回路的图称为欧拉图具有欧拉回路的图称为欧拉图 具有欧拉通路无欧拉回路的图称为半欧拉图具

2、有欧拉通路无欧拉回路的图称为半欧拉图 规定平凡图是欧拉图规定平凡图是欧拉图 1欧拉图。 2半欧拉图。 3不存在欧拉通路，也不存在欧拉回路。 4欧拉图。 5不存在欧拉通路，也不存在欧拉回路。 6不存在欧拉通路，也不存在欧拉回路。 例例 1 1 2 2 3 3 4 4 5 5 6 6 无向欧拉图与无向半欧拉图的判别方法无向欧拉图与无向半欧拉图的判别方法 定理定理15.115.1无向欧拉图的断定无向图无向欧拉图的断定无向图G G是欧拉图当是欧拉图当且仅当且仅当G G是连通图，且是连通图，且G G中没有奇度顶点。中没有奇度顶点。 定理定理15.215.2无向半欧拉图的断定无向图无向半欧拉图的断定无向图

3、G G是半欧拉是半欧拉图当且仅当图当且仅当G G是连通图，且是连通图，且G G中恰有两个奇度顶点。中恰有两个奇度顶点。1 1 2 2 3 3 判别所示两图能否为欧拉图、半欧拉图？ 有向欧拉图与有向半欧拉图的判别方法有向欧拉图与有向半欧拉图的判别方法 定理定理15.3 15.3 有向欧拉图的断定有向图有向欧拉图的断定有向图D D是欧拉图是欧拉图当且仅当当且仅当D D是强连通的且每个顶点的入度都等于出度。是强连通的且每个顶点的入度都等于出度。 定理定理15.415.4有向半欧拉图的断定有向图有向半欧拉图的断定有向图D D是半欧拉是半欧拉图当且仅当图当且仅当D D是单向连通的，且是单向连通的，且D

4、D中恰有两个奇度顶点，中恰有两个奇度顶点，其中一个的入度比出度大其中一个的入度比出度大1 1，另一个的出度比入度大，另一个的出度比入度大1 1，而其他顶点的入度都等于出度。而其他顶点的入度都等于出度。4 4 5 5 6 6 由两断定定理，立刻可知 4为欧拉图， 5、6即不是欧拉图，也不是半欧拉图。欧拉图的性质：欧拉图可以分解成假设干个边不重的圈。欧拉图的性质：欧拉图可以分解成假设干个边不重的圈。 定理定理15.515.5欧拉图的断定欧拉图的断定 G G是非平凡的欧拉图当是非平凡的欧拉图当且仅当且仅当G G是连通的且为假设干个边不重的圈的并。是连通的且为假设干个边不重的圈的并。 中国的“一笔画的

5、问题 从图某一点出发，线可以相交但不能重合将图画完的问题。 可以看出在“一笔画的问题中，终点与始点重合的图对应着欧拉图，不重合的对应半欧拉图。例15.2P296v2e2v3e3v4e14v9e10v2e1v1e8v8e9v2nFleury算法算法n1任取任取v0V(G)，令，令P0=v0。n2设设Pi=v0e1v1e2.eivi曾经行遍，曾经行遍，那么按下面方法来从那么按下面方法来从E(G)-e1,e2,.,ei中选取中选取ei+1：n aei+1与与vi相关联；相关联；n b除非无别的边可供选择，否那么除非无别的边可供选择，否那么ei+1不应该为不应该为 G-e1,e2,.,ei中的桥。中的

6、桥。n3当当2不能再进展时，算法停顿，不能再进展时，算法停顿，得到的得到的Pn=v0e1v1e2.envn为为G中的一中的一条欧拉回路。条欧拉回路。桥：设eE(G)，假设p(G-e)p(G)， 那么称e为G中的桥。例15.2P296v2e2v3e3v4e14v9e10v2e1v1e8v8e9v2例15.2P296 利用欧拉图可以处理哥尼斯堡七桥问题：从某地出发，对每座跨河桥只走一次，而在遍历了七座桥之后，却又能回到原地。 由定理15.1无向欧拉图的断定定理可知该问题无解。 思索 如以下图所示，从一房间出发，问能否不反复地穿过每一道门，经过一切房间？15.2 哈密顿图 1859年，爱尔兰数学家威

7、廉哈密尔顿发明了一个旅游世界的游戏。将一个正十二面体的20个顶点分别标上世界上大城市的名字，要求玩游戏的人从某城市出发沿12面体的棱，经过每个城市恰一次，最后回到出发的那个城市。 哈密尔顿游戏是在左图中如何找出一个包含全部顶点的圈。 定义哈密顿通路和哈密顿回路定义哈密顿通路和哈密顿回路 经过图有向图或无向图每个顶点一次经过图有向图或无向图每个顶点一次且仅一次的通路称为哈密顿通路。且仅一次的通路称为哈密顿通路。 经过图每个结点一次且仅一次的回路初经过图每个结点一次且仅一次的回路初级回路称为哈密顿回路。级回路称为哈密顿回路。 定义哈密顿图和半哈密顿图定义哈密顿图和半哈密顿图 存在哈密顿回路的图称为

8、哈密顿图。存在哈密顿回路的图称为哈密顿图。 存在哈密顿通路但不存在哈密顿回路的图存在哈密顿通路但不存在哈密顿回路的图称为半哈密顿图。称为半哈密顿图。 平凡图是哈密顿图。平凡图是哈密顿图。 1234为哈密顿图5为半哈密顿图6既不是哈密顿图，又不是半哈密顿图。 1 1 2 2 3 3 4 4 5 5 6 6 到目前为止，还没有找到判别哈密顿图简单的充分必要条件。 下面引见哈密顿图和半哈密顿图的必要条件 定理15.6 设无向图G=是哈密顿图，V1是V的恣意非空子集，那么有p(G-V1)|V1|,其中p(G-V1)为G-V1的连通分支数。 推论 设无向图G=是半哈密顿图，V1是V的恣意非空子集，那么有

9、p(G-V1)|V1|+1。 留意： 1定理15.6和推论是必要条件。 2两定理可以证明一个图不是哈密尔顿图或半哈密顿图。 易见p(G-v1,v2)=3，|v1,v2|=2p(G-v1,v2)|v1,v2|不满足定理15.6，所以图G不是哈密顿图。 例如例如 GG-v1,v2 彼得松图彼得松图满足定理15.6，但不是哈密顿图。例如例如 下面给出哈密顿图和半哈密顿图的充分条件 定理15.7 设G=为n阶无向简单图，如G中恣意两个不相邻的顶点vi,vj，均有d(vi)+d(vj)n-1，那么G中存在哈密顿通路，即G为半哈密顿图。 推论 设G=为nn3阶无向简单图，如G中恣意两个不相邻的顶点vi,v

10、j，均有d(vi)+d(vj)n，那么G是哈密顿图。 阐明：该推论是充分条件但不是必要的。 例如： 该五边形是哈密顿图，但恣意两个不相邻的顶点度数之和为4，图形阶数为5。 例例 在某次国际会议的预备会中，共有在某次国际会议的预备会中，共有8 8人参与，他人参与，他们来自不同的国家。假设他们中任两个无共同言语的人们来自不同的国家。假设他们中任两个无共同言语的人与其他有共同言语的人数之和大于或等于与其他有共同言语的人数之和大于或等于8 8，问能否将这，问能否将这8 8个人排在圆桌旁，使其任何人都能与两边的人交谈。个人排在圆桌旁，使其任何人都能与两边的人交谈。 解：将这解：将这8 8个人看为平面上的

11、个人看为平面上的8 8个点，设为个点，设为v1,v2,v3,v4,v5,v6,v7,v8v1,v2,v3,v4,v5,v6,v7,v8。 假设假设vivi和和vjvj有共同言语，就在有共同言语，就在vivi和和vjvj之间连无向边之间连无向边vi,vjvi,vj。 这样得到一个这样得到一个8 8阶无向简单图阶无向简单图G G。 viviV V，d(vi)d(vi)为与为与vivi有共同言语的人数。有共同言语的人数。 由知条件可知，由知条件可知，vi,vjvi,vjV V且且i ij j，均有，均有d(vi)+d(vj)d(vi)+d(vj)8 8。 由定理由定理15.715.7的推论可知，的推

12、论可知，G G中存在哈密顿回路，中存在哈密顿回路， 设设C=vi1vi2 vi7vi8C=vi1vi2 vi7vi8为为G G中一条哈密顿回路，按这中一条哈密顿回路，按这条回路的顺序安排座次即可。条回路的顺序安排座次即可。 座位问题亚瑟王和他的骑士们n 亚瑟王一次召见他的p个骑士，知每一个骑士在骑士中的仇人不超越p/2-1个。证明：能让这些骑士围坐在圆桌旁，使每个人都不与他的仇人相邻。15.3 带权图及其运用 定义定义15.315.3带权图带权图 给定给定G=VG=EG G为为有向图或无向图，对有向图或无向图，对G G中恣意的边中恣意的边e=(vi,vj)(e=(vi,vj)(或或)，有一实数

13、，有一实数wijwij与之相与之相对应，称该实数对应，称该实数wijwij为边为边e e上的权，并将上的权，并将wijwij标注标注在边在边e e上，称上，称G G为带权图，此时将带权图为带权图，此时将带权图G G记为记为VW。 带权图运用的领域很广，典型运用有最短途带权图运用的领域很广，典型运用有最短途径无向图和关键途径有向图。径无向图和关键途径有向图。 最短途径最具有代表性的问题有： 中国邮递员问题欧拉图 货郎担问题游览商问题哈密顿图 中国邮递员问题中国邮递员问题 问题描画：一个邮递员送信，要走完他担任投递的全问题描画：一个邮递员送信，要走完他担任投递的全部街道，完成义务后回到邮局，应该按

14、照怎样的道路走，部街道，完成义务后回到邮局，应该按照怎样的道路走，所走的路程最短。所走的路程最短。 转化为图论问题：给定一个带权无向连通图，要求找转化为图论问题：给定一个带权无向连通图，要求找一个回路未必是简单的，过每边至少一次，并使回路一个回路未必是简单的，过每边至少一次，并使回路的总权最小。的总权最小。 问题的处理：问题的处理： 欧拉图法欧拉图法: :假设该邮递员担任的范围内，街道图为欧假设该邮递员担任的范围内，街道图为欧拉图，那么他就可以从邮局出发，走过每条街道一次，最拉图，那么他就可以从邮局出发，走过每条街道一次，最后回到邮局，这样他所走过的路程也就是最短路程。后回到邮局，这样他所走过

15、的路程也就是最短路程。 奇偶点图上作业法奇偶点图上作业法: :假设该邮递员担任的范围内，街假设该邮递员担任的范围内，街道图有奇度点，那么必需在某些街道上反复走一次或多次。道图有奇度点，那么必需在某些街道上反复走一次或多次。 假设在某条道路中边vi,vj上反复走了几次，我们在图中vi,vj之间添加几条边，令所添加边的权与原来的权相等，并把新添加的边，称为反复边。 于是这条道路就是相应新图中的欧拉回路。 由于在任何一个图中，奇度点个数为偶数，所以假设图中有奇度点，就可以把它们配成对。又由于图是连通的，故每一对奇度点之间必有通路，把权和最小的通路上的一切边作为反复边加到图中去，可见新图中无奇度点。

16、我们把添加反复边而使新图不含奇度点的方案称为可行方案，称使反复边的权和最小的可行方案为最优方案。 这样一来，原来的问题就可以转化为在一个有奇度点的图中，要求添加一些反复边，使新图不含奇度点，即为一个欧拉图，并且所加反复边的权和最小。 如今的问题是在确定一个可行方案之后，怎样判别这个方案能否为最优方案？ 图中有四个奇度点，v2,v4,v6,v8，将它们分成两对，比如说v2与v4为一对，v6与v8为一对。 衔接的v2与v4、v6与v8的通路有好几条，但要取权和最小的一条。 这个图中没有奇度点，故它是欧拉图。对于这个可行方案，反复边的权和为17。 在最优方案中，图中每个圈的反复边的权和不大于该圈权和

17、的一半。 对于上述的可行方案，在圈v1v2v9v6v7v8v1中，圈的权和为24，但反复边的权和为13，大于该圈权和的一半，因此需求进展调整。 这样可以得到另一可行方案： 这一方案中，反复边的权和为15，并且图中每个圈的反复边的权和不大于该圈权和的一半。课后练习：求以下图所示的中国邮递员问题。课后练习：求以下图所示的中国邮递员问题。 货郎担问题游览商问题货郎担问题游览商问题 问题描画如下：设有问题描画如下：设有n n个城市，城市之间均个城市，城市之间均有道路，道路的长度均大于等于有道路，道路的长度均大于等于0 0，能够为，能够为对应关联的城市之间无交通线。今有一个游对应关联的城市之间无交通线。

18、今有一个游览商从某个城市出发，要经过其它览商从某个城市出发，要经过其它n-1n-1个城市恰个城市恰一次，最后回到出发城市，问如何走使得经过的一次，最后回到出发城市，问如何走使得经过的总路程最短？总路程最短？ 转化为图论问题：以城市为结点，两城市转化为图论问题：以城市为结点，两城市之间的路为边，路程长度为边上的权，那么问题之间的路为边，路程长度为边上的权，那么问题转化为在带权无向图转化为在带权无向图G=G=中找一个权和最中找一个权和最小的哈密尔顿回路。小的哈密尔顿回路。 解：求哈密顿回路可以从任何顶点出发。下面从解：求哈密顿回路可以从任何顶点出发。下面从a a点点出发，并思索顺时针与逆时针顺序不同的哈密顿回路。出发，并思索顺时针与逆时针顺序不同的哈密顿回路。C1=abcda C1=abcda 权和为权和为8 8C2=abdca C2=a