第四章欧拉图与哈密尔顿图 主要内容 一、 欧拉图与中国邮路问题 二、哈密尔顿图 三、度极大非哈密尔顿图与TSP问题 四、超哈密尔顿图问题 教学时数 安排8学时讲授本章内容
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 1 第四章 欧拉图与哈密尔顿图 主要内容 一、欧拉图与中国邮路问题 二、哈密尔顿图 三、度极大非哈密尔顿图与TSP问题 教学时数 安排8学时讲授本章内容 四、超哈密尔顿图问题
本次课主要内容 欧拉图与中国邮路问题 (一)、欧拉图及其性质 (二)、Fleury算法 (三)、中国邮路问题
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 2 本次课主要内容 (一)、欧拉图及其性质 (二)、Fleury算法 (三)、中国邮路问题 欧拉图与中国邮路问题
(一)、欧拉图及其性质 1、欧拉图的概念 (1)、问题背景。-欧拉与哥尼斯堡七桥问题 问题：对于图G,它在什么条件下满足从某点出发， 经过每条边一次且仅一次，可以回到出发点？
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 3 1、欧拉图的概念 (一)、欧拉图及其性质 (1)、问题背景-欧拉与哥尼斯堡七桥问题 问题：对于图G，它在什么条件下满足从某点出发， 经过每条边一次且仅一次，可以回到出发点？
哥尼斯堡城（位于德国北部），在欧拉的生活与图论历 史中扮演着非常重要角色。因为它，产生了著名的欧拉 图定理，因为它，产生了图论。 注：一笔画一中国古老的民间游戏 要求：对于一个图G,笔不离纸，一笔画成 (2)、欧拉图概念 定义1对于连通图G,如果G中存在经过每条边的闭 迹，则称G为欧拉图，简称G为E图。欧拉闭迹又称为 欧拉环游，或欧拉回路。 欧拉图 非欧拉图 非欧拉图 有欧拉迹 无欧拉迹
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 4 哥尼斯堡城(位于德国北部), 在欧拉的生活与图论历 史中扮演着非常重要角色。因为它，产生了著名的欧拉 图定理，因为它，产生了图论。 注：一笔画-中国古老的民间游戏 要求：对于一个图G, 笔不离纸, 一笔画成. (2)、欧拉图概念 定义1 对于连通图G，如果G中存在经过每条边的闭 迹，则称G为欧拉图，简称G为E图。欧拉闭迹又称为 欧拉环游，或欧拉回路。 欧拉图 4 1 3 2 4 1 3 2 非欧拉图 有欧拉迹 非欧拉图 无欧拉迹 1 2 3 4
2、欧拉图的性质 定理1下列陈述对于非平凡连通图G是等价的： (1)G是欧拉图； (2)G的顶点度数为偶数； (③)G的边集合能划分为圈。 证明：(1)→(2) 由(1)，设C是欧拉图G的任一欧拉环游，v是G中任 意顶点，v在环游中每出现一次，意味在G中有两条不 同边与v关联，所以，在G中与v关联的边数为偶数，即 v的度数为偶数，由v的任意性，即证明(2)。 (2)→(3) 由于G是连通非平凡的且每个顶点度数为偶数，所以 G中至少存在圈C1,从G中去掉C中的边，得到G的生成
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 5 2、欧拉图的性质 定理1 下列陈述对于非平凡连通图G是等价的： (1) G是欧拉图； (2) G的顶点度数为偶数； (3) G的边集合能划分为圈。 证明: (1)→(2) 由(1)，设 C是欧拉图G的任一欧拉环游，v是G中任 意顶点，v在环游中每出现一次，意味在G中有两条不 同边与v关联，所以，在G中与v关联的边数为偶数，即 v的度数为偶数，由v的任意性，即证明(2)。 (2)→(3) 由于G是连通非平凡的且每个顶点度数为偶数，所以 G中至少存在圈C1 ,从G中去掉C1中的边，得到G的生成