离散数学(第13章)陈瑜.pptVIP

计算机科学与工程学院 陈瑜 Email：yuchen@scu.edu.cn* 第13章 欧拉图与哈密顿图 主要内容(1) Euler图及其应用 1)欧拉道路（回路）的定义 2)如何判别欧拉图 3)一个图含有欧拉道路的条件 4)连通有向图G中含有有向欧拉道路和回路的充要条件 5)Fleury算法 6)Euler图的应用(中国邮递员问题算法) 主要内容(2) 哈密顿图及其应用： 哈密顿道路（圈 ）的定义 连通图G是哈密顿图的必要条件 连通图G是哈密顿图的充分条件 连通图G是哈密顿图的充要条件 哈密顿图的应用(推销商问题) 哥尼斯堡七桥问题 Euler图 Euler图 Euler图 例13.1 图a是欧拉图；图b不是欧拉图，但存在欧拉道路；图c不存在欧拉道路。 “?” 设连通图G的结点的度数都是偶数，则G必含有简单回路（可用归纳法证明） 。 设C是一条包含G中边最多的简单回路： ⑴ 若C已经包含G中所有的边，则C就是Euler回路，结论成立。 ⑵ 若C不能包含G中所有的边，则删边子图 G-E（C）仍然无奇数度结点。 “?” 设连通图G的结点的度数都是偶数，则G必含有简单回路（可用归纳法证明） 。 设C是一条包含G中边最多的简单回路： ⑴ 若C已经包含G中所有的边，则C就是Euler回路，结论成立。 ⑵ 若C不能包含G中所有的边，则删边子图 G-E（C）仍然无奇数度结点。 “?” 设连通图G的结点的度数都是偶数，则G必含有简单回路（可用归纳法证明） 。 设C是一条包含G中边最多的简单回路： ⑴ 若C已经包含G中所有的边，则C就是Euler回路，结论成立。 ⑵ 若C不能包含G中所有的边，则删边子图 G-E（C）仍然无奇数度结点。 “?” 设连通图G的结点的度数都是偶数，则G必含有简单回路（可用归纳法证明） 。 设C是一条包含G中边最多的简单回路： ⑴ 若C已经包含G中所有的边，则C就是Euler回路，结论成立。 ⑵ 若C不能包含G中所有的边，则删边子图 G-E（C）仍然无奇数度结点。 这样，就可以构造出一条由C和C′组成的G的回路，其包含的边数比C多，与假设矛盾。因此，C必是Euler回路，结论成立。 证明：“?” 设G具有一条Euler通路L，则在L中除起点和终点外，其余每个结点都与偶数条边相关联，所以，G中仅有零个（Euler回路）或者两个奇数度结点。 “?” ： ⑴若 G没有奇度数结点，则结论显然成立； ⑵若G有两个奇度数结点u和v，则G+uv是Euler图，从而存在Euler回路C。从C中去掉边uv，则得到一条简单道路L（起点u和终点v），且包含了G的全部边，即L是一条Euler道路。 注意：若有两个奇度数结点，则它们是G中每条欧拉通路的端点。 证明：“?” 设G具有一条Euler通路L，则在L中除起点和终点外，其余每个结点都与偶数条边相关联，所以，G中仅有零个（Euler回路）或者两个奇数度结点。 “?” ： ⑴若 G没有奇度数结点，则结论显然成立； ⑵若G有两个奇度数结点u和v，则G+uv是Euler图，从而存在Euler回路C。从C中去掉边uv，则得到一条简单道路L（起点u和终点v），且包含了G的全部边，即L是一条Euler道路。 注意：若有两个奇度数结点，则它们是G中每条欧拉通路的端点。 证明：“?” 设G具有一条Euler通路L，则在L中除起点和终点外，其余每个结点都与偶数条边相关联，所以，G中仅有零个（Euler回路）或者两个奇数度结点。 “?” ： ⑴若 G没有奇度数结点，则结论显然成立； ⑵若G有两个奇度数结点u和v，则G+uv是Euler图，从而存在Euler回路C。从C中去掉边uv，则得到一条简单道路L（起点u和终点v），且包含了G的全部边，即L是一条Euler道路。 注意：若有两个奇度数结点，则它们是G中每条欧拉通路的端点。 证明：“?” 设G具有一条Euler通路L，则在L中除起点和终点外，其余每个结点都与偶数条边相关联，所以，G中仅有零个（Euler回路）或者两个奇数度结点。 “?” ： ⑴若 G没有奇度数结点，则结论显然成立； ⑵若G有两个奇度数结点u和v，则G+uv是Euler图，从而存在Euler回路C。从C中去掉边uv，则得到一条简单道路L（起点u和终点v），且包含了G的全部边，即L是一条Euler道路。 注意：若有两个奇度数结点，则它们是G中每条欧拉通路的端点。 例13.2 例13.2 有向图的欧拉道路、欧拉图 有向图的欧拉道路、欧拉图 有向图的欧拉道路、欧