《关于图的h圈h通路》由会员分享，可在线阅读，更多相关《关于图的h圈h通路（33页珍藏版）》请在金锄头文库上搜索。
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图，则G至
10、少有一个H圈。由H圈变换性质，通过H圈变换可以把此H圈变换到矩阵的对角线上，即经过若干次H圈变换后，矩阵对角线上无X元。 3），在图对应的矩阵上检查也有规律，也很方便。这样图G的H圈1-2-3-P-1为最优H圈的必要条件是不等式组（）（）同时成立。同理作m（m4）元H圈变换，还可以得到更强的必要条件。3 基本不等式及最优H圈的充要条件 基本不等式设H圈1-2-3-P-1是图G的最优H圈，若用不在此H圈上的m（m3）条边 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 ()成立。若此m元H圈变换是基本H圈变换，则称此不等式()是此m元H圈变换所对应的m元基本不等式。否则此不等式是多余的，这是因为它可以由低元基本不等式相加得到。显然（）（）都是基本不等式。 最优H圈的充要条件定理四 图G的H圈1-2-3-P-1（记为Q*）为最优H圈的充要条件是所有m（m=2 3p）元基本不等式成立。证
