离散数学第23讲.pptVIP

信息学院计算机应用技术系 授课教师：胡静 办公地点：信息楼805 电子邮箱：ise_huj@ujn.cn 离散数学 第23讲 回顾上节课内容： 图论中的基本概念 握手定理及推论 完全图及其特征 通路及回路 离散数学 第23讲 本讲基本知识点： 1、欧拉图 欧拉图的定义 欧拉图的判断 2、哈密尔顿图 哈密尔顿图的定义 哈密尔顿图判断的充分条件 3、树 树的定义 最小生成树 第十五章 欧拉图与哈密尔顿图 第十五章 欧拉图与哈密尔顿图 第十五章 欧拉图与哈密尔顿图 第十五章 欧拉图与哈密尔顿图 例15.1(蚂蚁比赛问题) 一笔画问题的判断 对于上图，有图(a)能一笔画并且能回到出发点的， 图(b)能一笔画但不能回到出发点的。 求欧拉回路的Fleury算法 任取v0∈V，令P0＝v0； 设P0＝v0e1v1e2…eivi，按下面的方法从E-{e1,e2,…,ei}中选取ei+1： ei+1与vi相关联； 除非无别的边可选取，否则ei+1不应该为G＝G-{e1,e2,…,ei}中的桥； 当2）不能再进行时，算法结束。 例15.2： Fleury算法应用 　在右图所示的欧拉图 中，求从v1出发的欧拉回 路。 第十五章 欧拉图与哈密尔顿图 答案：图a和图d是欧拉图；图b和图e不是欧拉图，但存在欧拉通路；图c和图f不存在欧拉通路。 哈密尔顿图的起源： ------周游世界问题 第十五章 欧拉图与哈密尔顿图 第十五章 欧拉图与哈密尔顿图 利用哈密尔顿图解决实际问题典型例题1：某地有5个风景点，若每个风景点均有两条道路与其他点相通。问游人可否经过每个风景点恰好一次而游完这5处？ 解　将5个风景点看成是有5个结点的无向图，两风景点间的道路看成是无向图的边，因为每处均有两条道路与其他结点相通，故每个结点的度数均为2，从而任意两个不相邻的结点的度数之和等于4，正好为总结点数减1。故此图中存在一条哈密尔顿通路，因此本题有解。 第十五章 欧拉图与哈密顿图 第十五章 欧拉图与哈密尔顿图 第十五章 欧拉图与哈密尔顿图 解：设无向图G=V,E,其中 V={a,b,c,d,e,f,g}, E={(u,v)|u,v ∈V，且u和v有共同语言}。 如右图为连通图，将七人排座围圆桌而坐，使得每个人都能与两边的交谈。即在右图中寻找一条哈密尔顿回路， 第十六章 树 第十六章 树 第十六章 树 第十六章 树 第十六章 树 第十六章 树 第十六章 树 第十六章 树 第十六章 树 离散数学 第23讲 本讲小结 1、掌握欧拉图的定义 2、掌握判断欧拉图的方法 3、哈密尔顿图的定义 4、掌握判断哈密尔顿图的方法（充分条件） 5、掌握树的定义 6、最小生成树及其算法 作业：P304第9题 定义16.5 设无向连通带权图G=V,E,W,T是G的一棵生成树，T的各边权之和称为T的权，记作W(T).G的所有生成树中权最小的生成树称为G的最小生成树。 Kruskal算法 —— 一种求最小生成树的算法 设n阶无向连通带权图G=V,E,W有m条边,不妨设G中无环(否则可先删去)，算法为： (1) 将m条边按权从小到大顺序排列，设为e1,e2, … ,em。 (2) 取e1在T中，然后依次检查e2, … ,em ，若ej (j=2,3, …,m)与T中的边不能构成回路，则取ej在T中，否则放弃ej，考虑下一条边，直至jm。 (3) 算法停止时得到的T为G的最小生成树。 例：用Kruskal算法求下图的最小生成树。 2 1 2 1 3 4 3 1 5 1 1 3 1 。 。 。 。 。 OK! 。 。 。 。 。 。 。 2 1 4 5 1 5 5 4 5 3 3 2 练习：求下图的最小生成树。 * * 第 四 部 分 第23讲 18世纪，在俄国哥尼斯堡城（Konnigsberg）（今俄罗斯加里宁格勒）的普莱格尔（Pregel）河上有7座桥．河中间有两座岛，岛与河岸之间架有六座桥，另一座桥则连接着两个岛．星期天散步已成为当地居民的一种习惯，但试图走过这样的七座桥，而且每桥只走过一次却从来没有成功过．直至引起瑞士数学家欧拉(Leonhard Euler，1707—1783)注意之前，没有人能够解决这个问题． 陆地 岛屿 岛屿 陆地 哥尼斯堡七桥问题 如何不重复地走完七桥后回到起点？ 。 。 。 。 A B C D 15.1 欧拉图 定义15.1 通过图(无向图或有向图)中所有边一次且仅一次行遍所有