合計で n 個のノードがあります (n の最大値は 2000 です)。ここで、ノード h はすでに他のすべてのノードに接続されており、隣接行列内のノードのすべてのペアを接続するコストが与えられています。すべてのノードの次数を少なくとも 2 にする必要があります (最初はノード h に接続されているため、最初は各ノードの次数は 1 です)。
注:
(1) ノードの次数は nos です。そのノードに接続されているエッジの。
(2)h は常に 1 です。
どうすればこれを行うことができますか? 2 つのノードごとにコストのペアをソートし、すべてのノードが次数 2 に達するように最小コストのペアを選択する貪欲なアルゴリズムがありますが、これは確実に失敗します。