本文關(guān)鍵詞：關(guān)于一類特殊聯(lián)圖的交叉數(shù)的研究　出處：《湖南師范大學》2015年碩士論文　論文類型：學位論文

  更多相關(guān)文章： 圖 圈 畫法 交叉數(shù) 聯(lián)圖

【摘要】：圖的交叉數(shù)是在近代圖論中發(fā)展起來的一個重要概念,起源于19世紀五十年代,是拓撲圖論中的前沿問題.它主要研究圖在一個平面或曲面上最優(yōu)畫法下的最小交叉數(shù)目,是圖的非平面性的一個重要參數(shù).由于其在電路板設計和生物工程DNA圖示等領(lǐng)域的廣泛應用,吸引著眾多國內(nèi)外的專家和學者的關(guān)注與研究.但Garey和Johnson已確定一般圖的交叉數(shù)是NP-完全問題.因而,到目前為止,有關(guān)圖的交叉數(shù)方面的研究結(jié)果較少.但在一些特殊圖類和簡單圖的交叉數(shù)方面的研究結(jié)果還是比較豐富的.本文主要確定了幾個特殊的五階圖和圈Cn的聯(lián)圖的交叉數(shù),其中包過W4+Cn的交叉數(shù)的證明,并且在此基礎(chǔ)上還提出了關(guān)于Wm1+Cn的交叉數(shù)的猜想.本文主要結(jié)構(gòu)如下：第一章：緒論,簡述圖的交叉數(shù)的起源和應用意義,介紹研究背景及本文的結(jié)構(gòu).第二章：給出本文用到的圖論的一些基本的概念,以及在后文中常用的性質(zhì)、引理.第三章：確定了幾個特殊的五階圖和圈Cn的聯(lián)圖的交叉數(shù).第四章：關(guān)于Wm+Cn的交叉數(shù)的證明及猜想.第五章：總結(jié)本文和展望未來工作.
[Abstract]:The cross number of graphs is an important concept developed in modern graph theory, which originated in 1850s. It is a frontier problem in topological graph theory. It mainly studies the minimum cross number of graphs under the optimal drawing on a plane or surface. It is an important parameter of non-planarity of graphs, because of its wide application in the field of circuit board design and bioengineering DNA diagram. It has attracted the attention and research of many experts and scholars at home and abroad, but Garey and Johnson have determined that the crossing number of general graphs is NP-complete problem. There are few results on the cross number of graphs, but there are abundant results in some special graphs and simple graphs. In this paper, we mainly determine some special fifth-order graphs and the associative graphs of cycles CN. The cross number of. In this paper, we prove the crossover number of W4Cn, and put forward the conjecture about the crossover number of Wm1 CN. The main structure of this paper is as follows: chapter 1: introduction. This paper briefly describes the origin and application significance of cross number of graphs, introduces the research background and the structure of this paper. Chapter 2: gives some basic concepts of graph theory used in this paper, as well as the properties commonly used in later papers. Lemma. Chapter 3: determine the crossover numbers of some special fifth-order graphs and cycles CN. Chapter 4th: proof and conjecture on the crossover number of Wm CN. Chapter 5th: summary of this paper and prospect of future work.
【學位授予單位】：湖南師范大學
【學位級別】：碩士
【學位授予年份】：2015
【分類號】：O157.5

【相似文獻】

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

1 周志東;黃元秋;彭小多;歐陽娟;;一個小圖與路和圈的聯(lián)圖的交叉數(shù)[J];系統(tǒng)科學與數(shù)學;2013年02期

2 李敏;;一個五階圖與n個孤立點及路的聯(lián)圖的交叉數(shù)[J];湖北文理學院學報;2013年11期

3 麥安嬋;聯(lián)圖的鄰域完整度[J];南陽師范學院學報(自然科學版);2004年09期

4 鄭敦勇;黃元秋;;一個五點圖和路的聯(lián)圖的交叉數(shù)[J];汕頭大學學報(自然科學版);2011年04期

5 王曉琦;田雙亮;薛國梁;孫向濤;;若干圖的廣義聯(lián)圖的星全染色[J];西北民族大學學報(自然科學版);2012年02期

6 李敏;;兩個5階圖與路及圈的聯(lián)圖的交叉數(shù)[J];河南師范大學學報(自然科學版);2013年04期

7 張德龍;關(guān)于聯(lián)圖的圈唯一性[J];廣西工學院學報;1997年01期

8 周志東;呂勝祥;;關(guān)于一個特殊六階圖與路和圈的聯(lián)圖的交叉數(shù)[J];數(shù)學進展;2014年01期

9 田雙亮;;若干聯(lián)圖的鄰點可區(qū)別全染色[J];西北民族大學學報(自然科學版);2006年01期

10 柳順義;陳祥恩;;關(guān)于聯(lián)圖的強色指數(shù)的一點注記[J];甘肅科學學報;2008年02期

相關(guān)博士學位論文 前2條

1 歐陽章東;關(guān)于圖的交叉數(shù)問題研究[D];湖南師范大學;2011年

2 周志東;圖的交叉數(shù)有關(guān)問題研究[D];湖南師范大學;2013年

相關(guān)碩士學位論文 前10條

1 彭小多;幾類聯(lián)圖的交叉數(shù)研究[D];湖南師范大學;2012年

2 岳為君;關(guān)于一類特殊聯(lián)圖的交叉數(shù)的研究[D];湖南師范大學;2015年

3 歐陽娟;特殊圖G與路與圈以及與孤立點的聯(lián)圖的交叉數(shù)[D];湖南師范大學;2012年

4 孟獻青;聯(lián)圖的全染色及鄰點可區(qū)別全染色[D];山西大學;2007年

5 李婷;關(guān)于積圖和聯(lián)圖的交叉數(shù)問題研究[D];北京師范大學;2008年

6 魏甲靜;幾個特殊圖與空圖、路、圈的聯(lián)圖的交叉數(shù)[D];西北師范大學;2013年

7 景京;連通度與奇H-聯(lián)圖[D];華中師范大學;2008年

8 李光榮;幾類聯(lián)圖的全著色研究[D];中國人民解放軍信息工程大學;2005年

9 陳園;圖的模linkage研究[D];華中師范大學;2006年

10 趙麗桃;幾類圖的鄰點可區(qū)別全染色[D];山西大學;2009年

，

本文編號：1366459