国产bbaaaaa片,成年美女黄网站色视频免费,成年黄大片,а天堂中文最新一区二区三区,成人精品视频一区二区三区尤物

首頁> 中文學(xué)位 >關(guān)于可平面圖的邊剖分的若干結(jié)果
【6h】

關(guān)于可平面圖的邊剖分的若干結(jié)果

 
  • 目錄
  • 摘要
  • 著錄項
  • 相似文獻(xiàn)
  • 相關(guān)主題

目錄

文摘

英文文摘

論文說明：符號說明

原創(chuàng)性聲明及關(guān)于學(xué)位論文使用授權(quán)的聲明

第一章引言

§1.1基本概念

§1.2問題產(chǎn)生的背景及其進(jìn)展情況

§1.3本文的主要結(jié)果

第二章可平面圖的邊染色

§2.1邊染色的分類問題

§2.2最大度為5的可平面圖的邊染色

第三章可平面圖的線性蔭度

§3.1已有結(jié)論

§3.2最大度為7的可平面圖的線性蔭度

§3.3其它結(jié)果

參考文獻(xiàn)

致 謝

攻讀碩士學(xué)位期間發(fā)表及完成的論文

展開▼

摘要

本文考慮的圖若無特殊聲明均為簡單、無向有限圖。對于一個圖G=G(V(G)，E(G))，本文用V(G)和E(G)分別表示圖的頂點集合和邊集合。對任意的ν∈V(G)，采用d<,G>(ν)表示頂點ν在G中的度數(shù)?！?G)和δ(G)分別表示圖G的最大度和最小度。對V(G)的子集S，用G-S表示從G中刪去頂點集合S及其關(guān)聯(lián)的邊所得到的子圖。若S={ν}，則令G-ν=G-{ν}。對E(G)的子集x，用G-X表示從G中刪去邊集合X所得的子圖。若X={e}，則G-{e}簡記為G-e。若存在V(G)的兩個不交子集X、Y，使得V(G)=X ∪Y，且G的所有邊均一個端點在X內(nèi)，另一個端點在Y內(nèi)，則稱G為二部圖，記為G=(X，Y，E(G))。 若圖G可以表示在平面上，并且任兩條邊僅在其端點處才可能相交，則稱G是可平面圖。圖G的這種平面上的表示法稱為G的一個平面嵌入，或稱為平面圖。對于一個平面圖G，我們用F(G)來表示G的面集合。對于一個面f，我們把將f圍起來的所有的邊所構(gòu)成的集合稱為f的邊界，并且稱f關(guān)聯(lián)于其邊界上的所有的頂點和邊。同樣地，可以定義，的度dG(f)為f的邊界上的邊數(shù)。若G的兩個面f<,1>和f<,2>有一條公共邊e，則稱面f<,1>和f<,2>相鄰接于邊e。若存在映射φ：E(G)→{1，2，…，κ}，對于G中任意兩條相鄰接的邊e<,1>和e<,2>，滿足φ(e<,1>)≠φ(e<,2>)，則稱G是κ一邊可染色的。這時對于任意的1≤i≤κ，φ<'-1>(i)的邊導(dǎo)出子圖均是圖G的一個匹配。我們把使得圖G具有κ-邊染色的最小正整數(shù)κ定義為G的邊染色數(shù)，記作X(G)。 若圖的每一個連通分支都是一條路，則稱該圖為一個線性森林。我們稱映射ψ：E(G)→+{1，2，…，t)為圖G的一個t-線性染色，如果對于任意的1≤α≤t都有，ψ<'-1>(α)的邊導(dǎo)出子圖是一個線性森林。本文把使圖G具有t-線性染色的最小正整數(shù)t稱為G的線性蔭度，記作lα(G)。 圖的染色理論是圖論的一個重要分支，是圖論研究中最活躍的課題之一。根據(jù)一定的規(guī)則將一組目標(biāo)劃分為不同的種類，這是數(shù)學(xué)中的一個基本方法。不同的規(guī)則決定著該組中任意一對目標(biāo)是否在同一個類中。圖的染色理論就是研究這類問題的一門理論，它有著相當(dāng)廣泛的應(yīng)用背景。各種形式的日程表問題，時間表問題以及排序問題，從根本上來說都可以歸結(jié)為染色問題。對染色理論的研究最早可以追溯至1852年，即著名的“四色猜想”的提出。而圖的邊染色問題引起人們關(guān)注的時間相對較晚。但是，許多研究領(lǐng)域，如地圖染色，匹配理論以及拉丁方，都與邊染色問題有著緊密的聯(lián)系。關(guān)于邊染色的第一篇文章出現(xiàn)在1880年，由P.G.Tait在對“四色猜想”做進(jìn)一步的研究時，證明出“任一2-邊連通，3-正則的甲面簡單圖是3-邊可染色的”與“四色猜想”足等價的。此后，關(guān)于邊染色問題的研究又有了一些比較重要的結(jié)論，如Konig's Theorem，Shannon's Theorem以及Vizing's Theorem。圖的邊染色中，根據(jù)著名的Vizing's Theprem，可以將簡單圖分為兩類。圖的分類問題就是判斷一個圖G究竟是第一類圖，還是第二類圖的問題。關(guān)于圖的分類問題，雖然已有一些相關(guān)的結(jié)論，但是未解決的部分還有很多。而對于可平面圖的邊染色的分類問題，Vizing證明出任一△(G)≥8的可平面圖G均是第一類圖，而△∈{2，3，4，5}的可平面圖中存在第二類圖。于是Vizing在1968年的時候，提出了著名的可平面圖猜想。 圖G的線性蔭度這一概念是由Harary在1970年提出的。接著在1980年，由Akiyama，Exoo和Harary等人給出了關(guān)于正則圖的線性蔭度的猜想；并且在這一猜想的基礎(chǔ)上，產(chǎn)生了著名的線性蔭度猜想(the Linear Arboricity Conjecture，簡稱為LAC)。在對線性蔭度猜想進(jìn)行研究時，J.Wu解決了可平面圖條件下這個猜想的大部分情況，只余下△=7這一種情況仍未解決。 本文中主要研究的是可平面圖的邊染色及線性蔭度方面的一些結(jié)果。 全文共分三章，第一章簡單介紹一下圖論中的一些基本概念，并給出邊染色、線性蔭度問題的歷史背景和進(jìn)展?fàn)顩r以及一些已有的相關(guān)結(jié)論。這一章是后面其他各章節(jié)的基礎(chǔ)。 第二章我們主要討論可平面圖的邊染色的一些情況。主要結(jié)論為：定理2.1.10．設(shè)G是最大度為5的可平面圖。若G中不含長度為4的圈，或不含長度為5的圈，則G是第一類圖。 第三章則討論了可平面圖的線性蔭度的一些情況，其主要得出了33個定理。

著錄項

  • 作者

    吳玉文;

  • 作者單位

    山東大學(xué);

  • 授予單位 山東大學(xué);
  • 學(xué)科 運籌學(xué)與控制論
  • 授予學(xué)位 碩士
  • 導(dǎo)師姓名 吳建良;
  • 年度 2007
  • 頁碼
  • 總頁數(shù)
  • 原文格式 PDF
  • 正文語種 中文
  • 中圖分類 圖論;
  • 關(guān)鍵詞

    圖論; 染色理論; 線性蔭度; 可平面圖; 邊染色;

相似文獻(xiàn)

  • 中文文獻(xiàn)
  • 外文文獻(xiàn)
  • 專利
AI論文寫作

客服郵箱：kefu@zhangqiaokeyan.com

京公網(wǎng)安備：11010802029741號 ICP備案號：京ICP備15016152號-6 六維聯(lián)合信息科技 (北京) 有限公司?版權(quán)所有

  • 客服微信

  • 服務(wù)號