【摘要】 本文解决了图论的连通性理论中的一个重要的问题———以最小边集扩充一个任意有向树图为K点连通图 ,证明了该问题在算法上属于P问题 ,提出了一个时间复杂度为O(|V|3 )的有效算法DTKA ,该算法为可靠通讯网的计算机辅助设计提供了一个基础更多还原

【Abstract】 This paper studies an important problem in Connectivity Theory--augmenting a directed tree graph to a K Vertex Connected graph by adding a minimum set of edges and proves that this problem is P Problem.An effective algorithm DTKA with complexity of is given.This algorithm contributes a foundation to the Computer Aided Design of reliable communication networks.更多还原