[理学]关于图的h圈h通路

《[理学]关于图的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

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

3、eij称为矩阵的元素，i为行，j为列。脚码含i的元素称为矩阵的第i行列元素（实为过第i个顶点的边）。这种矩阵称为图对应的矩阵。例如（K6）对应的矩阵为：图一（K6）矩阵对角线及右上角元素比较重要，统称为对角线元素。K6对应矩阵对角线元素为e12e23e34e45e56e16；第三行列元素为e13e23e34e35e36。二图的H圈变换图G中由不同顶点不同边构成的圈称为初等圈（也称回路）。包含所有顶点的初等圈称为Hamilton圈，简称为H圈。若图G对应矩阵的对角线上都是非X元素，则这些元素构成图G的一个H圈。此时图G对应的矩阵，也称为该H

4、圈对应的矩阵。例如K6对应的矩阵也就是H圈331-2-3-4-5-6-1对应的矩阵。又如K6中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对应的矩阵上进行，仅用非对角线上元素替换对角线上元素

5、，就有1/2（P-1）！—1个。三在矩阵上进行二元H圈变换设Kp对应矩阵为A，则e12e13…e1ie1i+1……e1je1j+1……e1pei-1ieii+1……eijeij+1……eipei+1i+2…ei+1jei+1j+1……ei+1pA=ej-1jejj+1………ejpej+1j+2…ej+1pep-1p1在A上，用非对角线上元素eijei+1j+1（i=12…p-2，j=34…p）替换对角线上元素eii+1ejj+1是一个二元H圈变换(替换元素下打点，被替换元素下划横线，以下同)。设变换后新矩阵为B，则B对角线上元素构成的H圈

6、就是变换后的新H圈。2在A上，用非对角线上元素e1i+1eip（i=23…p-2）替换对角线上元素e1peii+133也是一个二元H圈变换。设变换后新矩阵为C，则C对角线上元素构成的H圈就是变换后的新H圈。由A变成B记为A→B，由A变成C记为A→C，它们都统称为图G的二元H圈变换。由A→B具体这样进行：将A的矩形块e1i+1eii+1eije1j列序颠倒，矩形块ei+1j+1ejj+1ejpei+1p行序颠倒，三角块ei+1i+2ej-1jei+1j的元素作关于斜边高的对称调换，其他元素不动，得矩阵B。由A→C具体这样进行：将A的矩形块e

7、1i+1eii+1eipe1p列序颠倒，三角块ei+1i+2ep-1pei+1p作关于斜边高的对称调换，其他元素不动，得矩阵C。这种矩阵上的二元H圈变换具有如下性质：性质1在图对应的矩阵上进行二元H圈变换时，矩阵对角线上未被替换的元素，经过变换后，仍在对角线上。性质2图的二元H圈变换可以在图对应的矩阵上连续进行，变换一次得一个新矩阵，对角线上得一个新H圈，新矩阵与新H圈一一对应。性质3图对应矩阵中有X元素，X元素也可以进行H圈变换，X元与非X元一样对待。以上性质明显成立。性质4若图G有H圈，则它的任一个H圈都可以变换到矩阵的对角线上。性质

8、5图的任一个m元H圈变换（m≥3）都可以在图对应的矩阵上连续用不超过m个二元H圈变换实现。四基本H圈变换图的三元及三元以上的H圈变换与二元H圈变换一样，可以在图对应的矩阵上进行，也有类似性质，