趙 凱, 王曉平,董大偉

(1.宜賓職業(yè)技術(shù)學(xué)院現(xiàn)代制造工程系，四川宜賓 644003；2.宜賓職業(yè)技術(shù)學(xué)院人文社科系，四川宜賓 644003； 3.西南交通大學(xué)牽引動(dòng)力國家重點(diǎn)實(shí)驗(yàn)室，四川成都 610031)

基于關(guān)聯(lián)矩陣主對角線譜理論的歐拉圖研究

趙 凱1, 王曉平2,董大偉3

(1.宜賓職業(yè)技術(shù)學(xué)院現(xiàn)代制造工程系，四川宜賓 644003；2.宜賓職業(yè)技術(shù)學(xué)院人文社科系，四川宜賓 644003； 3.西南交通大學(xué)牽引動(dòng)力國家重點(diǎn)實(shí)驗(yàn)室，四川成都 610031)

本文利用圖的頂點(diǎn)與邊鄰接矩陣建立并定義了頂點(diǎn)關(guān)聯(lián)矩陣和邊關(guān)聯(lián)矩陣，以及頂點(diǎn)關(guān)聯(lián)矩陣和邊關(guān)聯(lián)矩陣的主對角線譜概念，并給出了利用關(guān)聯(lián)矩陣主對角線譜判定歐拉圖問題的方法。

圖論；關(guān)聯(lián)矩陣；主對角線譜；哥尼斯堡七橋問題

目前，矩陣和圖論理論中對關(guān)聯(lián)矩陣和鄰接矩陣關(guān)系的研究較少[1].徐俊明[2]研究了關(guān)聯(lián)矩陣和鄰接矩陣的行列式問題，但沒有對關(guān)聯(lián)矩陣和鄰接矩陣之間的關(guān)系進(jìn)行關(guān)聯(lián).Jonathan L Gross and Jay Yellen[3]構(gòu)造的頂點(diǎn)關(guān)聯(lián)矩陣和邊關(guān)聯(lián)矩陣的對角線的值均為零，而J A Bondy[4]將各個(gè)頂點(diǎn)度引入到關(guān)聯(lián)矩陣中，但頂點(diǎn)關(guān)聯(lián)是人為設(shè)定的，對原始圖來講存在部分的信息遺失.本文引入主對角線譜建立頂點(diǎn)關(guān)聯(lián)矩陣和邊關(guān)聯(lián)矩陣之間的關(guān)系，并討論了關(guān)聯(lián)矩陣及主對角線譜的基本性質(zhì)，最后應(yīng)用頂點(diǎn)關(guān)聯(lián)矩陣的主對角線譜進(jìn)行歐拉圖的判定.

1 鄰接矩陣的定義

定義2 矩陣V(G)=(vij)m×m稱為圖G的頂點(diǎn)關(guān)聯(lián)矩陣，其中V(G)=K(G)KT(G).

定義3 矩陣E(G)=(eij)n×n稱為圖G的邊關(guān)聯(lián)矩陣，其中E(G)=KT(G)K(G).

顯然，V(G)和E(G)都是對稱矩陣.

性質(zhì)2 對于邊關(guān)聯(lián)矩陣E(G)=(eij)n×n，當(dāng)eii=0時(shí)矩陣變成圖論中的關(guān)聯(lián)矩陣.

性質(zhì)3 頂點(diǎn)關(guān)聯(lián)矩陣V(G)和邊關(guān)聯(lián)矩陣E(G)的跡相等，即tr(V)=tr(E).

定義4Diag-SpecV(G)稱為圖G的頂點(diǎn)關(guān)聯(lián)矩陣V(G)的主對角線譜，令

(1)

在圖論中，跡可用于統(tǒng)計(jì)圖中各頂點(diǎn)的度數(shù)和.

2 關(guān)聯(lián)矩陣用于歐拉圖的判斷實(shí)例

例1 判定哥尼斯堡七橋問題(圖1)是否為歐拉圖.

該問題的連通示意圖G(圖2)共有A、B、C、D四個(gè)頂點(diǎn)和標(biāo)號(hào)從1到7的七條邊.此問題曾經(jīng)是世界著名的數(shù)學(xué)難題，最終由數(shù)學(xué)家歐拉通過圖論辦法得以解決，其結(jié)論是無法只從每個(gè)橋通過一次走遍七座橋.實(shí)際上，可以通過建立其關(guān)聯(lián)矩陣的主對角線譜來判斷該難題是否成立.這一計(jì)算和判定方法易于以計(jì)算機(jī)算法的形式實(shí)現(xiàn)，也是對此類圖論判定問題的很好的自動(dòng)判定方法.

圖1 哥尼斯堡七橋問題

圖2 哥尼斯堡七橋問題的連通示意圖

首先，建立圖的頂點(diǎn)與邊鄰接矩陣K(G)，進(jìn)而推算頂點(diǎn)關(guān)聯(lián)矩陣V(G)=K(G)KT(G)和邊關(guān)聯(lián)矩陣E(G)=KT(G)K(G).

例2 判定圖3是否為歐拉圖.

例3 判定圖4是否為歐拉圖.

圖3 一種歐拉圖的連通圖

圖4 一種半歐拉圖的連通圖

由上述實(shí)例說明，利用頂點(diǎn)關(guān)聯(lián)矩陣對角線譜的計(jì)算和統(tǒng)計(jì)，可以有效地判定連通圖是否為歐拉圖，并判斷歐拉圖的類型.

實(shí)際上，從前面的推算過程可以看出，鄰接矩陣K(G)與關(guān)聯(lián)的V(G)和E(G)是互通的，只要知其一，其余兩個(gè)就可推算出來.一般而言，連通圖的頂點(diǎn)數(shù)量都比邊的數(shù)量少，所以常用頂點(diǎn)關(guān)聯(lián)矩陣表示圖，而另外兩個(gè)矩陣由頂點(diǎn)關(guān)聯(lián)矩陣推出.又因?yàn)轫旤c(diǎn)關(guān)聯(lián)矩陣是對稱矩陣，由性質(zhì)1可知，主對角線上的單元數(shù)據(jù)可以通過鄰接矩陣的行或列推導(dǎo)出來，因此，實(shí)際需要計(jì)算機(jī)儲(chǔ)存的數(shù)據(jù)量是m(m-1)/2.可見，使用圖的頂點(diǎn)關(guān)聯(lián)矩陣可以用較少的數(shù)據(jù)存儲(chǔ)相同大小信息量的圖。

3 通過主對角線譜法判定歐拉圖的方法

已為人們熟知的歐拉一筆畫的判據(jù)是：(1)歐拉圖是可以一筆畫成的，它是由偶點(diǎn)組成的連通圖.一筆畫時(shí)，可以從任一偶點(diǎn)開始，最后以這個(gè)點(diǎn)為終點(diǎn)畫完得到歐拉閉跡.(2)半歐拉圖是可以一筆畫成的，它是只有兩個(gè)奇點(diǎn)的連通圖(其余都為偶點(diǎn)).一筆畫時(shí)，必須把一個(gè)奇點(diǎn)作為起點(diǎn)，另一個(gè)奇點(diǎn)作為終點(diǎn).(3)其他情況的圖都不能一筆畫出.

4 結(jié)語

通過頂點(diǎn)與邊鄰接矩陣可以推導(dǎo)出頂點(diǎn)關(guān)聯(lián)矩陣和邊關(guān)聯(lián)矩陣，定義方陣的主對角線譜，闡明主對角線譜和矩陣跡在圖論中的意義.通過本文所引入的矩陣主對角線譜可以方便地自動(dòng)判定連通圖的歐拉性質(zhì)，所引入的關(guān)聯(lián)矩陣和鄰接矩陣在圖論以外的機(jī)構(gòu)學(xué)[5]等其他學(xué)科中有很大的應(yīng)用意義.

[1]張先迪,李正良.圖論及其應(yīng)用[M].北京:高等教育出版社,2005:15-16.

[2]徐俊明.圖論及其應(yīng)用[M].3版,合肥:中國科學(xué)技術(shù)大學(xué)出版社,2014:91-93.

[3] Jonathan L Gross,Jay Yellen.Handbook of graph theory[C].CRC Press Taylor & Francis Group,2014:12.

[4]J A Bondy,U S R Murty.Graph theory[M].Springer,2008:6.

[5]Z Kai.Planar mechanism incidence matrices and main diagonal spectrum[C].International Workshop on Materials Engineering and Computer Sciences,2015.

Euler Graph Research Based on Main Diagonal Spectrum Theory of Incidence Matrix

ZHAO Kai1，WANG Xiao-ping2，DONG Da-wei3

(1.Modern Manufacturing Engineering Department of Yibin Vocational and Technical College, Yibin Sichuan 644003,China； 2.Humanities and Social Science Department of Yibin Vocational and Technical College,Yibin Sichuan 644003,China； 3.Traction Power State Key Laboratory of SouthWest Jiaotong University,Chengdu Sichuan 610031,China)

By using the incidence matrix of vertex-edge and the main diagonal spectrum of the correlated matrix, the vertex incidence matrix and edge incidence matrix were established. Then, the main diagonal spectrum of the correlated matrix was used to prove or judge Euler graph problem.

graph theory; incidence matrix; main diagonal spectrum; Knigsberg bridges problem

2017-03-03

趙 凱(1972- )，男，副教授，碩士，從事機(jī)構(gòu)學(xué)、圖論及機(jī)械電子工程研究。

O151.22

A

2095-7602(2017)08-0010-04