论文题目：
院 系：
专 业：
姓 名：
学 号：
指导教师：
完成时间：
数学科学学院 应用数学 王荣荣 02211044 郭爱萍 2005年5月16号
旅行推销员问题的几种解法
王荣荣
（包头师范学院数学科学学院）
摘要：通过提出“旅行推销员问题traveling salesman problem ”来介绍如何求解与生活
息息相关的机床运行问题。最优哈密顿回路是“旅行推销员问题”的最优解，也是机床运行问题的最佳选择。
关键词：旅行推销员问题，最优哈密顿回路，最优推销员回路。
KEY WORD ：traveling salesman problem ，optimum Hamilton circuit ，optimum salesman circuit.
中图分类号：O1
一个旅行推销员在返回他所在的城市之前，他要访遍上司安排他去的所有城市。我们如何能找到一条路线，使推销员以最小的总路程（或时间，旅费）访遍这些城市，最后再回到他所在的城市。这就是著名的“旅行推销员问题”。这个问题可以用图论语言说的更广义一些，“旅行推销员问题“就是在给定的连通加权图（G ，W ）。其中G 的顶点视为各个城市，城市间的航线视为边，权视为两个城市间的踞离，也可以视为时间或旅费。
旅行推销员问题我们在实际工作中和理论研究中经常会遇到。在此我选取一个比较典型又实用的例子来求其最优哈密顿回路。
例1:某一机械车间，每一工件可以不按顺序地但必须走遍n 台不同机床的每一台。记这n 台不同机床为v 1, v 2„v n . 然而，只要工件从机床v i 到机床v j 就需要调整时间t ij 。现在我要利用“旅行推销员问题“来确定每一工件走遍n 台不同机床的最快路线。
设连通加权无向图(G,W),即为本例的流程图。至少包含图G 中每一个顶点的一次的回路称之为推销员回路（salesman circuit），而包含图G 中每一个顶点只有一次的回路称之为哈密顿回路（Hamiltonian circuit ），具有最小总长度的推销员回路称之为最优推销员回路（optimum salesman circuit），而且也是一
般推销员问题的最优解。具有最小总长度的哈密顿回路称之为最优哈密顿回路（optimum Hamiltonian circuit），而且也是推销员问题的最优解。
最优推销员回路不一定是最优哈密顿回路。例如：见下面所示的图。这个图的唯一的哈密顿回路是（a ，b ），（b ，c ），（c ，a ），总长度等于1+20+1=22。而通过顶点a 点两次的最优推销员回路（a ，b ），（b ，a ），（a ，c ），（c ，a ）的总长度等于1+1+1+1=4。因此，最优推销员回路不一定是最优哈密顿。那什么情况下一般推销员问题的解才是哈密顿回路呢？
定理：如果图G 中每一对x ，y 都存在a （x ，y ）≤a （x ，z ）+a（z ，y ）（对所有z 不等于x ，z 不等于y ）(1) 那么哈密顿回路就是图G 一般推销员问题的最优解(如果存在的话) 。（参见《网络和图的最优化算》[美]E.米涅尔 著 李家滢 赵关旗 译）
从定理我们可以看出，如果图G 满足三角不等式，那么图G 推销员问题的最优解就是图G 一般推销员问题的最优解。但遗憾的是并不是所有的图都具有哈密顿回路。因此，我们应该确定所研究的图是否具有哈密顿回路。（更详尽的关于哈密顿回路存在条件的分析可以参阅伯奇（Berge ）1973专著）。
下面我采用一种数学建模中用过的方法来求解上面提出的关于机床运行的问题。
设n=5，5个不同的机床间调整时间用矩阵D 表示如下：
⎡∞5346⎤V 1 ⎢5∞2109⎥V 2 ⎢⎥V 3 D=(tij ) 5*5 =⎢32∞87⎥ ⎢⎥V 4 4108∞1⎢⎥V 5 ⎢⎥6971∞⎣⎦ V 1 V 2 V 3
V 4 V 5
其中t ij 表示v i 到v j 的调整时间。上面的矩阵是对称的，即从v i 到v j 的调
整时间等于从v j 到v i 的调整时间。（此方法也可用于非对称型矩阵）
每行抽取最小的元素，并令矩阵D 的每行的所有元素都减去该行的最小元素，得：
⎡∞2023⎤⎢3∞087⎥⎢⎥D 1=⎢10∞65⎥ ⎢⎥397∞0⎢⎥⎢⎣5860∞⎥⎦3 2 2 1 1
再用D 1各列的所有元素减去该列的最小元素，得：
⎡∞2023⎤⎢2∞087⎥⎢⎥D 2=⎢00∞65⎥ ⎢⎥297∞0⎢⎥⎢⎣4860∞⎥⎦10=3+2+2+1+1+1
重要的结论在于以D 为调整时间矩阵问题的解和以D 2为调整时间的解是一样的。每行的所有元素减去该行的最小元素，相当于从该行所对应的机床到其它不同机床的调整时间一律减少，减少的时间量是相同的。每列的所有元素减去该列的最小元素，可看做是该列所对应的机床到其它不同机床的调整时间一律减少，而且减少的时间量是相同的。工件进入每个机床一次且仅一次，而且从该机床出去一次，也仅有一次。最佳路径仍是减少调整时间后的最佳路径。这就证明了我们的结论，反正进出都一次。下面讨论以D 2为调整时间矩阵问题的解。D 2的特点是每行每列都有零元素至少一个。例如：从v 1出发必然选择v 3作为下一站，因t 13=0。在D 2矩阵中划去t 13元素所在的行和列，并将t 13改为∞，这样是为了避免出现v 1v 1的现象，这不符合问题的要求。消去第一行及第三列的原因在于每点进出仅一次。
V 2 ⎡2∞87⎤
V 3 ⎢∞065⎥⎢⎥D 3= V 4 ⎢29∞0⎥
V 5 ⎢⎥480∞10 ⎣⎦
V 1 V 2 V 4 V 5
在矩阵D 3中第一行无零元素出现，该行所有元素减去最小元素，得： V 2
V 3
V 4
V 5
⎡0∞65⎤⎢∞065⎥⎢⎥ ⎢29∞0⎥⎢⎥⎣480∞⎦12=10+2
V 1 V 2 V 4 V 5
V 3的下一站必然是选V 2了，因t 32=0，t 32所在的行和列去掉，t 32改为∞。同时t 21也改为∞，t 32改为∞是避免v 3，但t 21改为∞是为了避免v 1v 1，这也不符合旅行推销员问题的要求，得：
V 2 ⎡∞65⎤
V 4 ⎢2∞0⎥ D 4= ⎢⎥V 5 ⎢40∞⎥⎣⎦
V V V 1 4 5
同样D 4的第一行减去第一行的最小元素5，第一列也减去第一列的最小元素2，得：
V 2 ⎡∞10⎤⎢0∞0⎥ V 4 D 5= ⎢⎥V 5 ⎢⎣20∞⎥⎦19=12+5+2
V 1 V 4 V 5
V 2的下一站自然选V 5，依上述办法得：
V 4 ⎡0∞⎤ D6= V 5⎢∞0⎥ ⎣⎦19
V 1 V 4
故得一条路径v 132541，总调整时间为19是否为最佳呢？以开始时3为例，若不取v 3究竟如何呢？若封锁v 13，在D 2中令t 13=∞可得
⎡∞2∞23⎤⎢2∞087⎥⎢⎥D 7= ⎢00∞65⎥ ⎢⎥297∞0⎢⎥10 ⎢⎣4860∞⎥⎦
第一行减去该行的最小元素2，得：
V 1
V 2
V 3
V 4
V 5
⎡∞0∞01⎤⎢2∞087⎥⎢⎥⎢00∞65⎥ ⎢⎥297∞0⎢⎥12=10+2 ⎢⎣4860∞⎥⎦
12是它的界，即封锁v 13后调整时间的下界，而下界也比v 13的调整时间长，所以只能取3。依此方法，我们可知所求得的路径是最佳路径。
下面介绍另一种解决问题的方法：
设G=(V,A)表示我们所研究的图。我们可以用最小费用流算法求得图G 中最短哈密顿回路长度的下界L 1（最小费用流算法参见《网络和图的最优化算法》第102页）, 如果用最小费用流算法求得的流符合图G 的一个回路，那么这个回路就是一个最优哈密顿回路，同时也就解决了推销员问题。但是，在任意实际的图中，有可能最终流相对应于拆开的回路。选择这些回路中的一个回路，并把包含在这个回路中的所有顶点表示为Vc={v1,v 2, „v k }.
在一个最优解中，工件离开顶点v 1后, 或通过不在Vc 中的某个顶点，或通过Vc 中的某一顶点。当是后者情况时，在工件离开顶点v 2后，又有可能去不在Vc 中的另一个顶点，或去在Vc 中的另一个顶点，如此等等。所以最优解一定可以至少存在于下述各图的某一个图中。
1．图G 具有所有被删去的弧(v1,x),x ∈Vc
2．图G 具有所有被删去的弧(v2,x),x ∉Vc ，以及具有所有被删去的弧（v 2，y ），
y ∈Vc
3．图G 具有所有被删去的弧(v1,x),(v2,x),x ∉Vc ，以及具有所有被删去的弧
3∈ . .
。 。
。 。
k ．图G 具有所有被删去的弧(v1,x),(v2,x) „(vk-1),x ∉Vc ，以及具有所有被删去的弧（v k ，y ），y ∈Vc （注：删去一条弧等于给它一个无穷大的长度）
分别称上述各图为G 1,G 2„G k . 由于在每个带下标图G i 中一条弧的长度不会小于在图G 中相应弧的长度，在图G i 中的一个最优哈密顿回路长度也不可能小于图G 中的一个最优哈密顿回路的长度。而且, 图G 的一个最优解至少也是带下标的图G 1,G 2„G k 这些图的一个最优解。
其次，利用最小费用流算法求出每一个图G 1,G 2„G k 的一个最优哈密顿回路长度的下界。分别称每一个图所得的下界为L 1（G 1），L 1（G 2）„L 1（G k ）。 如果在某一个下标图Gc 中的最小费用流相对应于一个哈密顿回路时，我们就需要再往下考虑任何其它的L 1（G i ）≥L 1（Gc ）的下标图G j 。因为L 1（Gc ）已经是所需达到的下界。这样，我们就可以删去好几个下标图的研究。然后把剩下的不能删去的每一个下标图G i 重复上述过程并用图G i1，G i2„来代替, 计算每一个图G ij 的一个最优哈密顿回路长度的下界L 1(Gij ), 并如上一样, 再删去尽可能多的双下标图.
最终, 能够找到一个其中具有最短的哈密顿回路的图, 这个图将删去其它所有的图. 这个哈密顿回路就一定是原图G 的一个最短哈密顿回路.
由于这种方法是从原图向其它一些图上分支, 以及沿着每一条分支形成一个最优解的界限, 所以这种方法就称之为分支界限求解法(branch and bound solution technique).
下面举一个连通加权有向图的例子
例; 用分支界限求解法求解图G` 的最优哈密顿回路. 由于图G`较小我们立即可以看出, 对于图G`用最小费用流算法可以求出两个回路(V1,V 2),(V2,V 3),(V3,V 1) 与
6554461个回路, 利用顶点Vc={V1,V 2,V 3},我们可以得出如图G`所示的三个图Ga,Gb,Gc.
图Ga 是从图G`中删去从V 1到V 2或V 3的一切弧, 也即删去弧(V1,V 2) 所形成的图.
图Gb 是从图G`中删去所有从V 1到V 4,V 5,V 6和从V 2到V 1和V 3的弧所形成的图. 因此图Gb 就是图G`中删去弧(V1,V 4) 与(V2,V 3) 所形成的图.
图Gc 则是删去所有从V 1和V 2到V 4,V 5,V 6, 以及从V 3到V 1和V 2的弧后的图G`,也就是删去弧(V1,V 4),(V2,V 4) 与(V3,V 1) 后的图G`.
由于Ga,Gb 与Gc 较小, 我们能够立即看出:最小费用流算法可以得出下列回路:
图 回路 下界 L1 Ga (V1,V 4),(V4,V 6),(V6,V 5),(V5,V 2),(V2,V 3),(V3,V 1) L1(Ga)=21 Gb (V1,V 2),(V2, V5),(V5,V 4),(V4,V 6),(V6,V 3),(V3,V 1) L1(Gb)=12 Gc (V1,V 2),(V2, V3),(V3,V 6),(V6,V 5),(V5,V 4),(V4,V 1) L1(Gc)=16
图Gb 的最小费用流法求得长度等于12的哈密顿回路. 因而图Ga 与图Gc, 由于它们的下界都超过L 1(Gb)=12,所以进一步研究时就可以删去. 所以哈密顿回路(V1,V 2),(V2,V 5),(V5,V 4),(V4,V 6),(V6,V 3),(V3,V 1) 就是原图G`的一个最优哈密顿回路.
参考文献：
[1] [美]E.米涅卡 著，李家滢 赵关旗 译 网络和图的最优化算法[M].中国
铁道出版社
[2] 杨骅飞，王朝瑞 组合数学及其应用[M].北京理工大学出版社
[3] 徐俊明 图论及其应用[M].中国科学技术大学出版社
[4] 卜月华，吴建专 图论及其应用[M].中国科学技术大学出版社
[5] 范逢曦 图论方法及其应用[M].山西科技教育大学出版社
[6] [美]Fred Buckley 著，李慧霸 王风芹 译 图论简明教程[M].清华大学
出版社
论文题目：
院 系：
专 业：
姓 名：
学 号：
指导教师：
完成时间：
数学科学学院 应用数学 王荣荣 02211044 郭爱萍 2005年5月16号
旅行推销员问题的几种解法
王荣荣
（包头师范学院数学科学学院）
摘要：通过提出“旅行推销员问题traveling salesman problem ”来介绍如何求解与生活
息息相关的机床运行问题。最优哈密顿回路是“旅行推销员问题”的最优解，也是机床运行问题的最佳选择。
关键词：旅行推销员问题，最优哈密顿回路，最优推销员回路。
KEY WORD ：traveling salesman problem ，optimum Hamilton circuit ，optimum salesman circuit.
中图分类号：O1
一个旅行推销员在返回他所在的城市之前，他要访遍上司安排他去的所有城市。我们如何能找到一条路线，使推销员以最小的总路程（或时间，旅费）访遍这些城市，最后再回到他所在的城市。这就是著名的“旅行推销员问题”。这个问题可以用图论语言说的更广义一些，“旅行推销员问题“就是在给定的连通加权图（G ，W ）。其中G 的顶点视为各个城市，城市间的航线视为边，权视为两个城市间的踞离，也可以视为时间或旅费。
旅行推销员问题我们在实际工作中和理论研究中经常会遇到。在此我选取一个比较典型又实用的例子来求其最优哈密顿回路。
例1:某一机械车间，每一工件可以不按顺序地但必须走遍n 台不同机床的每一台。记这n 台不同机床为v 1, v 2„v n . 然而，只要工件从机床v i 到机床v j 就需要调整时间t ij 。现在我要利用“旅行推销员问题“来确定每一工件走遍n 台不同机床的最快路线。
设连通加权无向图(G,W),即为本例的流程图。至少包含图G 中每一个顶点的一次的回路称之为推销员回路（salesman circuit），而包含图G 中每一个顶点只有一次的回路称之为哈密顿回路（Hamiltonian circuit ），具有最小总长度的推销员回路称之为最优推销员回路（optimum salesman circuit），而且也是一
般推销员问题的最优解。具有最小总长度的哈密顿回路称之为最优哈密顿回路（optimum Hamiltonian circuit），而且也是推销员问题的最优解。
最优推销员回路不一定是最优哈密顿回路。例如：见下面所示的图。这个图的唯一的哈密顿回路是（a ，b ），（b ，c ），（c ，a ），总长度等于1+20+1=22。而通过顶点a 点两次的最优推销员回路（a ，b ），（b ，a ），（a ，c ），（c ，a ）的总长度等于1+1+1+1=4。因此，最优推销员回路不一定是最优哈密顿。那什么情况下一般推销员问题的解才是哈密顿回路呢？
定理：如果图G 中每一对x ，y 都存在a （x ，y ）≤a （x ，z ）+a（z ，y ）（对所有z 不等于x ，z 不等于y ）(1) 那么哈密顿回路就是图G 一般推销员问题的最优解(如果存在的话) 。（参见《网络和图的最优化算》[美]E.米涅尔 著 李家滢 赵关旗 译）
从定理我们可以看出，如果图G 满足三角不等式，那么图G 推销员问题的最优解就是图G 一般推销员问题的最优解。但遗憾的是并不是所有的图都具有哈密顿回路。因此，我们应该确定所研究的图是否具有哈密顿回路。（更详尽的关于哈密顿回路存在条件的分析可以参阅伯奇（Berge ）1973专著）。
下面我采用一种数学建模中用过的方法来求解上面提出的关于机床运行的问题。
设n=5，5个不同的机床间调整时间用矩阵D 表示如下：
⎡∞5346⎤V 1 ⎢5∞2109⎥V 2 ⎢⎥V 3 D=(tij ) 5*5 =⎢32∞87⎥ ⎢⎥V 4 4108∞1⎢⎥V 5 ⎢⎥6971∞⎣⎦ V 1 V 2 V 3
V 4 V 5
其中t ij 表示v i 到v j 的调整时间。上面的矩阵是对称的，即从v i 到v j 的调
整时间等于从v j 到v i 的调整时间。（此方法也可用于非对称型矩阵）
每行抽取最小的元素，并令矩阵D 的每行的所有元素都减去该行的最小元素，得：
⎡∞2023⎤⎢3∞087⎥⎢⎥D 1=⎢10∞65⎥ ⎢⎥397∞0⎢⎥⎢⎣5860∞⎥⎦3 2 2 1 1
再用D 1各列的所有元素减去该列的最小元素，得：
⎡∞2023⎤⎢2∞087⎥⎢⎥D 2=⎢00∞65⎥ ⎢⎥297∞0⎢⎥⎢⎣4860∞⎥⎦10=3+2+2+1+1+1
重要的结论在于以D 为调整时间矩阵问题的解和以D 2为调整时间的解是一样的。每行的所有元素减去该行的最小元素，相当于从该行所对应的机床到其它不同机床的调整时间一律减少，减少的时间量是相同的。每列的所有元素减去该列的最小元素，可看做是该列所对应的机床到其它不同机床的调整时间一律减少，而且减少的时间量是相同的。工件进入每个机床一次且仅一次，而且从该机床出去一次，也仅有一次。最佳路径仍是减少调整时间后的最佳路径。这就证明了我们的结论，反正进出都一次。下面讨论以D 2为调整时间矩阵问题的解。D 2的特点是每行每列都有零元素至少一个。例如：从v 1出发必然选择v 3作为下一站，因t 13=0。在D 2矩阵中划去t 13元素所在的行和列，并将t 13改为∞，这样是为了避免出现v 1v 1的现象，这不符合问题的要求。消去第一行及第三列的原因在于每点进出仅一次。
V 2 ⎡2∞87⎤
V 3 ⎢∞065⎥⎢⎥D 3= V 4 ⎢29∞0⎥
V 5 ⎢⎥480∞10 ⎣⎦
V 1 V 2 V 4 V 5
在矩阵D 3中第一行无零元素出现，该行所有元素减去最小元素，得： V 2
V 3
V 4
V 5
⎡0∞65⎤⎢∞065⎥⎢⎥ ⎢29∞0⎥⎢⎥⎣480∞⎦12=10+2
V 1 V 2 V 4 V 5
V 3的下一站必然是选V 2了，因t 32=0，t 32所在的行和列去掉，t 32改为∞。同时t 21也改为∞，t 32改为∞是避免v 3，但t 21改为∞是为了避免v 1v 1，这也不符合旅行推销员问题的要求，得：
V 2 ⎡∞65⎤
V 4 ⎢2∞0⎥ D 4= ⎢⎥V 5 ⎢40∞⎥⎣⎦
V V V 1 4 5
同样D 4的第一行减去第一行的最小元素5，第一列也减去第一列的最小元素2，得：
V 2 ⎡∞10⎤⎢0∞0⎥ V 4 D 5= ⎢⎥V 5 ⎢⎣20∞⎥⎦19=12+5+2
V 1 V 4 V 5
V 2的下一站自然选V 5，依上述办法得：
V 4 ⎡0∞⎤ D6= V 5⎢∞0⎥ ⎣⎦19
V 1 V 4
故得一条路径v 132541，总调整时间为19是否为最佳呢？以开始时3为例，若不取v 3究竟如何呢？若封锁v 13，在D 2中令t 13=∞可得
⎡∞2∞23⎤⎢2∞087⎥⎢⎥D 7= ⎢00∞65⎥ ⎢⎥297∞0⎢⎥10 ⎢⎣4860∞⎥⎦
第一行减去该行的最小元素2，得：
V 1
V 2
V 3
V 4
V 5
⎡∞0∞01⎤⎢2∞087⎥⎢⎥⎢00∞65⎥ ⎢⎥297∞0⎢⎥12=10+2 ⎢⎣4860∞⎥⎦
12是它的界，即封锁v 13后调整时间的下界，而下界也比v 13的调整时间长，所以只能取3。依此方法，我们可知所求得的路径是最佳路径。
下面介绍另一种解决问题的方法：
设G=(V,A)表示我们所研究的图。我们可以用最小费用流算法求得图G 中最短哈密顿回路长度的下界L 1（最小费用流算法参见《网络和图的最优化算法》第102页）, 如果用最小费用流算法求得的流符合图G 的一个回路，那么这个回路就是一个最优哈密顿回路，同时也就解决了推销员问题。但是，在任意实际的图中，有可能最终流相对应于拆开的回路。选择这些回路中的一个回路，并把包含在这个回路中的所有顶点表示为Vc={v1,v 2, „v k }.
在一个最优解中，工件离开顶点v 1后, 或通过不在Vc 中的某个顶点，或通过Vc 中的某一顶点。当是后者情况时，在工件离开顶点v 2后，又有可能去不在Vc 中的另一个顶点，或去在Vc 中的另一个顶点，如此等等。所以最优解一定可以至少存在于下述各图的某一个图中。
1．图G 具有所有被删去的弧(v1,x),x ∈Vc
2．图G 具有所有被删去的弧(v2,x),x ∉Vc ，以及具有所有被删去的弧（v 2，y ），
y ∈Vc
3．图G 具有所有被删去的弧(v1,x),(v2,x),x ∉Vc ，以及具有所有被删去的弧
3∈ . .
。 。
。 。
k ．图G 具有所有被删去的弧(v1,x),(v2,x) „(vk-1),x ∉Vc ，以及具有所有被删去的弧（v k ，y ），y ∈Vc （注：删去一条弧等于给它一个无穷大的长度）
分别称上述各图为G 1,G 2„G k . 由于在每个带下标图G i 中一条弧的长度不会小于在图G 中相应弧的长度，在图G i 中的一个最优哈密顿回路长度也不可能小于图G 中的一个最优哈密顿回路的长度。而且, 图G 的一个最优解至少也是带下标的图G 1,G 2„G k 这些图的一个最优解。
其次，利用最小费用流算法求出每一个图G 1,G 2„G k 的一个最优哈密顿回路长度的下界。分别称每一个图所得的下界为L 1（G 1），L 1（G 2）„L 1（G k ）。 如果在某一个下标图Gc 中的最小费用流相对应于一个哈密顿回路时，我们就需要再往下考虑任何其它的L 1（G i ）≥L 1（Gc ）的下标图G j 。因为L 1（Gc ）已经是所需达到的下界。这样，我们就可以删去好几个下标图的研究。然后把剩下的不能删去的每一个下标图G i 重复上述过程并用图G i1，G i2„来代替, 计算每一个图G ij 的一个最优哈密顿回路长度的下界L 1(Gij ), 并如上一样, 再删去尽可能多的双下标图.
最终, 能够找到一个其中具有最短的哈密顿回路的图, 这个图将删去其它所有的图. 这个哈密顿回路就一定是原图G 的一个最短哈密顿回路.
由于这种方法是从原图向其它一些图上分支, 以及沿着每一条分支形成一个最优解的界限, 所以这种方法就称之为分支界限求解法(branch and bound solution technique).
下面举一个连通加权有向图的例子
例; 用分支界限求解法求解图G` 的最优哈密顿回路. 由于图G`较小我们立即可以看出, 对于图G`用最小费用流算法可以求出两个回路(V1,V 2),(V2,V 3),(V3,V 1) 与
6554461个回路, 利用顶点Vc={V1,V 2,V 3},我们可以得出如图G`所示的三个图Ga,Gb,Gc.
图Ga 是从图G`中删去从V 1到V 2或V 3的一切弧, 也即删去弧(V1,V 2) 所形成的图.
图Gb 是从图G`中删去所有从V 1到V 4,V 5,V 6和从V 2到V 1和V 3的弧所形成的图. 因此图Gb 就是图G`中删去弧(V1,V 4) 与(V2,V 3) 所形成的图.
图Gc 则是删去所有从V 1和V 2到V 4,V 5,V 6, 以及从V 3到V 1和V 2的弧后的图G`,也就是删去弧(V1,V 4),(V2,V 4) 与(V3,V 1) 后的图G`.
由于Ga,Gb 与Gc 较小, 我们能够立即看出:最小费用流算法可以得出下列回路:
图 回路 下界 L1 Ga (V1,V 4),(V4,V 6),(V6,V 5),(V5,V 2),(V2,V 3),(V3,V 1) L1(Ga)=21 Gb (V1,V 2),(V2, V5),(V5,V 4),(V4,V 6),(V6,V 3),(V3,V 1) L1(Gb)=12 Gc (V1,V 2),(V2, V3),(V3,V 6),(V6,V 5),(V5,V 4),(V4,V 1) L1(Gc)=16
图Gb 的最小费用流法求得长度等于12的哈密顿回路. 因而图Ga 与图Gc, 由于它们的下界都超过L 1(Gb)=12,所以进一步研究时就可以删去. 所以哈密顿回路(V1,V 2),(V2,V 5),(V5,V 4),(V4,V 6),(V6,V 3),(V3,V 1) 就是原图G`的一个最优哈密顿回路.
参考文献：
[1] [美]E.米涅卡 著，李家滢 赵关旗 译 网络和图的最优化算法[M].中国
铁道出版社
[2] 杨骅飞，王朝瑞 组合数学及其应用[M].北京理工大学出版社
[3] 徐俊明 图论及其应用[M].中国科学技术大学出版社
[4] 卜月华，吴建专 图论及其应用[M].中国科学技术大学出版社
[5] 范逢曦 图论方法及其应用[M].山西科技教育大学出版社
[6] [美]Fred Buckley 著，李慧霸 王风芹 译 图论简明教程[M].清华大学
出版社