找出一個度序列是否能夠形成一個簡單圖 | Havel-Hakimi演算法

在圖論中，度鍊錶示頂點度的順序。確定度的順序是否可以產生一個簡單圖或一個沒有平行或自環邊的圖是至關重要的。在本部落格中，我們將探討三種解決這個問題的方法，並重點介紹Havel-Hakimi演算法。我們將詳細介紹每種技術使用的演算法，提供相應的程式碼表示和適當的標題，並展示每種方法的獨特結果。

使用的方法

• Havel−Hakimi演算法

• 排序與檢查

• #直接計數

Havel− Hakimi演算法

Havel−Hakimi演算法是一種常用的技術，用於確定一個度序列是否可以產生一個簡單圖。在達到初始情況之前，逐一消除度數。

演算法

• 使用以下演算法按降序排列學位系列。

• 如果度鏈為零，則傳回true（它會建立一個簡單的圖）。

• 如果初始度數不利或高於剩餘度數總和，則傳回false（無法形成簡單圖）。

• 從清單中減去初始度數。

• 從以下 'k' 度中減去1，其中 'k' 是被刪除的度數的值。

• 再次從步驟1-5執行。

Example

#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.

Sort & Check

的中文翻譯為：

排序與檢查

第二種方法是將度數序列依非遞減順序排序，並重複確定是否滿足直接圖的先決條件。

演算法

• 使用以下演算法將學位系列按降序排序。

• 重複這個過程，針對系列中的每個度數。

• 如果當前等級不利或數量超過可用學位的數量，則傳回false。

• 如果每個度數都通過測試，則傳回true（它建立了一個直覺的圖形）。

Example

#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'是奇數（它不能形成一個簡單圖），則傳回false。

• 測量並保持「k」中的非零度數，這些度數比左度數多。

• 如果'k'高於剩餘度數的數量，則傳回false。

• 如果所有要求都滿足（它建立一個基本圖），則傳回true。

Example

#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演算法，它採用逐步減少的方法來確定圖形的形成是否可行。我們也研究了度數組方法、直接計數方法和排序和檢查方法，每種方法都有不同的策略來驗證基本圖形的條件。透過理解和使用這些技術，您可以快速判斷圖形是否可以從特定的度序列中建立。選擇的方法將取決於當前度序列的特定規格和特徵。

以上是找出一個度序列是否能夠形成一個簡單圖 | Havel-Hakimi演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章！