指定された Q 個の頂点を削除した後の、指定されたグラフの接続コンポーネントの数

Q 個の指定された頂点を削除した後、グラフ内の残りの頂点によって作成された切断されたサブグラフの数は、接続されたコンポーネントの数で表されます。個々のコンポーネント間にエッジ接続はなく、接続された各コンポーネントはエッジによって接続された頂点の集合で構成されます。 Q 頂点の削除により、一部の頂点が孤立し、接続が崩壊して新しいコンポーネントが形成される可能性があります。この方法の目的は、最終的に接続されていないサブグラフの数を決定することです。ネットワーク分析、ソーシャル ネットワーク調査、最適化手法などの多くのアプリケーションでは、接続されているコンポーネントの数についての知識が必要です。

使用説明書

• コサラジュアルゴリズム

• 行列ベースの方法

コサラジュアルゴリズム

指定された Q 個の頂点をグラフから削除した後、Kosaraju のアルゴリズムを使用してネットワーク内のリンクされたコンポーネントの数を決定します。 2 つのパスで深さ優先検索 (DFS) を使用します。最初のパスで元のグラフを調査して、各頂点の「完了時間」を取得します。 2 番目のパスでは、グラフが転置され (すべてのエッジの方向が反転され)、完了時間が最も長い頂点から開始して、変換されたグラフに DFS が適用されます。このメソッドは、変更されたグラフ内のリンクされたコンポーネントの数を決定し、プロセスで削除された Q 個の頂点を無視することにより、頂点の削除後に壊れたサブグラフの数を明らかにします。

＃＃＃アルゴリズム＃＃＃

最初の DFS チャネルの頂点を保存するには、空のスタックを作成します。
元のグラフで、最初の DFS トラバーサルを実行します。

• DFS を使用して、未探索の頂点から始めて接続された頂点のコンポーネントを探索します。

  頂点を囲むすべての頂点にアクセスすると、Mark は頂点にアクセスし、それをスタックにプッシュします。

各エッジの方向を反転して、形状を転置します。
2 番目の DFS パスでは、訪問した頂点を追跡するためのブール配列を作成します。
変更したグラフを 2 番目の DFS パスで実行します。

• スタックから各頂点を順番に削除します。

  DFS を使用して、(Q 内ではなく) アクセスまたは破棄されていない頂点の関連コンポーネント (存在しない場合) を調べます。プロセス全体を通して、マークは頂点を訪れました。

Q 個の頂点を削除した後、接続コンポーネントの数は 2 番目の DFS の呼び出し数と等しくなります。
Q 個の頂点を削除した後、このプロセスによりネットワーク内の接続コンポーネントの数が生成されます。

• ＃＃＃例＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー
行列ベースの方法

隣接行列または隣接リストは、行列ベースの方法でグラフを表現するために使用されます。次に、指定された Q 個の頂点を行列から削除します。変更されたグラフの接続コンポーネントの数は、深さ優先検索 (DFS) や幅優先検索 (BFS) などのグラフ走査アルゴリズムを使用して決定されます。再処理を防ぐために、通過した頂点を記録します。 Q 個の頂点を削除した後のグラフ内の連結成分の数は、トラバーサル メソッドが実行された回数に対応します。この方法では、さまざまなグラフ分析やネットワーク関連アプリケーションのリンク コンポーネント数を効率的に計算できます。

＃＃＃アルゴリズム＃＃＃

隣接行列または隣接リストを使用してグラフを表します。

指定された Q 頂点を行列またはリストから削除して、グラフを変更します。

• 接続されたコンポーネントの数を追跡する変数を設定します。

• 最初に、グラフ内の各頂点を繰り返し更新します。

• グラフ走査アルゴリズム (DFS または BFS) を未探索の各頂点に適用します。

• 再処理を防ぐために、トラバース中に訪問した頂点をマークします。

• 最初の頂点に関連するすべての頂点が表示されるまでトラバースを続けます。

• 見つかった相互接続された頂点の一意のセットごとに、方程式内の接続成分の数を 1 ずつ増やします。

• 更新されたグラフ内のすべての頂点にアクセスするには、必要に応じて手順 5 ～ 8 を繰り返します。

• 必要な頂点を削除した後、グラフ内の接続されていないサブグラフの総数は、接続コンポーネント数の最終値で表されます。

• ＃＃＃例＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー ＃＃＃結論は＃＃＃

  要約すると、ネットワーク解析および関連分野における重要な指標は、特定の数の頂点を削除した後にグラフに残る連結成分の数です。行列ベースの方法と Kosaraju のアルゴリズムは両方とも、この数を計算する効率的な方法を提供します。行列ベースの手法では、再設計されたグラフ上で DFS や BFS などのグラフ走査アルゴリズムを使用して、リンクされたコンポーネントを効率的に見つけます。一方、Kosaraju アルゴリズムは、2 つの走査で深さ優先検索を使用して、強く接続されたコンポーネントを特定します。どちらの方法でも、いくつかの頂点を削除した後でも信頼性の高い結果が生成され、グラフの接続性と構造特性を理解するのに役立ちます。グラフのプロパティと現在の課題の特定の要件によって、使用する方法が決まります。

以上が指定された Q 個の頂点を削除した後の、指定されたグラフの接続コンポーネントの数の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。