線值方陣的變換方法及最小圈值的估算

黃文旭

（海南師范大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院，海南 海口 571158）

線值方陣的變換方法及最小圈值的估算

黃文旭

（海南師范大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院，海南 海口 571158）

主要討論有向圖的線值方陣的變換方法及最小圈值的估算問題,得到了線值方陣可作等差變換、換法變換、倍法變換的方法以及這些變換方法的性質(zhì)，線值方陣的最小圈值的估算定理.

線值方陣；變換；最小圈值

貨郎問題（Travelling Salesman Problem）又稱推銷商問題，是組合優(yōu)化論中的一個著名問題［1-4］，與圖論中的哈密爾頓圈（Hamiltonian cycle）的問題相關(guān)［5］.線值方陣的引進主要是針對這一問題而提出的［6-8］.本文主要討論一般有向圖的線值方陣的若干變換方法以及最小圈值的估算問題,目的在于為線值方陣的最小圈值及最短圈元素的計算提供新的途徑.

1 基本概念

1.1 圖的概念

概念1所謂一個有向圖（簡稱圖）G=G（V，X）是由有n個點的非空集合V=V（G）和預(yù)先給定的V中不同點的m個有序?qū)?gòu)成的集合X組成；稱V為圖G的點集，每個P∈V稱為圖G的點；稱X為圖G的線集，X中的每一個有序?qū)Γ≒i，Pj）稱為圖G的一條有向線，也稱由點Pi到點Pj的線；記為PiPj，并稱點Pi為起點，點Pj為終點（本文所論的圖沒有以同一點為起點與終點的線）［7］.

概念 2設(shè) G=G（V，X）為有向圖，P1，P2，…，Pk是V中的k個互異點.如果線集C={P1P2，P2P3，…，Pk-1Pk}?X則稱C為圖G中由點P1到點Pk的一條開路，記為C：P1P2P3…Pk-1Pk，且稱點Pi為 C的起點，點Pk為C的終點；如果線集C={P1P2，P2P3，…，Pk-1Pk，PkP1}?X則稱C為圖G的一條閉路，記為C：P1P2P3…Pk-1PkP1；開路與閉路統(tǒng)稱為路.當{P1，P2，P3，…，Pk}=V（G）時，開路 C：P1P2P3…Pk-1PkP1稱為圖G的一條理想路，閉路C：P1P2P3…Pk-1PkP1稱為圖G的一個理想圈.如果圖G有理想路，則稱圖G為理想圖，如果圖G有理想圈，則稱圖G為有圈圖；若V（G）只有一個點，則圖G（V，X）是平凡的.（注：本文不討論平凡圖）.

概念3設(shè)圖G=G（V，X）是一個有向圖，若任意 PiPj∈X，都有唯一一個實數(shù) d（PiPj）與之對應(yīng)，則稱圖 G 是賦值 d 的圖，d（PiPj）稱線 PiPj的值；又若對任意 PiPj∈X，都有 PjPi∈X，且 d（PiPj）=d（PjPi），則稱圖 G 是無向圖.

概念5設(shè)H是圖G中具有某一特征的路的（非空）集合，H中值最小的路稱為的H最短路，其值記為d（H）；H中值最大的路稱為的H最長路，其值記為 m（H）.

1.2 線值方陣的概念

定義 1設(shè)G=G（V，X）是賦值d的圖，V中的 n 個點順序為 P1，P2，…，Pn，記

稱為賦值d的圖G給定點的順序P1，P2，…，Pn的一個線值方陣，簡稱圖G的一個線值方陣，簡記為A= （aij）n，aij稱為 A 的第 i行第 j列元素，aij（i=1，2，…，n）稱為A的主對角線元素，稱n為A的階.

顯然有：

性質(zhì)1若G=G（V，X）是賦值d的無向圖，則其線值方陣 A= （aij）n是對稱陣，即 aij=aij（i=1，2，…，n）

性質(zhì)2設(shè)G=G（V，X）是賦值 d的圖，若V中任意兩互異點P1，P2都有唯一有向線P1P2，則圖G的線值方陣A=（aij）n除主對角線元素外，其余所有元素是實數(shù)，此種圖稱為完全圖.

定理1設(shè)n階方陣A=（aij）n的主對角線元素都為*，其它元素為實數(shù)或為*，則A可看作某一個圖G的一個線值方陣.

證設(shè)點集 V={P1，P2，…，Pn}，線集 X={Pi給有向圖 G=G（V，X）賦值：d（PiPj） =aij（PiPj∈X），則 A= （aij）n為賦值d的圖G給定點的順序P1，P2，…，Pn的一個線值方陣.

定義 2設(shè)賦值 d的圖 G=G（V，X）給定點的順序 P1，P2，…，Pn的線值方陣為 A= （aij）n，若 An中不同行、不同列的n個非*元素可以排成

就稱它是A的一組最短圈元素.

證由性質(zhì)1結(jié)論成立.

2 線值方陣的變換

2.1 等差變換

2.2 換法變換

2）B可看作線值方陣;

3）A有一組最短圈元素當且僅當B有一組最短圈元素，且 d（A）=d（B）.

證 1）不難驗證;

2）不妨設(shè)i0＜j0，A為賦值d的圖G給定點的順序 P1，P2，…，Pi0，….Pj0，…，Pn的一個線值方陣，則B是賦值d的圖G給定點的順序P1，P2，…，Pj0，….Pi0，…，Pn的一個線值方陣;

3）由于圖G不變且圖G賦值不變，所以圖G若有短理想圈，則的最短理想圈不變，故A有一組最短圈元素當且僅當B有一組最短圈元素，且

2.3 倍法變換

定理7（倍法變換） 若n階線值方陣A=（aij）的每個非*元素都乘以同一個非負數(shù)k得到方陣B= （bij），記為 kA～B，則

1）B可看作線值方陣；

2）A有一組最短圈元素當且僅當B有一組最短圈元素，且 kd（A） =d（B）.

證 1）設(shè)賦值d的圖G=G（V，X）給定點的順序 P1，P2，…，Pn的線值方陣為 A= （aij），對每個PiPj∈X，令 d′（PiPj） =kd（PiPj），則 G=G（V，X）也是賦值d′的圖，此時B為賦值d′的圖G給定點的順序 P1，P2，…，Pn的一個線值方陣.

綜上可知 kd（A） =d（B）而 at1t2，at2t3，…，atk-1tk，atktk+1，…，atnt1是A的一組最短圈元素當且僅當bt1t2，bt2t3，…，btk-1tk，btktk+1，…，btnt1是 B 的一組最短圈元素.

3 降階定理

余方陣的概念及兩個降階定理在有向圖的最短圈問題一文已給出［7］，此不再論述.由第一降階定理可得

4 最小圈值的估算

定理8 設(shè)A=（aij）為一個n階線值方陣，A有圈，則

證設(shè) a1t1，a2t2，…，aktk，…，antn是 A 的一組最短圈元素，則Λnaij≤ aiti，i=1，2，…，n.

j=1

定理9 設(shè)A是線值方陣，A中的非*元素非負，若d（A）≤ k，則A的任一組最短圈元素中不含有大于k的非*元素.

≤ k（i=1，2，…，n）.

推論4 設(shè)A是線值方陣，A中的非*元素非負，將A的某一行（或列）中所有大于k的非*元素換為*得線值方陣 B，若 d（B）≤ k，則 d（A）=d（B）.

推論5 設(shè)A是線值方陣，A中的非*元素非負，將A中所有大于k的非*元素換為*得線值方陣 B，若 d（B） ≤ k，則 d（A） =d（B）.

定理 10設(shè) A= （aij），B= （bij）為兩個 n 階線值方陣，A，B 的和方陣 C= （cij），（其中 cij=aijV bij，i，j=1，2，…，n），記為 AVB=C 則 C 為一個 n階線值方陣，若C有圈，則A，B也有圈且

［1］馬振華.現(xiàn)代應(yīng)用數(shù)學(xué)手冊:運籌學(xué)與最優(yōu)化理論卷[M].北京:清華大學(xué)出版社,1997:276-277.

［2］潘玉奇,王濰,王永燕,等.貨郎問題求解算法分析[J].濟南大學(xué)學(xué)報:自然科學(xué)版,2002,16(4):336-339.

［3］廖春蘭.貨郎問題的近似解算法研究 [J].科技信息:科學(xué)教研,2008,24:41.

［4］徐海波.貨郎擔問題求解算法探討 [J].山東省農(nóng)業(yè)管理干部學(xué)院學(xué)報,2008,4:79-83.

［5］[美]F.哈拉里著.圖論[M].李慰萱譯.上海:上?？茖W(xué)出版社,1980:77-80.

［6］黃文旭.貨郎問題的算法[J].海南師范學(xué)院學(xué)報:自然科學(xué)版,1997,10(2):49-54.

［7］黃文旭.有向圖的最短圈問題[J].海南師范學(xué)院學(xué)報:自然科學(xué)版,2000,13:33-37.

［8］黃文旭.貨郎問題算法簡介 [J].海南教育學(xué)院學(xué)報,1990（創(chuàng)刊號）:89-94.

Transformation Methods of Square Matrix of Numerical Lines and Estimation of the Shortest Cycle Length

HUANG Wenxu

（College of Mathematics and Statics，Hainan Normal University，Haikou 571158，China）

The transformation methods of distance square matrix and the estimation of the shortest cycle length of directed graph are discussed in this article.As a result,we learn how to perform arithmetic transformation,exchange conversion and multiplier transformation of distance square matrix and find out the properties of these transformation methods.Moreover,a theorem for the estimation of the shortest cycle length of distance square matrix is deduced.

square matrix of numerical lines；transform algorithms；the shortest cycle length

O 157.5

A

1674-4942（2010）01-0004-04

2009-11-20

畢和平