三正則二部網(wǎng)絡(luò)的結(jié)構(gòu)

林馨

摘要：對任意的簡單圖G，若其存在兩條邊，滿足，E（G），令，該變換稱為圖G上的開關(guān)變換。若圖G經(jīng)過有限次開關(guān)變換后，得到圖G，則稱G和G在開關(guān)變換下是連通的。本文將三正則二部網(wǎng)絡(luò)抽象為三正則二部平面圖，討論此類圖的結(jié)構(gòu)，并用算法驗(yàn)證此圖類在開關(guān)變換下是連通的。

關(guān)鍵詞：三正則；二部；開關(guān)變換

中圖分類號(hào)：O157.5 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9416（2018）04-0227-01

1 引言

在圖論中，圖是由若干給定的頂點(diǎn)以及頂點(diǎn)之間的邊所構(gòu)成的圖形，這種圖形通常用來描述某些事物之間的某種特定關(guān)系，用頂點(diǎn)代表事物，用連接兩點(diǎn)的邊表示相應(yīng)兩個(gè)事物間具有的關(guān)系。

在組合網(wǎng)絡(luò)理論中，我們可將網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)可抽象為圖。其中，網(wǎng)絡(luò)中的節(jié)點(diǎn)對應(yīng)著圖中的頂點(diǎn)，而網(wǎng)絡(luò)中的連線則對應(yīng)著圖中的邊。

圖中，集合V的元素稱為圖G的頂點(diǎn)，而集合E的元素稱為圖G的邊。

若圖的各邊都沒有方向，稱為無向圖。

若圖若無重邊（即任意兩個(gè)頂點(diǎn)間至多只有一條邊），則稱為簡單圖。

若圖的每個(gè)頂點(diǎn)的度數(shù)（即其鄰接的邊數(shù)）皆為n，那么我們稱其為n-正則圖。

設(shè)G是無向圖，如果頂點(diǎn)集V可分割成兩個(gè)互不相交的子集，并且圖中的每條邊所關(guān)聯(lián)的兩個(gè)頂點(diǎn)分別屬于這兩個(gè)不同的頂點(diǎn)集，則稱G是一個(gè)二部圖。

本文將借助三正則二部圖，研究三正則二部網(wǎng)絡(luò)的結(jié)構(gòu)。而文中所涉及的而以上未提及的圖論中常用符號(hào)和概念參見[1]。

2 主要結(jié)論

對任意的簡單圖G，若其存在兩條邊，滿足，E（G），令，那么該變換稱為圖G上的一次開關(guān)變換。

若圖G經(jīng)過有限次開關(guān)變換后，得到圖G，我們就稱G和G在開關(guān)變換下是連通的。顯然，開關(guān)變換具有可逆性，圖G通過有限次開關(guān)變換后，也能得到圖G。因此，在開關(guān)變換的意義下，兩個(gè)圖連通具有對稱性。

對任意2n階三正則二部網(wǎng)絡(luò)G，G的頂點(diǎn)按次序編號(hào)并分為兩部分以及。我們將圖G的頂點(diǎn)集記為V（G），邊集記為。

定義1.記Jn為2n階三正則二部圖集合。

定義2. 我們定義2n階三正則二部圖的標(biāo)準(zhǔn)圖滿足：

定理2.若，則對G施加有限次的開關(guān)變換后可得到標(biāo)準(zhǔn)圖，且每次變換得到的圖仍屬于圖類Jn。

證. 由算法1可知，若，我們將G的頂點(diǎn)編號(hào)為兩部分以及，之后逐個(gè)考察其是否含有標(biāo)準(zhǔn)圖中的各邊，若沒有，則進(jìn)行適當(dāng)?shù)拈_關(guān)變換，得到該邊，直到得到標(biāo)準(zhǔn)圖中的所有邊。則對G進(jìn)行有限次開關(guān)變換之后可得到。又由于每次開關(guān)變換所產(chǎn)生的新邊仍然連接兩部的頂點(diǎn)，因此每次變換所得到的圖仍屬于圖類Jn。

3 結(jié)語

本文將三正則二部網(wǎng)絡(luò)抽象為三正則二部圖，驗(yàn)證了任意一個(gè)三正則二部圖經(jīng)過有限次開關(guān)變換都可以轉(zhuǎn)化為我們所定義的同階標(biāo)準(zhǔn)圖。又根據(jù)開關(guān)變換具有可逆性，我們知道整個(gè)三正則二部圖類在此開關(guān)變換下是連通的。此結(jié)論探索了三正則二部網(wǎng)絡(luò)的結(jié)構(gòu)特征，并為進(jìn)一步研究其他各類網(wǎng)絡(luò)結(jié)構(gòu)打下了基礎(chǔ)。

參考文獻(xiàn)

[1]J.A Bondy and U.S.R Murty，“graph theory with applications”， 1st Edition，The MacMillan Press，1976.