1

合計で n 個のノードがあります (n の最大値は 2000 です)。ここで、ノード h はすでに他のすべてのノードに接続されており、隣接行列内のノードのすべてのペアを接続するコストが与えられています。すべてのノードの次数を少なくとも 2 にする必要があります (最初はノード h に接続されているため、最初は各ノードの次数は 1 です)。

:
(1) ノードの次数は nos です。そのノードに接続されているエッジの。
(2)h は常に 1 です。

どうすればこれを行うことができますか? 2 つのノードごとにコストのペアをソートし、すべてのノードが次数 2 に達するように最小コストのペアを選択する貪欲なアルゴリズムがありますが、これは確実に失敗します。

4

1 に答える 1

1

hを無視して、各頂点の次数が1以上になるようにエッジを追加することと考えることができます。頂点の数が偶数の場合、これは単純に完全に一致します。それ以外の場合は、完全一致に加えて、1つの頂点が他の1つの頂点に接続されます(その頂点の次数が2になります)。余分な頂点のすべての可能性を試し、 n個の完全一致問題を解くことで、これらを解決できます。

于 2013-02-12T12:39:52.247 に答える