关于图的H圈H通路

1、关于图的H圈H通路陈业德（江西制造职业技术学院 330095） 摘要 本文给出了在图对应的矩阵上进行H圈变换和单向H通路变换，获得了图的最优H圈的充要条件，并给出了求最优H圈、最优H通路及最优单向H通路的计算方法。提供了一种实用的解“货郎担问题”和“排序问题”的有效方法。关键词 H圈变换 基本不等式 舍补法 最优H圈（货郎担问题） 最优H通路最优H通路不等式 单向H通路变换 最优单向H通路（排序问题） 自1859年，爱尔兰数学家Hamilton提出周游世界20个城市以来，图论中就有了H圈、H通路问题，如一个简单图是否有H圈，是否有H通路?如何求最优H圈，最优H通路及最优单向H通路等？直到目前都

2、没有一个有效的解决办法，成了图论中的难题。目前使用的枚举法、路线修改法都无济于事，解决不了实际问题。本文给出在图对应的矩阵上进行H圈变换，对解决这些问题取得了较理想的结果。一 图的矩阵表示设G是P个顶点的简单连通无向图（以下都讨论这种图）。联接i j两顶点的边，用表示。当G赋权后，ei j 也表示此边上的权。若i j两点间没有边，用X表示，理解此边是一个很大的数。这样任何一个图都可以看成是一个完全图（用KP表示）。当图的顶点标定后，图G可以用一个上三角形矩阵表示。此矩阵与代数图论中的矩阵都不同，更无一般矩阵的性质。e i j称为矩阵的元素，i为行，j为列。脚码含i的元素称为矩阵的第i行列元素（

3、实为过第i个顶点的边）。这种矩阵称为图对应的矩阵。例如（K6）对应的矩阵为： 图一（K6）矩阵对角线及右上角元素比较重要，统称为对角线元素。K6对应矩阵对角线元素为e 12 e 23 e 34 e 45 e 56 e 16 ；第三行列元素为e 13 e 23 e 34 e 35 e 36。二 图的H圈变换图G中由不同顶点不同边构成的圈称为初等圈（也称回路）。包含所有顶点的初等圈称为Hamilton圈，简称为H圈。若图G对应矩阵的对角线上都是非X元素，则这些元素构成图G的一个H圈。此时图G对应的矩阵，也称为该H圈对应的矩阵。例如K6对应的矩阵也就是H圈1-2-3-4-5-6-1对应的矩阵。又如K

4、6 中H圈1-5-2-4-3-6-1对应的矩阵为：其实这都是按H圈顺序写出的矩阵。定义 设Q是G的一个H圈，用非Q上的m条边替换Q上的m条边，若能得到一个新的H圈，则称这一过程是图G的一个m元H圈变换，简称为m元H圈变换。这种m元H圈变换，在图对应的矩阵上进行，可以看成是用m个非对角线上的元素替换对角线上的m个元素，变换一次得一个新矩阵，对角线上得一个新H圈，新H圈与新矩阵1-1对应。这种H圈变换在Kp对应的矩阵上进行，仅用非对角线上元素替换对角线上元素，就有1/2（P-1）！1 个。三 在矩阵上进行二元H圈变换设Kp对应矩阵为A，则 e12 e13e1ie1i+1 e1je1j+1 e1pe

5、i-1i eii+1 eijeij+1 eip ei+1i+2ei+1jei+1j+1 ei+1pA = ej-1j ejj+1ejp ej+1j+2 ej+1pep-1p1 在A上，用非对角线上元素e i j e i +1 j+1 （i=1 2p-2，j=3 4p）替换对角线上元素e i i +1 e j j +1是一个二元H圈变换(替换元素下打点，被替换元素下划横线，以下同)。设变换后新矩阵为B，则B对角线上元素构成的H圈就是变换后的新H圈。2 在A上，用非对角线上元素e 1 i+1 e i p （i=2 3p-2）替换对角线上元素e 1 p e i i+1也是一个二元H圈变换。设变换后新

6、矩阵为C，则C对角线上元素构成的H圈就是变换后的新H圈。 由A变成B记为AB，由A变成C记为AC，它们都统称为图G的二元H圈变换。由AB具体这样进行：将A的矩形块e1 i+1 ei i+1 ei j e1j列序颠倒，矩形块e i+1 j+1 ej j+1 ej p ei+1 p行序颠倒，三角块e i+1 i+2 ej-1 j ei+1 j的元素作关于斜边高的对称调换，其他元素不动，得矩阵B。由AC具体这样进行：将A的矩形块e1 i+1 ei i+1 e i p e1p列序颠倒，三角块e i+1 i+2 ep-1 p ei+1 p作关于斜边高的对称调换，其他元素不动，得矩阵C。这种矩阵上的二元H

7、圈变换具有如下性质：性质1 在图对应的矩阵上进行二元H圈变换时，矩阵对角线上未被替换的元素，经过变换后，仍在对角线上。性质2 图的二元H圈变换可以在图对应的矩阵上连续进行，变换一次得一个新矩阵，对角线上得一个新H圈，新矩阵与新H圈一一对应。性质3 图对应矩阵中有X元素，X元素也可以进行H圈变换，X元与非X元一样对待。以上性质明显成立。性质4 若图G有H圈，则它的任一个H圈都可以变换到矩阵的对角线上。性质5 图的任一个m元H圈变换（m3）都可以在图对应的矩阵上连续用不超过m个二元H圈变换实现。四 基本H圈变换图的三元及三元以上的H圈变换与二元H圈变换一样，可以在图对应的矩阵上进行，也有类似性质，

8、但都比较复杂。三元及三元以上的H圈变换，一般采用以下方法进行：先找出变换后所得的新H圈，再写出新H圈对应的矩阵，即为变换后所得新矩阵。图的m（m3）元H圈变换虽然复杂，但大多数m元H圈变换是由几个低元H圈变换合成的。例如K7中用e14 e57 e37 e26 e16替换H圈1-2-3-4-5-6-7-1中的e12 e34 e56 e67 e17 是一个五元H圈变换，但它是由一个二元H圈变换（用e16 e57 替换H圈1-2-3-4-5-6-7-1中的e56 e17 ）和一个三元H圈变换（用e14 e 26 e 37 替换H圈1-2-3-4-5-6-7-1中的e12 e 34 e 67）合成的。

9、我们称这种H圈变换是合成的H圈变换，否则称为是基本的H圈变换。一个H圈变换如能分解成几个低元的H圈变换，则这个H圈变换是合成的，否则是基本的H圈变换。显然二、三元H圈变换都是基本H圈变换。进一步研究发现：对m元（m3）H圈变换，当m较大时，大部分m元H圈变换是合成的，而基本H圈变换随着m的增大急剧减少。五 H图若图G含有H圈，则称G是一个Hamilton图，简称H图。若图G对应矩阵的对角线上无X元，则G是一个H图。一个图是否是H图，到目前为止还没有一个好的判别方法。这里仅从H圈变换考虑这个问题。定理 G是H图的充要条件是G对应的矩阵经过若干次H圈变换后，对角线上无X元。证明 >若G是H图

10、，则G至少有一个H圈。由H圈变换性质，通过H圈变换可以把此H圈变换到矩阵的对角线上，即经过若干次H圈变换后，矩阵对角线上无X元。 < 如果经过若干次H圈变换后，矩阵对角线上无X元，则对角线上元素构成G的一个H圈。G有H圈，所以G是H图。定理中的若干次H圈变换，主要是把非对角线上的非X元变换到对角线上，同时把对角线上的X元调出。例1：问图二是否是H图？ 图 二解 写出图二对应的矩阵A，对A进行以下二个二元H圈变换，最后矩阵对角线上无X元，所以图二是一个H图。并得到它的一个H圈1-2-4-5-6-3-7-1。变换如下：从最后一个矩阵还知道，用e14 e 26 e23替换对角线上的e12 e

11、24 e36是一个三元H圈变换，所以还可以得图二的另一个H圈1-4-5-6-2-3-7-1。一般说，若G有H圈，经过多次H圈变换，总可以把它的H圈变换到矩阵的对角线上。如果经过多次H圈变换后，矩阵对角线上仍有X元，则此图很可能就是非H图。六 最优H圈设G是一个赋权的H图，G中边权和最小的H圈称为图G的最优H圈，也称为对应矩阵的最优H圈。关于最优H圈，有下列几个定理。1 定理二（简化定理） 图G中，过第i个顶点的每条边减一个数a（可正可负）,图G的最优H圈不变，其边权和减2a。证明 因为图的每一个H圈都要经过第i个顶点一次，当过第i个顶点的每条边减一个数a时，G的每个H圈边权和都要减2a，所以G

12、的最优H圈不变，最优H圈边权和也减2a。G的第i个顶点的每条边减a，等于图对应矩阵的第i行列每个元素都减a，反之也对。由此可把G对应的矩阵简化，矩阵简化后，最优H圈没有变化。2 最优H圈的必要条件定理三 图G的H圈1-2-3-P-1为最优H圈的必要条件是下列个不等式ei i+1 + ej j+1 ei j + ei+1 j+1 （ I ）成立。其中当i、j =P时， i+1、j+1看成是1。证明：因为用ei j 、 ei+1 j+1 替换H圈1-2-3-P-1中的ei i+1 、ej j+1 是一个二元H圈变换，得H圈12ij（j-1）（i+1）（j+1）P1。又因为H圈1-2-3-P-1是最

13、优的，所以e12 + e23+e1 p e12+ e i-1 i+ e i j +e i+1 j+1+ e 1 p，两边减去公共边得ei i+1 + ej j+1 ei j+ei+1 j+1。定理中的不等式在矩阵上检查十分方便，满足不等式（I）的H圈是较优的H圈。同理若用e r1r2 e r2 r3 e r3r4 替换最优H圈1-2-3-P-1中的ei i+1 ej j+1 ek k+1 是一个三元H圈变换，则有不等式ei i+1 +ej j+1 +ek k+1 e r1r2 + e r2 r3 + e r3r4 （II）成立。其中当 i 、j 、k =p 时，i+1 、j+1 、k+1看成1

14、。这组不等式共有个（P>3），在图对应的矩阵上检查也有规律，也很方便。这样图G的H圈1-2-3-P-1为最优H圈的必要条件是不等式组（）（）同时成立。同理作m（m4）元H圈变换，还可以得到更强的必要条件。3 基本不等式及最优H圈的充要条件 基本不等式设H圈1-2-3-P-1是图G的最优H圈，若用不在此H圈上的m（m>3）条边 e r1r2 e r2 r3 e rmrm+1 替换最优H圈上的m条边ei i+1 ej j+1 e k k+1 是一个m元H圈变换,则同理有不等式: ei i+1 +ej j+1 +e k k+1 e r1r2 +e r2 r3 + +e rmrm+1 ()

15、成立。若此m元H圈变换是基本H圈变换，则称此不等式()是此m元H圈变换所对应的m元基本不等式。否则此不等式是多余的，这是因为它可以由低元基本不等式相加得到。显然（）（）都是基本不等式。 最优H圈的充要条件定理四 图G的H圈1-2-3-P-1（记为Q*）为最优H圈的充要条件是所有m（m=2 3p）元基本不等式成立。证明 >上述已证明。< 设H圈r1-r2-rp-r1 是G的任一个H圈（记为Q），由Q变换成Q*满足基本不等式，找出Q*与Q的公共边。若由Q变换成Q*是基本H圈变换，则由其对应的基本不等式，两边再加上公共边，有以下不等式成立： e12 + e23+e1p e r1r2 +

16、e r2 r3 + +e rpr1 （） 若由Q变换成Q*不是基本H圈变换，则此H圈变换可由几个低元基本H圈变换合成，这时不等式（）可由这几个低元基本H圈变换所对应的基本不等式相加，两边再加上公共边而得到。所以（）总是成立的，故Q*是最优H圈。4 最优H圈的充分条件定理五 设图G对应的矩阵为A，利用简化定理对A充分简化得矩阵B。若矩阵B对角线上元素都0，而非对角线上元素都0，则矩阵A对角线上元素构成图G的最优H圈。证明 由矩阵B满足的条件知，矩阵B所有基本不等式都满足，矩阵B对角线上元素构成B的最优H圈，又简化不改变最优H圈，矩阵B的最优H圈就是矩阵A的最优H圈。故矩阵A对角线上元素构成图G的

17、最优H圈。七 求最优H圈设G是一个赋权的H图，如何求它的最优H圈？这一问题到目前为止还没有一个好的计算方法。作为H圈变换的应用，下面给出两种比较实用的计算方法。方法一 用H圈变换求最优H圈1 写出图G对应的矩阵A；2 对矩阵A进行一系列H圈变换（主要是二元H圈变换简单，少数三元H圈变换，三元以上的H圈变换复杂，且绝大多数是合成的，其速度也不如二三元H圈变换快，所以不用），把非对角线上的边权和小的元素变换到对角线上，同时把对角线上的边权和大的元素调出。被替换元素之和与替换元素之和的差称为变换差。按变换差大小，从大到小，逐次变换。变换一次使对角线上元素边权和减少一次，直到对角线上元素边权和不能减少

18、为止。每变换一次，在矩阵上边同时写出新的与第一行列元素对应的H圈，即矩阵对角线上元素构成的H圈(有利于元素脚码的检查)。这样最后所得矩阵对角线上元素构成的H圈，虽然不能肯定是最优H圈，但至少是较优的。为了求得更优的H圈，可以从不同矩阵（即变换过程中所得矩阵）开始，重复上述过程，比较每次结果，选取最优者。3 对最后所得矩阵B，用简化定理充分简化得矩阵C。若矩阵C对角线上元素都0，而非对角线上元素都0，则矩阵B对角线上元素构成图G的最优H圈。若矩阵C对角线上个别元素，则在非对角线上找出比小的元素。这些元素中脚码含i、j的元素与剩下的元素，若不能构成更优的H圈变换，则矩阵B对角线上的元素仍然构成图G

19、的最优H圈；若能构成更优的H圈变换，则进行H圈变换。对变换后所得矩阵重复上述步骤，简化、检查，直到求出图G的最优H圈。例2 已知K9边权由下表给出，用H圈变换，求K9的最优H圈。 eij j i 2 3 4 5 6 7 8 912345678 9 4 2 3 1 6 5 77 6 3 8 5 3 6 1 7 8 6 2 5 4 3 6 1 7 2 9 7 2 3 8 4 5 3 2解：写出K9对应的矩阵A；按变换差大小，从大到小，对A进行下列二元H圈变换，得矩阵B。对矩阵B充分简化得矩阵C。 1-2- 3 - 4 - 5 - 6 - 7 - 8 -9 1- 4 -3 - 2 - 5 - 6 -

20、 7 - 8 9 1 - 4 -3 - 2 - 5 - 9 - 8 -7 - 6 1-4- 3 - 8 - 9 - 5 - 2 - 7 -6 1- 4 - 3 - 8 - 2 - 5 - 9 - 7 -6 矩阵C对角线上元素都0，而非对角线上元素都0，所以矩阵B对角线上元素构成K9的最优H圈。对角线元素是e14（2）e34（1） e38（2） e28（3） e25（3） e59（2） e79（3） e67（3） e16（1），所以最优H圈为1-4-3-8-2-5-9-7-6-1，其边权和为S=20。方法二 用舍补法求最优H圈1 写出图G对应的矩阵A2 在A的每个行列选二个最小元素，遇相等元素，

21、优先选取所在行列小元素都比较大的那个，要么都选。被选元素底下划横线。3 用下列舍补法，在n个被选元中，选取P个位于不同行列的元素。舍补法：若i、j 两行列都有二个以上的被选元，设 ei k el j是被选元，则选择k、l，舍去ei k el j ，补回未选元el k （舍去元素划圈，补回元素底下划横线，下同），并使（称为舍补差）最大。还有两个特殊情况： 当j=i 时，第 i 行列至少有四个被选元，设e k i e l i 是被选元，则选择k、l ，舍去e k i e l i，补回未选元ek l ，并使舍补差e k i +el i e k l 最大。当k=j、l=i 时，舍补元都是ei j ，舍

22、补差也是ei j ，这时ei j 实际是i、j 二行列的公共被选元。这时按ei j 的大小，由大到小可直接舍去。舍去这样一个公共被选元，就做了一次舍补。做以上舍补在矩阵上进行很方便。做舍补时要从较大的被选元开始找舍补，按舍补差大小，从大到小逐个进行。遇到某行列有几个舍补差相等的舍补时，一般优先做所在行列小元素比较多的那个（最好按不同顺序都做一做，选取最好结果）。做一次舍补，减少一个被选元，做完（n-p）个舍补，最后剩下位于不同行列的P个被选元。4 写出这P个被选元的脚码。若这些脚码形成一个循环，则这P个被选元就构成图G的一个H圈；若形成二个或二个以上的小循环，则调整最后一二个舍补差小，且与各小

23、循环元素有关的舍补。要是用调整舍补难于找到H圈，则在两个小循环中各选一个较大的被选元ei j 、ek l ，选择i、j、k、l ，舍去ei j 、ek l ，补回ei l 、ek j ，并使（ei j+ek l）（ei l +ek j）最大。这样做一二次，就能找到图G的一个H圈。5 以上找到的H圈肯定是G的一个较优H圈，是否是最优的H圈？只要写出此H圈对应的矩阵B，和方法一中的B一样简化，检查，最后可求得图G的最优H圈。例2 已知K10边权由下表给出，用舍补法求K10的最优H圈 eij j i 2 3 4 5 6 7 8 9 10123456789 9 8 6 1 2 4 3 5 72 6 7

24、 8 9 4 2 1 8 6 2 3 9 4 5 3 2 6 5 7 3 8 9 7 2 1 4 6 5 3 9 7 2 8 6 7解 写出K10对应的矩阵A； 在A上每行列选二个最小元素（相同者都选）；按舍补差大小，从大到小：舍去e4 10(3) e16(2) e23(2) , 舍去e28(4) e45(3)补回e48(5),再舍去e5 10(1) ，最后剩下10个被选元：e15(1) e18(3) e29(2) e2 10(1) e36(2) e37(3) e46(2) e48(5) e59(2) e7 10(2) 这些元素的脚码恰好形成一个循环，所以这些元素构成K10的一个H圈：1-5-

25、9-2-10-7-3-6-4-8-1。写出此H圈对应矩阵B。对B充分简化得矩阵C。矩阵C对角线上元素都0，而非对角线上的元素都0，所以矩阵B对角线上元素构成图G的最优H圈，所以最优H圈为1-5-9-2-10-7-3-6-4-8-1。其边权和S=23。八 应用设G是一个H图。如果边权表示路程，则最优H圈就是路程最短的路线，即我们中国的货郎担问题；如果边权表示时间，则最优H圈就是所费时间最少的路线；如果边权表示费用，则最优H圈就是费用最省的路线。这些问题都要会求图的最优H圈，即边权和最小的H圈。它在运输、线路建设、工程排序等问题中，都有广泛应用。另一方面，在运输问题中，若边权ei j 表示i、j

26、两地之间的运营收入，则要求的H圈就是运营收入最大的路线。这就要求边权和最大的H圈。求边权和最大的H圈与求边权和最小的H圈思路和方法都是一样的，但计算时要把大改成小，把小改成大。通过下例，介绍求图的边权和最大H圈的方法。例4 一辆公共汽车每天要跑8个乡镇各一次，最后回到出发地。根据以往经验，运营一次，每两个乡镇之间的运营收入见下表（单位元）。问这辆公交车应走怎样的线路，运营收入最大？eij j i 2 3 4 5 6 7 81234567 20 90 70 30 60 50 1060 90 80 20 70 30 20 50 40 0 60 90 0 20 70 60 30 90 70 20 6

27、0解 以各乡镇为顶点，运营收入为边权，划出图G（略），这一问题就变成了求图G边权和最大的H圈。下面也用二种方法计算。方法一 H圈变换法写出G对应的矩阵A；按变换差大小，从小到大对A进行下列二元H圈变换，把非对角线上边权和大的元素变换到对角线上，同时把对角线上边权和小的元素调出，直到没有更优的H圈变换为止，得矩阵B。对B充分简化得矩阵C。 矩阵C对角线上元素都0，而非对角线上的元素都0，所以矩阵B对角线上元素构成图G边权和最大的H圈。对角线元素为e13(90) e38(60) e58(90) e45(90) e24(90) e27(70) e67(70) e16(60) ，所以边权和最大的H圈为

28、1-3-8-5-4-2-7-6-1。方法二 舍补法写出图G对应的矩阵A每行列选二个最大元素（相同者都选）；按舍补差由小到大：舍去e23(60) e56(60) e14(70) e48(70) e25(80) ，剩下8个被选元：e16(60) e13(90) e24(90) e27(70) e38(60) e45(90) e58(90) e67(70)。它们恰好构成图G的一个H圈1-3-8-5-4-2-7-6-1。写出此H圈对应的矩阵B，矩阵B与方法一中的矩阵B完全一样。与方法一一样检查，知H圈1-3-8-5-4-2-7-6-1就是图G的边权和最大的H圈。故这辆公交车应选择的路线为1-3-8-5

29、-4-2-7-6-1。运营一次最大收入为S=620（元）。九 最优H通路图G中包含所有顶点，且每个顶点只通过一次的通路称为Hamilton通路，简称H通路。边权和最小的H通路称为最优H通路。图G是否有H通路？如何求最优H通路？这两个问题至今也没有好的解决方法。下面介绍解决这两个问题的一些有效而实用的方法。1 H通路图G是否有H通路？写出G对应的矩阵A，与求G是否为H图一样，对A进行一系列H圈变换，把非X元变换到对角线上，同时把对角线上的X元调出。经过多次H圈变换后： 若矩阵对角线上还有二个或二个以上的X元，则图G很可能没有H通路； 若矩阵对角线上只有一个X元，则对角线上元素构成G的一条H通路；

30、 若矩阵对角线上无X元，则G有H圈，当然就有H通路。这是因为H圈去掉一条边就是一条H通路。2 最优H通路不等式设图G对应的矩阵为A，对角线上无X元，对角线上最大元素为e*。 若用非对角线上元素e r1r2 e s1s2替换对角线上元素ei i+1 ej j+1 是二元H圈变换，当e r1r2e s1s2 时，且满足不等式：ei i+1 +ej j+1 e r1r2 > e* ( 其中当ij=p 时， i+1 j+1看成1)，则此二元H圈变换可使矩阵A对角线上元素（除e*）构成的H通路更优； 同样，若用非对角线上元素e r1r2 e s1s2 e t1t2 替换对角线上元素 ei i+1

31、ej j+1 ek k+1是一个三元H圈变换，当e r1r2 et1 t2 ，e s1s2et1 t2 时，且满足不等式：（ei i+1 +ej j+1 + e k k+1）( e r1r2+ e s1s2)> e* (其中当ij k=p时，i+1 j+1 k+1看成是1)，则此三元H圈变换也可使矩阵A对角线上元素（除e*）构成的H通路更优。同样还有很多类似的不等式，我们把这些不等式的相反不等式，统称为图G（或矩阵A）的最优H通路不等式。这些不等式在矩阵上检查方便。进一步研究表明，若矩阵A（除e*）无更优的H圈变换，且所有的最优H通路不等式都成立，则矩阵A对角线上元素（除e*）就构成图G

32、的最优H通路。3 设图G有H通路，如何求它的最优H通路？下面也介绍二种方法。方法一 用H圈变换求最优H通路 写出图G对应的矩阵A； 按变换差大小，从大到小对矩阵A进行一系列H圈变换，把非对角线上边权和最小的元素变换到对角线上，同时把对角线上边权和大的元素调出，直到没有更优的H圈变换，最后得矩阵B； 用最优H通路不等式，对矩阵B进行检查。若矩阵B对角线上无X元，最优H通路不等式都成立，则矩阵B对角线上元素（除e*）就构成图G的最优H通路；若最优H通路不等式中的某一个不等式不成立，则作相应的H圈变换得矩阵C。检查矩阵C（除e*）是否有更优的H圈变换，若有则变换，若无则与矩阵B一样，用最优H通路不等

33、式检查矩阵C。通过检查、变换、再检查，最后可求得图G的最优H通路。若对角线上有X元，则把所有X元都看成是同一个很大的数，与无X元一样进行计算。方法二 用舍补法求最优H通路 写出图G对应的矩阵A 与用舍补法求G的最优H圈一样进行，只要把最后一个舍补不做，改为舍去所在行列的二个（每行列一个）最大被选元素。 若剩下的（P-1）个被选元构成H通路，则此H通路就是G的一条较优H通路；若不构成H通路，则调整最后二个被舍去的元素，也同样可得G的较优H通路。 把所得H通路两端联起来，得一个H圈。写出此H圈对应的矩阵B，与方法一中的矩阵B一样检查、变换、再检查，最后可求得G的最优H通路。下面看一个例题：例5 已

34、知K7的边权如下，求K7的最优H通路。eij j i 2 3 4 5 6 7123456 10 20 3 6 9 44 2 3 6 8 7 9 14 9 1 8 10 5 1 2解 下面用两种方法求解方法一 用H圈变换求最优H通路写出K7对应的矩阵A，对A进行二元H圈变换得矩阵B： 对矩阵B检查知：矩阵B对角线上元素构成K7的最优H圈。用最优H通路不等式检查，发现 所以作二元H圈变换（用替换）得矩阵C。再检查C发现，所以作三元H圈变换（用 替换 ）得矩阵D。检查D，发现有更优的H圈变换（用替换）得矩阵E。检查E，除e*(20)无更优的H圈变换，最优H通路不等式都成立，所以矩阵E对角线上元素（除

35、e*(20)）构成K7的最优H通路。这些元素是e23(4) e26(6) e67(2) e57(1) e45(1) e14(3) ，它们构成的H通路为3-2-6-7-5-4-1。所以K7的最优H通路为3-2-6-7-5-4-1，其路长W=17。方法二 用舍补法求最优H通路写出K7对应的矩阵A，每行列选二个最小元素，按舍补差大小，由大到小，舍去e25(3)，再舍去e24(2) e56(5)补回e26(6)。最后一个舍补不做，直接舍去所在行列两个最大被选元 ，最后剩下6个被选元：，它们恰好构成H通路3-2-6-7-5-4-1。联此H通路两端点1、3，得H圈1-3-2-6-7-5-4-1。它们对应的

36、矩阵恰好是方法一中的矩阵E。与方法一一样检查，知H通路3-2-6-7-5-4-1为K7的最优H通路，其路长W=17。另外，最大H通路在实践中也有应用。如何求最大H通路？求最大H通路与求最优H通路的思路和方法都是一样的，但计算时，要把大改小，小改大。具体如何计算在此就不累赘了。十 最优单向H通路（一）竞赛图的矩阵表示及最优单向H通路 设图G是简单有向连通图（即有向完全图，也称竞赛图，以下都讨论这种图），其顶点用1 2 P 标定后，i与j两顶点之间的边权用表示，当方向为时就用表示，当方向为时，则用表示。这样一个竞赛图就可以用一个上三角形矩阵表示，且一个竞赛图就对应一个矩阵。如图三对应矩阵为： 图

37、三连接图G中几个顶点的路称为通路。如果通路是单向的，称为单向通路。连接所有顶点的单向通路，称为Hamilton单向通路，简称为单向H通路。（以下通路、单向通路、单向H通路、单向H圈分别用W 表示，请注意与向量的区别）。边权和最小的称为最优。一个竞赛图是否有，1934年Redei已证明：一个竞赛图必有。但如何求最优， 到目前为止还没有一个有效的计算方法，而在实践中（如排序问题等）又经常要用到。下面介绍一个有效而实用的方法。（二） 变换设G是p个顶点的竞赛图，对应矩阵为A，对角线上元素（除）已构成。则：1在矩阵A中，若 构成， 也构成（当j=p时只要求 构成）；则用替换对角线上的元素 后，对角线上

38、元素构成一条新的。设新的对应矩阵为B（实际是此把两端连接所得H圈对应的矩阵）则把A变换成B称为图G的变换(I)，记为。具体如下进行：在A中，三角块(1)不动，将矩形块(1)(2)位置对换，三角块(2)(3)位置对换，矩形块(3)转置，得矩阵B。2. 同样在矩阵A中，若 构成， 也构成（当i=1时，只要求 构成），则用 替换对角线上的元素 （都是所在行列对角线上元素，以上也同）后，对角线上元素也构成一条新的。设新的对应矩阵为C，则把A变换成C称为图G的变换()，记为。具体如下进行：在A中，将三角块(1)(2)位置对换，矩形块(1)转置，矩形块(2)(3)位置对换，三角块(3)不动，得矩阵C。变换

39、()与变换()是对称的。以上两种变换看上去都是二元变换，实际上都是三元H圈变换，只是把通路两端连接的边省去没有考虑。二元H圈变换除个别外都不能成为变换。但大多数三元H圈变换都可能成为三元变换，因此应该熟悉三元H圈变换。特别是这些元素()作三元H圈变换，都可能成为变换。变换首先必须是H圈变换，三元或三元以上的H圈变换能否成为相对应的变换，只要检查被替换后对角线上元素的脚码是否能构成一条。若能构成，则此H圈变换就是变换。写出新对应的矩阵，即为变换后所得新矩阵。（三）求最优 如何求赋权竞赛图G的最优？可按以下步骤进行。 1. 写出图G对应的矩阵A 2. 在A上找一条初始（从矩阵A左上方开始，元素脚码

40、追踪，左右相联，边追边记，不重复；不全就反向追踪没有出现的脚码；还不全就修正路线，直到全部脚码出现，即可得一。）并写出此对应的矩阵B，而此就在矩阵B的对角线上。 3. 对矩阵B进行一系列变换，（变换时矩阵上面同时写出与矩阵对应，也与矩阵最上行列元素对应的，有利于检查元素脚码和），把边权和小的元素调到对角线上，同时把对角线上边权和大的元素调出，按变换差（被替换元与替换元边权和之差）大小，从大到小逐个进行。若中途遇对角线上元素构成，则去掉对角线上最大元素，得一新的， 并写出此所对应的矩阵，继续进行变化。变换一次矩阵对角线上元素（除右上角元素）边权和减少一次，直到不能减少为止，得最后矩阵。（注意从不

41、同的初始进行，结果可能不一样，所以中途应选几个不同的变换进行，比较每次结果。选取最优者。）这时最后矩阵对角线上元素（除右上角元素）构成的虽然不能肯定是最优， 但一定是较优。 4. 最后矩阵对角线上元素构成的是否是最优，与检查最优H圈一样，充分简化最后所得矩阵。若简化后的矩阵对角线上元素（除右上角元素都，而非对角线上元素都，则最后矩阵对角线上元素构成的（即矩阵上的）是最优。若最后矩阵对角线元素构成，则还应该用最优H通路不等式检查。否则在简化后的矩阵上再寻找更优的三元及三元以上的变换，直到得出最优为止。下面看一个实例。例6 （排序问题）有一台数控机床必须加工九种不同零件。加工零件后，再加工零件，中

42、间需有间歇时间（要调整设备夹具、准备刀具、编写程序等），设间歇时间为（表示加工零件后再加工零件中间所需间歇时间，时，取时间短的，时间长的舍去）各零件加工转换具体间歇时间见下表（单位：小时），问怎样安排加工顺序，使总间歇时间最短？tij BjBi 解：以表示顶点i，表示边权，则加工不同零件之间的间歇时间和顺序可用一个竞赛图G表示(G不必划出)，这样本问题就转化为求竞赛图G的最优。具体这样进行：写出图G对应的矩阵A(见下面)；在矩阵A中找到再反向找到，这些元素构成初始,写出此所对应的矩阵B； 73 1 2 4 5 6 8 9= 检查B（从小元素开始，下同）：构成，也构成（这些元素的脚码和都由矩阵上

43、面的确定，下同）所以用替换对角线上元素作变换()得矩阵C； 73 1 2 5 6 8 9 4 25 6 8 7 3 1 9 4检查C：构成，也构成，所以用替换对角线上元素作变换()，得矩阵D；检查D：知道用替换对角线上的是三元H圈变换，且对角线上元素的脚码25, 56, 68, 87, 73, 31, 19, 94中的56, 73, 31被替换元素的脚码53, 36, 71替换后，对角线上元素脚码为25, 53, 36, 68, 87, 71, 19, 94，它们构成一条：，写出此对应的矩阵E；检查矩阵E没有找到更优变换。对矩阵E充分简化得矩阵F。25 3 6 8 7 1 9 4 矩阵F对角线

44、上的元素（除右上角）都，而非对角线上元素都，所以矩阵E对角线上元素（除右上角）构成图G的最优（即矩阵E上面的），因此图G的最优为。故最优加工顺序为。总间歇时间为17小时。十一 竞赛图的最优1、关于一个竞赛图一定有，但不一定有，一个竞赛图是否有，各书有不同论述，但最明显的是：若一个竞赛图某顶点的出度（或入度）为零，则此竞赛图一定没有，这是因为从这点起出不去（或回不来）。除了这种特殊情况，一般情况下竞赛图都有。2、变换设D是有的竞赛图，是D的一个，若用非上的m（2mp）条边，替换上的m条边，可以得到一个新的，这一过程称为图D的一个变换。设竞赛图D有，其对应的矩阵为A（也就是此H圈对应的矩阵）。在A

45、上：用(1，4)替换对角线上的是一个三元H圈变换，若满足：A. 构成，B. 构成 C. 构成，则此三元H圈变换是一个三元变换。此三元变换实际上是变换(I)(II)，像变换一样，可以在矩阵上进行。用 当时，看成1，下同替换对角线上元素是三元H圈变换，若满足：A. 构成，B.构成，则此三元H圈变换是三元变换。用替换对角线上元素是三元H圈变换，若满足A.构成，B构成，则此三元H圈变换是三元变换。用(当,看成1)替换对角线上元素是三元H圈变换，若构成，则此三元H圈变换是三元变换。变换首先必须是H圈变换，二元H圈变换都不是变换，以上所列四种三元H圈变换，若满足所列条件，则都是变换。四元及四元以上的H圈变

46、换是否是变换，只要看变换后元素脚码是否构成，若构成，则此H圈变换就是变换，写出新对应的矩阵，就完成了变换。3、如何求竞赛图的最优设D是有的赋权竞赛图。D中边权和最小的，称为D的最优。因为求最优H圈到目前为止都没有有效的计算方法，所以求最优就更没有好方法。下面用变换可比较有效地解决这一难题，具体如下进行（与求最优类似）写出对应矩阵A；在矩阵A上用追踪法找一初始，并写出此对应的矩阵B（在矩阵上同时写出此）；从矩阵B开始，做一系列调优变换，把边权和小的元素调到对角线上。按变换差大小，从大到小一次一次变换。变换一次，对角线上元素边权和减一次，直到不能减少为止。再从不同的初始进行，比较每次结果，选取最优

47、者。每次变换可这样进行：在矩阵上先找出新的更优变换，写出新，再写出新对应的矩阵，即为变换后所得新矩阵。这样变换比利用矩阵变换更适用更好记忆，有一般性。最后所得矩阵对角线上元素构成的虽然不能肯定是最优的，但一定是较优。最后矩阵对角线上元素构成的是否是最优的，利用充分定理，与最优H圈一样检查。经过检查，变换、检查最后可以得到较理想结果。例7某汽车配件厂有一台设备必须加工一批不同零件，加工完这批零件后，再回到初始状态准备加工下一批同样的零件，生产轮回转。已知加工零件后，再加工零件，中间调整设备所需时间为(若舍去)，具体时间见下表(单元:小时)。问如何安排这批零件的加工顺序，加工完后调整设备回到初始状

48、态，使一个生产轮回总的调整设备时间最短？tij2  3   4  5 6  7 8 912345678BjBi解：以为顶点，为边权得一竞赛图D。求一个加工顺序，使一个生产轮回总的调整设备时间最短，即要求图D的最优(与求最优不同的是加工完这批零件后，还要调整设备，回到初始状态)。具体如下进行：写出竞赛图D对应矩阵A；在A上找到初始并写出对应矩阵B。 1256473981 1234567891 1253647981 检查B发现用，替换对角线上元素，是更优的三元变换，变换后得新:，对应矩阵为C；BS=54CS=45 检查C发现用 替换对角线上元素是更

49、优的三元变换，变换后得新:，对应矩阵为D；检查D发现用 替换对角线上元素是更优的三元变换，变换后得:，对应矩阵为E；检查E发现用替换162534798 1362594781 162539478 FS=29ES=39DS=41 对角线上元素是更优三元变换，变换后得新:1362594781，对应矩阵为F；检查F发现用替换对角线上元素是更优三元变换，变换后得新:1362759481对应矩阵为H；检查矩阵H无更优的变换。充分简化矩阵H，得矩阵J，矩阵J对角线上元素都0，而非对角线上元素都0，1362759481 JHS=15 所以矩阵H对角线上元素构成图D的最优，即矩阵H上面的:1362759481。

50、故最优加工顺序为B1B3B6B2B7B5B9B4B8B1。一个生产轮回总的调整设备时间为15小时。十二 双向竞赛图的及（一）双向竞赛图有向图D称为双向竞赛图当且仅当D的任意两顶点，之间有且仅有两条互为反向的边。当方向为时，边权用表示，当方向为时，边权用表示。D的边权用两个数表示为()。这样一个双向竞赛图也可以用一个上三角形矩阵表示。这个矩阵就称为图D所对应的矩阵，其元素为。很明显双向竞赛图都有。（二）如何求双向竞赛图的最优、设D是一个赋权的双向竞赛图，如何求D的最优、，到目前为止还没有一个有效的计算方法，而在实践中又常有应用。其实求双向竞赛图的最优、比求竞赛图的最优、更容易，这是因为在作、变换

51、时，选择的机会更多，更灵活，且初始、在图D对应矩阵的对角线上是现成的。(特别当二元H圈变换满足,构成,构成，或者构成，构成，则用替换或者用替换都可成二元、变换。此变换在矩阵上与二元H圈变换一样进行，只是变换时对角线上部分元素反向)。具体求法如下：1、求双向竞赛图的最优求双向竞赛图的最优与求竞赛图的最优类似，具体这样进行。写出双向竞赛图D对应矩阵A；在矩阵A的对角线上，有现成的初始:123P，同时在矩阵A的上面写出此。从矩阵A开始，进行一系列调优变换（一般先作二元H圈变换）。把边权和小的元素调到对角线上，直到没有更优的变换为止。再从不同的初始，进行变换，得到不同结果，选取最优者。最后所得矩阵对角线上元素（除右上角元素）构成的(即矩阵上面的)是否是最优的，与求竞赛图最优一样，进行检查，变换，检查，便可得到较理想结果。1 2 3 4 5 6 71234567例8一台设备必须加工7种不同的零件B1B2B7，加工零件Bi后再加上零件，中间需要调整设备，设调整设备时间为()具体时间见右表(单位：小时)。问如何安排这批零件的加工顺序，使总的调整设备时间最短？解：以为顶点，为