张佳丽：图论的发展及其在生活中的应用
(7?1)?4(n?1)??G?m?13?12??
22由定理2．5．2,可知?1?G??5．图G列出了G的一个5边染色,从而也给出了一个具有最少天数(5)的时间安排表．
第一天： 亚特兰大－波士顿 纳什维尔－迈阿密 芝加哥－路易维尔 第二天： 波士顿－纳什维尔 亚特兰大－芝加哥 丹佛－路易维尔 第三天： 亚特兰大－迈阿密 芝加哥－波士顿 丹佛－纳什维尔 第四天： 芝加哥－丹佛 路易维尔－迈阿密 亚特兰大－纳什维尔 第五天： 丹佛－迈阿密 2.6 中国邮递员问题
中国邮递员问题即为邮递员路线问题．邮递员从邮局出发,经过他所投递范围的每一条街道至少一次,完成邮件的投递任务以后返回邮局．如何安排邮递员的行走路线,以使总路程最短,这个问题是中国学者管梅谷1962年首先提出,并给出了一个解法,被国际上称为中国邮递员问题． 2.6.1 基本理论
定义2.6.1
[26]
在图上,从某个顶点出发,对各条边只通过一次,这样的迹称为
Euler迹．闭Euler迹叫做Euler环游．一个图若包含Euler环游,则这个图称为Euler图．
定义2.6.2[27] 将边e的两个端点再用一条权同样为w?e?的新边连接，即得重复边．
定理2.6.1 [27] 若G是Euler图，则G中任意用Fleury算法做出的迹都是G上午
Euler环游．
定理2.6.2[27] 设赋权图G经添加重复边集EP后得到赋权欧拉图GE，重复边集EP权值总和w?EP??eP?EP?w?e?最小的充要条件是：每条边最多重复一次，并且GPE中任一
个圈C，其所含重复边的权值之和都不大于所在圈C中所有边权值的二分之一．
Fleury算法
[27]
:
(1) 任意选取一个顶点v0,置W0?v0；
(2) 假设迹Wi?v0e1v1...eivi已经选定，那么按下述方法从E\\?e1,e2,...,ei?中选取边
ei?1：
16
菏泽学院本科生毕业设计（论文）
1）ei?1和vi相关联；
2）除非没有别的边可选择，否则ei?1不是Gi?G\\?e1,e2,...,ei?的割边． (3)当2）不能再执行时，算法停止，得到G中一条迹． 非Euler图求最优环游的算法步骤[27] ：
(1)开始．任给一个初始方案，使非Euler赋权图各顶点变为偶点，得到一个初始赋权Euler图；
(2)检查．检查各圈是否满足圈中“重复边总权值小于等于非重复边总权值”的最优解条件．若条件已满足，则现行方案为最优解，再由Fleury算法得到一条最优环游，否则转（3）；
(3)调整．调整重复边并保持图仍为赋权Euler图．转（2）． 2．6．2 应用举例
例[28] 设邮递员所辖的投递区如下图2.6所示，其中边旁的数字为街道长度，问从邮局出发，如何走遍全区各街最后回到邮局A而又最短的路径．
A1012D16B1020E86FC
图2.6
解 d?A??1，d?F??1故此图为非欧拉图．添加重复边使其变为欧拉图，如下图2.6.1， 经检查所有圈皆符合定理2．6．2，故下图为最优方案．
10A1012D16B101020E6图2.6.1
C868F
17
张佳丽：图论的发展及其在生活中的应用
按Fleury算法可得到一条最优环游,这条最优环游是: ABCEFECBDEBA. 参考文献
[1]李冰．图论的起源和发展[J]．大众文艺，2010（9）：34．
[2]黄会芸．图论思想在生活中的运用[J]．赤峰学院学报（自然科学版），2009,25(12):23-24．
[3]耿素云、屈婉玲．离散数学[M]．2版．北京：高等教育出版社，2004:267． [4]傅彦．离散数学基础及应用[M]．成都：电子科技大学出版社，2000：149—150． [5]程钊．图论中若干著名问题的历史标记[J]．数学的实践与认识，2009，39（24）：75．
[6]耿素云、屈婉玲．离散数学[M]．2版．北京：高等教育出版社，2004:302． [7]乔维声、汤惟．离散数学[M]．西安：西安电子科技大学出版社，2005:157． [8]乔维声、汤惟． 离散数学[M]．西安：西安电子科技大学出版社，2005:158． [9]耿素云、屈婉玲．离散数学[M]．2版．北京：高等教育出版社，2004:274． [10]王朝瑞．图论[M]．3版．北京：北京理工大学出版社，2002:26． [11]王朝瑞．图论[M]．3版．北京：北京理工大学出版社，2002:33．
[12]耿素云、屈婉玲．离散数学[M]．2版．北京：高等教育出版社，2004:311． [13]王朝瑞．图论[M]．3版．北京：北京理工大学出版社，2002:34． [14]王朝瑞．图论[M]．3版．北京：北京理工大学出版社，2002:232．
[15]方冬云．图论在旅游路线选择中的应用[J]．长春工业大学学报（自然科学版），2009,30（5）：583．
[16]刘海英．最短路径问题在管理中的应用[J]．福建广播电视大学学报,2010，4（29）：87．
[17]程钊．图论中若干著名问题的历史标记[J]．数学的实践与认识，2009，39（24）：78．
[18]耿素云、屈婉玲．离散数学[M]．2版．北京：高等教育出版社，2004:276． [19]耿素云、屈婉玲．离散数学[M]．2版．北京：高等教育出版社，2004:333． [20耿素云、屈婉玲．离散数学[M]．2版．北京：高等教育出版社，2004:332． [21]Gary Chartrand、Ping Zhang．图论导引[M]．范益政等，译．北京：人民邮电出版社，2007：237．
[22]Gary Chartrand、Ping Zhang．图论导引[M]．范益政，朱明，龚世才等译．北京：
18
菏泽学院本科生毕业设计（论文）
人民邮电出版社，2007：246－247．
[23] Gary Chartrand、Ping Zhang．图论导引[M]．范益政，朱明，龚世才等译．北京：人民邮电出版社，2007：248—250．
[24]耿素云、屈婉玲．离散数学[M]．2版．北京：高等教育出版社，2004:269． [25] Gary Chartrand、Ping Zhang．图论导引[M]．范益政，朱明，龚世才等译．北京：人民邮电出版社，2007：255.
[26]刘缵武．应用图论[M]．长沙：国防科技大学出版社，2004：83． [27]刘缵武．应用图论[M]．长沙：国防科技大学出版社，2004：85—87． [28]刘缵武．应用图论[M]．长沙：国防科技大学出版社，2004：97． 致谢
在此论文撰写过程中，要特别感谢我的导师刘秀丽老师的指导与督促。刘秀丽老师对该论文从选题，构思到最后定稿的各个环节都给予细心指导和不懈的支持,使我得以最终完成毕业论文设计。
此外，本文最终得以顺利完成，也是与数学系其他老师的帮助分不开的，虽然他们没有直接参与我的论文指导，但在这个过程中却给我提供了不少的意见，提出了一系列可行性的建议，在此向他们表示深深的感谢！
最后再一次感谢所有在毕业设计中曾经帮助过我的良师益友和同学，以及在设计中被我引用或参考的论著的作者。
19