没有合适的资源?快使用搜索试试~ 我知道了~
有向树的不可避免性
2−22228可在www.sciencedirect.com在线获取理论计算机科学电子笔记346(2019)425-436www.elsevier.com/locate/entcs关于有向树的不可避免性FranncoisDross1和Fr′ed′ericHavet2Coati项目,I3S,CNRS,INRIAetUniversit'eC.摘要一个有向图是n-不可避免的,如果它包含在每个n阶竞赛图中。 我们首先证明了每一个具有k个叶的n阶树形图是(n + k − 1)-不可避免的。然后,我们证明了每个具有k个叶子的n阶定向树是(3n +3k − 2)-不可避免的和(9n − 5 k − 9)-不可避免的,因此(21(n − 1))-不可避免最后,证明了每一个n阶k叶定向树都是(n +144k2280k +124)-不可避免的.关键词:竞赛图,有向树,可分性,Ramsey理论。1介绍竞赛图是完全图的定向图一个有向图是n-不可避免的,如果它包含在每个n阶竞赛图中(作为子有向图)。有向图D的不可回避性,记为unvd(D),是最小整数n,使得 D.不可避免众所周知,n阶传递竞赛图是2n−1-不可避免的,因此每个n阶无圈有向图都是2n−1-不可避免的。然而,无圈有向图的弧少,更好的界限是预期。特别注意了有向路径和有向树,它们分别是路径和树的它开始于R′edei定理[ 14 ],其中规定n个顶点上的有向路的不确定性y是n。在1971年,Grunbaum研究了有向路径,即每个顶点的入度为0或出度为0的有向路径(换句话说,两个连续的边以相反的方式定向)。他证明了[6],一个反向路阶n是n,除非n= 3(在这种情况下,它不包含在有向3-循环中)或n= 5(在1电子邮件:francois. inria.fr2电子邮件:frederic. inria.frhttps://doi.org/10.1016/j.entcs.2019.08.0381571-0661/© 2019由Elsevier B. V.这是一篇基于CC BY-NC-ND许可证的开放获取文章(http://creativecommons.org/licenses/by-nc-nd/4.0/)。426F. Dross,F.Havet/Electronic Notes in Theoretical Computer Science 346(2019)425n3在这种情况下,它不包含在5阶的常规锦标赛中)或n= 7(在这种情况下,它不包含在7阶的佩利锦标赛中)。同年,Rosenfeld [16]给出了一个更简单的证明,并证明了存在一个最小整数NP> 7,使得unvd(P)= |P|对于每一条阶至少为NP的有向路。NP>7的条件是由Gruünbaum的例子得到的. 在Rosenfeld的猜想被Rosenason证实之前,已有几篇文章对这个猜想给出了部分的解答[1,5,17]最后,H avet和Thomas s′e[11]表明,u nvd(P) =|P|对于除3阶、5阶和7阶反向路以外的所有定向路P,关于定向树,萨姆纳(见[15])提出了以下著名的猜想。猜想1.1每一个阶n> 1的定向树都是(2 n-2)-不可避免的。第一个线性边界是由Hüaggkvist和Schaason[7]给出的。为了给Havet[8]和Havet和Thomass′e[10]提供一个新的概念,ElSahili[4]使用了中位序的概念,并在[ 10 ]中首次用作Sumner猜想的工具,并证明了每个n(n ≥ 2)阶的定向树都是(3 n − 3)-不可避免的最近,Kuhn,Mycroft和Osthus[13]证明了Sumner猜想对所有极大的n都他们的复杂证明利用了正则引理的有向版本以及同一作者最近一篇论文的结果和想法[12],其中证明了猜想的近似版本在 文献[10]中,H avet和Thomas se也 提 出 了Sumner猜想对a r b c s成立. 一个树状结构,(分别)树是一种有方向的树,其中所有的弧都朝向(分别)。一个叫做根的固定顶点。树形结构可以是内树形结构,也可以是外树形结构。如果是真的,萨姆纳的猜想将是严密的。事实上,外星S+,即由一个顶点支配其他n-1个顶点组成的n个顶点上的有向图,不包含在2n- 3阶的正则竞赛图然而,这样的有向图有许多v。因此,Havet和Thomass'e(见[9])使下面的翼猜想比萨姆纳猜想1.2任何n阶k叶定向树都是(n + k− 1)-不可避免的。作为这一猜想的一个证据,Hüaggkvist和Kazason[7]证明了极小函数g(k)≤2512k的存在性使得每一个n阶树,k个叶子是(n+g(k))-不可避免的。有两个叶子的树是路,所以上述结果意味着猜想1.2在k= 2时成立,Ceroi和Havet[3]证明了它在k= 3时成立。Havet[9]还证明了猜想1.2对一个大类的树。1.1我们的成果在第三节中,我们证明了关于树形图的猜想1.2定理1.3每一个具有k个叶的n阶树形图是(n + k−1)-不可避免的。F. Dross,F.Havet/Electronic Notes in Theoretical Computer Science 346(2019)42542738D22222DDD222428利用这个结果,在第4节中,我们得到以下结果。定理1.4每一个n阶k叶定向树是(3n+3k−2)-2 2不可避免这个结果给了我们一个很好的界限,树的叶子很少。特别是,它意味着萨姆纳猜想的树木,其中最多三分之一的顶点是树叶。推论1.5每个至多有n个叶子的n阶定向树是(2n- 2)-不可避免然后,在第5节中,我们给出了树的不可空性的上界,这对于具有许多叶子的树是好的定理1.6每一个有向树有n≥3个顶点和k个叶子是(9n-5k-9)-不可避免2 2 2定理1.4和1.6给出了对萨姆纳猜想的最佳界:推论1.7每个阶n≥2的定向树是。21(n-1)-不可避免。证据m i n 的值。3(n + k − 1),9n − 5k − 9n= 3(n + k −1)1)=9n−5k−9,即k=3n−3。在这种情况下,3(n+k−1)=21(n−1)。Q最后,在第6节中,我们通过证明以下内容,极大地降低了函数g(k)的上界,使得每个具有k个叶子的n阶树都是(n+g(k定理1.8每个有n个结点和k个叶子的定向树是(n +144 k2- 280 k + 124)-不可避免的。2定义和分类一般情况下,[2]。 有向图没有平行弧和环。设D是一个有向图。 如果(u,v)是一条弧,我们说u支配v,并写u→v。对任意W<$V(D),记D<$W <$V为W在D中诱导的子图.设v是D的一个顶点。v的外邻域,记为N+(v),是顶点w的集合,使得v→w。v的内邻域,记为N−(v),是顶点w的集合,使得w→v。出度d+(x)(分别的D D入度d−(x))为|N+(v)|(分别) |N−(v)|).设A是一棵定向树。A的叶子是D中(至多)一个顶点的相邻顶点。有两种叶:出度为1、入度为0的入叶和出度为0、入度为1的出叶。叶的集合(resp. A的in-leaves,out-leaves)表示为L(A)(resp. L−(A),L+(A))。简单地说,L(A)=L+(A)<$L−(A)。根树是一个有向树,有一个指定的顶点称为根。如果是一棵树,r是A的顶点,我们用(A,r)表示以r为根的树A。设A是一个428F. Dross,F.Havet/Electronic Notes in Theoretical Computer Science 346(2019)425树的根R。V(A)\ {r}中节点v的父节点是A中从r到v的唯一路径中与v相邻的节点。 如果u是v的父亲,那么v就是u的儿子。如果w在A中从r到v的路径上,我们说w是v的祖先,v是w的后代。为了清楚起见,树的顶点被称为节点。令σ=(v1,v2,.,v n)是D的顶点的排序。一条弧vi vj是向前的(根据σ),如果i j,并且是向后的(根据σ),如果ji。D的中位数阶是D的顶点的排序,具有最大数量的前向弧,或者等价地具有最小数量的后向弧。换句话说,中值阶是顶点的排序,使得后向弧的集合是最小反馈弧集合。让我们注意的基本性质的中位数秩序的比赛,其证明是留给读者。引理2.1设T是竞赛图且(v1,v2,., v n)T的中位阶。然后,对于任意两个索引i,j,其中1 ≤i< j≤ n:(M1)(v i,v i+1,., v j) 是导出子竞赛图 的中位 阶T {v i,v i+1,., v j}。(M2) 顶点Vi支配顶点Vi+1,Vi+2,...,v j,并且顶点v j由顶点v i,v i+1,.,v j−1。特别地,每个顶点v i,1 ≤i0,对于所有C ∈Cr↑,且|+的|L−(C)|−2 > 0对于所有C ∈ C r ↓。|−2>0forallC ∈Cr↓.F. Dross,F.Havet/Electronic Notes in Theoretical Computer Science 346(2019)425431i=1i=1i=1JJ引理4.1设A是一个有n个节点和k个叶子的有根树,使得根rA的入度为0。 则A是(n + k − 1+ γ r↓)-不可避免的。证据 令C1,…,Cj是A的向下森林的分支,对于1≤i≤j,设ni是Ci的节点数,ki是Ci的入叶数.通过定义,γ r↓=<$j(n i+ k i− 2)。设T是n+k−1+γr↓顶点上的竞赛图。注意,定理3.1证明中的嵌入过程可以用下面的过程代替,它产生相同的双射。设φ(r)=v1。对于i = 1到m,如果v i被击中,则取|N+(a i)|在{v i+1,.,”(《论语·子贡》)“子贡,不以其人之道,而以其人之道,而以其人之道。这个过程的兴趣在于它以不同的顺序考虑树的节点。我们将使用的主要属性是给定节点a的所有子节点的图像同时固定,并且在这些图像的集合已知之前,我们不需要固定Oa这意味着我们可以在知道哪些顶点是a的儿子的像之后选择Oa的顺序。因此,我们可以有效地选择a的哪个子嵌入到哪个顶点,并知道a的子的像的集合。现在我们从有根树A建立一个树形AJ,我们称之为A.对于所有的i∈ {1,., j},执行以下操作。设fi是Ci的根的父亲。注意,fi存在,因为A的根的入度为0,因此不在向下森林中移除Ci的所有弧,添加一个包含ki−1个新节点的集合Ni,并从fi到每个新节点和Ci的每个节点放置一条弧(除了到Ci的根,因为该弧已经存在)。观察到AJ是一个有根树,它与A有相同的根,由于我们去掉了向下的弧,只增加了向上的弧,所以AJ甚至是一个外树形图。通过构造AJ有n +<$j(k i− 1)个节点。 设i ∈ {1,...,j}。Ci的节点,是A中向上弧的尾部是AJ中相同向上弧的尾部,因此它们是而不是AJ中的叶子。 因此,Ci的每个in-leaf或者是A中的in-leaf(如果它是尾部或不为一,或不为一,或不为一。因此,在Ci中,最多有ni−ki是AJ中的非入叶的出叶。 回想一下,新节点是也会离开 因此AJ至多有k +<$j(n i− 1)个出叶。因此,根据定理3.1,存在AJ到T的嵌入φ。我们建立根据本证明开始时提出的程序。设i∈{1,.,j},并考虑S i= V(C i)<$N i。这是A中f i的n i+ k i−1个儿子的集合。如前所述,我们可以在选择将Si的哪个节点嵌入到哪个顶点之前知道φ(Si) 根据定理3.1,存在从C i到T<$φ(Si)<$的嵌入φ i。现在对于C i中的每个节点a,我们选择φ i(a)作为它的φ的图像。现在考虑将得到的嵌入φ限制到V(A)。 为所有 i∈ {1,.,j},则φ i与φ i重合。因此,因为A的所有向上弧都在A中,所以A的向下弧保持向上弧,并且因为A的每个向下弧都在某个Ci中,所以A的向下弧保持向下弧。所以,A是A到T的嵌入。Q432F. Dross,F.Havet/Electronic Notes in Theoretical Computer Science 346(2019)4252222||222222我们现在能够证明定理1.4,它指出每个有k个叶子的n阶定向树是(3(n+k)−2)-不可避免的。定理1.4的证明设T是3(n+k)−2个顶点上的竞赛图。 设A是一个有向树,有n个结点和k个叶子. 选择一个根r,使得min(γr↑,γr↓)最小。通过方向对偶性,我们可以假设这个最小值由γr↓得到。由于γ r↓≤γ r↑,我们有γ r↓≤1(γ r↑+ γ r↓)。对于一棵有根树A,设LJ(A)是A的不同于根的叶子注意,如果A1和A2是两个根如果一棵树除了一个顶点是A2的根之外都是不相交的,那么A1<$A2是一棵树,如果我们把它的根放在A1的根上,那么|LJ(A1<$A2)| ≥ |LJ(A1)|+的|LJ(A2)|-1。通过对(A,r)的向上森林和向下森林的所有分量连续应用这个公式,我们得到γr↑+ γ r↓≤ n + k − 2,因此γ r↓≤ 1(n + k)− 1。因此,我们认为,T至少有n+k−1+γr↓个顶点。假设一个矛盾,r有一个内邻s。(A,s)的向下森林Fs是从(A,r)的向下森林Fr通过移除弧sr以及可能的s或r(如果它们变得孤立)而获得的。Fr的所有不含sr的分量也是Fs的分量,Fr的含sr的分量C0要么消失(当sr是C0的唯一弧时),要么失去一个顶点(当r或s是C0的叶时),要么分裂成两个分量,其顶点总数与C0相同,最多比C0多一个入叶。无论如何,γs↓<γr↓,这是一个矛盾。因此r的入度为0。 引理4.1完成了证明。Q5多叶本节的目的是建立定理1.6,它指出每个有n≥3个顶点和k个叶子的定向树是(9n−5k−9)-不可避免的。证据 设m =[9n−5k−9|. 设T是m个顶点上的竞赛图。 设A是一种有向树,有n个节点和k个叶子。如果A是一个双树形图,则我们有推论3.5的结果。因此,我们假设A不是一个双树形图。特别是,k n-1。A的外叶簇,用S+表示,是A的节点集合,递归定义如下。每个外部叶子A都在S+中;如果a是一个只有一个内邻居的节点,并且它的所有外邻居都在S+中,那么a也在S+中。我们类似地定义A的叶内簇S−。注意,AS−是一个内树形森林,AS+是一个外树形森林。此外,S−<$S+=<$,因为A不是双树形。A的心脏,用H表示,是树A−(S−<$S+)。设置n H= |V(H)|且kH= L(H).我们首先注意到H的每一个外叶在S−中都有一个近邻,否则它就会在S+中。类似地,H的每个in-leaf在S+中都有一个邻居。特别是,|S−| ≥ |L+(H)|和|S+| ≥ |L−(H)|.我们现在描述一个算法,它产生树A到T的嵌入φ。它分三个阶段进行:在第一阶段,我们嵌入A的心脏,在第二阶段,我们嵌入外部叶簇,在第三阶段,我们嵌入内部叶簇。F. Dross,F.Havet/Electronic Notes in Theoretical Computer Science 346(2019)425433ΣJ+−C∈Cr∪22(二)第一、二阶段。2)当n=0时,n=0,n=|L−(C)|−1)2- 2≥22H2↓↓↑↓集群在每一步中,如果A的节点已经有了φ的图像,则它被嵌入,否则不被嵌入。如果T的一个顶点v j是一个节点的像,我们用symbolsaj=φ−1(vj)表示这个n o de by a j ;。如果一个顶点是一个顶点的像,我们就称它是命中令σ =(v1,v2,.,v m)是T的中位阶。我们区分两种情况:(1)S−或S+中有一个是空的,(2)S−和S+都是非空的。我们在这里只介绍最复杂的情况(2)。一个类似的(也是更容易的)论证适用于情况(1)。我们首先要找到足够的A来开始。 设Cr↓=Cr↓(H)且dCr↑=Cr↑(H)。 对于H的任意一个根,letβr↓=<$C∈Cr↓(3|V(C)|−3)+2|L−(H)|和β r↑= π↑(3 |V(C)|− 3)+2 |L+(H)|. 设r是最小化min{βr↓,βr↑}的根。通过方向对偶,我们可以假设βr= min{βr,βr}。因此,βr≤1βr↓+1βr↑= 3n H+ k H−3。 我们可以假设r的入度为0,因为每个r的近邻s满足β s↓≤ β r↓。让我们现在详细介绍我们的算法。设l=nH−kH−1 +C∈Cr↓(|V(C)|−1)+2|L−(H)|+2 |S−|. 注意l ≥ 1,因为|S−|≥ 1。 设p = l + n H+ k H− 1+ γ r↓。阶段1:我们将H嵌入T{v 1+ 1,.,v p},使用引理4.1的过程对H.注意,在这个过程中,我们嵌入了H的等效树形图H,它比H大。在这里,我们保持HJ的所有顶点嵌入,直到阶段2结束。阶段2:当S +中有一个未嵌入的顶点时,设i是最小的整数,使得φ−1(v i)在S +中有一个未嵌入的外邻居,并取v i在{v i+1,.,v m}尚未命中并将其分配给S中的未嵌入外邻居。解嵌入HJ−H的所有顶点。阶段3:当S−中有一个未嵌入的顶点时,设i是最大的整数,使得φ−1(vi)在S−中有一个未嵌入的内邻点,并取最后一个(i.e.具有最高索引)在{v1,...,v i−1}尚未命中并将其分配给S中未嵌入的内邻居。我们证明这个算法嵌入了A的所有节点。 首先,根据引理4.1,H的所有顶点都嵌入在阶段1中。现在让我们证明S+的所有顶点都嵌入在阶段2中。设B是由V(H)S+诱导的A的子树,BJ是由B用等价树形图HJ代替H得到的外树形图.观察到阶段1和阶段2可以被视为嵌入BJ并同时从BJ提取B让我们证明,我们的算法嵌入了整个BJ(因此整个结10-12-2016刘晓波(|L−(C)|− 1)+|S+|结C∈CrA的所有叶子要么在S-中或在S+中,则k≤ |S−| +的|S+|. 因此9 5 9m≥n−k9n+ 2 |S−|+2 |S+|-9。22434F. Dross,F.Havet/Electronic Notes in Theoretical Computer Science 346(2019)425ΣΣ22--2一对于所有C ∈Cr↓,我们都有|L−(C)|≤|V(C)|,thus1998年,|V(C)|+2 |L−(C)|− 3)+2 |L−(H)|≤ 100(3 |V(C)|− 3)+2 |L−(H)|C∈Cr↓C∈Cr↓3n H3前面两个方程得出≤2+ k H−2。m≥3 n H−k H− 3+(|V(C)|+2 |L−(C)|− 3)+ 2 |L−(H)|+2 |S−|+2|S+|、C∈Cr↓所以m−l≥2nH +2(|L−(C)|− 1)+ 2 |S+| − 2 ≥ 2 |BJ|-2。C∈Cr↓在阶段1和阶段2期间,在Bj的每个顶点的添加处,我们的过程取顶点vi在vi+1,.中的第一个(即具有最低索引)外邻居,v m尚未命中,并将其分配给φ−1(v i)的未嵌入外邻居。因此,在每一步,φ是BJ J的嵌入,B j j是迄今为止构造的BJi n到Tj n {vl+1,., vl+2|B′ ′|-2},因此,在每一个chend-i nter val{vj ,.,vl+2|B′ ′| −2}至多l+2|B′ ′| −2−j+1顶点在φ(BJ J)中。 利用引理2.1(M2),证明了vi作为外邻节点在{vi+1,., vl+2|B′ ′|}\φ(BJ J),并且逼近可收敛。因此,BJ可以被嵌入到Ti {vl+1,., v m}。假设算法在第3阶段失败,这意味着S-中的节点a没有嵌入。我们可以选择这样一个节点a,其外邻居b被嵌入。设vi是b的像。注意b在S−V(H)中,因此它已嵌入相位1或3中,并且必须在{v1,., v p}。考虑我们在阶段期间尝试嵌入b的内邻居的时刻3.设hit为{v1,.,i= 1,此时此刻。由于a未被填充,因此我们已命中≥|N−(vi)<${v1 , . . ., vi−1}|−|NA− ( b ) |+1 。 通 过引 理 2.1, |N−(v i)<${v1 ,. ,vi−1}|≥i−1。所以hit≥i−1−|N −(b)|+1。(3)给出命中的上界。设O
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- 共轴极紫外投影光刻物镜设计研究
- 基于GIS的通信管线管理系统构建与音视频编解码技术应用
- 单站被动目标跟踪算法:空频域信息下的深度研究与进展
- 构建通信企业工程项目的项目管理成熟度模型:理论与应用
- 基于控制理论的主动队列管理算法与稳定性分析
- 谷歌文件系统下的实用网络编码技术在分布式存储中的应用
- CMOS图像传感器快门特性与运动物体测量研究
- 深孔采矿研究:3D数据库在采场损失与稳定性控制中的应用
- 《洛神赋图》图像研究:明清以来的艺术价值与历史意义
- 故宫藏《洛神赋图》图像研究:明清艺术价值与审美的飞跃
- 分布式视频编码:无反馈通道算法与复杂运动场景优化
- 混沌信号的研究:产生、处理与通信系统应用
- 基于累加器的DSP数据通路内建自测试技术研究
- 跨国媒体对南亚农村社会的影响:以斯里兰卡案例的社会学分析
- 散单元法与CFD结合模拟气力输送研究
- 基于粒化机理的粗糙特征选择算法:海量数据高效处理研究
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功