《离散数学ch15》PPT课件.ppt

* 解 C1= a b c d a, W(C1)=10 C2= a b d c a, W(C2)=11 C3= a c b d a, W(C3)=9 可见C3 (见图中(2)) 是最短的，其权为9. 例6 求图中(1) 所示带权图K4中最短哈密顿回路. (1) (2) * 第十五章 习题课 主要内容 欧拉通路、欧拉回路、欧拉图、半欧拉图及其判别法 哈密顿通路、哈密顿回路、哈密顿图、半哈密顿图 带权图、货郎担问题 基本要求 深刻理解欧拉图、半欧拉图的定义及判别定理 深刻理解哈密顿图、半哈密顿图的定义. 会用哈密顿图的必要条件判断某些图不是哈密顿图. 会用充分条件判断某些图是哈密顿图. 要特别注意的是，不能将必要条件当作充分条件，也不要将充分条件当必要条件. * 1. 设G为n（n?2）阶无向欧拉图，证明G中无桥(见例1思考题) 方法二：反证法. 利用欧拉图无奇度顶点及握手定理的推论. 否则，设e=(u,v)为G中桥，则G?e产生两个连通分支G1, G2，不妨设u在G1中，v在G2中. 由于从G中删除e时，只改变u,v 的度数(各减1)，因而G1与G2中均只含一个奇度顶点，这与握手定理推论矛盾. 练习1 方法一：直接证明法. 命题 (*)：设C为任意简单回路，e为C上任意一条边，则C?e连通. 证 设C为G中一条欧拉回路，任意的e?E(C)，可知C?e是G?e的子图，由(?)知 C?e 连通，所以e不为桥. * 2. 证明下图不是哈密顿图. (破坏必要条件) 方法一. 利用定理15.6， 取 V1 = {a, c, e, h, j, l}，则 p(G?V1) = 7 |V1| = 6 练习 2 方法二. G为二部图，互补顶点子集 V1 = {a, c, e, h, j, l}, V2 = {b, d, f, g, i, k, m}， |V1| = 6 ? 7 = |V2|. 方法三. 利用可能出现在哈密顿回路上的边至少有n(n为阶数) 条——这也是哈密顿图的一个必要条件，记为（?）. 此图中，n = 13，m = 21. 由于h, l, j 均为4度顶点，a, c, e为3 度顶点，且它们关联边互不相同. 而在哈密顿回路上， 每个顶点准确地关联两条边，于是可能用的边至多有21?(3?2+3?1) = 12. 这达不到（?）的要求. * 3．某次国际会议8人参加，已知每人至少与其余7人中的4人有共同语言，问服务员能否将他们安排在同一张圆桌就座，使得每个人都与两边的人交谈？ 解 图是描述事物之间关系的最好的手段之一. 做无向图G=V,E, 其中 V={v| v为与会者}， E={(u,v) | u,v?V且u与v有共同语言，且u ? v}. 易知G为简单图且?v?V, d(v)?4，于是，?u,v?V, 有d(u)+d(v) ? 8，由定理15.7 的推论可知G为哈密顿图. 服务员在G中找一条哈密顿回路C，按C中相邻关系安排座位即可. 练习 3 由本题想到的：哈密顿回图的实质是能将图中所有的顶点排在同一个圈中. * 4. 距离(公里) 如图所示. 他如何走行程最短？ 练习 4 最短的路为ABCDA，距离为36公里，其余两条各为多少？ * * * * * * * * * * * * * * * * * * * * * * * * * 第十五章 欧拉图与哈密顿图 主要内容 欧拉图 哈密顿图 带权图与货郎担问题 * 哥尼斯堡七桥 18世纪初普鲁士的哥尼斯堡，有一条河穿过，河上有两个小岛，有七座桥把两个岛与河岸联系起来（如左图）。有个人提出一个问题：一个步行者怎样才能不重复、不遗漏地一次走完七座桥? 最后回到出发点后来 大数学家欧拉把它转化成一个几何问题（如右图）——一笔画问题。他不仅解决了此问题，且给出了连通图可以一笔画的重要条件是它们是连通的，且奇顶点(通过此点弧的条数是奇数)的个数为0或2. * 15.1 欧拉图 历史背景：哥尼斯堡七桥问题与欧拉图 * 欧拉图定义 定义15.1 (1) 欧拉通路——经过图中每条边一次且仅一次行遍所有顶点的通路. (2) 欧拉回路——经过图中每条边一次且仅一次行遍所有顶点的回路. (3) 欧拉图——具有欧拉回路的图. (4) 半欧拉图——具有欧拉通路而无欧拉回路的图. 几点说明： 规定平凡图为欧拉图. 欧拉通路是简单通路，欧拉回路是简单回路. 环不影响图的欧拉性. * 上图中，(1) ,