0

Skiena の本によると、これは HW ではなく、面接の準備にすぎません。

この質問を考えると、

無向グラフ G = (V, E) のマッチングは、共通の頂点を持たないエッジのセットです。完全一致は、すべての頂点が一致する一致です。

(a) 2n 個の頂点と n^2 個の辺を持つグラフ G を作成し、G が指数関数的な数の完全一致を持つようにします。

(b) 2n 個の頂点と n^2 個の辺を持つグラフ G を作成し、G が一意の完全一致を 1 つだけ持つようにします。

どうやって始めたらいいのかわからない。a は n = 3 を選んだので、頂点が 6 個、辺が 9 個あることがわかったので、それらを接続してみましたが、完全に一致するかどうかはわかりませんでした。

4

2 に答える 2

1
  1. a) の場合: 両方のパーティションがそれぞれ n 個の頂点を持つ 2n 個の頂点にわたる完全な二部グラフを取得します。これらのグラフには n! n > 2 に対して 2^n を超える完全一致。
  2. b) の場合: (n,n) 頂点にわたる完全な 2 部グラフに似たものを作成します。パーティションを A=(1,2,3,...,n) および B=(n+1,n+2,n+3,...2n) と呼びます。

    A をクリークにする。

    B のすべての頂点 n+i に対して、j<=i である A のすべての頂点 j にエッジ (n+i,j) を追加します。たとえば、頂点 n+1 のみがエッジ (n+1,1) に付随しています。頂点 n+2 は (n+2, 1) および (n+2,2) に付随します。頂点 n+3 は (n+3,1) (n+3,2) (n+3,3) に付随しています。

    これにより、一意の完全一致は強制的に {e in E | e = (n+i,i) for some i in [1;n]} (帰納法を練習するためにこれを証明してみてください)。

    A は n 個の頂点のクリークであるため、n^2/2 - n/2 個のエッジがあります。A と B の間のエッジの合計sum from 1 to nは n^2/2 + n/2 なので、合計すると
    n^2/2 - n/2 + n^2/2 + n/2 = n^2になります。エッジ。

于 2013-04-20T20:14:52.360 に答える