3度图的最小顶点覆盖问题的多项式时间算法

最小顶点覆盖问题是图论和组合数学中经典的NP-Hard问题之一,在实际问题中有着广泛的应用.本文首先给出最小顶点覆盖问题的若干性质,然后根据这些性质设计了3度图最小顶点覆盖问题的一个多项式时间算法,并通过2个实例对算法进行了说明.     

Petersen图的点传递正则覆盖图

运用基图自同构能被提升的线性准则 ,对满足 :1覆叠变换群 K =Znp,2覆盖图的保簇变换群是点传递的 Petersen图的连通正则覆盖图进行了完全分类 .这种图共有 1 2种类型 .     

最小权点覆盖问题的一个近似算法

在点、边赋权的简单图中,关于最小权点覆盖问题,以经典的最短路算法-Dijkstra算法为基础,提出了一个求解该问题的近似算法.首先,在给定的赋权图中任选一点作为初始点,并给出允许集及相关定义.然后,利用经典的最短路算法-Dijkstra算法,求出初始点到允许集中各顶点的最短路径,并按照一定的原则选择近似最小权点覆盖集.最后,通过算例阐释了算法的实现过程的合理性及有效性.     

基于LBP算子和类覆盖捕获图的人脸检测算法

针对传统人脸检测中的过分类问题,提出一种结合LBP算子与类覆盖捕获图的人脸检测算法.该算法首先用ε-LBP算子提取人脸图像纹理特征,并把对应不同ε值提取的LBP特征数据加权融合起来,形成人脸图像特征向量,然后采用类覆盖捕获图构造分类器,最终对人脸图像实现有效检测.与传统方法相比,基于随机图理论的类覆盖捕获图能够克服过分类缺陷,比其他近邻图分类器更具优势,性能也比较稳定.实验结果表明,该算法可以有效检测人脸图像,尤其对存在模糊和光照异常的人脸图像具有较高的精确度和鲁棒性.     

f—因子覆盖的图

设G为图,f是定义在V(G)上的正整数值函数。称图G的支撑子图F为f-因子如果d_(?)(x)-f(x),x∈V(G).称图G是f-因子覆盖的如果G的每条边包含在一个f-因子中.本文给出了一个图是f-因子覆盖的图的充要条件,其结果推广了C.H.C.Little et al.[1]的1-因子覆盖定理。     

笛卡尔乘积图里的最小k-路点覆盖

对于子集$S\subseteq V(G)$,如果图$G$里的每一条$k$路都至少包含$S$中的一个点,那么我们称集合$S$是图$G$的一个$k$-路点覆盖.很明显,这个子集并不唯一.我们称最小的$k$-路点覆盖的基数为$k$-路点覆盖数, 记作$\psi_k(G)$.本文给出了一些笛卡尔乘积图上$\psi_k(G)$值的上界或下界.     

λKv的最大K2,3填充设计和最小K2,3覆盖设计

对于一个有限简单图G,λKv的G-设计(G-填充,G-覆盖),记为(v,G,λ)-GD((v,G,λ)-PD,(v,G,λ)-CD),是一个(X,B),其中X是Kb的顶点集,B是Kv的子图族,每个子图(称为区组)均同构于G,且Kv中任一边都恰好(最多,至少)出现在B的λ个区组中.一个填充(覆盖)设计称为是最大(最小)的,如果没有其它的这种填充(覆盖)设计具有更多(更少)的区组.本文对于λ>1确定了(v,K2,3,λ)-GD的存在谱,并对任意λ构造了λKv的最大K2,3-填充设计和最小K2,3-覆盖设计.     

Ad Hoc网络区域划分和资源分配问题研究

主要利用图论、概率统计及优化理论对Ad-Hoc网络进行了数学建模.研究了等圆(不等圆)区域覆盖、带障碍区域的覆盖、确定性点覆盖、信道分配、抗毁度、节能性和通信质量等问题.定义了覆盖效率、抗毁性概率指标、覆盖系数、期望覆盖系数、网络寿命等一系列评价系数和衡量标准,提出了基于单位距离覆盖系数和期望覆盖系数的启发式寻优算法,并编程加以实现,得到较满意的近似解.     

图的κ-覆盖与Grbner基求解

证明图的k-覆盖存在性问题等价于一个多元多项式方程组在{0,1}范围的求解问题,并通过使用Grbner基给出一个图有k-覆盖的有效判别与求解方法,进而求得图的覆盖数和极小覆盖.     

通往图的双圈覆盖猜想的新途径

本文提出了一些新的方法以接近图的用圈二重覆盖边的猜想,通称图的双圈覆盖猜想。因２０余年尚未解决而在图论中著名。从中,也提出了一些新的猜想。并论述了它们之间,以及它们与图的驿圈盖猜想之间的关系。     

消去图、覆盖图和均匀图的若干结果

设 G是一个图 ,g,f是定义在图 G的顶点集上的两个整数值函数 ,且g≤f.图 G的一个 ( g,f) -因子是 G的一个支撑子图 F,使对任意的 x∈V( F)有g( x)≤ d F( x)≤ f ( x) .文中推广了 ( g,f) -消去图、( g,f ) -覆盖图和 ( g,f) -均匀图的概念 ,给出了在 g相似文献   

关于一类(g,f)-3-覆盖图的判据

本文首先给出了(g,f)-3-覆盖图的定义,即一个图G称为(g,f)-3-覆盖图,如果G的任何三条边都属于它的一个(g,f)-因子；其次,黄光鑫曾先后给出了当g＜f时一个二部图分别是(g,f)-2-覆盖图和(g,f)-3-覆盖图的充分必要条件,在此基础上,本文进一步得到了,当g≤f时一个二部图G=(X,Y)是(g,f)-3-覆盖图的一个充分必要条件；最后,研究了f(X)=f(Y)的情形,得到了当f(X)=f(Y)时一个二部图G=(X,Y)是f-3-覆盖图的一个充分必要条件．     

曲面上图的短圈结构与Mohar和Thomassen的一个问题的解决

研究了(赋权)图的圈基结构并且对包含在最小圈基中的短圈提供了大量信息. 建立了一个基变换的Hall型定理, 利用此定理, 给出了判断一个圈基是最小圈基的充分必要条件, 而且，证明了一个(赋权)图的最小圈基结构是唯一的. 这一性质对于最大圈基也成立 (尽管在最小圈基方面已有很多工作, 而在最大圈基方面的工作几乎没有). 利用这些方法， 发现了(赋权)图中具有特定性质的短圈的一些新结果. 作为应用， 决定了一个嵌入图的短圈的结构, 并找到一个多项式算法能够判断一个嵌入图中是否存在双侧圈, 如果这样的圈存在, 就可以找到一个最短的双侧圈. 这回答了B. Mohar和C. Thomassen提出的一个未解决问题, 并对他们提出的另一个未解决问题给出了部分解答.     

图的极大Tutte集的几个有效算法

图G=(V,E)的Tutte集定义为X■V(G)满足ω_o(G-X)一|X|=def(G).若不存在Tutte集Y■X,则称X为图G的极大Tutte集.通过找极大extreme集和D-图的极大独立集给出一般图G的找极大Tutte集的两个有效算法,并给出结论:X■V(G)是二部图G的极大Tutte集当且仅当X为二部图G的最小覆盖,从而得到找二部图G的极大Tutte集的一个有效算法.     

完全有向图的奇长圈覆盖

设DK_v表示完全有向对称图,C（v,m）表示覆盖DK_v的m长有向圈的最小圈数（称为覆盖数）.对任意正整数m和v,当m≤v≤m+6时,覆盖数C（v,m） 被确定.     

K5的弧传递循环正则覆盖

-个图称为弧传递的,如果它的自同构群在其弧集合上作用传递.冯衍全等已经决定了4阶完全图K4的弧传递循环正则覆盖,本文给出了5阶完全图K5的弧传递循环正则覆盖的分类.     

求解最小点覆盖问题实例的计算成本的一种度量方法

最小点覆盖问题是NP难问题,传统的计算复杂性理论认为,当规模n较大时,问题是难计算的,但大量的实例表明,即使规模相同的实例,由于其结构的不同,求最优解时也会花费不同的计算时间,所以建立一种度量具体实例求解难度的方法是必要的.介绍了一种度量最小点覆盖问题任一实例求解所需计算成本的方法,度量方法是以计算时间复杂度为O~*(2.314~(k-vc~*)(G))的参数算法为参照的,参数算法可用来求解点覆盖问题的判定问题,在参数算法中,当参数k为常数时,点覆盖问题可在多项式时间内求解,当k表现为n的函数时,点覆盖问题的难解性就表现出来了,结合最小点覆盖问题的近似算法—线性规划松弛来估计每个实例对应的参数k的取值范围,可在多项式时间内实现对最小点覆盖问题实例的计算成本的预测.对于平面点覆盖问题,则以EPTAS算法为工具实现更精确的度量.     

λKv的最大K2,3填充设计和最小K2,3覆盖设计

对于一个有限简单图G,λK_v的G-设计(G-填充,G-覆盖),记为(v,G,λ)-GD((v,G,λ)-PD,(v,G,λ)-CD),是一个(X,B),其中X是K_v的顶点集,B是K_v的子图族,每个子图(称为区组)均同构于G,且K_v中任一边都恰好(最多,至少)出现在B的λ个区组中.一个填充(覆盖)设计称为是最大(最小)的,如果没有其它的这种填充(覆盖)设计具有更多(更少)的区组.本文对于λ>1确定了(v,K_2,3,λ)-GD的存在谱,并对任意λ构造了λK_v的最大K_2,3-填充设计和最小K_2,3-覆盖设计.     

一类点传递但边不传递的正则图及其覆盖图

利用轮子图构造出一类图,证明了这类图都是点传递但边不传递的正则图,并证明了通过覆盖的方法,可以使一类2m²(m>3,m为正整数)阶非边传递图变成对称图,这类对称图实际上是亚循环图.     

关于图的星形因子覆盖

如果图 G 的支撑子图 M 的每个分支都同构于{K_(1,1)K_(1,2,)…,K_(1,k}(k≥2)中的某个 K_(1,i),则 M(?)叫做 G 的星形因子。进一步,如果对于图 G 的每一条边都存在一个星形因子包含这条边,则称图 G 是星形因子覆盖的。本文给出了图是{P_2,P_3}一因子覆盖的充要条件,并证明了任意正则图均存在星形因子覆盖。