黃文旭

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

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

黃文旭

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

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

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

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

1 基本概念

1.1 圖的概念

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

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

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

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

1.2 線值方陣的概念

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

稱(chēng)為賦值d的圖G給定點(diǎn)的順序P1，P2，…，Pn的一個(gè)線值方陣，簡(jiǎn)稱(chēng)圖G的一個(gè)線值方陣，簡(jiǎn)記為A= （aij）n，aij稱(chēng)為 A 的第 i行第 j列元素，aij（i=1，2，…，n）稱(chēng)為A的主對(duì)角線元素，稱(chēng)n為A的階.

顯然有：

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

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

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

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

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

就稱(chēng)它是A的一組最短圈元素.

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

2 線值方陣的變換

2.1 等差變換

2.2 換法變換

2）B可看作線值方陣;

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

證 1）不難驗(yàn)證;

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

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

2.3 倍法變換

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

1）B可看作線值方陣；

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

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

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

3 降階定理

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

4 最小圈值的估算

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

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

j=1

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

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

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

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

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

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

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

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

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

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

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

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

［8］黃文旭.貨郎問(wèn)題算法簡(jiǎn)介 [J].海南教育學(xué)院學(xué)報(bào),1990（創(chuàng)刊號(hào)）: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

畢和平