最小カットについて

先ほどの記事(SRM 653 div1 med:Singing - mayoko’s diary)で

①

・頂点がたくさんある。それを赤と青に塗り分ける。全部の頂点を必ず赤か青に塗らなくてはいけない
・必ず赤色に塗らなくてはいけない頂点(Sとする)と青色に塗らなくてはいけない頂点(Tとする)が存在する
・「Xが赤で、Yが青の時にZ円の罰金がかかる」という制約が沢山ある
・罰金の最小値は？

という問題は
②

・「Xが赤で、Yが青の時にZ円の罰金がかかる」ならX->Yに容量Zの辺を貼る
・SからTに最大流
・流せた量が答え

とすることで解けるとしています。

というのがなぜなのかがよくわからないとしていましたが,理由がわかった気がするので証明してみたいと思います。
まず証明しなければならないことをはっきりさせます。①の問題で決定しなければならないことは「それぞれの頂点を何色で塗るか」ということであり,②の問題で決定しなければならないことは(最小カットで考えると)「どの辺を取り除くことでSとTがカットされるか」ということです。

②の問題は要するに辺を選べば良いだけです。主張では①の答えと②の最小カットは一致するとしているので,次の予想が得られます。

予想1:
②で最小カットとして選ばれる辺と,①においてその辺で結ばれている赤-青対応は一致している。

例えばこんな感じです。

水色の辺が最小カットとして選ばれる辺を表しており,それに対応して赤,青が決定しているのがわかります(a->bのa側が赤でb側が青)。
じゃあこれを証明しましょうかね。。。と思ったらいきなり反例！？

(水色の辺が最小カットとして選ばれた辺。このように辺が選ばれてしまうと,1は何色にすればよいのかわからない(=予想で主張しているような赤-青対応が決定できない))
・・・と思いきや,これは大丈夫です。最小カットを考えるときの前提としてすべての辺の重みは非負になっています。そうであるならば,最小カットとして選択されるものとして,余計な辺が選ばれすぎています(s->1の辺か1->tおよび1->2の辺はいらない)。

ここからわかることは,予想に示したように辺と赤-青対応が一致するためには,一つの頂点から,最小カットで選ばれる辺が同時に入ったり出て行ったりしてはいけないということです。もしこのような頂点があると,上に示したようなオレンジ色の点が存在して赤-青対応がなくなってしまいますからね。

ということで,示すべきことはこれです。

予想2:
最小カットを考えた時,選ばれた辺は以下の性質を満たす。
各々の頂点について,辺は出て行くか入ってくるかのどちらか一方しか存在しない。

これを簡単な例で背理法で証明します。

頂点pに注目します。もし予想2が成り立たなかったとすると,この頂点について次のどちらかが成り立ちます。
①a->p,b->pのすべてが最小カットの辺として選ばれ,かつp->c,p->d,p->eのどれかも選ばれる。
②a->p,b->pの少なくとも1つが最小カットの辺として選ばれ,かつp->c,p->d,p->eのどれかも選ばれる。
①はありえません。上で見たように,a->pとb->pの両方を封鎖したならpの後ろで更に封鎖する必要はないからです(最小カットの最小性に反する)。
また,②もありえません。なぜなら,一度pで封鎖できなかった以上,tにたどり着くまでに結局pからtまでのルートを封鎖しなければなりません。しかし,その封鎖の過程の中で,a->pやb->pの封鎖はなんの影響もありません。すなわち,余計な辺を最小カットの辺として選んでいることになるのでやはり最小性に反します。
よって,予想2は正しいことが示されました。
これがわかれば予想1は簡単に示せます。以上によってもともとの目的のことが示されました。お疲れ様です。

グラフを書くツールを使ったことがなかったのでこの記事を書く過程で初めて探してみたんですが,Graphvizっていうのとても便利ですね。