対称二部マッチングの整数のランダムなリストと

Question

スタートは、言う：

list = [2,5,7,1,3] 

は目的：最大限リスト内の別のエントリでリスト内の各エントリをペア。 log_base_2（（m + n）/ gcd（m、n））が整数でない場合は、値（m、n）のエントリを照合できます。私。 （7,3）は有効な照合であり、（1,3）は一致しません。

A=B=list=[2,5,7,1,3] 

し、次いで二部マッチング問題として扱い：

は私が最初のリストと同等の二つのリスト、AとBを生成することですこれを実行する1つの方法をかなり確信していますA [m]がB [n]と一致する場合、A [n]もB [m]と一致しなければならないという追加の制約（上記の一致制約に加えて）。結果として得られるフローネットワークの視覚化が水平に対称である（すなわち、ソース - シンク軸に沿って、したがってタイトル）ことが想像される。

私はMaxFlowを使用して二部構成のマッチング問題を解決する方法を知っていますが、この最後の太字の制約を実装する方法を理解することはできません。どんな助けも非常に役に立つでしょう。

Answer 1

追加の制約は、（A[m]が一致する場合B[n]その後、A[n]もB[m]と一致する必要があります）根本問題の性質が変化します。実際には、その制約は入力グラフの双対性を破壊し、実際にはそれを一般的な無向グラフに変えます。したがって、あなたが探しているのは、一般的なグラフで最大一致を見つけるためのアルゴリズムです。

Edmonds Algorithmを使用して問題を解決することができます。これは、2つの場合の最大フロー解法とは異なります（ただし、拡大パスの概念を使用します）。このアルゴリズムは、バイパートマッチングを容易に解決することができるという事実を利用し、奇数サイクルを崩壊させることによって入力グラフをバイパータイトに変える方法を試みている（グラフは、奇数サイクルがなく、グラフ中の奇数サイクルの数は、入力グラフが2部構成から遠くなる程度を測定する）。アルゴリズムの正確な動作の詳細については、上のリンクで詳しく説明しています。

ここにはa Python implementation of the algorithmです。このアルゴリズムは、スパースグラフではかなり効率的ですが、密集グラフでは効率的ではありません。グラフの密度は、m, nの項目ペアの数が2の累乗である(m + n)/gcd(m, n)を満たすかどうかによって決まります。ほとんどのペアが条件を満たす場合、ランタイムは約O(n^4)になります。一般にランタイムはO(E•V^2)です。

Answer 2

これはバイパータイトのマッチングの問題ではなく、むしろ「バイパータイルではないマッチング」のより一般的なクラスです。 Edmonds/'Blossom' algorithmは、溶液（Snakile's answer pointed this out）を提供する。

一部が周囲に検索した後、私は私が使用して巻き取っエドモンズ/「ブロッサム」アルゴリズムの簡単な実装が見つかりました： https://www.python.org/doc/essays/graphs/

：それはグイド・ヴァンロッサムの非常に直感的なグラフ構造を利用 http://code.activestate.com/recipes/221251-maximum-cardinality-matching-in-general-graphs/

を将来の読者には最高の運があります！