带权无向图中反馈顶点集的固定参数枚举算法

反馈顶点集(FVS)问题是一个经典的NP-完全问题,在很多领域有重要的应用.人们对该问题进行了大量的研究,但目前还没有有效的算法枚举带权无向图的反馈顶点集.文中通过对带权无向图中反馈顶点集问题的结构的深入分析,给出了一个有效的基于分支搜索技术的固定参数枚举算法.算法将反馈顶点集问题转化为反馈边集问题,通过枚举z个权值最大的森林来枚举z个权值最小的含k条边的反馈边集,从而得到z个权值最小的含k个顶点的反馈顶点集,算法时间复杂度为O(5kn2(logn+k)+3kz(n2logn+z)).

过特定顶点集S的S-D-圈与S-D-路

利用邻域交给出了图Ｇ的每个Ｓ－最大圈都是Ｓ－Ｄ－圈的一个充分条件．并给出了对任意｛ｕ，ｖ｝Ｖ（Ｇ），Ｇ的每条（ｕ。

过特定顶点集的S-圈与S-路

证明了下面两个结论 :(1)设G是k-连通的n阶图 ,k≥ 2 ,S V(G) .若对G[S]的任意 (k+ 1) -独立集X ,有 k+1i=1k +i- 1k si(X)>n- 1,则G中有含S的全部顶点的圈 ;(2 )设G是 (k+ 1) -连通的n阶图 ,k ≥ 2 ,S V(G) .若对G[S]的任意 (k+ 1) -独立集X ,有 k+1i=1k+i - 1k si(X) >n ,则对任意的 {u ,v}≤V(G) ,G中有含S的全部顶点的 (u ,v) 路 .其中 ,G是有限无向简单图 .X为G的 (k+ 1) -独立集 ,Si(X) ={v∈V(G) N(v) ∩X =i} ,si(X)=si(x) ,i∈ { 0 ,1,2 ,… ,k + 1} .

无向图中子集反馈顶点集问题的精确算法

子集反馈顶点集问题是一个经典的NP难问题,该问题是指在一个无向图中删除最少的顶点使得图中某些给定的顶点不在任何圈中.子集反馈顶点集问题包含了经典的最小反馈顶点集、多路割等重要特例问题,并且可应用于电路测试、操作系统解死锁等领域.子集反馈顶点集问题也是精确算法中的一个重要问题,该问题存在一个运行时间为O~*(2~n)的简单暴力搜索算法,其中n为图中顶点数.直到2011年Fomin等人给出一个运行时间为O~*(1.8638n)的算法,这个运行时间界才被打破.文中将该运行时间上界进一步改进到O~*(1.7743n).文中的算法是一个分支搜索算法,为了改进该问题的运行时间界,文中对问题的结构性质进行了深入的分析,挖掘出若干有效的规约和分支规则,再采用测量治之方法对算法的运行时间进行分析,最终将运行时间上界给予改进.

求图的最小顶点覆盖集的一个近似算法

已有的求图的最小顶点覆盖集近似算法或者近似比较高,或者为降低时间复杂度限制了图的规模.根据顶点的度分析了图的局部结构特征,提出了悬挂链、封闭链和稠部等重要概念,并在这些概念的基础上提出了相应的3个伪最小覆盖点选取启发式策略.运用这些伪最小覆盖点选取启发式策略设计了一个近似算法.该算法不限制图的规模,时间复杂度为O(|V|2),近似比为4/3,接近已知的可能的近似比下界1.1666,低于2005年认为最低的近似比1.361.与同类算法相比,该算法设计思路清晰,容易理解,易于编程实现,执行效果好,是图的最小顶点覆盖集问题的近似算法的一个重要补充.

求一般图的最小顶点覆盖集问题的混合贪婪算法

现有的求一般图的最小顶点覆盖集近似算法或者近似比较高,或者为降低复杂度限制了图的规模,或者算法搜索过程中盲目性大。根据顶点的度特点及贪婪法的思想,提出了邻接度数、覆盖边等主要概念,并在此概念的基础上设计了混合贪婪算法。该算法设计思路清晰,容易理解,易于编程实现,且在最坏情况下的时间复杂度为 O( | V | 2) ,执行效果较好,性能近似比不大于 4/3,接近已知的可能的近似比下界 1. 166 6,低于 2005 年认为最低的近似比 1. 361,是图的最小顶点覆盖问题算法的一个较好的补充。

顶点偏序集上的平面序（英文）

平面序是渐进平面图的边偏序的一类特殊线性扩张,平面序的定义对一般的有限偏序集都有意义,并且事实上等价于共轭序的概念。这里证明了一个渐进平面图的边偏序集上平面序可以自然诱导其顶点偏序上的一个平面序.

基于网络化简和配合关系的最小断点集计算方法

基于保护主后备配合依赖关系有向图,提出了通过有向图化简计算保护配合最小断点集(MBPS)的新方法。定义了配合依赖关系有向图化简操作的顺序和原则,按照优先级顺序将保护分类,根据保护后备依赖度最大原则从具有较高优先级的类中选择候选断点,将化简过程中得到的自环顶点选为断点。所述方法适用于环网全网配合和同段配合中MBPS的计算。

钻石项链图Nk的点被多重集可区别的E-全染色(2 ≤ k ≤ 165)

利用反证法和构造具体染色的方法,讨论了钻石项链图Nk的顶点被多重集可区别的E-全染色。给出了钻石项链图Nk的相应染色方案,构造了具体的钻石项链图Nk的点被多重集可区别的E-全染色,其中2 ≤ k ≤ 165。

反馈集问题的研究进展

反馈集问题是经典的NP难问题,在电路测试、操作系统解死锁、分析工艺流程、生物计算等领域都有重要应用,按照反馈集中元素类型可分为反馈顶点集(FVS)问题和反馈边集(FAS)问题。人们利用线性规划和局部搜索等技术设计了一系列关于FVS和FAS问题的近似算法,并基于分枝-剪枝策略和加权分治技术提出了FVS问题的精确算法。随着参数计算理论的发展,近年来参数化反馈集问题引起了人们的重视,并取得了很大突破。目前已经证明了无向图和有向图中FVS问题和FAS问题都是固定参数可解的(FPT)。利用树分解、分支搜索、迭代压缩等技术,对无向图FVS问题提出了一系列FPT算法。针对某些特殊的应用,人们开展了对具有特殊性质的图上FVS问题的研究,提出了一些多项式时间可解的精确算法。现首先介绍了在无向图中关于FVS问题的近似算法与精确算法,然后具体分析了FVS问题的参数化算法。进一步阐述了关于有向图和特殊图上FVS问题的研究现状,介绍了FAS问题的研究成果。基于对反馈集问题研究现状的分析,提出了今后FVS问题研究中值得关注的几个方面。

求顶点着色问题的一种新方法

给出了图的着色问题的一种新方法,即运用置换相似变换(置换行和相应的列)得到图G的顶点集V(G)的一种分划(V1,V2,…,Vn)。

图顶点着色问题的DNA粘贴算法

利用DNA粘贴模型的巨大并行性,从图顶点着色问题的本质出发,先把着色问题分解成顶点独立集问题和顶点划分问题并给出这两个问题的DNA粘贴算法,然后调用这两个算法解决了图顶点着色问题。实例证明DNA粘贴算法在理论上可以实现的。

2015中国国家集训队选拔考试

1．如图1，在等腰AABC中，AB=AC〉BC，D为△ABC内一点，满足DA=DB＋DC．边AB的中垂线与∠ADB的外角平分线交于点P，边AC的中垂线与∠ADC的外角平分线交于点Q．证明：B、C、P、Q四点共圆．

关于K级顶点角的正弦定理及应用

1、引 言 1968年,P.Bartos引进了几维单形顶点角的概念: 设Ω是En中的n维单形,e0,e1,…,en,依次是Ω的n+1个界面上的单位法向量,令 Di=det(e0,e1,…,ei-1,ei+1,…,en)则把θi=arcsin/Di/定义为此单形的第i个界面对应的顶点角。从这个定义出发,Bartos建立了几维单形的正弦定理:

图中完美对集的一个充分必要条件及其计数

本文将任意无向简单图加辅助顶点和边,再利用其反对称邻接矩阵,得到了一个容易判定图中存在完美对集的充分必要条件,还解决了图中完美对集的计数问题。

图∪ from i=1 to n(F_(mi,4))的优美性

给出图∪ni=1Fmi,4 的一类非连通图 ,并证明这类图是优美图 ,且也是交错图 .

路代数的同构

设K(Δ)表示有向图Δ在域K上的路代数,本文证明:(1)K(Δ)^+与K(Γ)^+代数同构当且仅当Δ与Γ边同构。(2)K(Δ)与K(Γ)代数同构当且仅当Δ与Γ同构。

新的上可嵌入图类

图G的C 划分是指 :G的一个顶点划分 {V1 ,V2 ,… ,Vk}使得每个G[Vi]为多重完全图 (1≤i≤k) .证明了如下结果 :设G为连通图 ,且对任意v∈V(G) ,dG(v)≡ 1 (mod 4) .若G的顶点集存在一个C 划分 {V1 ,V2 ,… ,Vk}使得对每个 1≤i≤k,|Vi|≥ 4 ,且 |Vi|≡ 0 (mod 4) ,则G是上可嵌入的 .另外 ,联系着图的点的度和其它条件 ,推广和深化了目前有关这方面的一些结果 。

最大匹配图的围长(英文)

将一个图的所有最大匹配作为顶点集，称两个最大匹配相邻，若它们之一通过交换一条边得到另一个，由此所得图为该图的最大匹配图．本文研究了最大匹配图的围长，从而给出了最大匹配图是树或完全图的条件．

图的相邻强边着色数(英文)

如果在一个图的正常边着色中,相邻两点关联的边集所着的颜色集合不同,则称此正常边着色为相邻强边着色.对图G进行相邻强边着色所需要的最小色数称为G的相邻强边着色数,记作X'as(G).给出了相邻强边着色数的两个上界:一是对于任何d-正则图G(d≥3),X'as(G)≤16d;二是如果图G有两个边不交的完美匹配,则X'as(G)≤3△(G)+1.