一般图上的最小权边覆盖问题

  1. 2周前

    问题背景:为通信骨干网络选择备用线路
    给出带权无向图G中的一个生成树(边集)S,寻找一个边集S'使得S并S'的导出子图边二连通且S'的权值和最小。
    与该问题有关的一篇文章
    该问题在菊花图(只有一个顶点的度数大于1)中退化为帖子标题所述的问题,即
    在一个带权无向图G中选出一组边集S使得G中所有顶点都被S中至少一条边连接且S的权值和最小。
    这个链接 里提到了如何把这个问题转化为一般图上的最小(大)权匹配问题,但缺乏相关的证明。
    所以我来伸手了(感觉他说的好有道理但无法独立完成证明)。
    我现在仅有的证明思路是:
    (参考给出的第二个链接)证明最优解OPT(边集)一定是在已有的基础上(给每个点指派与其连着的最小权边)加上一个匹配M(对于匹配M中的每一条边(u,v),将之前给u,v指派的边删去再加上边(u,v))形成的,并且这个匹配M是新图(原图中的边(u,v)的边权改为c_u+c_v-w_(u,v))中任意一个最大匹配。

 

后才能发言