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

摘要

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