寻找独立路径问题的一个关键顶点和一条关键弧

通信网络中不同的顶点和弧在多径路由中的作用具有差异性,为此,提出了独立路径问题的关键顶点和关键弧问题.若由定义来求关键顶点和关键弧,算法效率太低.对于弧独立路径数问题,文中引入关键度的概念来量化每个顶点和每条弧的关键程度,发现并证明了顶点的关键度与出度的关系,并由此设计了求关键顶点的算法.根据独立路径数问题本身的特点,提出了求弧独立路径数问题关键弧及顶点独立路径数问题关键顶点和关键弧的方法.对于K-弧独立路径问题,文中利用网络流理论构造替代路径来寻找关键顶点和关键弧.通过变换网络结构,用相似的方法求K-顶点独立路径问题的关键顶点和关键弧.