本文關(guān)鍵詞：圖中短圈及相關(guān)問題

  更多相關(guān)文章： 最短圈 廣探樹 Euler公式 圖染色

【摘要】：短圈是圖的重要結(jié)構(gòu).本文的第二章到第四章主要介紹了找到各類圖中短圈的算法.第二章主要介紹了一種找到平面圖中任意兩點之間的所有最短路的算法,同時證明了平面連通圖G中非測地的最短偶長圈一定是某棵支撐樹的基本圈或是兩個基本圈的和.在找平面連通圖G中的最短奇長圈時,得到結(jié)論:如果最短奇長圈是圖G中的最短圈,那么我們可以找到圖中的所有最短奇長圈;否則,可以利用算法找到一個最短奇長圈.第三章我們研究的是特殊情況下的符號圖中的最短正圈以及最短負圈.主要利用廣探樹算法,最終得到了如果符號圖中的最短正圈(負圈)的長度大于最短負圈(正圈)的長度,那么最短正圈(負圈)是一個基本圈或是兩個基本圈的和,從而得到了符號圖中的最短圈是一個基本圈或是兩個基本圈的和.第四章研究的是賦權(quán)圖中的短圈結(jié)構(gòu).利用Dijkstra算法,我們設計了一種算法可以找到賦權(quán)圖中的一個最短偶長圈.在本文的第五章,我們主要利用Euler公式以及Gallai提出的研究色臨界圖的方法,用一種較簡單的方法證明了曲面S上7-色臨界圖的個數(shù)是有限的,且計算出了曲面S上的7-色臨界圖中至多有120(g-1)個點,其中g(shù) ≥ 2.同時也給出了曲面S上的每一個k-色臨界圖(k≥ 7)點數(shù)的上界為 12(k + 3)(g-1),其中 k≥7,g≥2.
【學位授予單位】：華東師范大學
【學位級別】：碩士
【學位授予年份】：2017
【分類號】：O157.5

【相似文獻】

中國期刊全文數(shù)據(jù)庫 前10條

1 王順年;;分數(shù)染色臨界圖及其性質(zhì)[J];科學技術(shù)與工程;2006年24期

2 劉峙山;關(guān)于邊著色臨界圖的一個問題[J];內(nèi)蒙古師大學報(自然科學漢文版);1991年04期

3 杜之亭，，孫惠泉;若干色臨界圖和色極小圖的構(gòu)造[J];北京郵電大學學報;1994年04期

4 歐陽克智,張忠輔,張建勛;全著色臨界圖[J];蘭州大學學報;1991年02期

5 苗連英;苗正科;段滋明;曲積彬;;邊色臨界圖的1-因子和幾乎1-因子的存在性[J];中國礦業(yè)大學學報;2008年01期

6 李雪峰;;一種構(gòu)造k—色臨界圖的方法[J];廊坊師范學院學報(自然科學版);2009年03期

7 苗連英;楊星星;苗正科;;邊色臨界圖的1-因子和幾乎1-因子的存在性[J];中國礦業(yè)大學學報;2010年02期

8 曲積彬;;最大度為9和10時邊染色臨界圖的下界[J];黑龍江科技學院學報;2007年06期

9 龔和林;舒情;;色臨界圖的最大度與色數(shù)的一個關(guān)系式[J];數(shù)學的實踐與認識;2012年07期

10 王發(fā)友,王萬方,任慶軍;路色數(shù)臨界圖[J];臨沂師專學報;1999年03期

中國碩士學位論文全文數(shù)據(jù)庫 前5條

1 齊林明;關(guān)于邊染色臨界圖有關(guān)性質(zhì)的研究[D];中國礦業(yè)大學;2015年

2 劉兵兵;曲面上嵌入圖染色的綜述[D];華東師范大學;2015年

3 李青青;圖中短圈及相關(guān)問題[D];華東師范大學;2017年

4 王順年;圖的分數(shù)染色[D];山東師范大學;2007年

5 范青菊;全著色臨界圖及鄰點可區(qū)別全著色[D];山西大學;2008年

本文編號：1278626