求最大完全子图的启发式着色算法

本文提出了一种求最大完全子图的启发式着色算法.该算法通过为顶点着色将已知无向图划分为极大完全子图的并集,再根据各极大完全子图中顶点的多少选取最大完全子图.随后为提高算法执行效率,又对该算法提出了一种精简措施.最后将该算法运用于一集成电路测试数据编码压缩实验中,证明了该算法对求解最大完全子图的有效性.     

K3,4的生成子图的计数和构造

给出了生成子图的定义;证明了生成子图的计数定理和构造定理;提出了生成树的计数方法和构造方法;介绍了完全二分图K3,4的生成子图的计数和构造.     

团图为数的图中的闭团贯数

Given a graph G,a subgraph C is called a clique of G if C is a complete subgraph of G maximal under inclusion and |C|≥2. A clique-transversal set S of G is a set of vertices of G such that S meets all cliques of G. The clique-transversal number, denoted as TC (G), is the minimum cardinality of a clique-transversal set in G. The clique-graph of G, denoted as K (G), is the graph obtained by taking the cliques of G as vertices, and two vertices are adjacent if and only if the corresponding cliques in G have nonempty intersection. Let F be a class of graphs G such that F={G|K(G) is a tree}. In this paper the graphs in F having independent clique-transversal sets are shown and thus TC (G)/|G|≤1/2 for all G ∈ F.     

不含2K_2为导出子图的图的染色

利用强完美图定理,得到不含{2K2、C4、C5}为导出子图的图是完美图。进而证明了每一个不含{2K2、C4}为导出子图的图是(ω(G)+1)可着色的,并且给出一类满足不含{2K2、C4}为导出子图且χ(G)=ω(G)+1的图类,其中ω(G)和χ(G)分别为图G的团数和色数。     

哈密尔顿图的一个充分条件

本文用ＮＣ２去研究哈密尔顿图,得到比文献「１」「２」「３」「４」的一些结果好的结果。     

禁用子图为2K_2和K_1+C_4的图的色数

通过对禁用子图为2K_2和K_1+C_4的图的结构进行分析,利用强完美图定理,得到了该类图色数的一个关于团数的线性函数的上界。此结果是对Wagon关于2K_2结论的精细刻画,是Gyárfás猜想的特殊类型。     

图的笛卡尔积的邻域完整度

图的邻域完整度是由M .B .Cozzens和S .-S .Y .Wu在文献 [1]中引入的一个衡量网络的脆弱性的参数。首先利用投影法 ,得出了图K2 ×Cn 和图K2 ×Pn 的邻域完整度的一个界 ;其次通过对图Km×Kn 的图形的分析 ,利用递归的方法 ,对图Km×Kn 的邻域完整度进行了讨论     

完全图K7的性质

本文证明了在文献[1]和[2]的命题条件下,不存在恰好3个同一色三角形的完全图K7,而是至少存在4个同一色的三角形.     

完全二部多重图的K1,k—因子分解

本文讨论了二部多重图λKm,n的K1，k-因子分解，给出λKm，存在K1,k-因子分解的必要条件以及kKm,n存在K1,k-因子分解的充分条件。     

禁用子图为C_4和K_1∪P_4的图色数上界

利用图的结构分析法,得到了禁用子图为C_4和K_1∪P_4的图的一个结构定理,根据强完美图定理,得到了该类图色数的一个关于团数的线性函数的上界。进一步得到了禁用子图为2K_2和K_1+P_4的图色数上界,此结果是对Wagon关于2K_2结论的精细刻画,是Gyárfás猜想的特殊类型。     

特殊子图的计数

计数问题是图论研究的一个课题,图的一些特殊子图的计数确定了图的着色性;在这里使用组合数学的方法,估计了二部图K（u,v）-A和三部图K（n＋a1,n＋a2,n＋a3）-A的三角形子图和没有弦的四边形子图的计数,在三部图中比较了这些特殊子图的计数。     

L图的确定

通过对Ｌ图存在性的探讨研究，得出结论：当顶点数ｖ与边数ε分别满足公式。ｖ＝２＋∑＾ｍｎｎ＝１ε＝ｖ＋ｍ－１（２≤ｍ≤３）时，可以确定出人图。     

平面图的着色数

用数学归纳推理的方法，论证了图论中的简单平面图Gn是4着色的．     

特殊子图的计数

计数问题是图论研究的一个课题,图的一些特殊子图的计数确定了图的着色性;在这里使用组合数学的方法,估计了二部图K(u,v)-A和三部图K(n+a1,n+a2,n+a3)-A的三角形子图和没有弦的四边形子图的计数,在三部图中比较了这些特殊子图的计数.     

禁用子图为P3∪mP2的图色数上界

Gyárfás在完美图概念的基础上,提出了色界函数的概念,并给出猜想：对于给定的森林F,存在整数函数f (F, x)使得每一个以F为禁用子图的图G都满足χ(G)≤f (F,ω(G)),其中χ(G)和ω(G)分别表示图G的色数和团数。通过分析禁用子图为P₃∪P₂的图结构,给出色界函数f (P₃∪P₂,ω(G))的一个上界;并且以此为基础,得到禁用子图为P₃∪mP₂的图色数上界。     

具有性质Γ(x)(≌)3*K3的距离正则图的一些结果

讨论了具有性质Γ(x)(≌)3*K3的距离正则图当d=r+2,cr+1=2时的一些情形,证明出当d=r+2,cr+1=2时,ar+1≠5.     

L图的确定

通过对L图存在性的探讨研究 ,得出结论 :当顶点数ν与边数ε分别满足公式。ν=2 ∑mn=1 n　　ε=ν m - 1　 ( 2≤m≤ 3)时 ,可以确定出人图     

关于对图最小覆盖算法的一点补充

通过对图的最小覆盖的理解，结合分析图的关联矩阵的特点，对文献[1]中求一图的最小覆盖集的算法作了一定的补充，使其更具有一般性和通用性。     

团树传播算法在贝叶斯网络攻击图中概率计算分析

攻击图模型中对属性节点的状态评估主要是通过计算该节点置信度进而分析节点的威胁状态。当前运用贝叶斯攻击图评估整体网络安全性,在计算贝叶斯攻击图先验概率以及结合入侵检测系统计算后验概率方面,存在属性节点增加,贝叶斯网的计算复杂度呈指数级增长的问题。针对计算复杂度问题,提出了一种将贝叶斯网络攻击图转化成团树的方法,降低了计算过程中的时间复杂度。实验结果表明,采用该方法使计算节点的置信度、时间复杂度得到一定程度降低。     

连通图的(邻接)树图的上可嵌入性

若图G可2胞腔嵌入到可定向曲面S上，且G嵌入S后至多只有2个面，则称G在S上是上可嵌入的，文章证明了：若图G是连通图，则G的邻接树图Gt、树图Gr都是上可嵌入的。