判斷度數序列是否能構成簡單圖 | Havel-Hakimi 演算法

---

圖論中的度數序列表示頂點度數的順序。確定一個度數序列是否可以構成一個簡單圖（即沒有平行邊或自環的圖）至關重要。在本博文中，我們將探討解決這個問題的三種方法，重點介紹 Havel-Hakimi 演算法。我們將介紹每種方法使用的演算法，提供相應的程式碼表示以及相應的標頭檔案，並展示每種方法的獨特結果。

使用的方法

• Havel-Hakimi 演算法

• 排序與檢查

• 直接計數

Havel-Hakimi 演算法

Havel-Hakimi 演算法是一種流行的技術，用於確定度數序列是否可以構成一個簡單圖。直到達到一個基本情況，度數會一個接一個地被消除。

演算法

• 使用以下演算法將度數序列按降序排列。

• 如果度數序列為零，則返回真（它構成一個簡單圖）。

• 如果初始度數為負數或大於剩餘度數之和，則返回假（它不能構成一個簡單圖）。

• 從列表中減去初始度數。

• 從接下來的 'k' 個度數中減去 1，其中 'k' 是已刪除度數的值。

• 重複步驟 1-5。

示例

#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;
}

輸出

The sequence cannot represent a valid graph.

排序與檢查

第二種方法是將度數序列按非遞減順序排序，並反覆檢查是否滿足簡單圖的條件。

演算法

• 使用以下演算法將度數序列按降序排列。

• 對序列中的每個度數重複此過程。

• 如果當前度數為負數或大於可用度數的數量，則返回假。

• 如果每個度數都透過測試，則返回真（它構成一個簡單圖）。

示例

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool havelHakimiAlgorithm(vector<int>& degrees) {
    // Sort the degree sequence in non-increasing order
    sort(degrees.rbegin(), degrees.rend());

    while (!degrees.empty() && degrees[0] > 0) {
        int highestDegree = degrees[0];
        int n = degrees.size();

        // Check if the highest degree is greater than the number of remaining vertices
        if (highestDegree >= n) {
            return false;
        }

        // Remove the highest degree vertex
        degrees.erase(degrees.begin());

        // Decrease the degrees of its neighbors
        for (int i = 0; i < highestDegree; ++i) {
            degrees[i]--;
        }

        // Sort the degree sequence again
        sort(degrees.rbegin(), degrees.rend());
    }

    // If all degrees are zero, the degree sequence can form a simple graph
    return degrees.empty();
}

int main() {
    // Example degree sequence
    vector<int> degrees = {3, 3, 2, 2, 1};

    // Check if the degree sequence can form a simple graph
    bool canFormGraph = havelHakimiAlgorithm(degrees);

    if (canFormGraph) {
        cout << "The degree sequence can form a simple graph." << endl;
    } else {
        cout << "The degree sequence cannot form a simple graph." << endl;
    }

    return 0;
}

輸出

The degree sequence cannot form a simple graph.

直接計數

第四種方法只是透過計算滿足預定條件的度數的數量來確定該序列是否可以表示為簡單圖。

演算法

• 確定大於或等於 0 的度數的數量，並將結果儲存在 'n' 中。

• 如果 'n' 是奇數，則返回假（它不能構成一個簡單圖）。

• 測量並儲存在 'k' 中，有多少個非零度數大於剩餘度數的數量。

• 如果 'k' 大於剩餘度數的數量，則返回假。

• 如果所有條件都滿足，則返回真（它構成一個簡單圖）。

示例

#include <iostream>
#include <vector>

using namespace std;

bool directCount(vector<int>& degrees) {
    int n = 0;
    int k = 0;

    for (int degree : degrees) {
        if (degree >= 0) {
            n++;
            if (degree > degrees.size() - n) {
                k++;
            }
        }
    }

    return (n % 2 == 0) && (k <= n);
}

int main() {
    // Test the directCount function
    vector<int> degrees = {3, 1, 2, 3, 1, 0};
    bool result = directCount(degrees);

    if (result) {
        cout << "The sequence can represent a valid graph." << endl;
    } else {
        cout << "The sequence cannot represent a valid graph." << endl;
    }

    return 0;
}

輸出

The sequence can represent a valid graph.

結論

在這篇文章中，我們探討了三種不同的方法來確定特定的度數序列是否可以構成一個簡單圖。我們討論了 Havel-Hakimi 演算法，該演算法使用逐步縮減的方法來確定圖是否可行。我們還研究了度數陣列方法、直接計數方法和排序與檢查方法，每種方法都有不同的策略來驗證簡單圖的條件。透過理解和應用這些方法，您可以快速確定是否可以從特定的度數序列建立圖。選擇哪種方法將取決於當前度數序列的具體規範和特性。