1)量出各条道路长度(可用丝线沿道路曲线测量)，得到一个加权图，从而问题转化为中国邮路问题。若只有一辆扫雪车，且（1）地图为Euler图情形，则可按Fleury算法求出Euler途径即为最佳扫雪方案。
2）若地图不是Euler图的情形，则要在某些边重复，即增加一些重边使之变为Euler图。问题则转化为求一个新边集E?, 使G?(V,E?E?)为Euler图前提下，??(e)最
e?E?小。
(1)若只有二个奇度点，则只要在该二点间加一“边”即可：若相邻，则在该二点间联一条边即可；非相邻，则用下面Dijkstra算法求出最短路线，然后在该线路上的每一边加一重边即可得到一Euler图。
Dijkstra算法： ② 对每一v?Si 用min{L(v), L(ui)+W(uiv)} 代替 L(v), 设ui?1 为L(v)中最小者（v?Si ）令Si+1=Si∪{ui?1} ，转③；
③ 若i=∣V(G)∣-1 止；若 i<∣v(G)∣-1,则转②
此时，每个顶点所标L(v)即为到u的最短距离，此算法的复杂度 O(V2)（顶点数V的平方的一个同阶量）。
Dijkstra算法不仅给出了二点间的最短距离，而且由此可得到最短路线。
(2)多于二个奇度点，则易知其奇度点个数为偶数个。可将所有的奇度点之间分别
4联一条“边” 并使得所联 “边” 的总长度为最短（这
21里边的意义同（1））。 这样得到的图即为最短路线（其中重边即为需要重复走的路段）。
755① L(u0)=0， L(v)=∞ v≠u0， S0={u0},i=0 ，转②；
3623412517223374图2-30
2 下面用实例（如图2-30）说明做法：
341）求奇度点集 X1={①②③④}； 32）用Dijkstra算法求出对应点间最短距离：
８３
图2-31
1 2 3 4 1 0 4 5 7 2 4 0 2 5 3 4
5 2 0 3 7 5 3 0
3）构作加权完全图 K(X1,E0)（完全图：任意二顶点间都有边的图）。图2-29(对奇度点集)；
4）求出最佳匹配 {①②，③④}
①②+③④最小，此时保证：①过每一奇度点，增一边（使每一奇度点变为偶度点）②增加的边的总长最短；
5）求出①--②最短路①-⑦-② ，
③--④最短路 ③-④；
6）在相应边上加一同权新边，即得Euler图G?； 7）求出G?上Euler路（用Fleury算法） 4．货郎担问题, Hamilton路问题
1859年，著名数学家Hamilton（U.K）提出了所谓“周游世界游戏”：用正十二面体的20个顶点代表二十个大城市北京，东京，华盛顿等大都市名称(图2-32)。要求玩的人从某大城市出发，沿着正12面体的棱通过每个大城市恰一次，再回到出发城市。这种游戏曾风靡欧洲一时，后来Hamilton以25个金币的高价把该项专利卖给了一个玩具商。
若将图中前面的五边形“拉开”，使之变成平面图则得到下边的图形（图2-32b）。
问题转化为：在图上找一条从某点出发的道路经过所有顶点一次且仅一次回到起点。
含图上一切顶点的道路称为Hamilton路；闭的Hamilton路称为Hamilton圈。 寻找Hamilton路（圈）是图论上难点之一，至今未发现Hamilton路存在的充要条件，下面是一些主要结论：
充分条件1：（Ore,1960, [5],P.64） 设图的顶点数为n(≥3), 若对于任意u,v∈V(G) ，d(u)+d(v)≥n ，则G为 Hamilton圈 ；若对于任意u,v∈V(G) ，d（u）+d(v)≥n-1， 则该图存在Hamilton路。
８４
(a)(b)图2-32
充分条件2： （Dirac, [4],P.42）设图G的顶点数n(≥3), w为度数最小的顶点，若deg(w)≥n/2, 则G为Hamilton图。
充分条件1，2的本质：每个顶点的度数均充分大。
充分条件3： G为n个顶点（n≥3）的连通图，?k≤(n-1)/2的正整数，次数小于k的顶点数≤k, 则G为Hamilton图。
例12 亚瑟王（传说中的英国国王）在宫中召见他的2n个骑士，而骑士中有些有怨仇。若已知每个骑士最多与n－1个骑士有仇，问能否将这2n名骑士在一个（著名的）圆桌上安排就餐，且使每个骑士不与他的仇人相邻。（其谋士摩尔林做到了这一点）。
解：化为图论问题：以2n个图的顶点表示骑士，若二骑士之间无仇则在二顶点之间画一条边，得到一图G(V，E)。 问题转化为：是否能在图G(V，E)上寻求一条Hamilton圈。
由条件，每一顶点的度数≥n， 故?u， v∈V， d(u)+d(v)≥n+n=2n， 由Ore知存在一条Hamilton圈。
上述条件为充分而非必要条件。如周游世界游戏（图2-30）不满足条件，但存在Hamilton圈。
引入如下概念：
图的闭包：若图G的任意顶点u，v若满足d(u)+d(v)??V (顶点数)，则当这二点之间无边时，连一条边。依次做下去直到不存在这样的顶点，这样得到的图称为图G的闭包，记为C(G) （如图2-33）。
定理2-4：（充要条件）图G为Hamilton图的充分必要条件是C(G)为Hamilton图。
注：此条件仍不能判断周游世界游戏为H图。
目前，对如何判别一个图为Hamilton图仍是世界难题。 与之相关的问题是：
货郎担问题：一货郎挑担到n个村去卖货，能否找到一条
最近的路，使货郎经过各村庄一次再回到出发地。（假设各村之间路程为已知）
它可以视为加权Hamilton圈问题，记G(V，E，w)（ w为相应边的权）。 Hamilton图可视为特殊的货郎担问题，即各边权值相等皆为1。
由于Hamilton图的判别仍是未解决的问题，因此，货郎担问题当然无法解决。
思路1：将通过各顶点的道路方案“历数”，比较并找出最佳路线。但这是不现实的：如有20个村庄，
图2-33
vi?1vivj?1vj８５
图2-31
任二个村之间都有路相通，则要比较上也要计算770年。（[5]，P.4）
12×20！=2.43×1018次，这在每秒千万次的计算机
思路2：当已知c=v1v2?vvv1为一回路，则可用下边的“改良圈算法”进行优化，得到一条最佳路线。
改良圈算法：
（1）检查c上是否有i≠j， 使vi-1vj∈E(G)， vivj+1∈E(G)且w(vi-1vj)+w(vivj+1) （2）用c1代替c，转入（1）直至终止。 该算法计算复杂度为O(V)。 此算法前提：vivj+1及vi-1vj有边，否则无法“改良”。特别，当图为完全图时，此算法有效。 例13一学者从北京(Pe)到伦敦(L)、 墨西 Pe2 L605156706813MCT27835216168515736PaNY哥城(Mc)、 纽约（NY）、巴黎（Pa）、 图2-34 东京（Tokyo）讲学（各地之间的距离见图2-34，单位：百公里），现为其设计一路程方案，使之 花费最少。 取初始圈 c=(Pe)(T)(L)(Mc)(NY)(Pa)(Pe) 总路程13+60+56+21+36+51=237（百公里） 。 用改良圈算法计算（如图2-35），计算结果： c1 =(Pe)(T)(L)(Pa)(NY)(Mc)(Pe)=210 c2 =(Pe)(T)(Mc)(NY)(Pa)(L)(Pe)=193 c3 图2-35 =(Pe)(T)(Mc)(NY)(L)(Pa)(Pe)=192 c3为最佳路线。 思路3. 可用“最邻近方法”或称“贪婪算法” 。 ８６ 方法：从v0出发，比较v0到v1，┅，vn 的边长，先到距v0最近的点，依次下去可得一条较好的线路。 例14.有一商店v1 ，售货点4个，他们之间路程如图2-36。 按贪婪算法解得最佳路线为 v1v4v3v5v2v（长度为40），但v1v5v2v3v4v（长度为37 ）11 更优。 此算法未必能得到最佳路线，但算法简单，容易实现。 思路4. 最近插入法 方法：设已得到一部分顶点的Hamilton圈Vk 。在剩余点中寻找距Vk中点最近的点加入vk得Vk+1。而新点加在哪里，可采用比较方法，即将该点加至不同位置，取路径最短者。 又解例14. 用“最近插入法”： 先取v1作为V1。 显然下一点取v4，加入V1得到V2=v1v4v1回路。再看距v1，v4最近的点。比较v1v2=14 ， v1v3=12，v1v5=10，v4v2=13，v4v3=6 ，v4v5=11故增加v3。 又比较不同的路线长度v1v3v4v1=12+6+7=25 ，v1v4v3v1=7+6+12=25，二者相同，不妨取新回路为V3= v1v4v3v1；再计算出距{v1，v4，v3}最近点 v5 ，找出最佳回路：V4=v1v4v3v5v1 ={v1，v4，v3，v5}；剩唯一点v2 ，最后比较得最佳回路 v1v4v3v2v5v1，总距离37。 5．好算法与NP完全问题 下面就此问题作一个简单介绍 1965年，Hartmanis和Stearns 在所谓Turing机的意义下，（它是一个数字概念，也是后来真正计算机诞生的理论基础）提出了所谓计算复杂度的概念。 定义2-1（1965，Edmonds）某问题在Turing 机([3],[5])上的计算时间作为输入长n的函数有某个多项式为其上界，则称该问题有多项式时间算法。 好算法：若给定一问题，如果某算法使得：对于输入长度为n，存在一个多项式P(n)，，使该问题使用本算法至多经过不超过P(n) 次的运算，可得到其解，则称此算法为好算法。 坏算法：若给定一问题，如果某算法使得：对于输入长度为n，至少要经过n的某指数函数次运算得到其解，则称此算法为坏算法。 如某问题的计算复杂度为2n ，则若某问题能在1小时完成2机器的100倍速度，则新机器在一小时内可处理 2n=2的办法解决问题的目的不能实现。 ８７ n0n0图2-36 ，现改进计算机为原 ×100，此时 n=n0+log2100 即计算机运算速度提高100倍，仅能增加7个参数长度，从而使我们试图用改进计算机