一类图的独立多项式的指标

本文将在给定的条件下,对任意的独立数为α（G）=5,6的图G,证明G^＊的独立多项式是单峰的,并给出G＊的独立多项式的指标的可能的位置.     

关于图多项式及圈唯一性

证明对于１≤ｉ≤ｓ，当ｒｉ≤ｐ／２时，ｐ阶完全多部图Ｋｒ１，ｒ２，…，ｒｓ是圈唯一的．并且给出了圈多项式、匹配亏量多项式及特征多项式相等的充要条件．     

一个求解简单超图中最大独立集的算法

本文从贪婪横贯求法中得到启示,通过改进得到一种基于贪婪准则的求解有限的简单超图的极大独立集的算法:求出一定数量的极大独立集合,再从中挑出顶点数最多的作为极大独立集合。给出了算法和它的时间复杂度的分析以及正确性的证明。     

一类单圈图的最大独立集的交

设G=(V(G),E(G))为有限简单图,X是V(G)的子集.若X中任意两个点不相邻则称X是独立集.用core(G)表示G的所有最大独立集的交.X的差是指X的顶点数与其邻集的顶点数之差.在G的所有顶点子集中,差最大的子集即为G的临界集.用ker(G)表示G的所有临界集的交.在图G中,core(G)?ker(G);当图G...     

枚举图的全部极大独立集的普遍性方法

完整地研究了寻找一个图的全部极大独立集所需要的理论、寻找范围、计算公式和枚举方法，采用有根树描述，以邻接矩阵中任意一行所对应的顶点为根，再以该行中各个非零元素所对应的那些顶点为根，按照文中所述方法生成有根树，这些有根树就描述出图的全部极大独立集，本方法已用计算机程序实现。     

关于平面图的几类一元运算图的特征多项式

给出了由平面图经一元运算而构造的4类图,并得到了这4类图的特征多项式.     

图中度和与基本独立集

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

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

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

关于多项式Julia集的几何估计

主要讨论几类具有高拓扑度的多项式Ｐ的Ｊｕｌｉａ集Ｊ（Ｐ）的性质,包括（Ⅰ）对Ｊ（Ｐ）的范围的估计：（Ⅱ）一类特殊的具有相同Ｊｕｌｉａ集且同度的多项式间的共轭性。     

一个求外平面图最小反馈点集的多项式时间算法

如果从一个图中去掉某些顶点后得到的导出子图是无圈图，则所去的那些顶点组成的集合就是原图的反馈点集。本文讨论外平面图的反馈点集并给出了一个求外平面图最小反馈点集的多项式时间算法。     

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

设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和H的匹配多项式相等,则称它们匹配等价.用δ(G)表示图G的所有不同构的匹配等价图的个数.计算了一些路的并图的匹配等价图的个数.首先将整数m(≥2)按它所含的最大奇因数分成3-系和2k(k=1.2,…)-系,再按它所含2的方幂分为级.设A是不小于2的整数组成的可重集,B_i(i=1,2,…,t)是同系整数构成的可重集,且A=B_1∪B_2∪…∪B_t,则δ(■P_i)=■δ(■P_i),若x∈B_i,y∈B_j(i≠j),则x与y是互不相同系的整数.设B={m_1~(k_1),m_2~(k_2),…,m_n~(k_n)}是同系整数构成的可重集,其中m_i(≥2)是第i级的,有k_i(≥0)个,则n =1,δ(■P_i)=1;n≥2,δ(■P_i)=sum from i_m-0 to k_n sum from i_(m-1)-0 to k_(n-1) i_m…sum from i_2-0 to k_2 i_3 1.作为推论,计算了路并补图的匹配等价图的个数.     

循环图及单圈图的有效控制集与完美控制集

图的完美控制集和有效控制集是两类特殊的控制集．通常要判断一个图是否存在有效控制集是困难的．该文证明了无向循环图一定存在有效控制集．此外，给出了单圈图的完美控制数与其阶数的关系．     

Halin图的集染色

对于非平凡连通图G,G的k集染色是指映射c：V（G）→Nk,对任意顶点v∈V（G）,定义邻色集cN（v）={c（u）｜u∈N（v）},若对uv∈E（G）有cN（u）≠cN（v）,则称c为G的一个k集染色.满足上述条件的最小k值称为G的集色数,记为χs（G）.为了更快更有效地给Halin图着色,采用集染色的着色方法,证明了当p≥4时,Halin图G（Cp,Tq）的集色数是3,并且还证明了对任意的Halin图G（Cp,Tq）,有p＋1≤q≤2p-2成立.     

简单连通图的k阶幂图的指数集(英文)

设Ｇ 是一个ｎ 阶简单连通图,ｋ≥２ 是一个整数．Ｇ 的ｋ 阶幂图记作Ｇｋ ,定义为：Ｖ（ Ｇｋ） ＝ Ｖ（ Ｇ） 且对任意ｕ ,ｖ∈Ｖ（ Ｇｋ） （ ｕ≠ｖ） ,（ ｕ ,ｖ） ∈Ｅ（ Ｇｋ） 当且仅当ｄＧ（ ｕ ,ｖ） ≤ｋ ,则对任意的ｋ≥２ ,Ｇｋ 本原．令Ｅ（ｋ,ｎ） ＝ ｛ γ（ Ｇｋ）｜ Ｇ 是ｎ阶简单连通图｝ ,可以得到Ｅ（ｋ ,ｎ） ＝ｄｋ ｋ＋ １ ≤ｄ ≤ｎ － １ ,　　若２ ≤ｋ≤ｎ － ２ ,｛２｝ ,　　　　　　　　　　　　若ｋ≥ｎ － １ ．     

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

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

基于扩展多项式集的一种串行乘法器设计

基于多项式基定义了扩展多项式集,利用其形式表示有限域F_2n中的元素.通过分析多项式集下的乘法运算公式,设计出一种有效的串行乘法器,仅需n个异或门和n+1个门数.     

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

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

极大独立集的逻辑算法

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