变换图G^＊xy的独立数

变换图的概念由全图推广而来。文章在中图的补图M^-（G）的定义启发下,定义了四类变换图,其中一个恰是M（G）,并探讨了这些变换图的独立数。研究了变换图G^＊-＋的独立数与原图最大度的关系,以及G^-＋＋与G^-＋-的独立数与原图边独立数的关系。     

Hamiltonian连通图的一个范—型条件

在一个图Ｇ中，对于两个不相邻点ｕ，ｖ，用ａ（ｕ，ｖ）表示包含ｕ和ｖ的最大独立集的数。本文证明了：如果Ｇ是一个包含ｎ个顶点的３－连通图，对于Ｇ中每一对满足１≤｛Ｎ（ｕ）∩Ｎ（ｖ）｜≤ａ（ｕ，ｖ）－１的不相邻楔点ｕ，ｖ有ｍａｓｘ｛ｄ（ｕ），ｄ（ｖ）｝≥ｎ＋１／２，那么Ｇ是Ｈａｍｉｌｔｏｎｉａｎ连通的或者Ｇ属于特殊图类。     

单圈图的Merrifield-Simmons指数的极值图

用i(G)表示图G的Merrifield-Simmons指数,定义为G的独立集数目.利用图的关于Merrifield-Simmons指数的变换技巧,研究了单圈图的Merrifield-Simmons指数,得到Merrifield-Simmons指数前八大的单圈图,刻画了极值图.     

几个NP完全问题的整数规划模型

文中给出了图论中受度约束的生成树、最短全部通路长的生成树、团和独立集等六个ＮＰ完全问题的整数规划模型，使这些问题能应用任一种求解整数规划的算法去求解。     

关于2-连通图中最长圈的一个注记

设Ｇ是一个ｎ阶２－连通图，ｍ＞０是一个整数．本文证明了：如果对于图Ｇ中任意三点独立集Ｓ＝｛ｕ，ｖ，ｗ｝｝，都存在ｘ≠ｙ∈Ｓ使得ｄ（ｘ）＋ｄ（ｙ）≥ｍ，则ｃ（Ｇ）≥ｍｉｎ｛ｎ，ｍ｝．其中ｃ（Ｇ）表示图Ｇ的周长．这个结果推广了三个有关的已知结果。     

邻集与Hamilton性质

设G是阶为n的简单图，我们证明对于G中任何2－独立集S＝u,v,w，存在两点，x,y∈S，使λxy≥min{a^2xy,t^2xy 1}或S中任意两点xy，使|N(x)∪N(y)|≥n-△（S），则G是Hamilton图。     

图的最大独立集问题的模拟退火算法

给出了一种具有全局优化特性的改进的模拟退火算法，建立了图的最大独立集的模拟退火模型，研究了扰动的形成和算法参数的选择，并用计算机进行模拟。结构表明该算法是有效的。     

Ramsey数下界的一个新结果

Ramsey数是组合数学中很有意义的一个数^[1]，但确定Ramsey数的具体数值仍是一个尚未解决的问题，因此，给出Ramsey数尽可能小的上界和尽可能大的下界是有意义的。通过构造两个图的连结图，利用连结图的性质，得到求Ramsey数下界的一个新公式，利用该公式得到的Ramsey数的下界比其它公式得到的要好。     

Hamiltonian连通图的一个范－型条件

在一个图Ｇ中，对于两个不相邻点ｕ，ｖ，用α（ｕ，ｖ）表示包含ｕ和ｖ的最大独立集的个数．本文证明了：如果Ｇ是一个包含ｎ个顶点的３－连通图，对于Ｇ中每一对满足１≤｜Ｎ（ｕ）∩Ｎ（ｖ）｜≤α（ｕ，ｖ）－１的不相邻顶点ｕ，ｖ有ｍａｘ｛ｄ（ｕ），ｄ（ｖ）｝≥ｎ＋１２，那么Ｇ是Ｈａｍｉｌｔｏｎｉａｎ连通的或者Ｇ属于特殊图类     

若干色临界图和色极小图的构造

一个图Ｇ,若对任意的顶点Ｖ（边ｅ）,Ｘ（Ｇ－ｖ）＜Ｘ（Ｇ）（Ｘ（Ｇ－ｅ）＜Ｘ（Ｇ））,则称Ｇ是色临界的（色极小的）．给出了色临界图和色极小图的几个构造方法,并探讨了这些构造方法的性质。     

关于简单图的独立集多项式

定义了简单图的独立集多项式，讨论了图的独立集多项式与图的匹配多项式的关系，给出了图的独立集多项式的结构特征。     

图的色数问题研究（续）

进一步研究发现,“图的色数问题研究”一文中的“算法”,实际上是构造图的着色方案的一种算法,也可能得到图的色数,也可能是一种近优值。为了完善该算法,在对不同的最大独立点集进行比较分析后,归纳出存在有多个最大独立点集时,从中选取色数分块的选优准则,并对最大独立点集的有关性质定理作了证明,从而使图的色数算法得以完善。     

Hamilton连通图的一个Fan型条件

设G是一个n阶3-连通图,本文证明了:若对G中任意两个不相邻的顶点u和v使得1≤|N(u)∩N(v)|≤α_(uv),蕴含max{d(u),d(v)}≥(n+1)/2,则G是Hamilton连通的。     

无爪图中的邻集交和Hamilton性质

本文证明了如下结果：设G是n阶2连通无爪较,K为连通度,若对G中每一个阶为K＋1的独立集S,存在u,v∈S,有|N(u)|≥（n-2k)/4,则G是Hamilton图。     

利用最小缓和集族策略解决知识管理系统中角色冲突

在知识管理系统中,数据库管理员在给个人或群组配置角色时,可能会出现“角色冲突”现象,本文提出了一种有效解决这个问题的办法——最小缓和集族策略,并利用图论中极大独立集与极小点复盖之间的关系以及逻辑运算,给出了最小缓和集族的算法.