【摘要】：圖的交叉數(shù)是衡量一個圖與平面圖距離有多遠的標(biāo)準(zhǔn),也是圖的一個重要參數(shù),并且具有相當(dāng)廣泛的實際應(yīng)用.但是,M.R.Garey和D.S.Johnson曾經(jīng)證明了圖的交叉數(shù)問題是NP-難問題[2],而且交叉數(shù)問題一直是拓撲圖論中的前沿難題.現(xiàn)在還沒有一個統(tǒng)一的方法來計算圖的交叉數(shù),因此關(guān)于這方面的結(jié)果并不豐富.本篇論文主要研究兩類特殊圖的交叉數(shù)的下界.第一部分:運用局部構(gòu)建新圖法建立了完全三部圖K3,3,n與完全二部圖K6,n+3的交叉數(shù)關(guān)系,從而得到了它的一個下界值;第二部分:運用收縮手術(shù),求出了笛卡爾積圖K2,6 × Sn的交叉數(shù)的下界值.本文主要分為下面五個章節(jié):第一章:緒論,主要介紹了圖論的研究背景以及目前所出現(xiàn)的幾類特殊圖的研究成果,簡要的概括研究內(nèi)容.第二章:主要給出本文中會涉及到的基本概念及相關(guān)性質(zhì),介紹本文的主要結(jié)果.第三章:首先介紹了本章所需要的概念與引理,對K3,3,,n的交叉數(shù)下界值進行證明.第四章:給出了本章所需要的引理,建立笛卡爾積圖K2,6 ×Sn與完全三部圖K2,6,n之間的交叉數(shù)關(guān)系,從而部分解決了猜想:cr(K2,m X Sn)= cr(K2,m,n)+n[m/2][m-1/2](m ≥ 5).第五章:總結(jié)與展望.
【學(xué)位授予單位】：湖南師范大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2018
【分類號】：O157.5
【圖文】：

令Ｇ表示所有位于位于和＾ｅ３，ｉ＋１）形成的７ｉ邊集合／＃，其中下標(biāo)取逡逑模３．逡逑如圖３．１所示，我們有ＥＬ⑷＝闖＝ＥＬ呦＝ｎ．另外，在平逡逑面ｉＥ２，存在關(guān)于祝辦）的圓盤領(lǐng)域，ｉＶ（４（ａ：ｆｃ），ｅ）邋＝邋｛ｓ邋ｅ邋ｉ？２邋：丨丨ｓ邋－《（辦）丨丨＜邋ｅ｝，逡逑其中ｅ充分小，并滿足於，３，？中不與辦相關(guān)聯(lián)的邊ｅ，有咖）ｎ邋ｉＶ（火辦），0邋＝邋０．逡逑下面，由欠３，３，？任意畫法也我們構(gòu)造私，？＋３的一個畫法么．逡逑步驟１：增加一個新點知＋１在《（ｅｄｎｉＶＯ＾ｉ）＃）的某個位置上．逡逑步驟２：對所有１彡ｉ邋＜邋３，去掉位于（注意保留知＋１）．逡逑步驟３：分別連接２？＋１和偵；ｄ），多（２：２），辦３），《⑷，多（ｙ２），你３）｝．逡逑例如，連接２？＋１１；和４（０：１）沿著外１，１）（＂１＾＾（０；１），￡），連接４＋１到４（２／１）首先逡逑沿著多（ｅｉａ）邋ｎｉＶＷｈ），＾），然后沿著ｉＶ＾ｘＡｅ）的外部？接著，連接＿２ｎ＋１逡逑和火如）首先沿著ａｉ邋（靠近４（ａ：ｉ））

邐＝邐（ｆ＞｛＾ｓ，３，ｎ）邋＋邋Ｃｉ邋＋邋ｃ？ｉ邋＋邋ｅｉ邋＋邋２ｎ邋＋邋Ａｃｒ＾＾Ｓｙ＾邋＋邋９．（３．１．２）逡逑完全類似上述過程，得到私，ｎ＋３的另外兩個畫法如和如如圖３．２逡逑Ｍ：；逡逑ｃ，邋／？＇逡逑／邋ｃ３逡逑／逡逑⑴逡逑廣逡逑（２）逡逑圖３．２：從＜＾（／＾３，３，７１）得到＾６，ｎ＋３的兩個畫法也和如逡逑因此逡逑＾２（７＾６，７１＋３）邋＝邋ｃｒ＾（ｉｆ３，３，ｎ）邋＋邋１＾２！邋＋邋｜＾３｜邋＋邋Ｉ－Ｂ２Ｉ邋＋邋１＾３！邋＋邋ＩＣ２Ｉ邋＋邋ＩＣ＾Ｉ逡逑＋邋２ｔｉ邋＋邋４。７＊彡（５＾９）邋＋邋９．逡逑１３逡逑

逡逑時私，６的畫法乃在同構(gòu)意義下是唯一的，如圖４．４所示，而且任何一個區(qū)域最多逡逑含有欠２，６的６個頂點，所以Ｇ中欠２０６頂點一定會落在欠２，６的任何至少兩個區(qū)域逡逑中，類似情形３．１，有＞邋４，矛盾？逡逑子情況３．３邋如果ｃｔ￡ｉ（／１）邋＝邋２，因為ｃｒｘ＾ＡｕＣ）邋＝邋４，那么彡邋２，這逡逑時私，６的畫法乃在同構(gòu)意義下如圖４．５所示，而且至少有兩個區(qū)域才能含有＆｜６的逡逑所有頂點，當(dāng)Ｇ中欠２Ｑ６頂點落在至少兩個區(qū)域中，類似情形３．１，有彡逡逑４，矛盾．逡逑子情況３．４如果ｃｒ0（＞４）邋＝邋３，因為ｃｒＤ0ｌ邋Ｕ邐＝邋４，則ｃｒ＾ＣＡＣ）彡１，這時在逡逑同構(gòu)意義下私

【參考文獻】

相關(guān)期刊論文 前5條

1 歐陽章東;黃元秋;;關(guān)于K_(2,2,2)□S_n的交叉數(shù)[J];應(yīng)用數(shù)學(xué)學(xué)報;2015年06期

2 呂勝祥;黃元秋;;K_(2,4)×S_n的交叉數(shù)[J];系統(tǒng)科學(xué)與數(shù)學(xué);2010年07期

3 張莉茜;李波;黃元秋;;關(guān)于六階圖與星的笛卡兒積交叉數(shù)[J];湖南文理學(xué)院學(xué)報(自然科學(xué)版);2008年01期

4 黃元秋;趙霆雷;;ON THE CROSSING NUMBER OF THE COMPLETE TRIPARTITE GRAPH K_(1,8,n)[J];數(shù)學(xué)物理學(xué)報;2006年S1期

5 黃元秋;趙霆雷;;關(guān)于完全3-部圖K_(1,6,n)的交叉數(shù)[J];應(yīng)用數(shù)學(xué)學(xué)報;2006年06期

相關(guān)博士學(xué)位論文 前1條

1 王晶;若干圖類交叉數(shù)的研究[D];湖南師范大學(xué);2009年

本文編號：2778229