2

重み付けされた無向2部グラフの最大重み付けマッチングを計算するためのさまざまなアルゴリズムを知っています(つまり、割り当ての問題)。

たとえば...ハンガリーアルゴリズム、ベルマンフォード法、またはブロッサムアルゴリズム(一般的な、つまり2部グラフではない)でさえ機能します。

ただし、2部グラフのエッジに重みが付けられ、方向付けられている場合、最大の重み付きマッチングを計算するにはどうすればよいですか?

前述のアルゴリズムのいずれかを適用できるように、グラフを無向にするための、多項式の複雑さを備えたアルゴリズムまたは事前の変換へのポインターをいただければ幸いです。

編集:マッチングはエッジの重みを最大化する必要があることに注意してください。そのため、有向エッジがあると違いが生じます(A->BはB->Aとはまったく異なる重みを持つ可能性があります)。

確かに、カーディナリティを最大化する場合、有向エッジは違いをもたらさず、カーディナリティを最大化するためによく知られたアルゴリズムのいずれかを適用できます:ホップクロフト-カープ、最大ネットワークフロー...。

編集2マッチングは通常無向グラフに適用される用語なので、この質問でマッチングすることによって正確に何を意味するのかを明確にしましょう:開始頂点または終了頂点を共有しない有向エッジのセット。より正式には、U->VとU'-> V'がマッチングの一部である場合、V /=U'とV'/=Uです。

4

1 に答える 1

2

dfbのコメントは正しいです。任意の2つの頂点A、Bについて、2つのエッジABとBAのうち安い方を破棄できます。

証拠はワンライナーです:

定理:最大マッチングMには、任意の2つの頂点A、BのABとBAの安価なエッジが含まれることはありません。

証明: Mを最大マッチングとします。ABがMであり、BAよりも安いとします。M'= M-{AB}+{BA}を定義します。M'は明らかに一致していますが、より高価です。これは、Mが最大一致であるという仮定と矛盾します。

于 2013-02-12T02:52:34.993 に答える