论文部分内容阅读
图G的弦图扩充问题包含两个问题:图G的最小填充问题和树宽问题,分别表示为f(G)和TW(G);图G的区间图扩充问题也包含两个问题:侧廓问题和路宽问题,分别表示为P(G)和PW(G),对一般图而言,它们都是NP-困难问题,一些特殊图类的填充数、树宽、侧廓问题和路宽具体值已被求出,主要研究树T的线图L(T)的弦图扩充问题;其次涉及到了两类特殊树一毛虫树和直径为4的树的线图的区间图扩充问题.