陳其 金素萍 徐佳衡 楊雙雙

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

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

1 引言

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

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

2 研究應用

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

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

3.1 線圖

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

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

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

圖1 無向圖G和它的線圖L（G）

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

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

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

3.3 線圖的應用

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

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

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

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

4.1 凱萊圖

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

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

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

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

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

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

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

4.3 凱萊圖的應用

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

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

5 啟示與展望

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

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

參考文獻

[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.