樹狀圖的路覆蓋問題及其應用.pdf

1、近五十年來，隨著計算機科學和互聯(lián)網(wǎng)技術的發(fā)展，圖論得到了廣泛的重視。各種形式的覆蓋問題成為圖論領域重要的研究方向。覆蓋問題在VLSI設計（超大規(guī)模集成電路設計）、程序測試、網(wǎng)絡問題、環(huán)協(xié)議、代碼優(yōu)化等方面有著廣泛應用。本文主要研究圖的路覆蓋問題。
　　 給定一個圖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、稱路集合P是圖G的一個路覆蓋。最小路覆蓋的基數(shù)稱為圖G的最小路覆蓋數(shù)，記為c(G)。路覆蓋問題就是尋找圖G中有c(G)條路的路覆蓋。
　　 在本文第一部分里，給出了頂點數(shù)大于l的樹T路覆蓋數(shù)的下界p-eh-1，其中p表示葉子數(shù)，eh表示連接兩個度大于2的頂點的邊數(shù)。第二部分，得到了塊圖G與塊割點一樹(block-cutpoint-tree)Tc的最小路覆蓋數(shù)之間的關系，從而給出了一類終端塊數(shù)為b的塊圖的最小路覆蓋數(shù)是b-1，其中