三正則二部網絡的結構

林馨

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

關鍵詞：三正則；二部；開關變換

中圖分類號：O157.5 文獻標識碼：A 文章編號：1007-9416（2018）04-0227-01

1 引言

在圖論中，圖是由若干給定的頂點以及頂點之間的邊所構成的圖形，這種圖形通常用來描述某些事物之間的某種特定關系，用頂點代表事物，用連接兩點的邊表示相應兩個事物間具有的關系。

在組合網絡理論中，我們可將網絡拓撲結構可抽象為圖。其中，網絡中的節點對應著圖中的頂點，而網絡中的連線則對應著圖中的邊。

圖中，集合V的元素稱為圖G的頂點，而集合E的元素稱為圖G的邊。

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

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

若圖的每個頂點的度數（即其鄰接的邊數）皆為n，那么我們稱其為n-正則圖。

設G是無向圖，如果頂點集V可分割成兩個互不相交的子集，并且圖中的每條邊所關聯的兩個頂點分別屬于這兩個不同的頂點集，則稱G是一個二部圖。

本文將借助三正則二部圖，研究三正則二部網絡的結構。而文中所涉及的而以上未提及的圖論中常用符號和概念參見[1]。

2 主要結論

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