第四部分（图论）.ppt

Discrete Math. , huang liujia CHAPTER Fifteen Discrete Math. , huang liujia * Discrete Math. , huang liujia * 离散数学 Discrete Mathematics * * 第十二章 特殊图 §12.1 欧拉图 §12.2 哈密顿图 §12.3 带权图与货郎量担问题 * * 12.1 欧拉图 哥尼斯堡七桥 * * 欧拉图 定义12.1 欧拉通路:经过图中所有顶点且每条边恰好经过一次的通路 欧拉回路:经过图中所有顶点且每条边恰好经过一次的回路 欧拉图:有欧拉回路的图 半欧拉图:有欧拉通路而没有欧拉回路的图 说明： 上述定义对无向图和有向图都适用 规定平凡图为欧拉图 欧拉通路是简单通路, 欧拉回路是简单回路 环不影响图的欧拉性 欧拉图可用一笔画完图形. * * 例 (1), (4)为欧拉图; (2), (5)为半欧拉图; (3), (6)既不是欧拉图, 也不是半欧拉图. 在(3), (6)中各至少加几条边才能成为欧拉图? * * 实例 无欧拉通路 欧拉图 欧拉图 有欧拉通路 非欧拉图 有欧拉通路 非欧拉图 无欧拉通路 * * 欧拉图判别定理 定理12.1 无向图G为欧拉图当且仅当G连通且无奇度顶点. 定理12.2 无向图G是半欧拉图当且仅当G连通且恰有两个奇度顶点. 定理12.3 有向图D是欧拉图当且仅当D连通且每个顶点的入度都等于出度. 定理12.4有向图D具有欧拉通路当且仅当D连通且恰有两个奇度顶点, 其中一个入度比出度大1, 另一个出度比入度大1, 其余顶点的入度等于出度. 定理12.5 G是非平凡欧拉图当且仅当G连通且为若干个不重的圈的并. * * 例子 例12.1 设G是非平凡的且非圈的欧拉图,证明: (1) ?(G)?2; (2) 对于G中任意两个不同的顶点u,v都存在简单回路C含u和v. 证(1)由定理12.5可知,?e?E(G), 存在圈C, e在C中,因而 p(G-e)= p(G),故e不是桥. 由e的任意性可知?(G)?2. (2) ?u,v ?V(G), u?v, 由G的连通性可知, u和v之间必存在路径?1. 设G ‘= G –E(?1), 则G ‘中u与v 必连通. 否则u与v处在G ‘的不同连通分支中, 这说明?1上存在G中的桥. 这与(1)相矛盾.于是在G’中 u和v之间必存在路径?2. 而显然?1 和?2边不重, 故存在简单回路C= ?1 ??2含u和v. * * 实例 欧拉图 无欧拉通路 无欧拉通路 有欧拉通路 无欧拉回路 无欧拉通路 有欧拉通路 无欧拉回路 * * Fleury算法 算法： (1)任取v0?V(G)．令P0＝v0。 (2)设Pi＝v0 v1 …vi已选定，则从E(G)-E(Pi)中选一条边ei+1 使得ei+1与vi 相关联, 且非必要时, ei+1 不要选G-E(Pi)的桥. (3)反复执行(2)，直至每边e?E(G))皆入选为止。 例12.2 P298 * * 周游世界问题(W.Hamilton, 1859年) 12.2 哈密顿图 * * 哈密顿回路与哈密顿通路 定义12.2 哈密顿通路: 经过图中所有顶点一次且仅一次的通路. 哈密顿回路: 经过图中所有顶点一次且仅一次的回路. 哈密顿图: 具有哈密顿回路的图. 半哈密顿图: 具有哈密顿通路但没有哈密顿回路的图. 说明： 哈密顿通路是初级通路 哈密顿回路是初级回路 有哈密顿通路不一定有哈密顿回路 环与平行边不影响图的哈密顿性 * * 哈密顿图的必要条件 定理12.6 设无向图G=V,E是哈密顿图, 则??V1?V,均有 p(G?V1)?|V1|. 证 设C为G中一条哈密顿回路, 有p(C?V1) ? |V1|. 又因为C?G为生成回路, 故 p(G?V1) ? p(C?V1) ? |V1|. 注:本定理的条件是哈密顿图的必要条件，而不是充分条件。利用该定理可以证明一个图不是哈密顿图. 推论设无向图G=V,E是半哈密顿图,则??V1?V,均有 p(G?V1)?|V1|+1. 分析:考虑通路的始终点 * * 例子 右图彼得松图满足定理12.6的条件，但可以验证它不是哈密顿图。 又如，在左图中，令S=?a,b?，则p(G-S)=3，|S|=2，故p(G–S)≤|S|不成立。所以该图不是哈密顿图。 例 实际上由定理可知,当s?r+1时Kr,s不是哈密顿图. 当r?2时, Kr,r是哈密顿图, 而Kr,r+1是半哈密顿图.