在信息时代,互联网的蓬勃发展推动着社会的进步,并影响着我们生活的方方面面。人们对互联网的依赖促使了对网络空间安全领域研究的迫切需求。通过将网络中的主机和服务器等看作点,将他们之间的联系或通路看作边,计算机网络可以被抽象成图,这也揭示了信息网络科学与图论之间的紧密联系。在计算机科学的研究中,研究人员经常使用图模型来刻画分析网络,并借助图论方法解决实际问题。其中,图划分方法在网络安全相关问题的研究上有着十分广阔的应用前景,例如网络的去中心化与网络的稳定性分析等问题。同时,图划分理论在图论学科中有着重要的地位,产生了众多著名的研究成果,并且在大规模集成电路设计等领域也具有重要的应用价值。本文着眼于网络空间安全中的图划分理论,主要分析的划分模式包括可行划分、公平划分以及一类特殊的划分—Erd（?）s-Pósa性质与横截集。无向图模型在应用中的重要性是显而易见的,而有向图模型又是网络安全分析的有效工具。于是就划分的讨论对象而言,本文同时考虑了有向图和无向图（包括简单图和重边图）。具体的研究工作和贡献陈述如下。1.将网络可靠性及去中心化组网问题转化为简单图和重边图最小度限制条件下的划分问题展开研究,得到保证可行划分存在性的条件。网络可靠性与图论理论中的连通性密切相关,而组网方式在其中起着重要的影响作用。由于中心化网络在遭受攻击时易发生大规模网络瘫痪,于是人们开始寻求稳定性更高的网络模式,进而去中心化网络逐渐成为了人们关注的方向。针对该问题,在第2章中分别研究了简单图和重边图的可行划分,考虑需要什么样的最小度限制条件能够满足存在性成立。取图G和两个顶点赋值函数a,b:V（G）→N\{0,1},如果V（G）的一个划分（A,B）对任意x∈A都有dA（x）≥ a（x）,且对任意y∈ B都有dB（y）≥b（y）,那么称（A,B）为一个（a,b）-可行的划分。针对可行划分问题,采取结合反证及结构分析的方法,首先对划分定义权值函数,然后在初始两部之间进行移点操作来观察权值函数取值的变化情况,进而分析结构找到矛盾。在研究的过程中,度的限制条件在权值函数计算时起到了重要作用。具体研究结论阐述如下。·首先,关于简单图的一些特殊族类,得到了若干结论:令G是一个H-禁用的简单图,（i）当H∈ {E5+,{L3+},{F1,1},{F2.0,F0,2}}时,度限制条件dG（x）≥a（x）+b（x）可以保证（a,b）-可行划分的存在性。（ii）当H={C3,C6,H}时,度限制条件dG（x）≥a（x）+b（x）-1可以保证（a,b）-可行划分的存在性,其中H是用两条长度分别为2和3的内部不相交路径替换K4中两条不相邻的边得到的图。这些结果可以涵盖现在已有的很多结论,同时具有紧性。·其次,通过寻找反例证明了结论:令G是一个不包含三角形和K2,3的图,度限制条件dG（x）≥ a（x）+b（x）-1无法保证（a,b）-可行划分的存在性。该结论对Liu和Xu的一个问题给出了否定的答案。·最后,对于重边图G,如果图G中每一个四边形都不与其他三角形或者四边形共边,那么度限制条件dG（x）≥a（x）+b（x）+2μG（x）-3可以保证（a,b）-可行划分的存在性。2.利用攻击图模型讨论网络空间安全风险评估问题,研究了有向图和无向图的公平划分,寻找到同时满足多个参量优化的划分方式。网络空间安全风险评估从攻击者的角度出发,综合分析网络状况,帮助网络管理者清晰网络,进而提升网络安全性。该问题可以抽象为对攻击图模型的讨论。针对该问题,在第3章中分别研究了有向图和无向图的公平划分,致力于寻找同时满足多个参量优化的划分。本章主要采用顶点赋值的方法,在合适的初始赋值上逐步增加扰动,直至找到满足条件的划分。该方法具有很大的优势:其在优化多个参量的同时还能够控制划分所得两部分的点数大小。这也更便于在后续的应用中根据需求设定划分两部的大小条件。具体研究结论阐述如下。·对于任意有向图D,致力于寻找可以同时优化e（V1,V2）和e（V2,V1）取值的划分。主要证明了结论:D中存在顶点划分V=V1∪V2使得|V1|=[n/2]+k和|V2|=[n/2-k,并且min{e（V1,V2）,e（V2,V1）}大于等于[（[n/2+k）（[n/2]-k）m/n2-ρ/4-1/2],其中 ρ = maxu,ν∈V|s（u）-s（ν）|和s（u）=d+（u）-d-（u）。该结论具有紧性。同时其在k=0时的推论改进了许多现有的结果。·对于无向图G,致力于寻找可以同时优化e（V1）和e（V2）取值的划分。主要证明了结论:G中存在顶点划分V=V1∪V2使得|V1|=[n/2]+k和|V2|=[n/2]-k,并且max{e（V1）,e（V2）}小于等于[（[n/2]+k）2m/n2+（Δ-δ+1）/4],其中Δ和δ分别为图G的最大度和最小度。该结论同样具有紧性。3.以覆盖图网络中的圈结构为目的寻找小的横截集,研究了关于Erd（?）s-Pósa性质的Birmelé-Bondy-Reed猜想,提升了已有的界。图网络中圈结构的存在会增加分析的复杂性以及网络系统的不稳定性,如网络安全分析中的含圈攻击路径问题。故考虑如何覆盖图网络中的圈结构。该问题与理论计算机科学中众所周知的反馈集等问题密切相关。针对该问题,在第4章中研究了一类特殊的划分问题—横截集,讨论了关于Erd（?）s-Pósa性质的Birmelé-Bondy-Reed猜想:对于任意整数l≥3,如果图G中长度大于等于l的圈两两顶点相交,则G中存在一个可以与所有长度大于等于l的圈都相交的顶点子集且其大小至多为l。本章通过结合Menger定理以及结构分析的方法证明了满足条件的小于等于3l/2+7/2个点的横截集的存在性。该结果改进了 Birmele,Bondy 和Reed 的界 2l+3 以及 Meierling,Rautenbach 和 Sasse 的界5l/3+29/2。