周智勇[1]2007年在《笛卡儿积图交叉数的若干结果》文中指出我们已经知道确定图的交叉数是一个NP完全问题(见文献[2])，正是因为其计算复杂性，目前为止有关交叉数的结果比较少，甚至在许多情况下，找出图的一个好的上界或下界也很艰难。对具体图类的研究方法和图自身的结构特征紧密相连，相同的方法甚至不能用在结构相近的两类图上。本文具体研究了路，圈与某些6-阶图的笛卡儿积图交叉数。首先，交代了本文的写作背景，交叉数研究在国内外发展的动态，研究工作的意义以及本文中要解决的问题和创新之处。然后，给出了一些基本概念和性质，介绍了阅读本文所需要的预备知识其中主要包括交叉数的概念，并介绍了在后面文章中会出现的一些相关概念、性质以及常用到的一些定理，而部分使用较少的概念等我们放到了具体的章节中去交代。再接下来，在第叁章，对图K_(3,3)×P_n在一个已知上界的限制下的结构做了具体细分，同时运用归纳法，确定了K_(3,3)×P_n的交叉数。在第四章，先确定一个子图的交叉数，通过母图的交叉数大于等于子图的交叉数，从而确定了笛卡尔积图S_5×C_n及S_5×S_n的交叉数。最后指出了研究工作中遇到的一些问题以及作者以后研究的主攻方向。
卢俊杰[2]2004年在《图的交叉数的若干结果》文中研究说明本文主要研究拓扑图论中一个重要课题一图的交叉数．它是一个重要的拓扑参数．交叉数在离散几何与计算几何众多领域有着广泛的应用，在研究最大平面子图[30]及图的VLSI线路分布方面[27]也起着重要作用。但是确定一个图的交叉数非常困难，而且对这方面的工作所知也甚少，就计算复杂度来讲，Garey和Johnson[16]证明了图的交叉数问题是NP-完备的，本文得到以下结果： 1．给出循环图C(m,3)的交叉数的精确值； 2．给出循环图C(4k,4)的交叉数的精确值； 3．得出两个平面图的交叉数的部分结果。
王晶[3]2009年在《若干图类交叉数的研究》文中提出图的交叉数问题,起源于二战期间Pual Tur(?)n在砖厂碰到的一个实际难题,逐渐发展成为图论学科中非常活跃的一个分支,吸引着国内外许多学者的关注.然而,确定一般图的交叉数是一个NP-完全问题,因此,到目前为止有关交叉数的结果比较少,仅限于一些特殊简单图的交叉数.甚至在许多情况下,试图找出图的交叉数的一个好的上界或下界也很困难.本文运用组合方法和归纳思想以及反证法,确定了一些特殊图类,如广义Petersen图P(3k,k),循环图C(3k-1;{1,k}),W_m×P_n,两个特殊的六阶图与星S_n的笛卡尔积图,星图S_m与路P_n、星图S_m与圈C_n的联图的交叉数的精确值或者其上、下界,并试图研究交叉数的一般性质,从画法上着手得到了一个好画法为最优画法的充分条件.全文由9个章节组成.第一章较为详细地交代了交叉数的起源,研究工作的理论与实际意义,以及目前交叉数研究在国内外的发展动态.同时还简要介绍了本文的主要结构.第二章介绍了阅读本文所要用到的图的交叉数方面的基本概念和预备知识.第叁章得到了当k≥4时,广义Petersen图P(3k,k)的交叉数为k.第四章讨论了当k≥3时,循环图C(3k-1;{1,k})交叉数的上界和下界.第五章确定了对任意的m≥3和n≥1,轮W_m与路P_n的笛卡尔积图的交叉数.第六章对两个特殊的六阶图与星S_n的笛卡尔积图的交叉数进行了研究.第七章讨论了当m=3,4,5时,星S_m与路P_n的联图的交叉数,和当m=3,4时,星S_m与圈C_n的联图的交叉数.第八章研究图的交叉数的一般性质,并从画法上着手得到了一个好画法为最优画法的充分条件.第九章给出了本文的总结和对未来工作的展望.
赵霆雷[4]2006年在《线图与若干典型图类的交叉数研究》文中进行了进一步梳理图的交叉数是近代图论中发展起来的一个重要概念,自从上个世纪五十年代初匈牙利数学家Paul Turán根据其在一个砖厂碰到的实际难题(Turán's brick factory problem),从而提出了交叉数的概念以来,图的交叉数逐渐成为国际上一个非常活跃的分支,使得很多图论专家对这方面进行了深入研究。 研究图的交叉数不仅具有重要理论意义,而且有较强的现实意义,如超大规模集成电路VLST中的圈布局问题、电子线路板设计中的布线问题等。1983年计算机科学家Carey和Johnson证明了确定图的交叉数是NP-完全问题,由于其难度,目前只知道一些特殊图类的交叉数,如完全图,完全2-部图,完全3-部图,圈与圈以及路与点数较少的图的笛卡尔积图,循环图,Petersen图以及线图等。关于非平面图,Kulli与Beineke等在1979年给出了使得它的线图的交叉数为1的条件;Jendrol′与Kle(?)于2001年研究了平面图的线图的交叉数为1的条件。关于完全2-部图K_(m,n,)目前只能确定当m≤6时,Zarankiewicz猜想为真,而确定完全图K_n的交叉数目前也是一个公开问题。上世纪八十年代,Asano确定了完全3-部图K_(1,3,n)和K_(2,3,n)的交叉数。此后,关于完全3-部图一直没有新结果。 本文在第一章较为详细地介绍了目前图的交叉数研究的历史与现状,并简要介绍一些与本文有关的交叉数的概念。 在第二章,着重研究图及其线图的交叉数,给出了图与其线图的交叉数的有关性质,并得到了一个图与其线图的交叉数为都为k的充分必要条件: 设G为图,cr(G)=K(K≥1),其线图为L(G)。若cr(L(G))=K,则当且仅当下列条件成立: (1) △(G)≤4,且G中每个4-度点都是割点; (2) 存在G的一个恰有K个交叉数的最优画法使得每条交叉的边关联G中的一个2度点。 该结果实质性地推广了Stanislav Jendrol′和Marian Kle(?)的关于非平面图和它的线图的交叉数都是1结果。
欧阳章东[5]2011年在《关于图的交叉数问题研究》文中认为图的交叉数问题起源于一个实际应用问题,其理论在电路板设计,草图识别与重画以及生物工程DNA的图示等领域有广阔的应用.国内外许多学者都从事过交叉数问题研究.但是,已经被证明计算图的交叉数是个NP-完全问题.由于其难度,到目前为止有关交叉数的结果并不丰富,且能确定其交叉数的图类基本上结构都比较特殊,故很多方法都无法推广到更一般的情形.有时候,我们就连试图找出一个图的交叉数上界或下界都比较困难.本文尝试用一些新的方法去研究积图、联图等一些典型图类的交叉数.确定了若干积图、联图等图类的交叉数,以及得到了一些交叉数的性质.具体如下：(1)得到了一个拉链积性质,作为性质的一个直接应用,证明了：对于任意包含4个支配点的图G,都有,(2)利用“局部加边法”得到了Kme的交叉数(m≤12).进而,确定了Km×Pn的交叉数(m≤10),这也就证明了郑文平和杨元生等提出的关于Km×Pn的交叉数猜想对于m≤10成立.(3)Klesc得到了K4e×Pn以及K5e×Pn的交叉数.杨元生和杨希武得到了K6×Pn的交叉数.用与他们不同的方法,我们得到K7×Pn以及K9×Pn的交叉数.(4)修改了Klesc常用的收缩手术,证明了cr(K3.3×Sn)=cr(K3,3,n)+ 3n,以及cr(K2,2,2×Sn)=Z(6,n)+6n(5)灵活利用K2,3e的结构特征,得到了K2,3e与路、圈的联图的交叉数.证明过程是简洁的.(6)确定了K3,3-2K2与路、圈的联图的交叉数,以及与星的积图的交叉数.虽然用的是“边集划分”法,但巧妙地利用6圈的结构特征,避免了穷举K3,3-2K2的所有画法.(7)运用组合计数方法,给出了两个交叉数递推不等式.作为不等式的应用,确定了K4,ne的交叉数.并且给出了确定K1,3,n交叉数的一个简单方法.除了以上内容外,本文还比较详尽地综述了交叉数问题研究现状.特别是积图的交叉数研究现状.
杨希武[6]2007年在《Flower Snark和K_m-e□P_n的交叉数》文中进行了进一步梳理图的交叉数是衡量图的非平面性的一个重要参数，计算图的交叉数是非常困难的，Garey和Johnson在1983年证明了计算图的交叉数问题是NP完全的。目前只有很少的图的交叉数的精确值是已知的，比如广义Petersen图P(n，3)，所有5个顶点的图与路径的交图等，而完全图、完全二分图等图族的交叉数仍然是拓扑图论中待解决的难题。本文对叁正则图Flower Snark及其相关图F_n(n≥3)和Twisted Flower Snark及其相关图F_n~*(n≥3)的交叉数进行了研究，分别给出了这两类图的交叉数的精确值。证明了cr(F_3)=2、cr(F_4)=3、cr(F_5)=4、cr(F_n)=n(n≥6)。cr(F_3~*)=1、cr(F_4~*)=2、cr(F_5~*)=4、cr(F_n~*)=n(n≥6)。另外本文还研究了路径与图K_m-e的交图K_m-e□P_n的交叉数。首先给出了这类图的交叉数上界：同时给出了K_m-e□P_n的交叉数下界公式：进一步本文确定了K_6-e□P_n的交叉数：cr(K_6-e□P_n)=12n，n≥1。
邓成瑞[7]2006年在《W_（3，n）和K_m□C_n的交叉数》文中研究表明图的交叉数是衡量图的非平面性的一个重要参数，Garey和Johnson证明了计算图的交叉数问题是NP完全的。目前仅确定了少数几类图的交叉数。完全图，完全二分图，广义Petersen图，循环图，顶点数较小的图与路径、圈或者星图的交图是交叉数问题中活跃的研究对象。 Kn(?)del图是一种互连网络，研究互连网络的交叉数有助于更好地理解其拓扑性质。本文研究了Kn(?)del图W_(3，n)(n≥8，n为偶数)的交叉数。首先利用计算机构造了W_(3，n)交叉数较少的画法，给出交叉数上界；然后设计了W_(3，n)的边分组方式和交叉点计数函数给出其下界。最终证明： cr(W_(3，8))=0；cr(W_(3，10))=1；cr(W_(3，n))=[n/6]+n mod 6/2，当n≥12时。 Ringeisen和Beineke给出了K_3□C_n以及K_4□C_n的交叉数。本文进一步研究了完全图和圈的交图K_m□C_n的交叉数。通过设计K_m□C_n的分组方式和交叉点计数方法，给出了K_m□C_n交叉数的下界： cr(K_m□C_n)≥n cr(K_(m+2))。通过改进计算图的交叉数算法CCN的限界条件，利用计算机构造了K_m□C_n好的画法，给出了K_m□C_n交叉数的上界： cr(K_m□C_n)≤n/4[m+2/2][m+1/2][2/2][m-1/2](n为偶数)； cr(K_m□C_n)≤n/4[m+2/2][m+1/2][m/2][m-1/2]+[m-1/2]~2(n为奇数)。因为m≤12时Guy给出的完全图交叉数猜想成立，所以当m≤10，n为偶数时，有： cr(K_m□C_n)=n/4[m+2/2][m+1/2][m/2][m-1/2](m≤10且n为偶数)。当n为奇数时，利用计算机构造出了K_5□C_n，K_6□C_n和K_7口C_n的交叉数更少的画法，进一步改进了上界。从而完全确定了这叁类图的交叉数： cr(K_5□C_n)=9n；cr(K_6□C_n)=18n；cr(K_7□C_n)=36n。
欧阳娟[8]2012年在《特殊图G与路与圈以及与孤立点的联图的交叉数》文中进行了进一步梳理图的交叉数问题起源于二战时期Pual Turán在砖厂碰到的一个实际问题,后来逐渐发展成为图论学科中非常活跃的一个分支,吸引着大批国内外学者的关注和研究,其理论在电路板设计,草图识别与重画以及生物DNA的图示等领域有广泛的应用.但是,k确定一般图类的交叉数问题已经被证明是一个NP-完全问题.因此,至今为止有关图的交叉数问题的结果还非常少,且己被确定交叉数的图类大多数都是一些比较特殊的图类,故很多方法都不能推广到一般情况.甚至有的时候找出图的交叉数的一个比较好的上界或下界也很困难.本文运用归纳法的思想以及反正法确定了两个特殊图类的交叉数：一个六阶图H与路Pn的联图的交叉数以及一个四阶不连通图G与路,圈联图的交叉数本文一共由五个章节组成.第一章主要介绍了交叉数的起源,交叉数研究的理论与实际意义,目前关于交叉数的一些研究现状,同时本章节还简要的介绍了本文主要结构.第二章介绍了阅读本文时所必须的一些关于交叉数方面的基本概念以及一些重要结果.第叁章,本章节主要得到关于图H与n个孤立点nK1的联图的交叉数,以及此图与路Pn的联图的交叉数及与圈的联图的交叉数的上下界.第四章,本章主要介绍一个四阶不连通图G与路,圈的联图的交叉数.第五章,给出本文的总结.
耿智琳, 张耀峰[9]2006年在《一类1-齐次图的参数性质》文中研究说明利用距离正则图的交叉表、交叉数的性质以及已知相关结论,对满足条件pd2,d=0,bd,1=1,a1=0的直径d≥2,价k>2的1-齐次图进行了研究,得到其参数的若干性质,部分地解决了一个相关的公开问题。
郑百功[10]2013年在《冒泡排序图B_n和广义Petersen图P（10,3）的交叉数》文中指出一个图G的交叉数cr(G)是其重要的拓扑不变量,是图的非平面性的重要度量尺度。图的交叉数问题已经成为图论的重要研究方向之一,而且它在大规模集成电路板的设计、CAD制图等很多领域都有重要应用。然而,由于计算具体某一个图的交叉数已经在上个世纪被国外学者证明是一个NP完全问题,所以现在只有少数一些图族的交叉数是确切已知的,例如路径图、环路图和一些较小阶图的笛卡尔乘积图；而对于一些特殊的图类,如经典的完全图和完全二部图,则仅有一些对其交叉数的猜想。n维冒泡排序图Bn是一种基于Cayley方法构造出的新的网络拓扑结构。相比于经典的n维超立方体结构Qn,Bn在连通度和容错性等方面都有更好的性质,因此有关其各种性质的研究都引起了相关领域内的研究者的重视。然而对其交叉数的研究并不多,主要原因在于其顶点随着维度的增加而成阶乘级的增加。本文利用已有的计算机算法成果和数学分析相结合的方法,给出了一种Bn的可递归的画法。对n<7的情况,本文给出了一些较好的Bn的画法；而对n≥7的情况,本文通过研究可递归画法中的交叉点种类,进而估计该画法中的交叉点的数量,并给出了cr(Bn)的一个上界：作为交叉数领域中的一个研究热点,广义Petersen图的交叉数一直是研究者很关注的问题,进而也已经产生了很多与之的相关结果。例如,广义Petersen图P(3k+1,3)的交叉数作为其中的经典问题,曾经被国外学者用归纳法证明。然而作为其归纳法的起点,P(10,3)的交叉数的相关结果只是一个被计算机验证的结果,而并没有明确的数学证明。而理论上与P(10,3)的交叉数相关的结果只有cr(P(10,3))≥5。本文通过研究P(10,3)的画法,并利用其子图的画法的一些性质,从理论上证明了cr(P(10,3))=6。
参考文献：
[1]. 笛卡儿积图交叉数的若干结果[D]. 周智勇. 湖南师范大学. 2007
[2]. 图的交叉数的若干结果[D]. 卢俊杰. 华东师范大学. 2004
[3]. 若干图类交叉数的研究[D]. 王晶. 湖南师范大学. 2009
[4]. 线图与若干典型图类的交叉数研究[D]. 赵霆雷. 湖南师范大学. 2006
[5]. 关于图的交叉数问题研究[D]. 欧阳章东. 湖南师范大学. 2011
[6]. Flower Snark和K_m-e□P_n的交叉数[D]. 杨希武. 大连理工大学. 2007
[7]. W_（3，n）和K_m□C_n的交叉数[D]. 邓成瑞. 大连理工大学. 2006
[8]. 特殊图G与路与圈以及与孤立点的联图的交叉数[D]. 欧阳娟. 湖南师范大学. 2012
[9]. 一类1-齐次图的参数性质[J]. 耿智琳, 张耀峰. 武汉科技学院学报. 2006
[10]. 冒泡排序图B_n和广义Petersen图P（10,3）的交叉数[D]. 郑百功. 大连理工大学. 2013