また、このウィキペディア
しかし、最小パスカバーを解決するために最大マッチング問題を解決する方法を理解できません。解が nm であることはわかっています。ここで、n は G の頂点の数、m は最大一致ですが、理由がわかりません。
2 に答える
2
この事実の直感的な説明を次に示します (厳密な証明ではありません)。パス カバー内の各パスを見てみましょう。パスの最初の頂点を除くすべての頂点には、一意の先行があります。さらに、各頂点には 1 つのサクセサーがあります (各パスの最後のものを除く)。そのため、各頂点はその前の頂点と一致していると言えます。頂点が何にも一致しない場合、それは何らかのパスの最初の頂点です。そのため、パスの数は一致しない頂点の数と同じです (各パスには最初の頂点が 1 つだけあります)。不一致の頂点の数は、明らかに、頂点の総数から一致した頂点の数を引いたものに等しくなります。n - mそれが式を得る方法です。最大マッチングのサイズよりも少ないパスを取得することはできません (そうでない場合n - m1 < n - m=> m1 > m=>mは最大値ではありません)。同時に、n - mパスを明示的に使用してソリューションを構築できます。
于 2014-12-18T16:10:32.187 に答える