判断度数序列是否能构成简单图 | 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 算法，该算法使用逐步缩减的方法来确定图是否可行。我们还研究了度数数组方法、直接计数方法和排序与检查方法，每种方法都有不同的策略来验证简单图的条件。通过理解和应用这些方法，您可以快速确定是否可以从特定的度数序列创建图。选择哪种方法将取决于当前度数序列的具体规范和特性。