张佳丽：图论的发展及其在生活中的应用
2．2 旅行推销员问题
该问题是说：“给定n个城市和它们之间的距离，问如何设计一条路线，使得一个推销员从他所在的城市出发途经其余n?1个城市刚好一次，最后回到原驻地并使得行程最短[5]？” 2．2．1 基本理论
定义2.2[6] 给定图G?V,E（G为无向图或有向图），设W：E?R（R为实数集），对G中任意的边e??vi,vj? (G 为有向图时，e?vi,vj)，设W?e??wij，称实数
wij为边e上的权，并将wij标注在边e上，称G为带权图，此时常将带权图G记作
V,E,W．设G??G，称最邻近法[7]
e?E?G???W?e?为G?的权，记作W?G??，即W?G??=
e?E?G???W?e?．
(1)由任意选择的结点开始，找与该点最近（即权最小）的点，形成有一条边的初始路径．
(2)设X表示最新加到这条路上的结点，从不在路上的所有结点中选一个与X最靠近的结点，把连接X与这一结点的边加到这条路上，重复这一步，直到G中所有结点包含在路上．
(3)将连接起始点与最后加入的结点之间的边加到这条路上，就得到一个圈，即为问题的近似解． 2．2．2 应用举例
例[8] 某流动售票员居住在A城，为推销货物他要访问B、C、D城后返回A城，若该四城间的距离如下图2.2所示，找出完成该访问的最短路线．
B11A138C6D图2.2
716
解 步骤如下图①—④
6
菏泽学院本科生毕业设计（论文）
BAC8D
①
BAC86D
②
B7AC86D③
B11AC86D
④
7最短距离为：8+6+7+11=32． 2．3 最小生成树 2．3．1 基本理论
定义2.3.1[9] 设G?V,E，G??V?,E?为两个图（同为无向图或同为有向图），
7
张佳丽：图论的发展及其在生活中的应用
若V??V且E??E，则称G?是G的子图，G为G?的母图，记作G??G．又若V??V或，
E??E则称G?为G的真子图，若V??V，则称G?为G的生成子图．
定义2.3.2[10] 不含圈的连通图称为树．
定义2.3.3[11] 如果T是G的一个生成子图而且又是一棵树，则称T是图G的一棵生树．
定义2.3.4[12] 设无向连通带权图G?V,E,W，T是G的一棵生成树，T的各边权之和称为T的权．G的所有生成树中，权最小的生成树称为G的最小生成树． ⑴破圈法[13]
在G中任取一个圈，去掉其中一条边，然后再取一个圈，再去掉这个圈中的一条边，如此继续下去，最后得到的连通图的无圈的生成子图就是G的一棵生成树． ⑵用破圈法求带权的最小生成树的方法
在赋权图G中任取一个圈，然后去掉这个圈中权最大的边，如此继续进行直到G中不再有圈时为止，这时剩下的边组成的子图就是最小树．[14] 2．3．2 应用举例
旅游线路中的最短问题 对于旅客来说，要求在最短的时间内用最少的钱来旅游最多的景点，考虑到无论采取哪种方案，在门票的花费均相同且路费在速度恒定的情况下可由路程的多少来求得，从而把问题转化为求最短的旅游路线的问题．[15]
例[16] 公园的路径系统图如图2.3，其中S为入口，T为出口，A，B，C，D，E为五个景点，现求如何能使观光旅游车从入口S到出口T所经过的距离最短．
A2S4C512D74B347E
51T图2.3
解 用破圈法求带权的最小生成树的方法求解，求解步骤如下图①—⑥
8
菏泽学院本科生毕业设计（论文）
A2S4C12D74B347E1T5
①
A2S1C2D74B347E1T5
②
A2S1C42B34D51T7E
③
A2S1C④ 9
D2B37E451T
张佳丽：图论的发展及其在生活中的应用
A2S1C⑤
D2B37E1T5
A2S1C⑥
D2B3E1T5
由图可知，从如口S到出口T的最短路径为S?A?B?E?D?T 最短距离为：2+2+3+1+5=13． 2．4 四色问题
1852年10月23日英国数学家德?摩根写给当时还属于英国的爱尔兰数学家哈密尔顿的一封信中，他写道：“我的一位学生今天请我解释一个我过去不知道，现在仍不甚了了的事实．他说任意划分一个地图并给各部分着上颜色，使任何具有公共边界的部分颜色不同，那么需要且仅需要四种颜色就够了．”德?摩根提到的这位学生名叫弗雷德里克?格里斯．而据他后来撰文披露，该问题的真正发现者实际是他是的哥哥弗兰西斯?格里斯．[17] 2.4.1 基本理论
定义2.4.1[18] 设G为无向标定图，G中的顶点与边的交替序列?? vi0ej1 vi1ej2?
ejlvil称为vi0到vil的通路，其中vir-1，vir为ejr的端点，r=1,2, ?l， vi0，vil分别称为?的始点与终点，?中边的条数称为它的长度，若vi0 =vil，则称通路为回路．若?的所有边各异，则称?为简单通路，又若vi0=vil，则称?为简单回路．若?的所有顶点（除vi0 与
10