查找一个度序列是否能够形成一个简单图 | Havel-Hakimi算法

在图论中，度链表示顶点度的顺序。确定度的顺序是否可以产生一个简单图或者一个没有平行或自环边的图是至关重要的。在本博客中，我们将探讨三种解决这个问题的方法，重点介绍Havel-Hakimi算法。我们将详细介绍每种技术使用的算法，提供相应的代码表示和适当的标题，并展示每种方法的独特结果。

使用的方法

• Havel−Hakimi算法

• 排序和检查

• 直接计数

Havel− Hakimi算法

Havel−Hakimi算法是一种常用的技术，用于确定一个度序列是否可以生成一个简单图。在达到初始情况之前，逐个消除度数。

算法

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

• 如果度链为零，则返回true（它创建一个简单的图）。

• 如果初始度数不利或高于剩余度数之和，则返回false（无法形成简单图）。

• 从列表中减去初始度数。

• 从以下 'k' 度中减去1，其中 'k' 是被删除的度数的值。

• 再次从步骤1-5执行。

Example

#include 
#include 
#include 

using namespace std;

bool havelHakimi(vector& 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 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

排序和检查

第二种方法是将度数序列按非递减顺序排序，并重复确定是否满足直接图的先决条件。

LogoMaker

免费在线制作Logo，在几分钟内完成标志设计

下载

算法

• 使用以下算法将学位系列按降序排序。

• 重复这个过程，针对系列中的每个度数。

• 如果当前级别不利或数量超过可用学位的数量，则返回false。

• 如果每个度数都通过测试，则返回true（它创建了一个直观的图形）。

Example

#include 
#include 
#include 

using namespace std;

bool havelHakimiAlgorithm(vector& 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 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 
#include 

using namespace std;

bool directCount(vector& 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 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算法，它采用逐步减少的方法来确定图形的形成是否可行。我们还研究了度数组方法、直接计数方法和排序和检查方法，每种方法都有不同的策略来验证基本图形的条件。通过理解和使用这些技术，您可以快速判断一个图形是否可以从特定的度序列中创建。选择的方法将取决于当前度序列的特定规格和特征。