1、第十五章 欧拉图与哈密顿图主要内容l 欧拉图l 哈密顿图l 带权图与货郎担问题1第十五章 欧拉图与哈密顿图预备知识l 无向图 G = l d(v), d+(v), d(v)l 奇度顶点与偶度顶点l 连通，通路，回路2 瑞士数学家，最多产的数学家 1100书籍论文 全集 75卷 13个孩子 最后 17年失明ADBCQuestion: 如何将左边图所示的七桥问题转换为点和边来描述 ? 一个游人怎样才能不重复地一次走遍七座桥，最后又回到出发点呢？ Link to the videoLeonhard Euler:17071783历史背景3下面哪些图形可以一笔画，哪些图形不能一笔画？试一试：(1) (2
2、) (3)(4) (5) (6)4（ 2） （ 2）（ 2）（ 2）（ 3） （ 3）（ 4）（ 4）（ 2）（ 2）（ 3）（ 2） （ 3）（ 2）（ 3） （ 4）（ 3）（ 1）（ 1）（ 1）（ 3）（ 4）（ 2）（ 2） （ 2）偶点（ 1）（ 3）（ 2） （ 2）奇点5中途点特征： 笔沿着某条边进去后，必定沿另一条边出去，于是知道与中途点为端点的边必定是成对出现的，这样中途点必定是偶点。进去出来进去出来p如果起点和终点重合，则与他们相连的边是偶数条，所以也是偶点p起点和终点不重合，与他们相连的边奇数条，则是都是奇点“一 笔画 ”图形特征：一个图形可以 “一笔画 ”则奇点的个数
3、是 0个或 2个6欧拉图定义定义 15.1 (1) 欧拉通路 经过图中每条边一次且仅一次行遍所有顶点的通路 . (2) 欧拉回 路 经过图中每条边一次且仅一次行遍所有顶点的回路 .(3) 欧拉图 具有欧拉回路的图 .(4) 半欧拉图 具有欧拉通路而无欧拉回路的图 .几点说明：规定平凡图为欧拉图 .欧拉通路是生成的简单通路，欧拉回路是生成的简单回路 .环不影响图的欧拉性 .7上图中， (1) ,(4) 为欧拉图， (2),(5)为半欧拉图， (3),(6)既不是欧拉图，也不是半欧拉图 . 在 (3),(6)中各至少加几条边才能成为欧拉图？ 欧拉图实例8无向欧拉图的判别法定理 15.1 无向图 G是欧拉图当且仅当 G连通且无奇度数顶点 .证 若 G 为平凡图无问题 . 下设 G为 n 阶 m 条边的无向图 .必要性 设 C 为 G 中一条欧拉回路 .(1) G 连通显然 .(2) viV(G)， vi在 C上每出现一次获 2度，所以 vi为偶度顶点. 由 vi 的任意性，结论为真 . 充分性 对边数 m做归纳法（第二数学归纳法） .(1) m=1时， G为一个环，则 G为欧拉图 .(2) 设 mk（ k1）时结论为真， m=k+1时如下证明：9PLAY从以上证明不难看出：欧拉图是若干个边不重的圈之并，见示意图 3. 10
