Skip to content →

最小平均長閉路問題

有向グラフGの閉路について、辺の長さの平均の最小値 \(\mu\) を求める問題を、最小平均長閉路問題と言います。

手っ取り早い方法として、この問題は \(\mu\) の二分探索により、\(O(\log(W)VE)\) で解けます。ただし、\(W\) は辺の長さの取りうる幅とします。これは、すべての辺の長さを \(\mu’\) だけ引いたときに負閉路が存在することと、\(\mu < \mu’\) が同値であることから分かります。

\(F_i(v)\) を始点 \(s\)(固定)から \(v\) までの辺数iの最短歩道の長さ、\(n\) を頂点数とすると、実は以下が成り立ちます。$$\mu=\min_v \max_{0 \leq k < n} \frac{F_n(v)-F_k(v)}{n-k}$$

\(F_i(v)\) はBellman-Ford法により列挙できるので、この定理を認めると、\(\mu\) は \(O(VE)\) でも求まります。では定理を証明しましょう。

証明:すべての辺から \(\mu\) だけ引くと、\(\frac{F_n(v)-F_k(v)}{n-k}\) も \(\mu\) だけ小さくなるので、\(\mu=0\) の場合に帰着できます。長さ \(n\) の歩道には閉路が存在し、\(\mu=0\) よりそれは負閉路ではありません。従って、\(F_n(v) \geq F_k(v)\) を満たす \(k<n\) が存在します。等号が成立する \(v, k\) が存在することを言えばいいです。

平均長が 0 の閉路を \(C\) として、その閉路への \(s\) からの最短パスを \(P\)、その終点を \(w\) とします。閉路の長さが0なので、パスPのあとに何周かして \(w\) に戻ってきても、また、\(w\) への(その辺数での)最短歩道になっています。 十分な回数周ると、辺数 m \geq n と仮定できます。終点を一つ手前の頂点 w’ にしてもなお、辺数 m-1 の w’ への最短歩道になっています。終点を削ることを繰り返すと、閉路 C のある頂点 w” への辺数 n と k=n-|C| の最短歩道が得られます。従って、F_n(w”)=F_k(w”)となります(証明終)。

この定理は、最小費用流の残余ネットワークで負閉路を見つけるときに、用いるようです。

Published in データ構造

Comments

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

CAPTCHA