發(fā)布時(shí)間：2017-12-11 13:25

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

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

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

【相似文獻(xiàn)】

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 王順年;圖的分?jǐn)?shù)染色[D];山東師范大學(xué);2007年

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

本文編號：1278626