基于彩虹著色的網絡安全研究

陳其 金素萍 徐佳衡 楊雙雙

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

關鍵詞：網絡安全；彩虹著色；彩虹連通圖；線圖；凱萊圖

1 引言

為防止網絡受到敵方的惡意攻擊，我們需要對有關聯的節點之間設置防火墻。這樣就出現了一個問題：最少需要多少防火墻使得任意兩個機構之間至少有一條安全的路徑？這種情況可建立圖論模型計算相應的數值。

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

2 研究應用

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

3 與線圖相關的結果

3.1 線圖

Harary和Norman[6]在1960年首次提出了線圖的概念。線圖是圖論中最重要的課題之一，它所對應的圖論參數有連通度，Euler性和Hamilton性等。鑒于線圖的重要性，Hemminger和Beineke[7]寫了一篇文獻綜述。基于線圖方法，我們可以設計和分析互聯網拓撲結構。

圖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 線圖彩虹著色的相關結論

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

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

3.3 線圖的應用

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

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

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

4 與凱萊圖相關的研究

4.1 凱萊圖

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

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

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

4.2 凱萊圖彩虹著色的相關結論

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

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

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

4.3 凱萊圖的應用

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

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

5 啟示與展望

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

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

參考文獻

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