グラフ内の他のすべてのノードから切断されているノードの数を最大化するには、最も接続されていないノードを見つけて分離する必要があります。この戦略では、最も低い次数 (最も接続度の低い) のノードを、これらのノードが見つからなくなるまで繰り返し削除する必要があります。この結果、相互に分離されたノードの最大数が提供され、グラフ内のさまざまなコンポーネントが常に分離されます。この戦略では、残りのノードの関連性が無視できる程度になるようにすることで、他のノードに関連しないグラフ内のノードの数を増やします。
貪欲な方法
最大独立集合 (MIS) 法
貪欲な方法では、他のノードに接続されていないグラフ内のノードの数を最大化するために、最も低い次数 (最も接続されていない) ノードを繰り返し削除します。このプロセスは、そのようなノードがなくなるまで続行されます。最も接続の少ないノードを繰り返し削除して孤立ノードの数を増やし、グラフ内に切断されたコンポーネントを作成します。貪欲なアプローチでは、切断されたノードの正確な最大数が常に保証されない可能性があるため、ノードが削除される順序によって異なる可能性があることに留意することが重要です。それにもかかわらず、グラフ内の未接続のノードの数を増やすためのシンプルで効果的な戦略が提供されます。
###アルゴリズム###
a. 現在のグラフ G で、次数が最も低い (接続が最も低い) ノードを特定します。
b. 同じ最小次数を持つノードが複数ある場合は、任意のノードを選択します。
c. 選択したノードをグラフ G から削除した後、切断ノード リストに追加します。
最低次数のノードがなくなるまで検索を続けます。
###例### リーリー ###出力### リーリー
MIS にノードを追加できなくなるまで、次の手順を繰り返します。
b.選択したノードを MIS セットに含めます。
###例### リーリー ###出力### リーリー ###結論は###
グリーディ法と最大独立集合 (MIS) 法という 2 つのアクティブな方法を使用して、グラフ内の相互に接続されていないノードの数を最大化します。貪欲な方法には、切断されたコンポーネントを作成し、最低次数のノードを繰り返し削除し、孤立したノードの数を増やすことが含まれます。シンプルではありますが、常に正確な最大数が保証されるとは限りません。一方、MIS 手法は、隣接する接続を持たないノードの実現可能な最大のサブセットを特定することによって、ノードを相互に分離しようとします。 MIS 方法は、独立したセットにノードを追加し、グラフからノードとその隣接ノードを削除することを繰り返して、切断されたノードの最大数に系統的に到達する、より信頼性の高い方法を提供します。以上がグラフ内の他のすべてのノードから切断されているノードの数を最大化します。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。