生成图的全部极大独立集的一般方法

图的极大独立集问题是图论中重要的NPC问题,独立集具有广泛的应用领域,如编码理论、信道分配、资源配置、纠错码理论等.文章运用拟序关系理论,系统研究了生成图的全部极大独立集的一般方法,该方法简单实用,程序化实现容易.     

含有2个最大度点的树的极大独立集个数

研究了限制条件下图的极大独立集的计数问题.运用数学归纳法,给出了含有2个最大度点的树的极大独立集个数的最大值,同时刻画了取得最大值时的树.     

基于极大独立集的协作竞价频谱分配算法

将认知无线电中的动态频谱分配归结为图论中的着色问题.针对目前基于系统吞吐量的分布式贪婪算法和基于复杂度的分布式随机算法效率不高的问题,提出了一种改进的基于极大独立集(MIS)的协作竞价算法.根据MIS中协作用户出价高于集外认知用户最大效用,可以获得授权用户的效用曲线,从而最大化系统总效用,达到充分利用频谱资源的目的.此外,协作竞价算法还能在一定程度上抑制用户之间的共谋.     

基于图着色的极大团求解算法

极大团问题是图论中一个经典的组合优化问题,也是一类NP完全问题,在国际上已有广泛的研究。作者在对其他现有极大团求解算法进行研究之后,设计了一种基于图着色思想的极大团求解算法。基本思想是通过不同的方式对随机图的相应补图进行顶点着色,寻找出所有顶点的极大独立集。而后返回到原图之中找出极大团,并且通过比较删减寻找到随机图的所有极大团。     

极大独立集的逻辑算法

给出了利用命题逻辑公式的析取范式和主析取范式求图的独立集和极大独立集的方法，并给出了一解算法。     

独立集可削去因子临界图和无爪的独立集可削去因子临界图的度条件

研究了不含开邻集是独立集或空集的小团(奇数个顶点)的独立集可削去因子临界图以及无爪的独立集可削去因子临界图的度条件.     

图中度和与基本独立集

设Ｇ是一个图，ｐ（Ｇ）和ｃ（Ｇ）分别表示Ｇ中最长路的阶和最长圈的阶。本文将证明如果Ｇ是连通图σ３（Ｇ）≥ｎ，那么或者Ｇ包含一条Ｈａｍｉｌｔｏｎ路或者ｃ（Ｇ）≥ｐ（Ｇ）－１。     

认知无线电中基于极大独立集的频谱分配算法

针对认知无线电系统的特点和要求,建立图论着色扩展模型,提出一种基于极大独立集的频谱分配算法.在不考虑频谱效益差异性的情况下,该算法能够有效兼顾频谱分配的利用率和公平性,并能够减小分配的收敛时间,更加适合认知无线电动态频谱分配的实际要求.对于算法的频谱利用率和公平性能,该算法与列表着色贪婪算法和列表着色公平算法进行比较,仿真结果分析验证了该算法的性能.     

最大独立集在高校排课表系统中的应用

在分析排课系统特征的基础上,利用图论中最大独立集的理论,对排课资源进行合理抽象并建模,实现自动排课的功能要求,并进行算例分析.算例分析表明,该方法解决排课表问题相当实用,而且效率较高.该方法具有效性和可靠性.     

关于Ramsey图:一个递归型查找图中所有给定元素个数独立集的算法

改进了作者在文献〔1〕中给出的算法 ,给出一个速度较快的新算法 ,对一个可能的 ( s,t,n) -Ramsey图 ,该算法可以找出其中所有给定元素个数的独立集 ,进而可以检验该图是否是一个 ( s,t,n) -Ramsey图 .     

点可迁图中的两个不相交的极大独立点集

C.Berp,E.J.Ockayne和S.T.Hedetniemi猜想每个非空点可迁图包含两个不相交的极大独立点集.本文证明了下面的结果: 1.设L在V(G)上可迁且为交换群,则G有两个不相交的极大独立点集。 2.设L在V(G)上可迁且为幂零群,则G有两个不相交的极大独立点集。 3.p~k阶(p为素数)非空点可迁图包含两个不相交的极大独立点集。     

利用初等行变换求极大无关组的一些条件

本文讨论利用初等行变换求行向量组的极大线性无关组的方法,澄清一些线性代数教学用书中存在的一种模糊认识,并给出修正后的方法。     

极大前缀集的一些刻画

设M(X)是字母表X上的语言幺半群.给出了M(X)的极大前缀集的一些刻画.     

哈密尔顿性和部分平方图的独立集

设G是一个图,G的部分平方图G^＊满足V（G^＊）=V（G）,E（G^＊）=E（G）∪{uv：uv∈E（G）,且J（u,v）≠φ},这里J（u,v）={w∈N（u）∩N（v）,N（w）（∈）N[u]∪N[v]}.本文利用插点方法,给出了关于k,或（k＋1）-连通（k≥2）图G是哈密尔顿的,1-哈密尔顿的或哈密尔顿连通的统一证明.其充分条件是在图G中关于^k∑i=1｜N（Yi）｜＋b｜N（y0）｜与n（Y）的不等式,这里Y是图G的部分平方图G^＊的任一独立集,对于i∈{1,2,…,k},Yi={yi,yi-1,…,yi-（b-1）}（∈ ）Y（yj的下标将取模k）;b是一个整数,且0＜b＜k＋1;n（Y）=｜{v∈V（G）,dist（v,Y）≤2}｜.     

图与其补图的独立数之间的关系

文章讨论了图G及其补图(?)的独立数之间的关系,得到的主要结果是a(G) a((?))(?)n 1.