圖G的最小伸展支撐樹問題是尋求圖G的支撐樹T,使得相鄰兩頂點(diǎn)在T中的最大距離達(dá)到最小。這個最小值稱為圖G的樹展,記作σ(G)。此問題已被證明為NP-困難的,對若干特殊圖類亦已得到上界估計(jì)。例如對區(qū)間圖已知σ(G)≤3,對區(qū)間圖得到σ(G)=k,k=1,2,3的完整刻畫。

【文章頁數(shù)】：6 頁

【文章目錄】：
1 基本性質(zhì)
2 區(qū)間圖的最優(yōu)性刻畫
3 結(jié)論



本文編號：4045889