论文部分内容阅读
最小强连通图问题在图论算法和组合最优化中都占重要地位。本文通过限制有向圈的弧数，把最小强连通图问题归约成带自环二部图最小边覆盖问题，并设计出解决带圈弧数限制的最小强连通图问题的多项式最优算法。 本论文研究的最小强连通图问题基于一个带弧权重的强连通有向图D=(V,A;w)，其中w: A→ R+，且有向图D是任意有向圈弧数不超过3的强连通图，问题是在D中寻找一个弧子集A(C)A，使得对于V中任意两点u和v，在诱导子图D[A]中存在一条从u到v的有向路，目标是使得所选弧的权重之和达到最小，即w(A)=∑e∈Aw(e)达到最小。本文设计了解决带圈弧数限制的最小强连通图的一个O(m5 log m)的最优算法，并给出了算法的正确性证明与算法时间复杂性分析。