区间图最小伸展支撑树问题的最优性刻画

发布时间：2025-05-14 23:21

　　 图G的最小伸展支撑树问题是寻求图G的支撑树T,使得相邻两顶点在T中的最大距离达到最小。这个最小值称为图G的树展,记作σ(G)。此问题已被证明为NP-困难的,对若干特殊图类亦已得到上界估计。例如对区间图已知σ(G)≤3,对区间图得到σ(G)=k,k=1,2,3的完整刻画。

【文章页数】：6 页

【文章目录】：
1 基本性质
2 区间图的最优性刻画
3 结论



本文编号：4045889