樹(shù)狀圖的路覆蓋問(wèn)題及其應(yīng)用.pdf

1、近五十年來(lái)，隨著計(jì)算機(jī)科學(xué)和互聯(lián)網(wǎng)技術(shù)的發(fā)展，圖論得到了廣泛的重視。各種形式的覆蓋問(wèn)題成為圖論領(lǐng)域重要的研究方向。覆蓋問(wèn)題在VLSI設(shè)計(jì)（超大規(guī)模集成電路設(shè)計(jì)）、程序測(cè)試、網(wǎng)絡(luò)問(wèn)題、環(huán)協(xié)議、代碼優(yōu)化等方面有著廣泛應(yīng)用。本文主要研究圖的路覆蓋問(wèn)題。
　　 給定一個(gè)圖G=(V,E)和圖G中路的集合P={P1，P2，…，Pr}，定義P=(Vi，Ei)，l≤i≤r，若路集合P滿足：(1)Vi∩Vi=θ，i≠j;(2)∪i=1Vi=V，則

2、稱(chēng)路集合P是圖G的一個(gè)路覆蓋。最小路覆蓋的基數(shù)稱(chēng)為圖G的最小路覆蓋數(shù)，記為c(G)。路覆蓋問(wèn)題就是尋找圖G中有c(G)條路的路覆蓋。
　　 在本文第一部分里，給出了頂點(diǎn)數(shù)大于l的樹(shù)T路覆蓋數(shù)的下界p-eh-1，其中p表示葉子數(shù)，eh表示連接兩個(gè)度大于2的頂點(diǎn)的邊數(shù)。第二部分，得到了塊圖G與塊割點(diǎn)一樹(shù)(block-cutpoint-tree)Tc的最小路覆蓋數(shù)之間的關(guān)系，從而給出了一類(lèi)終端塊數(shù)為b的塊圖的最小路覆蓋數(shù)是b-1，其中