网络安全是一门涉及计算机科学、网络技术、通信技术、密码技术、信息安全技术、应用数学、数论、信息论等多种学科的综合性学科。通常,网络安全定义为:“保护网络系统中的软件、硬件及信息资源,使之免受偶然或恶意的破坏、篡改和泄露,保证网络系统的正常运行、网络服务不中断。”随着网络规模的扩大和网络动态性的发展,网络安全问题已经受到了极大的关注并得到广泛研究。从本质上讲,网络安全是“攻击者”和“保护者”之间的对抗,所以我们在研究的过程中将博弈论的思想应用到网络攻击和网络防御中。网络的拓扑结构可以用图来表示,我们可以通过研究图的性质来研究网络的结构。研究图的性质的理论就是图论。本文就是通过图论和博弈论的相关知识来研究网络安全问题。本文考虑的所有图都是|V(G)|=n,|E(G)|=m的无向简单图G(V,E)。一个信息网络被描述成一个无向图G(V,E),顶点代表网络中的主机,边代表通信联系。我们把网络安全问题转化为在图G上的非合作。多人组成的策略博弈。本文分为六章,主要研究了三种基于图论的网络安全博弈,并得到了一些结果。首先,论文讨论了病毒攻击者和系统保护者之间的博弈,证明了在一些特殊的图中可以在多项式时间内计算网络攻击者与保护者博弈的混合纳什均衡.这些特殊图包括:正则图,完美图,非二部图。另外,论文根据攻击者对网络的另一种攻击方式,提出了一种新型的保护者-攻击者模型,迹模型,证明了在迹模型中纯纳什均衡的存在性,并与Mavronicolas提出的边模型和路径模型进行了比较。其次,论文研究了病毒受害者的接种策略博弈,分析了病毒受害者的接种策略博弈中纯纳什均衡的计算问题,并证明了计算具有最低费用的纯纳什均衡和计算具有最好费用的纯纳什均衡是NP-hard问题。还给出了最坏纳什均衡是如何影响接种费用的变化情况和混乱状态代价的上界值和下界值。此外,论文还研究了网络数据的安全传输博弈,不仅从理论上证明了网络数据安全传输博弈过程存在混合纳什均衡解,且攻防双方在均衡点处所取得的收益值是最大的,还用具体的网络拓扑从数值上说明了这一点。