离散数学(第13章)陈瑜

1、陈瑜陈瑜Email：2022年年7月月5日星期二日星期二 第第1313章章 欧拉图与哈密顿图欧拉图与哈密顿图7/5/2022计算机学院计算机学院2/98/98主要内容主要内容(1)EulerEuler图及其应用图及其应用 1)1)欧拉道路（回路）的定义欧拉道路（回路）的定义 2)2)如何判别欧拉图如何判别欧拉图 3)3)一个图含有欧拉道路的条件一个图含有欧拉道路的条件 4)4)连通有向图连通有向图G G中含有有向欧拉道路和回路的中含有有向欧拉道路和回路的充要条件充要条件 5)Fleury5)Fleury算法算法 6)Euler6)Euler图的应用图的应用( (中国邮递员问题算法中国邮递员问题

2、算法) )7/5/2022计算机学院计算机学院3/98/98主要内容主要内容(2)哈密顿图及其应用：哈密顿图及其应用：哈密顿道路（圈哈密顿道路（圈 ）的）的定义定义连通图连通图G G是哈密顿图的是哈密顿图的必要条件必要条件连通图连通图G G是哈密顿图的是哈密顿图的充分条件充分条件连通图连通图G G是哈密顿图的是哈密顿图的充要条件充要条件 哈密顿图的应用哈密顿图的应用( (推销商问题推销商问题) )7/5/2022计算机学院计算机学院4/98/98哥尼斯堡七桥问题哥尼斯堡七桥问题 哥尼斯堡城市有一条横贯全城的普雷格尔哥尼斯堡城市有一条横贯全城的普雷格尔(Pregel)(Pregel)河，城的各部

3、分用七座桥联接，每逢假日，城中居民进河，城的各部分用七座桥联接，每逢假日，城中居民进行环城逛游，这样就产生了一个行环城逛游，这样就产生了一个问题：问题：能不能设计一次能不能设计一次“遍游遍游”，使得从某地出发对每座跨河桥只走一次，而，使得从某地出发对每座跨河桥只走一次，而在遍历了七桥之后却又能回到原地？在遍历了七桥之后却又能回到原地？ A Ab b2 2B BD DC Cb b4 4b b1 1b b3 3b b5 5b b7 7b b6 67/5/2022计算机学院计算机学院5/98/98EulerEuler图图n定义定义13.113.1设设G G是一个无孤立结点的图，包含是一个无孤立结点的

4、图，包含G G的的每条边每条边的的简单道路简单道路（回路回路）称为该图的一条）称为该图的一条欧拉道路欧拉道路（回路回路）。）。具有欧拉回路具有欧拉回路的图称为的图称为欧欧拉图拉图。规定平凡图为欧拉图。规定平凡图为欧拉图。 显然，每个欧拉图必然是连通图。显然，每个欧拉图必然是连通图。 因此，一条欧拉道路（回路）是经过图中每因此，一条欧拉道路（回路）是经过图中每边一次且仅一次的道路（回路）。边一次且仅一次的道路（回路）。为什么？为什么？无重复边复习：若道路中的所有边复习：若道路中的所有边e1，e2，ek（有向边）（有向边）互不相同，则称此道路为互不相同，则称此道路为简单道路简单道路；闭的简单道路；

5、闭的简单道路称为称为回路回路。7/5/2022计算机学院计算机学院6/98/98EulerEuler图图n定义定义13.113.1设设G G是一个无孤立结点的图，包含是一个无孤立结点的图，包含G G的每条边的简单道路（回路）称为该图的一条的每条边的简单道路（回路）称为该图的一条欧拉道路（回路）。具有欧拉回路的图称为欧欧拉道路（回路）。具有欧拉回路的图称为欧拉图。拉图。规定规定平凡图为欧拉图平凡图为欧拉图。 显然，每个显然，每个欧拉图欧拉图必然是连通图。必然是连通图。 因此，一条欧拉道路（回路）是经过图中每因此，一条欧拉道路（回路）是经过图中每边一次且仅一次的道路（回路）。边一次且仅一次的道路（

6、回路）。为什么？为什么？7/5/2022计算机学院计算机学院7/98/98EulerEuler图图n定义定义13.113.1设设G G是一个无孤立结点的图，包含是一个无孤立结点的图，包含G G的每条边的简单道路（回路）称为该图的一条的每条边的简单道路（回路）称为该图的一条欧拉道路（回路）。具有欧拉回路的图称为欧欧拉道路（回路）。具有欧拉回路的图称为欧拉图。拉图。规定平凡图为欧拉图。规定平凡图为欧拉图。 显然，每个欧拉图必然是连通图。显然，每个欧拉图必然是连通图。 因此，一条因此，一条欧拉道路欧拉道路（回路回路）是经过图中）是经过图中每每边一次且仅一次边一次且仅一次的道路（的道路（回路回路）。）

7、。为什么？为什么？7/5/2022计算机学院计算机学院8/98/98例例13.113.1v v5 5v v1 1v v2 2v v3 3v v4 4a)a)v v5 5v v1 1v v2 2v v3 3v v4 4b)b)v v4 4v v1 1v v2 2v v3 3c)c) 图图a a是欧拉图；图是欧拉图；图b b不是欧拉图，但存在欧拉道不是欧拉图，但存在欧拉道路；图路；图c c不存在欧拉道路。不存在欧拉道路。7/5/2022计算机学院计算机学院9/98/98n定理定理13.1 13.1 无向连通图无向连通图G GVE是欧拉图当是欧拉图当且仅当且仅当G G的的所有结点的度数都为偶数所有结

8、点的度数都为偶数。证明：证明： “ “” 设设G G是是EulerEuler图，则图，则G G必然存在一条包含所有边必然存在一条包含所有边（也包含所有结点）的回路（也包含所有结点）的回路C C，对，对 u u V V，u u必然在必然在C C中出现一次（可出现多次），中出现一次（可出现多次），每出现每出现u u一次，都一次，都关联着关联着G G中的两条边，而当中的两条边，而当u u又重复出现时，它又又重复出现时，它又关联着关联着G G中的另外的两条边，（为什么？）中的另外的两条边，（为什么？） 因而因而u u每出现一次，都将使得结点每出现一次，都将使得结点u u的度数增的度数增加加2 2度，若

9、度，若u u在通路中重复出现在通路中重复出现j j次，则次，则deg(u)deg(u)2j2j。 即即u u的度数必为偶数。的度数必为偶数。7/5/2022计算机学院计算机学院10/98/98n定理定理13.1 13.1 无向连通图无向连通图G GVE是欧拉图当是欧拉图当且仅当且仅当G G的所有结点的度数都为偶数。的所有结点的度数都为偶数。证明：证明： “” 设设G G是是EulerEuler图，则图，则G G必然存在一条包含所有边必然存在一条包含所有边（也包含所有结点）的回路（也包含所有结点）的回路C C，对，对 u u V V，u u必然在必然在C C中出现一次（可出现多次），中出现一次（

10、可出现多次），每出现每出现u u一次，都一次，都关联着关联着G G中的两条边，而当中的两条边，而当u u又重复出现时，它又又重复出现时，它又关联着关联着G G中的另外的两条边，（中的另外的两条边，（为什么？为什么？） 因而因而u u每出现一次，都将使得结点每出现一次，都将使得结点u u的度数增的度数增加加2 2度，若度，若u u在通路中重复出现在通路中重复出现j j次，则次，则deg(u)deg(u)2j2j。 即即u u的度数必为偶数的度数必为偶数。7/5/2022计算机学院计算机学院11/98/98n定理定理13.1 13.1 无向连通图无向连通图G GVE是欧拉图当是欧拉图当且仅当且仅当

11、G G的所有结点的度数都为偶数。的所有结点的度数都为偶数。证明：证明： “” 设设G G是是EulerEuler图，则图，则G G必然存在一条包含所有边必然存在一条包含所有边（也包含所有结点）的回路（也包含所有结点）的回路C C，对，对 u u V V，u u必然在必然在C C中出现一次（可出现多次），中出现一次（可出现多次），每出现每出现u u一次，都一次，都关联着关联着G G中的两条边，而当中的两条边，而当u u又重复出现时，它又又重复出现时，它又关联着关联着G G中的另外的两条边，（中的另外的两条边，（为什么？为什么？） 因而因而u u每出现一次，都将使得结点每出现一次，都将使得结点u

12、u的度数增的度数增加加2 2度，若度，若u u在通路中重复出现在通路中重复出现j j次，则次，则deg(u)deg(u)2j2j。 即即u u的度数必为偶数的度数必为偶数。由于在回路由于在回路C中边不可能重中边不可能重复出现复出现7/5/2022计算机学院计算机学院12/98/98“” 设连通图设连通图G G的结点的的结点的度数度数都是偶数，则都是偶数，则G G必必含有简单回路含有简单回路（可用归纳法证明可用归纳法证明） 。 设设C C是一条包含是一条包含G G中边最多的简单回路：中边最多的简单回路： 若若C C已经包含已经包含G G中所有的边，则中所有的边，则C C就是就是EulerEule

13、r回回路，结论成立。路，结论成立。 若若C C不能包含不能包含G G中所有的边，则删边子图中所有的边，则删边子图 G-EG-E（C C）仍然无奇数度结点。）仍然无奇数度结点。 由于由于G G是连通的，是连通的，C C中应至少存在一点中应至少存在一点v v，使，使G-G-E E（C C）中有一条包含）中有一条包含v v的回路的回路CC。（见示意图）（见示意图）7/5/2022计算机学院计算机学院13/98/98“” 设连通图设连通图G G的结点的度数都是偶数，则的结点的度数都是偶数，则G G必必含有简单回路（可用归纳法证明）含有简单回路（可用归纳法证明） 。 设设C C是一条包含是一条包含G G

14、中边最多的简单回路：中边最多的简单回路： 若若C C已经包含已经包含G G中所有的边，则中所有的边，则C C就是就是EulerEuler回回路，结论成立。路，结论成立。 若若C C不能包含不能包含G G中所有的边，则删边子图中所有的边，则删边子图 G-EG-E（C C）仍然无奇数度结点。）仍然无奇数度结点。 由于由于G G是连通的，是连通的，C C中应至少存在一点中应至少存在一点v v，使，使G-G-E E（C C）中有一条包含）中有一条包含v v的回路的回路CC。（见示意图）（见示意图）7/5/2022计算机学院计算机学院14/98/98“” 设连通图设连通图G G的结点的度数都是偶数，则的

15、结点的度数都是偶数，则G G必必含有简单回路（可用归纳法证明）含有简单回路（可用归纳法证明） 。 设设C C是一条包含是一条包含G G中边最多的简单回路：中边最多的简单回路： 若若C C已经包含已经包含G G中所有的边，则中所有的边，则C C就是就是EulerEuler回回路，结论成立。路，结论成立。 若若C C不能包含不能包含G G中所有的边，则删边子图中所有的边，则删边子图 G-EG-E（C C）仍然无奇数度结点。）仍然无奇数度结点。 由于由于G G是连通的，是连通的，C C中应至少存在一点中应至少存在一点v v，使，使G-G-E E（C C）中有一条包含）中有一条包含v v的回路的回路C

16、C。（见示意图）（见示意图）7/5/2022计算机学院计算机学院15/98/98“” 设连通图设连通图G G的结点的度数都是偶数，则的结点的度数都是偶数，则G G必必含有简单回路（可用归纳法证明）含有简单回路（可用归纳法证明） 。 设设C C是一条包含是一条包含G G中边最多的简单回路：中边最多的简单回路： 若若C C已经包含已经包含G G中所有的边，则中所有的边，则C C就是就是EulerEuler回回路，结论成立。路，结论成立。 若若C C不能包含不能包含G G中所有的边，则删边子图中所有的边，则删边子图 G-EG-E（C C）仍然无奇数度结点。）仍然无奇数度结点。 由于由于G G是连通的

17、，是连通的，C C中应至少存在一点中应至少存在一点v v，使，使G-G-E E（C C）中有一条包含）中有一条包含v v的回路的回路CC。（见示意图）（见示意图）7/5/2022计算机学院计算机学院16/98/98 这样，就可以构造出一条由这样，就可以构造出一条由C C和和CC组成的组成的G G的回路，其包含的边数比的回路，其包含的边数比C C多，与多，与假设矛盾假设矛盾。因此，因此，C C必是必是EulerEuler回路，结论成立。回路，结论成立。7/5/2022计算机学院计算机学院17/98/98证明：证明：“” ” 设设G G具有一条具有一条EulerEuler通路通路L L，则在，则在

18、L L中除起点中除起点和终点外，其余每个结点都与偶数条边相关联，所以，和终点外，其余每个结点都与偶数条边相关联，所以，G G中仅有零个（中仅有零个（EulerEuler回路）或者两个奇数度结点。回路）或者两个奇数度结点。“” ” ：若若 G G没有奇度数结点，则结论显然成立；没有奇度数结点，则结论显然成立；若若G G有两个奇度数结点有两个奇度数结点u u和和v v，则，则G+uvG+uv是是EulerEuler图，从而图，从而存在存在EulerEuler回路回路C C。从。从C C中去掉边中去掉边uvuv，则得到一条简单道，则得到一条简单道路路L L（起点（起点u u和终点和终点v v），且包

19、含了），且包含了G G的全部边，即的全部边，即L L是一是一条条EulerEuler道路。道路。注意：若有两个奇度数结点，则它们是注意：若有两个奇度数结点，则它们是G中每条欧拉通中每条欧拉通路的端点。路的端点。n推论推论13.1.113.1.1非平凡连通图非平凡连通图G GVE含有欧拉道路当且含有欧拉道路当且仅当仅当G G仅有零个或者两个奇数度结点。仅有零个或者两个奇数度结点。7/5/2022计算机学院计算机学院18/98/98证明：证明：“” 设设G G具有一条具有一条EulerEuler通路通路L L，则，则在在L L中除起点中除起点和终点外，其余每个结点都与偶数条边相关联和终点外，其余每

20、个结点都与偶数条边相关联，所以，所以，G G中中仅有零个仅有零个（EulerEuler回路回路）或者或者两个两个奇数度结点奇数度结点。“” ” ：若若 G G没有奇度数结点，则结论显然成立；没有奇度数结点，则结论显然成立；若若G G有两个奇度数结点有两个奇度数结点u u和和v v，则，则G+uvG+uv是是EulerEuler图，从而图，从而存在存在EulerEuler回路回路C C。从。从C C中去掉边中去掉边uvuv，则得到一条简单道，则得到一条简单道路路L L（起点（起点u u和终点和终点v v），且包含了），且包含了G G的全部边，即的全部边，即L L是一是一条条EulerEuler道

21、路。道路。注意：若有两个奇度数结点，则它们是注意：若有两个奇度数结点，则它们是G中每条欧拉通中每条欧拉通路的端点。路的端点。n推论推论13.1.113.1.1非平凡连通图非平凡连通图G GVE含有欧拉道路当且含有欧拉道路当且仅当仅当G G仅有零个或者两个奇数度结点。仅有零个或者两个奇数度结点。7/5/2022计算机学院计算机学院19/98/98证明：证明：“” ” 设设G G具有一条具有一条EulerEuler通路通路L L，则在，则在L L中除起点中除起点和终点外，其余每个结点都与偶数条边相关联，所以，和终点外，其余每个结点都与偶数条边相关联，所以，G G中仅有零个（中仅有零个（EulerE

22、uler回路）或者两个奇数度结点。回路）或者两个奇数度结点。“” ” ：若若 G G没有奇度数结点，则结论显然成立没有奇度数结点，则结论显然成立；若若G G有两个奇度数结点有两个奇度数结点u u和和v v，则，则G+uvG+uv是是EulerEuler图图，从而，从而存在存在EulerEuler回路回路C C。从。从C C中去掉边中去掉边uvuv，则得到一条简单道，则得到一条简单道路路L L（起点（起点u u和终点和终点v v），且包含了），且包含了G G的全部边，即的全部边，即L L是一是一条条EulerEuler道路。道路。注意：若有两个奇度数结点，则它们是注意：若有两个奇度数结点，则它们

23、是G中每条欧拉通中每条欧拉通路的端点。路的端点。n推论推论13.1.113.1.1非平凡连通图非平凡连通图G GVE含有欧拉道路当且含有欧拉道路当且仅当仅当G G仅有零个或者两个奇数度结点。仅有零个或者两个奇数度结点。7/5/2022计算机学院计算机学院20/98/98证明：证明：“” ” 设设G G具有一条具有一条EulerEuler通路通路L L，则在，则在L L中除起点中除起点和终点外，其余每个结点都与偶数条边相关联，所以，和终点外，其余每个结点都与偶数条边相关联，所以，G G中仅有零个（中仅有零个（EulerEuler回路）或者两个奇数度结点。回路）或者两个奇数度结点。“” ” ：若若

24、 G G没有奇度数结点，则结论显然成立；没有奇度数结点，则结论显然成立；若若G G有两个奇度数结点有两个奇度数结点u u和和v v，则，则G+uvG+uv是是EulerEuler图，从而图，从而存在存在EulerEuler回路回路C C。从。从C C中去掉边中去掉边uvuv，则得到一条简单道，则得到一条简单道路路L L（起点（起点u u和终点和终点v v），且包含了），且包含了G G的全部边，即的全部边，即L L是一是一条条EulerEuler道路。道路。注意：注意：若有两个奇度数结点，则它们是若有两个奇度数结点，则它们是G中每条欧拉通中每条欧拉通路的端点。路的端点。n推论推论13.1.113

25、.1.1非平凡连通图非平凡连通图G GVE含有欧拉道路当且含有欧拉道路当且仅当仅当G G仅有零个或者两个奇数度结点。仅有零个或者两个奇数度结点。7/5/2022计算机学院计算机学院21/98/98例例13.213.2由由定理定理13.113.1及及推论推论13.1.113.1.1容易看出：容易看出：是欧拉图；是欧拉图；不是欧拉图，但存在欧拉道路；不是欧拉图，但存在欧拉道路；既不是欧拉图，也不存在欧拉道路。既不是欧拉图，也不存在欧拉道路。V V2 2V V1 1V V5 5V V3 3V V4 4(a)(a)V V2 2V V1 1V V5 5V V3 3V V4 4(b)(b)V V1 1V

26、V4 4V V2 2V V3 3(c)(c)7/5/2022计算机学院计算机学院22/98/98例例13.213.2由由定理定理13.113.1及及推论推论13.1.113.1.1容易看出：容易看出：是欧拉图；是欧拉图；不是欧拉图，但存在欧拉道路；不是欧拉图，但存在欧拉道路；既不是欧拉图，也不存在欧拉道路。既不是欧拉图，也不存在欧拉道路。V V2 2V V1 1V V5 5V V3 3V V4 4(a)(a)V V2 2V V1 1V V5 5V V3 3V V4 4(b)(b)V V1 1V V4 4V V2 2V V3 3(c)(c)现在，我们是现在，我们是不是已经解决不是已经解决了哥尼斯

27、堡七了哥尼斯堡七桥问题？桥问题？7/5/2022计算机学院计算机学院23/98/98有向图的欧拉道路、欧拉图有向图的欧拉道路、欧拉图n 定理定理13.213.2（教材（教材p165p165）有向连通图有向连通图G G含有有向欧拉道路，当且仅当含有有向欧拉道路，当且仅当除了两个结点以外，其余结点的入度等于出度，除了两个结点以外，其余结点的入度等于出度，而这两个例外的结点中，一个结点的入度比出而这两个例外的结点中，一个结点的入度比出度大度大1 1，另一个结点的出度比入度大，另一个结点的出度比入度大1 1。）有向连通图）有向连通图G G含有有向欧拉回路，当且仅当含有有向欧拉回路，当且仅当G G中的所

28、有结点的入度等于出度。中的所有结点的入度等于出度。 类似于无向图的讨论，对有向图我们有以下类似于无向图的讨论，对有向图我们有以下结论：结论：同样，有向同样，有向EulerEuler图的结点度数都为偶数；含有有图的结点度数都为偶数；含有有向向EulerEuler道路的图道路的图仅有零个或者仅有零个或者两个奇度数结点。两个奇度数结点。7/5/2022计算机学院计算机学院24/98/98有向图的欧拉道路、欧拉图有向图的欧拉道路、欧拉图n 定理定理13.213.2（教材（教材p165p165）有向连通图有向连通图G G含有有向欧拉道路，当且仅当含有有向欧拉道路，当且仅当除了两个结点以外，其余结点的入度

29、等于出度，除了两个结点以外，其余结点的入度等于出度，而这两个例外的结点中，一个结点的入度比出而这两个例外的结点中，一个结点的入度比出度大度大1 1，另一个结点的出度比入度大，另一个结点的出度比入度大1 1。）有向连通图有向连通图G G含有含有有向欧拉回路有向欧拉回路，当且仅当，当且仅当G G中的中的所有结点的入度等于出度所有结点的入度等于出度。 类似于无向图的讨论，对有向图我们有以下类似于无向图的讨论，对有向图我们有以下结论：结论：同样，有向同样，有向EulerEuler图的结点度数都为偶数；含有有图的结点度数都为偶数；含有有向向EulerEuler道路的图道路的图仅有零个或者仅有零个或者两个

30、奇度数结点。两个奇度数结点。7/5/2022计算机学院计算机学院25/98/98有向图的欧拉道路、欧拉图有向图的欧拉道路、欧拉图n 定理定理13.213.2）有向连通图有向连通图G G含有有向欧拉道路，当且仅当含有有向欧拉道路，当且仅当除了两个结点以外，其余结点的入度等于出度，除了两个结点以外，其余结点的入度等于出度，而这两个例外的结点中，一个结点的入度比出而这两个例外的结点中，一个结点的入度比出度大度大1 1，另一个结点的出度比入度大，另一个结点的出度比入度大1 1。）有向连通图有向连通图G G含有有向欧拉回路，当且仅当含有有向欧拉回路，当且仅当G G中的所有结点的入度等于出度。中的所有结点

31、的入度等于出度。 类似于无向图的讨论，对有向图我们有以下类似于无向图的讨论，对有向图我们有以下结论：结论：同样，同样，有向有向EulerEuler图的图的结点度数都为偶数；含有结点度数都为偶数；含有有有向向EulerEuler道路道路的图的图仅有零个或者仅有零个或者两个奇度数结点。两个奇度数结点。7/5/2022计算机学院计算机学院26/98/98例例13.313.3V V1 1V V2 2V V3 3V V4 4V V1 1V V2 2V V3 3V V4 4V V8 8V V2 2V V4 4V V6 6V V1 1V V3 3V V5 5V V7 7n 图图a)a)存在一条的欧拉道路：存

32、在一条的欧拉道路：v v3 3v v1 1v v2 2v v3 3v v4 4v v1 1；(a)(a)(b)(b)(c)(c)n 图图(b)(b)中存在欧拉回路中存在欧拉回路v v1 1v v2 2v v3 3v v4 4v v1 1v v3 3v v1 1，因而，因而(b)(b)是欧拉图；是欧拉图；n 图图(c)(c)中有欧拉回路中有欧拉回路v v1 1v v2 2v v3 3v v4 4v v5 5v v6 6v v7 7v v8 8v v2 2v v4 4v v6 6v v8 8v v1 1因而因而(c)(c)是欧拉图。是欧拉图。7/5/2022计算机学院计算机学院27/98/98例例

33、13.413.4解解在图中，仅有两个度数为奇数的结点在图中，仅有两个度数为奇数的结点b b，c c，因而存，因而存在从在从b b到到c c的欧拉通路，蚂蚁乙走到的欧拉通路，蚂蚁乙走到c c只要走一条欧拉通路，只要走一条欧拉通路，边数为边数为9 9条。而蚂蚁甲要想走完所有的边到达条。而蚂蚁甲要想走完所有的边到达c c，至少要，至少要先走一条边到达先走一条边到达b b，再走一条欧拉通路，因而它至少要走，再走一条欧拉通路，因而它至少要走1010条边才能到达条边才能到达c c，所以乙必胜。，所以乙必胜。甲、乙两只蚂蚁分别位于右图甲、乙两只蚂蚁分别位于右图中的结点中的结点a a，b b处，并设图中的边长

34、处，并设图中的边长度是相等的。甲、乙进行比赛：从度是相等的。甲、乙进行比赛：从它们所在的结点出发，走过图中的它们所在的结点出发，走过图中的所有边最后到达结点所有边最后到达结点c c处。如果它们处。如果它们的速度相同，问谁先到达目的地？的速度相同，问谁先到达目的地？c cb(b(乙乙) )a(a(甲甲) )7/5/2022计算机学院计算机学院28/98/98例例13.413.4解解 在图中，仅有两个度数为奇数的结点在图中，仅有两个度数为奇数的结点b b，c c，因而存，因而存在从在从b b到到c c的欧拉通路，蚂蚁乙走到的欧拉通路，蚂蚁乙走到c c只要走一条欧拉通路，只要走一条欧拉通路，边数为边

35、数为9 9条。而蚂蚁甲要想走完所有的边到达条。而蚂蚁甲要想走完所有的边到达c c，至少要，至少要先走一条边到达先走一条边到达b b，再走一条欧拉通路，因而它至少要走，再走一条欧拉通路，因而它至少要走1010条边才能到达条边才能到达c c，所以乙必胜。，所以乙必胜。甲、乙两只蚂蚁分别位于右图甲、乙两只蚂蚁分别位于右图中的结点中的结点a a，b b处，并设图中的边长处，并设图中的边长度是相等的。甲、乙进行比赛：从度是相等的。甲、乙进行比赛：从它们所在的结点出发，走过图中的它们所在的结点出发，走过图中的所有边最后到达结点所有边最后到达结点c c处。如果它们处。如果它们的速度相同，问谁先到达目的地？的

36、速度相同，问谁先到达目的地？c cb(b(乙乙) )a(a(甲甲) )7/5/2022计算机学院计算机学院29/98/98FleuryFleury算法算法（构造（构造EulerEuler回路）回路）n设设G GVE是一个是一个欧拉图欧拉图任取任取v v0 0VV，令，令P P0 0v v0 0；设设P P0 0v v0 0e e1 1v v1 1e e2 2eei iv vi i，按下面的方法从，按下面的方法从 G GK K=E-e=E-e1 1,e,e2 2,e,ei i 中选取中选取e ei+1i+1：e ei+1i+1与与v vi i相关联；相关联；除非无别的边可选取，否则除非无别的边可

37、选取，否则e ei+1i+1不应该为不应该为 G Gk kG-eG-e1 1,e,e2 2, ,e,ei i 中的桥；中的桥；当当G Gk k为零图时，算法结束；否则，返回为零图时，算法结束；否则，返回2 2。7/5/2022计算机学院计算机学院30/98/98FleuryFleury算法算法（构造（构造EulerEuler回路）回路）n设设G GVE是一个欧拉图是一个欧拉图任取任取v v0 0VV，令，令P P0 0v v0 0；设设P P0 0v v0 0e e1 1v v1 1e e2 2eei iv vi i，按下面的方法从，按下面的方法从 G GK K=E-e=E-e1 1,e,e2

38、 2,e,ei i 中选取中选取e ei+1i+1：e ei+1i+1与与v vi i相关联相关联；除非无别的边可选取除非无别的边可选取，否则，否则e ei+1i+1不应该为不应该为 G Gk kG-eG-e1 1,e,e2 2, ,e,ei i 中的中的桥桥；当当G Gk k为零图时，算法结束；否则，返回为零图时，算法结束；否则，返回2 2。即如果即如果e ei+1i+1是割边，是割边，同时还有其它边同时还有其它边与与v vi i相关联，则相关联，则不能选不能选e ei+1i+17/5/2022计算机学院计算机学院31/98/98FleuryFleury算法算法（构造（构造EulerEule

39、r回路）回路）n设设G GVE是一个欧拉图是一个欧拉图任取任取v v0 0VV，令，令P P0 0v v0 0；设设P P0 0v v0 0e e1 1v v1 1e e2 2eei iv vi i，按下面的方法从，按下面的方法从 G GK K=E-e=E-e1 1,e,e2 2,e,ei i 中选取中选取e ei+1i+1：e ei+1i+1与与v vi i相关联相关联；除非无别的边可选取除非无别的边可选取，否则，否则e ei+1i+1不应该为不应该为 G Gk kG-eG-e1 1,e,e2 2, ,e,ei i 中的中的桥桥；当当G Gk k为零图时，算法结束；否则，返回为零图时，算法结

40、束；否则，返回2 2。即如果即如果e ei+1i+1是割边，是割边，同时还有其它边同时还有其它边与与v vi i相关联，则相关联，则不能选不能选e ei+1i+1能不走能不走桥就不桥就不走桥！走桥！7/5/2022计算机学院计算机学院32/98/98FleuryFleury算法算法（构造（构造EulerEuler回路）回路）n设设G GVE是一个欧拉图是一个欧拉图任取任取v v0 0VV，令，令P P0 0v v0 0；设设P P0 0v v0 0e e1 1v v1 1e e2 2eei iv vi i，按下面的方法从，按下面的方法从 G GK K=E-e=E-e1 1,e,e2 2,e,e

41、i i 中选取中选取e ei+1i+1：e ei+1i+1与与v vi i相关联；相关联；除非无别的边可选取，否则除非无别的边可选取，否则e ei+1i+1不应该为不应该为 G Gk kG-eG-e1 1,e,e2 2, ,e,ei i 中的桥；中的桥；当当G Gk k为零图时，算法结束；否则，返回为零图时，算法结束；否则，返回2 2。7/5/2022计算机学院计算机学院33/98/98例例13.513.5v v4 4v v5 5v v6 6e e4 4e e5 5e e6 6e e1010e e9 9e e8 8e e3 3在右图所示的欧拉图中，某在右图所示的欧拉图中，某人用算法求中的欧拉回

42、路时，人用算法求中的欧拉回路时，走了简单的回路：走了简单的回路：v v2 2e e2 2v v3 3e e3 3v v4 4e e1414v v9 9e e1010v v2 2e e1 1v v1 1e e8 8v v8 8e e9 9v v2 2之后，无法行遍了，试分析在哪之后，无法行遍了，试分析在哪步他犯了错误？步他犯了错误？v v1 1v v3 3v v7 7e e1 1e e2 2e e7 7v ve e1 1e e1 1e e1 1e e1 1v v2 2v v4 4v v5 5v v6 6e e4 4e e5 5e e6 6e e1010e e9 9e e8 8e e3 3v v1

43、 1v v3 3v v7 7e e1 1e e2 2e e7 7v ve e1 1e e1 1e e1 1e e1 1v v2 2此人行遍此人行遍v v8 8时犯了能不走桥就不走桥的错时犯了能不走桥就不走桥的错误，因而未能行遍出欧拉回路。当他走到误，因而未能行遍出欧拉回路。当他走到v v8 8时，时，e e2 2，e e3 3，e e1414，e e1010，e e1 1，e e8 8, ,见右图，此时，见右图，此时，e e9 9为该图中的桥为该图中的桥，而，而e e7 7、e e1111均不是桥。因此，他不该走均不是桥。因此，他不该走e e9 9 ，而应，而应该走该走e e7 7或或e e1

44、111 。但在行遍。但在行遍v v3 3和和v v1 1时，也遇时，也遇到桥，为什么没有问题呢？到桥，为什么没有问题呢？v v9 9v v9 97/5/2022计算机学院计算机学院34/98/98中国邮递员问题中国邮递员问题 山东师范大学，管梅谷先生山东师范大学，管梅谷先生19621962提出并解决。提出并解决。 （参考文献：参考文献：19621962（数学通报）（数学通报）81.10,P81.10,P3232, , ,81.5,81.5） 一个邮递员从邮局出发，在其分管的投递区域内一个邮递员从邮局出发，在其分管的投递区域内走遍所有的街道把邮件送到每个收件人手中，最后又走遍所有的街道把邮件送到

45、每个收件人手中，最后又回到邮局，要走怎样的线路使全程最短。回到邮局，要走怎样的线路使全程最短。 这个问题用图来表示：街道为图这个问题用图来表示：街道为图的边，街道交叉口为图的结点，的边，街道交叉口为图的结点，问题就是要从这样一个图中找出问题就是要从这样一个图中找出一条一条至少包含每条边一次的总长至少包含每条边一次的总长最短的回路最短的回路。7/5/2022计算机学院计算机学院35/98/98 对此，管梅谷曾证明，对此，管梅谷曾证明，若图的边数为若图的边数为m m，则所求回，则所求回路的长度最小是路的长度最小是m m，最多不超过，最多不超过2m2m，并且每条边在其中，并且每条边在其中最多出现两次

46、最多出现两次。中国邮递员问题，一般为在带权连通图。中国邮递员问题，一般为在带权连通图中找一条包括全部边的且权最小的回路。中找一条包括全部边的且权最小的回路。 这个问题有着有效的解决办法，其中最直观的方法这个问题有着有效的解决办法，其中最直观的方法之一是之一是: :把图中的某些边复制成两条边，然后在所求图把图中的某些边复制成两条边，然后在所求图中找一条欧拉回路。中找一条欧拉回路。 中国邮递员问题是运筹学中一个典型的优化问题。中国邮递员问题是运筹学中一个典型的优化问题。 显然，当这个图是欧拉图时，任何一条欧拉回路都显然，当这个图是欧拉图时，任何一条欧拉回路都符合要求；当这个图不是欧拉图时，所求回路

47、必然要重复符合要求；当这个图不是欧拉图时，所求回路必然要重复通过某些边。通过某些边。关键是：复制哪些边？关键是：复制哪些边？7/5/2022计算机学院计算机学院36/98/98算法算法（1 1）若）若G G不含奇数度结点，则任一欧拉回路就是问题的不含奇数度结点，则任一欧拉回路就是问题的解决。解决。 （2 2）若）若G G含有含有2K(2K(K0K0) )个奇数度结点，则个奇数度结点，则先求出其中任何先求出其中任何两点间的最短路径两点间的最短路径，然后再在这些路径之中找出，然后再在这些路径之中找出K K条路条路径径P P1 1，P P2 2，P PK K，使得满足以下，使得满足以下条件条件： 任

48、何任何P Pi i和和P Pj j（ijij）没有相同的起点和终点。）没有相同的起点和终点。 在所满足在所满足的的K K条最短路径的集合中，条最短路径的集合中， P P1 1，P P2 2，PPK K的长度总和最短。的长度总和最短。（3 3）根据（）根据（2 2）中求出的）中求出的K K条最短道路条最短道路P P1 1，P P2 2，P PK K，在原图在原图G G中复制所有出现的在这条道路上的边，设所得中复制所有出现的在这条道路上的边，设所得之图为之图为G G。（4 4）构造）构造G G的欧拉回路，即得中国邮递员问题的解。的欧拉回路，即得中国邮递员问题的解。 找出需复找出需复制的边制的边连通

49、图中，奇数度结点的个数必为偶数个。连通图中，奇数度结点的个数必为偶数个。7/5/2022计算机学院计算机学院37/98/98例例13.613.61 1因为因为G G含有奇数度结点，所以含有奇数度结点，所以2 2G G中有中有2K=4(2K=4(K=2K=2) )个奇结点个奇结点: : V V1 1，V V2 2，V V3 3，V V5 5。 这这4 4点间的距离点间的距离: : d(V d(V1 1,V,V2 2)=3)=3， d(Vd(V1 1,V,V3 3)=5)=5， d(Vd(V1 1,V,V5 5)=4)=4， d(Vd(V2 2,V,V3 3)=2)=2， d(Vd(V2 2,V,

50、V5 5)=3)=3， d(Vd(V3 3,V,V5 5)=4)=4各路径各路径:V:V1 1V V2 2(3),V(3),V3 3V V5 5(4)7(4)7 V V1 1V V3 3(5),V(5),V2 2V V5 5(3)(3)8 8 V V1 1V V5 5(4),V(4),V2 2V V3 3(2)(2)6 6两条两条长度最短长度最短P P1 1=V=V1 1V V7 7V V5 5,P,P2 2=V=V2 2V V3 33 3构造构造GG的任一的任一E E图就是中国邮递员图就是中国邮递员问题的解。问题的解。 GG7/5/2022计算机学院计算机学院38/98/98Euler图的应

51、用图的应用 模数转换问题模数转换问题：设有旋转鼓轮其表面被等分成：设有旋转鼓轮其表面被等分成1616个部分，如图个部分，如图1 1所示。所示。 其中每一部分分别用绝缘体或其中每一部分分别用绝缘体或导体组成，绝缘体部分给出导体组成，绝缘体部分给出信号信号0 0，导体部分给出导体部分给出信号信号1 1，在图中阴影部，在图中阴影部分表示导体，空白部分表示绝缘体，分表示导体，空白部分表示绝缘体，根据鼓轮的位置，根据鼓轮的位置，触点触点将得到信息将得到信息11011101，如果鼓轮沿顺时针方向旋转，如果鼓轮沿顺时针方向旋转一个部分，触点将有信息一个部分，触点将有信息10101010。问问鼓轮上鼓轮上16

52、16个部分怎样安排导体及绝个部分怎样安排导体及绝缘体，才能使鼓轮每旋转一个部分，缘体，才能使鼓轮每旋转一个部分，四个触点能得到一组不同的四位二四个触点能得到一组不同的四位二进制数信息。进制数信息。图图1 17/5/2022计算机学院计算机学院39/98/98n 设有一个设有一个八个结点八个结点的有的有向图（向图（图图2 2 ），其结点分），其结点分别 记 为 三 位 二 进 制 数别 记 为 三 位 二 进 制 数000000，001001，010010，011011，100100，101101，110110，111111，设设a ai i00，11，从结点从结点a a1 1a a2 2a a

53、3 3可引出两条有向边，可引出两条有向边，其终点分别是其终点分别是a a2 2a a3 30 0以及以及a a2 2a a3 31 1。该两条边分别记。该两条边分别记为为a a1 1a a2 2a a3 30 0和和a a1 1a a2 2a a3 31 1。图图2 27/5/2022计算机学院计算机学院40/98/98 按照上述方法，对于八个结点的有向图共有按照上述方法，对于八个结点的有向图共有1616条条边，在这种图的任一条路中，其邻接的边必是边，在这种图的任一条路中，其邻接的边必是a a1 1a a2 2a a3 3a a4 4和和a a2 2a a3 3a a4 4a a5 5的形式，

54、即是的形式，即是第一条边标号的后三位数与第第一条边标号的后三位数与第二条边标号的头三位数相同。二条边标号的头三位数相同。 因为图因为图2 2中中1616条边被记成不同的二进制数，可见前条边被记成不同的二进制数，可见前述鼓轮转动所得到述鼓轮转动所得到1616个不同位置触点上的二进制信息，个不同位置触点上的二进制信息，即对应于图中的一条欧拉回路，由回路中每条边对应即对应于图中的一条欧拉回路，由回路中每条边对应码的第一个符号构成的循环序列就是所求结果。码的第一个符号构成的循环序列就是所求结果。 如如e e0 0e e1 1e e2 2e e4 4e e9 9e e3 3e e6 6e e1313e

55、e1010e e5 5e e1111e e7 7e e1515e e1414e e1212e e8 8是一条欧拉是一条欧拉回路，这回路，这1616个二进制数可写成对应的二进制数序列个二进制数可写成对应的二进制数序列00001001101011110000100110101111。把这个序列排成环状。把这个序列排成环状, ,即与所求的即与所求的鼓轮相对应。鼓轮相对应。 7/5/2022计算机学院计算机学院41/98/98 按照上述方法，对于八个结点的有向图共有按照上述方法，对于八个结点的有向图共有1616条条边，在这种图的任一条路中，其邻接的边必是边，在这种图的任一条路中，其邻接的边必是a a1

56、 1a a2 2a a3 3a a4 4和和a a2 2a a3 3a a4 4a a5 5的形式，即是第一条边标号的后三位数与第的形式，即是第一条边标号的后三位数与第二条边标号的头三位数相同。二条边标号的头三位数相同。 因为图因为图2 2中中1616条边被记成不同的二进制数，可见前条边被记成不同的二进制数，可见前述鼓轮转动所得到述鼓轮转动所得到1616个不同位置触点上的二进制信息，个不同位置触点上的二进制信息，即对应于图中的一条欧拉回路，由回路中每条边对应即对应于图中的一条欧拉回路，由回路中每条边对应码的第一个符号构成的循环序列就是所求结果。码的第一个符号构成的循环序列就是所求结果。 如如e

57、 e0 0e e1 1e e2 2e e4 4e e9 9e e3 3e e6 6e e1313e e1010e e5 5e e1111e e7 7e e1515e e1414e e1212e e8 8是一条欧拉是一条欧拉回路，这回路，这1616个二进制数可写成对应的二进制数序列个二进制数可写成对应的二进制数序列00001001101011110000100110101111。把这个序列排成环状。把这个序列排成环状, ,即与所求的即与所求的鼓轮相对应。鼓轮相对应。 7/5/2022计算机学院计算机学院42/98/98 按照上述方法，对于八个结点的有向图共有按照上述方法，对于八个结点的有向图共有

58、1616条条边，在这种图的任一条路中，其邻接的边必是边，在这种图的任一条路中，其邻接的边必是a a1 1a a2 2a a3 3a a4 4和和a a2 2a a3 3a a4 4a a5 5的形式，即是第一条边标号的后三位数与第的形式，即是第一条边标号的后三位数与第二条边标号的头三位数相同。二条边标号的头三位数相同。 因为图因为图2 2中中1616条边被记成不同的二进制数，可见前条边被记成不同的二进制数，可见前述鼓轮转动所得到述鼓轮转动所得到1616个不同位置触点上的二进制信息，个不同位置触点上的二进制信息，即对应于图中的一条欧拉回路，由回路中每条边对应即对应于图中的一条欧拉回路，由回路中每

59、条边对应码的第一个符号构成的循环序列就是所求结果。码的第一个符号构成的循环序列就是所求结果。 如如e e0 0e e1 1e e2 2e e4 4e e9 9e e3 3e e6 6e e1313e e1010e e5 5e e1111e e7 7e e1515e e1414e e1212e e8 8是一条欧拉是一条欧拉回路，这回路，这1616个二进制数可写成对应的二进制数序列个二进制数可写成对应的二进制数序列00001001101011110000100110101111。把这个序列排成环状。把这个序列排成环状, ,即与所求的即与所求的鼓轮相对应。鼓轮相对应。 7/5/2022计算机学院计算

60、机学院43/98/98习题习题P P174174 5 57/5/2022计算机学院计算机学院44/98/98哈密顿图哈密顿图周游世界问题周游世界问题 18571857（5959）年爱尔兰数学家）年爱尔兰数学家W.R.HamiltonW.R.Hamilton在给他朋友的一封在给他朋友的一封信中，首先谈到关于十二面体的信中，首先谈到关于十二面体的一个数学游戏：将左图中的每个一个数学游戏：将左图中的每个结点看成一个城市，联结两个结结点看成一个城市，联结两个结点的边看成是交通线，他的问题点的边看成是交通线，他的问题就是能不能找到旅行路线，沿着就是能不能找到旅行路线，沿着交通线经过每个城市恰好一次，交通