林馨
摘要:對任意的簡單圖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)變換
中圖分類號:O157.5 文獻(xiàn)標(biāo)識碼:A 文章編號:1007-9416(2018)04-0227-01
1 引言
在圖論中,圖是由若干給定的頂點(diǎn)以及頂點(diǎn)之間的邊所構(gòu)成的圖形,這種圖形通常用來描述某些事物之間的某種特定關(guān)系,用頂點(diǎn)代表事物,用連接兩點(diǎn)的邊表示相應(yīng)兩個事物間具有的關(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的邊。
若圖的各邊都沒有方向,稱為無向圖。
若圖若無重邊(即任意兩個頂點(diǎn)間至多只有一條邊),則稱為簡單圖。
若圖的每個頂點(diǎn)的度數(shù)(即其鄰接的邊數(shù))皆為n,那么我們稱其為n-正則圖。
設(shè)G是無向圖,如果頂點(diǎn)集V可分割成兩個互不相交的子集,并且圖中的每條邊所關(guān)聯(lián)的兩個頂點(diǎn)分別屬于這兩個不同的頂點(diǎn)集,則稱G是一個二部圖。
本文將借助三正則二部圖,研究三正則二部網(wǎng)絡(luò)的結(jié)構(gòu)。而文中所涉及的而以上未提及的圖論中常用符號和概念參見[1]。
2 主要結(jié)論
對任意的簡單圖G,若其存在兩條邊,滿足,E(G),令,那么該變換稱為圖G上的一次開關(guān)變換。……