1、1第十五章 欧拉图与哈密顿图主要内容l 欧拉图l 哈密顿图l 带权图与货郎担问题2哥尼斯堡七桥18世纪初普鲁士的哥尼斯堡，有一条河穿过，河上有两个小岛，有七座桥把两个岛与河岸联系起来（如左图）。有个人提出一个问题：一个步行者怎样才能不重复、不遗漏地一次走完七座桥 ? 最后回到出发点后来大数学家欧拉把它转化成一个几何问题（如右图） 一笔画问题。他不仅解决了此问题，且给出了连通图可以一笔画的重要条件是它们是连通的，且奇顶点 (通过此点弧的条数是奇数 )的个数为 0或 2.315.1 欧拉图历史背景：哥尼斯堡七桥问题与欧拉图4欧拉图定义定义 15.1 (1) 欧拉通路 经过图中每条边一次且仅一次行遍
2、所有顶点的通路 . (2) 欧拉回 路 经过图中每条边一次且仅一次行遍所有顶点的回路 .(3) 欧拉图 具有欧拉回路的图 .(4) 半欧拉图 具有欧拉通路而无欧拉回路的图 .几点说明：规定平凡图为欧拉图 .欧拉通路是简单通路，欧拉回路是简单回路 .环不影响图的欧拉性 .5上图中， (1) ,(4) 为欧拉图， (2),(5)为半欧拉图， (3),(6)既不是欧拉图，也不是半欧拉图 . 在 (3),(6)中各至少加几条边才能成为欧拉图？ 欧拉图实例6无向欧拉图的判别法定理 15.1 无向图 G是欧拉图当且仅当 G连通且无奇度数顶点 .证 若 G 为平凡图无问题 . 下设 G为 n 阶 m 条边的
3、无向图 .必要性 设 C 为 G 中一条欧拉回路 .(1) G 连通显然 .(2) viV(G)， vi在 C上每出现一次获 2度，所以 vi为偶度顶点 . 由 vi 的任意性，结论为真 . 充分性 对边数 m做归纳法（第二数学归纳法） .(1) m=1时， G为一个环，则 G为欧拉图 .(2) 设 mk（ k1）时结论为真， m=k+1时如下证明：7PLAY从以上证明不难看出：欧拉图是若干个边不重的圈之并，见示意图 3. 8欧拉图的判别法定理 15.2 无向图 G是半欧拉图当且仅当 G 连通且恰有两个奇度顶点 .证 必要性简单 . 充分性（利用定理 15.1）设 u,v为 G 中的两个奇度顶
4、点，令G =G(u,v)则 G 连通且无奇度顶点，由定理 15.1知 G 为欧拉图，因而存在欧拉回路 C，令=C(u,v)则 为 G 中欧拉通路 .实例9无欧拉通路 欧拉图 欧拉图有欧拉通路非欧拉图有欧拉通路非欧拉图无欧拉通路10有向欧拉图的判别法定理 15.3 有向图 D是欧拉图当且仅当 D是强连通的且每个顶点的入度都等于出度 .本定理的证明类似于定理 15.1. 定理 15.4 有向图 D是半欧拉图当且仅当 D是单向连通的，且D中恰有两个奇度顶点，其中一个的入度比出度大 1，另一个的出度比入度大 1，而其余顶点的入度都等于出度 . 本定理的证明类似于定理 15.1. 定理 15.5 G是非平凡的欧拉图当且仅当 G是连通的且为若干个边不重的圈之并 . 可用归纳法证定理 15.5.
