一类特殊的极大＋和支撑树在调整和权值下的逆问题

本文研究的是一类特殊的极大＋和支撑树在调整和权值下的逆问题．给定一个边赋权连通网络G=（VE，c，w），对于每一条边e∈E，已知一个费用c（e）和一个权值叫（e），极大＋和支撑树问题是指寻找一棵支撑树T＊，使得其是权值marxw（e）＋∑c（e）最小的一棵支撑树．而在极大＋和支撑树的逆问题中，给定一棵支撑树％，eET它不是已知网络中最优的极大＋和支撑树，要求调整网络中各边的费用c（e），使死变成调整后网络中最优的极大＋和支撑树，目标函数是使得在l1模意义下的边权调整费用尽可能的小．本文针对已知网络中各边费用都相等这一特殊情况，给出了求解该逆问题的列生成算法，每次迭代时入基向量的选择可以转化为一个新参数下的极大＋和支撑树问题，从而可在多项式时间内确定入基向量的选择．本文最后给出了一个实例说明算法的有效性．