辺連結度の算出
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/01/24 09:59 UTC 版)
辺連結度を決定するための多項式時間アルゴリズムが存在する。ある簡単なアルゴリズムは、全てのペア (u,v) に対して、G 内のすべての辺の容量が両方向に対して 1 に定められているような、u から v への最大フローを決定するものである。グラフが k-辺連結であるための必要十分条件は、任意ペア (u,v) に対して u から v への最大フローは最小でも k であること、すなわち k が全ての (u,v) の中での最小の u-v-フローであることである。 V をグラフに含まれる頂点の数としたとき、この簡単なアルゴリズムでは O ( V 2 ) {\displaystyle O(V^{2})} 回の最大フロー問題の反復が行われ、時間 O ( V 3 ) {\displaystyle O(V^{3})} 内に解決される。したがって、この簡単なアルゴリズムの計算量は、総合すると O ( V 5 ) {\displaystyle O(V^{5})} となる。 改善されたアルゴリズムでは、任意の固定された u と、固定されていない任意の v からなる全てのペア (u,v) に対する最大フロー問題を解く。このアルゴリズムでは計算量は O ( V 4 ) {\displaystyle O(V^{4})} へと減らされており、適切なものである。なぜならば、もし容量が k より少ないカットが存在するのなら、それは u を他の頂点から切り離すからである。
※この「辺連結度の算出」の解説は、「k-辺連結グラフ」の解説の一部です。
「辺連結度の算出」を含む「k-辺連結グラフ」の記事については、「k-辺連結グラフ」の概要を参照ください。
- 辺連結度の算出のページへのリンク
