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

1、三正則二部網(wǎng)絡(luò)的結(jié)構(gòu)1 引言 在圖論中，圖是由若干給定的頂點(diǎn)以及頂點(diǎn)之間的邊所構(gòu)成 的圖形，這種圖形通常用來(lái)描述某些事物之間的某種特定關(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)對(duì)應(yīng)著圖中的頂點(diǎn)，而網(wǎng)絡(luò)中的連?則對(duì)應(yīng)著圖中的邊。圖中，集合V的元素稱(chēng)為圖G的頂點(diǎn)，而集合E的元素稱(chēng)為 圖G的邊。若圖的各邊都沒(méi)有方向，稱(chēng)為無(wú)向圖。 若圖若無(wú)重邊（即任意兩個(gè)頂點(diǎn)間至多只有一條邊），則稱(chēng) 為簡(jiǎn)單圖。若圖的每個(gè)頂點(diǎn)的度數(shù)（即其鄰接的邊數(shù)）皆為 n,那么我 們稱(chēng)其為 n- 正則圖。設(shè)G是無(wú)向圖，如果頂點(diǎn)集V

2、可分割成兩個(gè)互不相交的子集， 并且圖中的每條邊所關(guān)聯(lián)的兩個(gè)頂點(diǎn)分別屬于這兩個(gè)不同的頂 點(diǎn)集，則稱(chēng)G是一個(gè)二部圖。本文將借助三正則二部圖， 研究三正則二部網(wǎng)絡(luò)的結(jié)構(gòu)。 而 文中所涉及的而以上未提及的圖論中常用符號(hào)和概念參見(jiàn) 1 。2 主要結(jié)論對(duì)任意的簡(jiǎn)單圖G若其存在兩條邊，滿(mǎn)足，E (G),令， 那么該變換稱(chēng)為圖G上的一次開(kāi)關(guān)變換。若圖G經(jīng)過(guò)有限次開(kāi)關(guān)變換后，得到圖 G，我們就稱(chēng)G和 G在開(kāi)關(guān)變換下是連通的。 顯然，開(kāi)關(guān)變換具有可逆性，圖G 通過(guò)有限次開(kāi)關(guān)變換后，也能得到圖G因此，在開(kāi)關(guān)變換的意義下，兩個(gè)圖連通具有對(duì)稱(chēng)性。對(duì)任意2n階三正則二部網(wǎng)絡(luò)G, G的頂點(diǎn)按次序編號(hào)并分為 兩部分以及。我們

3、將圖 G的頂點(diǎn)集記為V(G)，邊集記為。定義 1. 記 Jn 為 2n 階三正則二部圖集合。定義 2. 我們定義 2n 階三正則二部圖的標(biāo)準(zhǔn)圖滿(mǎn)足：定理2.若，則對(duì)G施加有限次的開(kāi)關(guān)變換后可得到標(biāo)準(zhǔn)圖， 且每次變換得到的圖仍屬于圖類(lèi) Jn。證.由算法1可知，若，我們將G的頂點(diǎn)編號(hào)為兩部分以及， 之后逐個(gè)考察其是否含有標(biāo)準(zhǔn)圖中的各邊， 若沒(méi)有， 則進(jìn)行適當(dāng) 的開(kāi)關(guān)變換，得到該邊，直到得到標(biāo)準(zhǔn)圖中的所有邊。則對(duì)G進(jìn)行有限次開(kāi)關(guān)變換之后可得到。 又由于每次開(kāi)關(guān)變換所產(chǎn)生的新 邊仍然連接兩部的頂點(diǎn)，因此每次變換所得到的圖仍屬于圖類(lèi) Jn。3 結(jié)語(yǔ)本文將三正則二部網(wǎng)絡(luò)抽象為三正則二部圖， 驗(yàn)證了任意一 個(gè)三正則二部圖經(jīng)過(guò)有限次開(kāi)關(guān)變換都可以轉(zhuǎn)化為我們所定義 的同階標(biāo)準(zhǔn)圖。又根據(jù)開(kāi)關(guān)變換具有可逆性， 我們知道整個(gè)三正 則二部圖類(lèi)在此開(kāi)關(guān)變