21934.幾類圖的線性蔭度和線性k蔭度

1、分類編號(hào)：密級(jí)：?jiǎn)挝淮a：10065學(xué)號(hào)：1210050018天滓?guī)熫么骭掌研究生學(xué)位論文論文題目：幾類圖的線性蔭度和線性尼一蔭度學(xué)生姓名：何圣潔申請(qǐng)學(xué)位級(jí)別：理學(xué)碩士申請(qǐng)專業(yè)名稱：運(yùn)籌學(xué)與控制論研究方向：指導(dǎo)教師姓名：論文提交日期：幾類圖的線性蔭度和線性忌一蔭度摘要圖的著色理論和分解理論在許多領(lǐng)域都有很重要的應(yīng)用。圖的線性蔭度和線性缸蔭度是圖的著色理論和分解理論中兩個(gè)重要的概念，近三十年來(lái)在國(guó)內(nèi)外得到了廣泛的研究。一個(gè)圖G的線性缸森林

2、是圖G的一個(gè)子圖，其中，它的每個(gè)連通分支為長(zhǎng)度最多為七的路。圖G的線性舡蔭度z釓(G)即為分解圖G的邊集E(G)所需要的線性七一森林的最小數(shù)目。圖G的線性缸蔭度的概念最早是由Habib和Peroche提出的，它是邊染色的自然推廣。顯然，一個(gè)線性1一森林就是一個(gè)匹配，2口1(G)就是圖G的邊色數(shù)，也即)(，(G)。當(dāng)森林的每條路的長(zhǎng)度沒(méi)有限制時(shí)，則圖G的邊集E(G)分解成這種森林的最小數(shù)目就是圖G的線性蔭度，記作fn(G)或者fn。(G)

3、。下面關(guān)于Zn七(G)的上界的猜想11是由Habib和Peroche在1982年提出的。猜想11∽≤，l精I(xiàn)]秈p卜Ⅳ∽州1’一Il幫l，秈(G)∽(G)Il，當(dāng)七=Iy(G)I一1時(shí)，這就是Al【iy鋤a的猜想。猜想12zn(G)≤本文主要包括五章，其中第五章又分為兩節(jié)：在第一章中，介紹了預(yù)備知識(shí)和圖的線性蔭度和線性七蔭度的相關(guān)研究背景。第二章中，我們得到了m個(gè)圈ck的笛卡爾積圖c：【：：：的線性(佗一1)一蔭度的精確值。第三章中，我