共查询到20条相似文献,搜索用时 296 毫秒
1.
图的交叉数是图的一个重要参数,研究图的交叉数问题是拓扑图论中的前沿难题.确定图的交叉数是NP-难问题,因为其难度,能够确定交叉数的图类很少.通过圆盘画法途径,确定了一个特殊6点图与n个孤立点nK_1,路P_n及圈C_n的联图的交叉数分别是cr(Q+nK_1)=Z(6,n)+2[n/2],cr(Q+P_n)=Z(6,n)+2[n/2]+1及cr(Q+C_n)=Z(6,n)+2[n/2]+3. 相似文献
2.
图G的交叉数是刻画图的非平面性的一个重要参数.它是指图G在平面上的所有画法中边与边之间交叉数目的最小值.确定具体图类的交叉数是图的交叉数问题中一个经典的研究方向.Zarankiewicz于1954年提出了完全二部图交叉数的猜想:■.1971年,Kleitman证明了当min{m,n}≤6时,上式成立.由于其难度,完全二部图交叉数的研究进展是较缓慢的.至今,完全二部图K7,n(n≥11)的交叉数都还未确定.然而,我们发现研究近完全二部图的交叉数可了解在完全二部图中加边与完全二部图交叉数的增长程度之间的关系.因此,为了促进完全二部图交叉数的研究,本文借助旋系与交叉数之间的关系、图的结构性质以及图的顶点度局部修改法确定了五个近完全二部图的交叉数. 相似文献
3.
Garey和Johnson证明了确定图的交叉数问题是一个NP-难问题.目前,已确定交叉数的图类并不多.本文证明了一个特殊6阶图与n个孤立点,路P_n及圈C_n的联图的交叉数分别是cr(Q+nK_1)=Z(6,n)+n;cr(Q+P_n)=Z(6,n)+n+1及cr(Q+C_n)=Z(6,n)+n+3. 相似文献
4.
李丽萍 《数学的实践与认识》2014,(11)
目前已经确定的两个图的联图的交叉数结果较少.设H是由一个4圈及一个孤立点所构成的5阶图.研究了图H与路、圈的联图的交叉数,得到了cr(H+P_n)=Z(5,n)+[n/2]+l,cr(H+C_n):Z(5,n)+[n/2]+2,其中,P_n与C_n分别表示含n个顶点的路与圈. 相似文献
5.
利用Kleitman D J给出的完全二部图的的交叉数cr(_(5,n))=Z(5,n)的结果,分别得到了联图G_(12)∨P_n,G_(15)∨P_n,G_(18)∨P_n的交叉数.同时,给出了目前已知的所有五阶图与路的联图交叉数情况. 相似文献
6.
7.
8.
9.
本文研究与星图有关的联图的交叉数,得到了对任意的n≥1,当m=3,4,5时,星Sm与路P_n的联图的交叉数;以及对任意的n≥3,当m=3,4时,星S_m与圈C_n的联图的交叉数. 相似文献
10.
苏振华 《数学的实践与认识》2017,(12):182-188
目前关于积图的交叉数的研究已经推广到六阶图与星图的积图.研究得到了一个特殊六阶图Q与n个孤立点nK_1的联图交叉数,然后通过收缩的方法,得到了Q与星图S_n的积图交叉数. 相似文献
11.
确定图的交叉数是NP.完全问题.目前已确定交叉数的六阶图与星图的笛卡尔积图极少。本文确定了—个六阶图G与星图5k积图的交叉数为Z(6,n)+2n+[n/2]. 相似文献
12.
13.
14.
15.
路与完全图的笛卡尔积图和广义图K(n,m)的关联色数 总被引:4,自引:0,他引:4
Richrd A.Brualdi和J.Quinn Massey在[1]中引入了图的关联着色概念,并且提出了关联着色猜想,即每一个图G都可以用△(G)+2种色正常关联着色.B.Guiduli[2]说明关联着色的概念是I.Algor和N.Alon[3]提出的有向星荫度的一个特殊情况,并证实[1]的关联着色猜想是错的,给出图G的关联色数的一个新的上界是△(G)+O(Log(△G)).[4]确定了某些特殊图类的关联色数.本文给出了路和完全图的笛卡尔积图的关联色数,而且利用此结果又确定了完全图Kn的广义图K(n,m)的关联色数. 相似文献
16.
图G的Alon-Tarsi数,是指最小的k使得G存在一个最大出度不大于k-1的定向D满足G的奇支撑欧拉子图的个数不同于偶支撑欧拉子图的个数.通过分析Halin图的结构,利用Alon-Tarsi定向的方法确定了Halin图的Alon-Tarsi数. 相似文献
17.
确定图的交叉数是NP-完全问题. 目前有关完全二部图与星图的积图的交叉数结果并不多. 引入了一些新的收缩技巧, 建立了积图K_{3,3}\square S_n与完全三部图K_{3,3,n}之间的交叉数关系. 从而, 为进一步完全确定积图K_{3,3}\square S_n的交叉数提供了一条新途径. 相似文献
18.
完全3-部图K_(1,10,n)的交叉数 总被引:1,自引:0,他引:1
在上世纪五十年代初,Zarankiewicz猜想完全2-部图Km,m(m≤n)的交叉数为[m/2][m-1/2][n/2][n-1/2](对任意实数x,[x]表示不超过x的最大整数),目前只证明了当m ≤ 6时,Zarankiewicz猜想是正确的.假定Zarankiewicz猜想对m=11的情形成立,本文确定完全3-部图K1,10,n的交叉数. 相似文献
19.
C(6,2)表示由圈C6增加边vivi 2(i=1,…,6,i 2(m od6))所得的图,把边vivi 2叫做C(6,2)的弦,B表示C(6,2)除去一条弦所得到的图,我们确定了B与Pn笛卡尔积的交叉数为5n-1. 相似文献