某些特殊圖與正則圖的路覆蓋數(shù).pdf

1、圖論在近三十多年來發(fā)展十分迅速，其應(yīng)用已涉及計(jì)算機(jī)科學(xué)、物理學(xué)、信息論、控制論、運(yùn)籌學(xué)以及網(wǎng)絡(luò)理論等領(lǐng)域。路覆蓋是圖論中的一個(gè)非常重要的概念，可以應(yīng)用于并行算法設(shè)計(jì)，程序代碼優(yōu)化，應(yīng)用程序測(cè)試，環(huán)協(xié)議設(shè)計(jì)等問題。本文主要討論圖的路覆蓋問題。
　　連通圖與其生成樹的路覆蓋數(shù)之間有非常密切的關(guān)聯(lián)，我們將利用生成樹的路覆蓋數(shù)來研究一般連通圖的路覆蓋數(shù)問題，為此探討樹狀圖的路覆蓋數(shù)是研究的基礎(chǔ)。正則圖是非常重要的一個(gè)圖類。由于正則圖具有很

2、好的對(duì)稱性，所以正則圖的系列性質(zhì)是圖論中一直被研究的話題，同時(shí)也是圖論研究中相當(dāng)活躍的一個(gè)領(lǐng)域，因此其路覆蓋數(shù)應(yīng)該有更為精細(xì)的結(jié)論，本文將重點(diǎn)討論正則圖的路覆蓋數(shù)問題。
　　圖G的路覆蓋是由頂點(diǎn)不相交的路所構(gòu)成的一個(gè)集合，使得圖G的每個(gè)頂點(diǎn)恰好包含于路覆蓋的某條路中。在圖G的所有路覆蓋中，包含路條數(shù)最少的那個(gè)路覆蓋稱為圖G的一個(gè)最小路覆蓋，記為p。所包含路的條數(shù)稱為G的路覆蓋數(shù)，記為P(G)。
　　本文對(duì)圖的路覆蓋數(shù)進(jìn)行了研

3、究和探討，主要得出了下面的結(jié)論：
　　1.本文從圖的路覆蓋數(shù)出發(fā)，討論了簡(jiǎn)單連通圖去掉一條邊或者去掉一個(gè)頂點(diǎn)時(shí)的路覆蓋數(shù)的變化情況；對(duì)k層完全二叉樹T的路覆蓋數(shù)進(jìn)行了研究，分別得出了k為奇數(shù)和偶數(shù)時(shí)樹T的最小路覆蓋數(shù)；研究了某些線圖的路覆蓋數(shù)與原圖邊覆蓋數(shù)之間的關(guān)系，以及k-擬正則圖的路覆蓋數(shù)；分情況研討了樹狀圖的路覆蓋數(shù)與重邊數(shù)之間的關(guān)系，同時(shí)也得到了不同重邊數(shù)條件下路覆蓋數(shù)的值；給出了2-sparse樹的一個(gè)充分必要條件。