Find whether a degree sequence forms a simple graph | Havel-Hakimi algorithm

In graph theory, degree chain represents the order of vertex degrees. It is crucial to determine whether the order of degrees can produce a simple graph or a graph without parallel or self-looping edges. In this blog, we will explore three methods to solve this problem, focusing on the Havel-Hakimi algorithm. We will detail the algorithms used by each technique, provide corresponding code representations and appropriate titles, and demonstrate the unique results of each approach.

usage instructions

• Havel−Hakimi algorithm

• Sort and Check

• Direct counting

Havel− Hakimi algorithm

Havel−Hakimi algorithm is a commonly used technique for determining whether a degree sequence can generate a simple graph. Eliminate degrees one by one until the initial situation is reached.

algorithm

• Use the following algorithm to sort degree series in descending order.

• Returns true if the degree chain is zero (it creates a simple graph).

• If the initial degree is unfavorable or higher than the sum of the remaining degrees, return false (cannot form a simple graph).

• Subtract the initial degree from the list.

• Subtract 1 from the following 'k' degrees, where 'k' is the value of the degree being removed.

• Perform steps 1-5 again.

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

Output

The sequence cannot represent a valid graph.

The Chinese translation of

Sort & Check

is:

Sort & Check

The second method is to sort the degree sequence in non-decreasing order and repeatedly determine whether the prerequisites for a direct graph are met.

algorithm

• Use the following algorithm to sort degree series in descending order.

• Repeat this process for each degree in the series.

• Returns false if the current level is unfavorable or the number exceeds the number of available degrees.

• Returns true if each degree passes the test (it creates an intuitive graph).

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

Output

The degree sequence cannot form a simple graph.

Direct counting

The fourth method simply measures the number of levels that meet predetermined conditions to determine whether the sequence can be represented as a simple graph.

algorithm

• Determine the number of degrees greater than or equal to 0 and save the result in 'n'.

• If 'n' is an odd number (it does not form a simple graph), return false.

• Measures and maintains the non-zero degrees in "k" that are more than the left.

• If 'k' is higher than the number of remaining degrees, return false.

• Returns true if all requirements are met (it creates a base graph).

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

Output

The sequence can represent a valid graph.

in conclusion

In this article, we explore three different ways to determine whether a specific degree sequence forms a simple graph. We discussed the Havel−Hakimi algorithm, which uses a stepwise reduction method to determine whether the formation of a graph is feasible. We also looked at degree array methods, direct counting methods, and sort-and-check methods, each with different strategies for validating conditions on basic graphs. By understanding and using these techniques, you can quickly determine whether a graph can be created from a specific sequence of degrees. The method chosen will depend on the specific specifications and characteristics of the current degree sequence.

The above is the detailed content of Find whether a degree sequence forms a simple graph | Havel-Hakimi algorithm. For more information, please follow other related articles on the PHP Chinese website!