次数列が単純なグラフを形成するかどうかを調べる | Havel-Hakimi アルゴリズム

グラフ理論では、次数チェーンは頂点の次数の順序を表します。次数によって単純なグラフが作成できるか、それとも平行エッジや自己ループ エッジのないグラフが作成できるかを判断することが重要です。このブログでは、Havel-Hakimi アルゴリズムに焦点を当てて、この問題を解決する 3 つの方法を検討します。各手法で使用されるアルゴリズムを詳しく説明し、対応するコード表現と適切なタイトルを提供し、各アプローチの独自の結果を示します。

使用説明書

• Havel-Hakimi アルゴリズム

• 分類とチェック

• 直接カウント

Havel- ハキミアルゴリズム

Havel-Hakimi アルゴリズムは、次数シーケンスが単純なグラフを生成できるかどうかを判断するために一般的に使用される手法です。初期状況に到達するまで次数を 1 つずつ消去します。

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

次のアルゴリズムを使用して、次数シリーズを降順に並べ替えます。
次数チェーンが 0 の場合は true を返します (単純なグラフが作成されます)。
初期次数が不利な場合、または残りの次数の合計より高い場合は false を返します (単純なグラフを作成できません)。
リストから最初の学位を減算します。
次の 'k' 度から 1 を減算します。ここで、「k」は削除される度数の値です。
手順 1 ～ 5 を再度実行します。

• ＃＃＃例＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー
Sort & Check

の中国語訳:

Sort & Check

2 番目の方法は、次数シーケンスを非降順でソートし、直接グラフの前提条件が満たされているかどうかを繰り返し判断することです。

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

次のアルゴリズムを使用して、次数シリーズを降順に並べ替えます。

シリーズの学位ごとにこのプロセスを繰り返します。

• 現在のレベルが不利であるか、数値が利用可能な度数を超えている場合は false を返します。

• 各度がテストに合格した場合は true を返します (直感的なグラフが作成されます)。

• 例

  #include <iostream>
  #include <algorithm>
  #include <vector>
  
  using namespace std;
  
  bool havelHakimi(vector<int>& degrees) {
      sort(degrees.rbegin(), degrees.rend()); // Sort in non-increasing order
  
      while (!degrees.empty() && degrees.front() > 0) {
          int firstDegree = degrees.front();
          degrees.erase(degrees.begin()); // Remove the first degree
  
          if (firstDegree > degrees.size()) {
              return false;
          }
  
          for (int i = 0; i < firstDegree; ++i) {
              degrees[i]--;
          }
  
          sort(degrees.rbegin(), degrees.rend()); // Re-sort the sequence
      }
  
      return degrees.empty(); // Return true if the sequence is empty
  }
  
  int main() {
      // Test the havelHakimi function
      vector<int> degrees = {3, 1, 2, 3, 1, 0};
      bool result = havelHakimi(degrees);
  
      if (result) {
          cout << "The sequence can represent a valid graph." << endl;
      } else {
          cout << "The sequence cannot represent a valid graph." << endl;
      }
  
      return 0;
  }
  
  

  ＃＃＃出力＃＃＃ リーリー
直接カウント

• 4 番目の方法は、単純に所定の条件を満たすレベルの数を測定し、数列が単純なグラフとして表現できるかどうかを判断します。

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

0 以上の度数を決定し、結果を「n」に保存します。

'n' が奇数の場合 (単純なグラフを形成しない場合)、false を返します。

「k」の左より大きい非ゼロ度を測定して維持します。

• 「k」が残りの次数より大きい場合は、false を返します。

• すべての要件が満たされる場合は true を返します (基本グラフが作成されます)。

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

  この記事では、特定の次数シーケンスが単純なグラフを形成するかどうかを判断する 3 つの異なる方法を検討します。段階的削減法を使用してグラフの形成が可能かどうかを判断する、Havel-Hakimi アルゴリズムについて説明しました。また、次数配列メソッド、直接カウントメソッド、ソートアンドチェックメソッドも検討しました。それぞれが基本グラフの条件を検証するための異なる戦略を備えています。これらのテクニックを理解し、使用することで、特定の次数シーケンスからグラフを作成できるかどうかをすぐに判断できます。選択される方法は、現在の学位シーケンスの特定の仕様と特性によって異なります。

以上が次数列が単純なグラフを形成するかどうかを調べる | Havel-Hakimi アルゴリズムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。