Linear and Discrete Optimization の第六週目のメモ。 #linearopt 今回は二部グラフの最大マッチング問題の話と、重み付き有効グラフにおいてある頂点からの最短パスを計算する話。 この二つがどう関係するのかはイマイチよくわかってない……
* 二部グラフの最大マッチング (Maximum cardinality bipartite matching) 問題の話
マッチングMに関する augmenting path を定義して、(二部グラフとは限らない)任意の無向グラフで、マッチングMのサイズが最大であることと、Mに関する augmenting path が存在しないことが同値であることを証明。
M に関する augmenting path を見つけられれば、そこからより大きなM'を計算可能であるので、augmenting pathを探せばよい。これは二部グラフの場合、うまく有効グラフに変換して、BFSを使えば探せる。
* 重み付き有効グラフにおいてある頂点からの最短パスを計算する話
重み(=距離)が負になるようなサイクルがない場合には、Bellman-Fordのアルゴリズム というので解けることを証明(そういえば、Bellman-Fordのアルゴリズムって、difference logic の決定手続きで使うやつだよね)。また、同じ条件がなり立つ場合には、各頂点に対してポテンシャルとして距離の下界を表す変数を定義し、これを最大化するようにすることで、LPとして解くことが出来る。
第一週目の感想
https://plus.google.com/100215187201873478127/posts/LhApNmsFT2B
第二週目の感想
https://plus.google.com/100215187201873478127/posts/WcTEf8nmxHs
第三週目の感想
https://plus.google.com/100215187201873478127/posts/2B5nsPfjGx6
第四週目の感想
https://plus.google.com/100215187201873478127/posts/JKJTRLZDNzm
第五週目の感想
https://plus.google.com/100215187201873478127/posts/X82uh1odHTm