moistx https://blog.hatena.ne.jp/moistx/ Logfiles https://logfiles.hatenablog.com/ 問題 一般グラフにおいて辺数最大マッチングのサイズを求めよ。 解法 蟻本P198や組合せ最適化P271 系10.9 に載っているTutte行列を用いて最大マッチングを求めるLovaszのランダム化アルゴリズムを使う。 別の解法としては、Edmondsの辺数最大マッチングアルゴリズム(Cardinality Matching Algorithm)を投げるものがある。 Lovaszのランダム化アルゴリズムは、以下の定理に基づく。 定理(Tutte[1947]) が完全マッチングを持つための必要十分条件は、が恒等的に零ではないことである。 Tutte行列は変数を要素としている。行列の行列式は計算が難… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Flogfiles.hatenablog.com%2Fentry%2F2016%2F10%2F30%2F143025" title="LiveArchive 5874 Social Holidaying - Logfiles" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> http://chart.apis.google.com/chart?cht=tx&chl=N%20%5Ctimes%20N Hatena Blog https://hatena.blog 2016-10-30 14:30:25 rich https://logfiles.hatenablog.com/entry/2016/10/30/143025 1.0 100%