陳其 金素萍 徐佳衡 楊雙雙

摘 要：針對(duì)網(wǎng)絡(luò)攻擊者經(jīng)常利用破壞防火墻對(duì)網(wǎng)絡(luò)進(jìn)行滲透攻擊的特點(diǎn)，我們提出基于圖論的網(wǎng)絡(luò)安全優(yōu)化與應(yīng)用方法，運(yùn)用已有的彩虹著色理論設(shè)置防火墻。以計(jì)算機(jī)網(wǎng)絡(luò)為研究對(duì)象，我們分別研究線圖與凱萊圖彩虹著色的相關(guān)結(jié)論，建立圖論模型將結(jié)論運(yùn)用于網(wǎng)絡(luò)構(gòu)造中設(shè)置網(wǎng)絡(luò)防火墻，提高網(wǎng)絡(luò)安全性進(jìn)而優(yōu)化網(wǎng)絡(luò)。

關(guān)鍵詞：網(wǎng)絡(luò)安全；彩虹著色；彩虹連通圖；線圖；凱萊圖

1 引言

為防止網(wǎng)絡(luò)受到敵方的惡意攻擊，我們需要對(duì)有關(guān)聯(lián)的節(jié)點(diǎn)之間設(shè)置防火墻。這樣就出現(xiàn)了一個(gè)問(wèn)題：最少需要多少防火墻使得任意兩個(gè)機(jī)構(gòu)之間至少有一條安全的路徑？這種情況可建立圖論模型計(jì)算相應(yīng)的數(shù)值。

假設(shè)G是非平凡的連通圖，其邊著色為c，如果一條路徑的任意兩個(gè)邊的著色不同，那么這條路徑是彩虹路徑。如果邊著色圖G的任意兩個(gè)頂點(diǎn)由彩虹路徑連接而成，那么圖G是彩虹連通圖，圖G的邊著色是彩虹著色。連通圖G的彩虹連通數(shù)定義為使得圖G是彩虹連通圖的最小顏色數(shù)，記為rc（G）。

2 研究應(yīng)用

計(jì)算機(jī)網(wǎng)絡(luò)在生活中應(yīng)用十分廣泛。本文得到的結(jié)果將運(yùn)用于對(duì)網(wǎng)絡(luò)設(shè)置防火墻，包括防火墻的安排和數(shù)量，從而確保網(wǎng)絡(luò)安全優(yōu)化網(wǎng)絡(luò)。計(jì)算機(jī)系統(tǒng)具有如下六大主要特征：資源分散性；結(jié)構(gòu)模塊性；控制自治性；工作并行性；運(yùn)行堅(jiān)定性；系統(tǒng)透明性。它應(yīng)用的范圍將比以前的網(wǎng)絡(luò)技術(shù)更為寬泛，更為實(shí)用。

3 與線圖相關(guān)的結(jié)果

3.1 線圖

Harary和Norman[6]在1960年首次提出了線圖的概念。線圖是圖論中最重要的課題之一，它所對(duì)應(yīng)的圖論參數(shù)有連通度，Euler性和Hamilton性等。鑒于線圖的重要性，Hemminger和Beineke[7]寫了一篇文獻(xiàn)綜述?；诰€圖方法，我們可以設(shè)計(jì)和分析互聯(lián)網(wǎng)拓?fù)浣Y(jié)構(gòu)。

圖G的線圖L（G）的頂點(diǎn)集合V（L（G））=E（G），L（G）的兩個(gè)頂點(diǎn)e1，e2是相連的當(dāng)且僅當(dāng)在圖G中的這些邊界是相連的。圖G的迭代線圖L2（G）是圖L（G）的線圖，k階迭代線圖Lk（G）是圖Lk-1（G）的線圖，L1（G）=L（G）。

例1，圖1所示的是無(wú)向圖G和它的線圖L（G）。

圖1 無(wú)向圖G和它的線圖L（G）

3.2 線圖彩虹著色的相關(guān)結(jié)論

定理3.21 [1]假設(shè)G是連通圖，T是一組由t邊不交的三角形組成的集合，n'2是不屬于T三角形的內(nèi)部頂點(diǎn)，c表示子圖G（E（T））的連通分支的個(gè)數(shù)，那么 。

定理3.22 [2]如果連通圖G有m條邊界，m1條雙路徑，那么rc（L2（G））？燮m-m1，當(dāng)且僅當(dāng)圖G中路徑的長(zhǎng)度至少為3時(shí)取得等號(hào)。

3.3 線圖的應(yīng)用

我們考慮例1的彩虹連通數(shù)，易知t=2，n'2=0，c=2，根據(jù)定理3.21可得： 。例1的一個(gè)彩虹著色如圖2所示，其中1，2，3，4表示四種不同的顏色。

圖2 線圖L（G）的彩虹著色

線圖在網(wǎng)絡(luò)構(gòu)造中有十分重要的作用。圖2有7個(gè)連接點(diǎn)，10條路徑，彩虹著色為四種顏色。我們將這7個(gè)不同的點(diǎn)當(dāng)成計(jì)算機(jī)，而不同著色的彩虹路徑看為防火墻，利用線圖來(lái)設(shè)置防火墻，從而保障網(wǎng)絡(luò)的安全性。

4 與凱萊圖相關(guān)的研究

4.1 凱萊圖

基于有限群，A.Cayley[8]提出一種構(gòu)造互連網(wǎng)絡(luò)的凱萊方法，該方法為我們?cè)O(shè)計(jì)、分析和改進(jìn)網(wǎng)絡(luò)提供了一類很重要的圖論模型。通過(guò)建立圖論模型，我們可以得到一類高對(duì)稱圖——?jiǎng)P萊圖。

假設(shè)G為有限群，S為對(duì)稱（逆元素封閉）且不含單位元的生成集。G相應(yīng)于S的凱萊圖記為？祝=？祝（G，S）：？祝的頂點(diǎn)集合G中兩個(gè)元素g，h在？祝中相鄰當(dāng)且僅當(dāng)g-1h∈S。假設(shè)元素a∈？祝，表示由a構(gòu)成的？祝的循環(huán)生成子群。S的？祝-凱萊圖記為C（？祝，S）：頂點(diǎn)x和y是相連的當(dāng)且僅當(dāng)xy-1∈S（或者yx-1∈S），在可逆的條件下S？哿？祝＼{1}是封閉的。

例2，假設(shè)G=Zn是n階循環(huán)群，集合S由G的標(biāo)準(zhǔn)生成元和逆元構(gòu)成，則相應(yīng)的凱萊圖為圈Cn。當(dāng)n=6時(shí)得到圈C6（如圖3所示）。

4.2 凱萊圖彩虹著色的相關(guān)結(jié)論

定理4.21 [3]給定一個(gè)Abelian群？祝和一個(gè)逆閉集S？哿？祝＼{1}，我們得到下列結(jié)果：

（i）rc（C（？祝，S））？燮min{a/2]}|S*∈S是？祝的一個(gè)最小的生成子集}

（ii）如果S是？祝的一個(gè)最小的逆閉集，S*？哿S是？祝的最小的生成

4.3 凱萊圖的應(yīng)用

我們考慮例2的彩虹連通數(shù)，由定理4.21可知，rc（Cn）例2的一個(gè)彩虹著色如圖4所示，其中1，2，3表示三種不同的顏色。

凱萊圖在網(wǎng)絡(luò)構(gòu)造中有十分重要的作用。圖4有6個(gè)連接點(diǎn)，6條路徑。我們把這6個(gè)不同的點(diǎn)當(dāng)成計(jì)算機(jī)，不同的彩虹路徑是防火墻，利用這個(gè)模型模擬網(wǎng)絡(luò)，將圖跟網(wǎng)絡(luò)等同起來(lái)設(shè)置防火墻從而保護(hù)計(jì)算機(jī)。

5 啟示與展望

我們需要確保在滿足任意兩點(diǎn)之間都有一條安全通道連接，并且這條安全通道上的防火墻都不相同的條件下，使得防火墻數(shù)量最少的情況下合理地設(shè)置防火墻，達(dá)到提高網(wǎng)絡(luò)安全性的目的。

我們根據(jù)已得出的線圖和凱萊圖彩虹連通數(shù)的結(jié)論和彩虹著色方案，建立圖論模型；再根據(jù)彩虹連通數(shù)以往的結(jié)果和研究方法，研究計(jì)算機(jī)網(wǎng)絡(luò)的彩虹連通數(shù)，得出具體的彩虹著色方案，從而為計(jì)算機(jī)網(wǎng)絡(luò)設(shè)置防火墻。

參考文獻(xiàn)

[1]XueLiang Li，Yongtang Shi，Yunfang Sun ：Raninhow Connection of Graphs ：A Surary .Graphs and Combinatorics （2013） 29：1-38.

[2] Li X，Sun Y （2012） Upper bounds for the rainbow connection numbers of line graphs. Graphs Combin. 28（2），251-263.

[3] He，J.，Liang，H.： On rainbow-k-connectivity of random graphs. Inf. Process. Lett. 112（10），406-410 （2012）.

[4]Chen，L.，Li，X.，Shi，Y.： The complexity of determining the rainbow vertex-connection of graphs. Theoret.Comput. Sci. 412，4531-4535 （2011）.

[5]Chartrand，G.，Johns，G.L.，McKeon，K.A.，Zhang，P.： On the rainbow connectivity of cages. Congr.Numer. 184，209-222 （2007）.

[6]Harary F，Norman R Z. Some properties of line digraphs.Rendiconti del Circolo Matematicodi Palermo.9（1960），161～169.

[7]Hemminger R L，Beineke L W.Line graphs and line digraphs.In Selected Topics in Graph Theory. London，New York，San Francisco：Academic Press，1978，271～305.

[8]Cayley A. The theory of graphs，graphical representation.Mathematical Papers，Cambridge，10（1895），26～28.