有向グラフGの閉路について、辺の長さの平均の最小値 \(\mu\) を求める問題を、最小平均長閉路問題と言います。
手っ取り早い方法として、この問題は \(\mu\) の二分探索により、\(O(\log(W)VE)\) で解けます。ただし、\(W\) は辺の長さの取りうる幅とします。これは、すべての辺の長さを \(\mu’\) だけ引いたときに負閉路が存在することと、\(\mu < \mu’\) が同値であることから分かります。
\(F_i(v)\) を始点 \(s\)（固定）から \(v\) までの辺数iの最短歩道の長さ、\(n\) を頂点数とすると、実は以下が成り立ちます。
\(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”)\)となります（証明終）。
この定理は、最小費用流の残余ネットワークで負閉路を見つけるときに、用いるようです。
Comments