基于彩虹着色的网络安全研究

陈其 金素萍 徐佳衡 杨双双

摘 要：针对网络攻击者经常利用破坏防火墙对网络进行渗透攻击的特点，我们提出基于图论的网络安全优化与应用方法，运用已有的彩虹着色理论设置防火墙。以计算机网络为研究对象，我们分别研究线图与凯莱图彩虹着色的相关结论，建立图论模型将结论运用于网络构造中设置网络防火墙，提高网络安全性进而优化网络。

关键词：网络安全；彩虹着色；彩虹连通图；线图；凯莱图

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.