Havel-Hakimi算法 | Baeldung中文网

1. Overview

In this tutorial, we’ll explain how to construct a graph whose nodes have the given degrees.

In particular, we’ll explain the Havel-Hakimi algorithm.

2. Problem Description

Let $D = (d(v_1), d(v_2), \ldots, d(v_n))$ be a degree sequence, where d(v_n) is the degree of the vertex v_n . The Havel-Hakimi algorithm checks if there is a simple undirected graph with vertices $\boldsymbol{v_1, v_2, \ldots, v_n}$ whose degrees are given by $\boldsymbol{D}$ .

For example, let’s say we have the degree sequence (4, 3, 3, 3, 3). The corresponding graph is:

Degree Sequence Graph

So, the Havel-Hakimi algorithm should return this graph for this input.

We can check that the degree sequence (4, 3, 3, 1, 1) doesn’t have a corresponding simple undirected graph. So, the Havel-Hakimi algorithm should indicate there’s no graph with this degree sequence.

3. The Havel-Hakimi Algorithm

This algorithm uses the Havel-Hakimi theorem.

Let $D = (d(v_1), \ldots, d(v_s), \ldots, d(v_n))$ be a degree sequence, where the degrees are in descending order and s = d(v_1) + 1 . The theorem states that there’s a graph with the degree sequence if and only if there’s a graph with the degree sequence $D' = (d(v_2) - 1, \ldots, d(v_s) - 1, \ldots, d(v_n))$ .

This gives us a recursive rule for solving the problem.

We recursively apply the Havel-Hakimi theorem to construct a graph for the given degree sequence as follows:

algorithm HavelHakimiAlgorithm(D):
    // INPUT
    //    D = a degree sequence
    // OUTPUT
    //    A graph G that realizes the degree sequence D or false if such a graph does not exist

    Initialize an empty graph G

    while D is not all zeros:
        Scan D for its largest value a
        Set i to the position of a
        Set D[i] to 0

        if v_i not in G:
            Add vertex v_i to G

        Decrease the a largest degrees in D by 1

        if D contains a negative value:
            return false

        Add to G the nodes corresponding to the decremented degrees
        Connect them to vertex v_i

    return G

First, wet initialize an empty undirected graph . Then, we repeat the below steps until the degree sequence is all zeros:

Next, we set to the position of the largest degree in the degree sequence
Then, we set to zero and add the corresponding vertex (if one doesn’t already exist) to
The third step is to decrease the largest degrees by 1. If one of the decremented degrees is less than zero, we terminate the algorithm and return false. Otherwise, we add the corresponding vertex (if one doesn’t already exist) to for each decremented degree and connect it to

The degree sequence can be unsorted. So, to find largest elements in step 3, we can scan the array times for the maximum. After finding each consecutive maximum, we move it to the beginning of the array next to the previous one and exclude its new position from future scans in this iteration. This is similar to Selection Sort.

4. Example

Let’s work out an example with the input degree sequence: (4, 3, 3, 3, 3).

First, we initialize an empty undirected graph . Then, we decrement the largest degree in the sequence by its value. We get the degree sequence (0, 3, 3, 3, 3).

Following this, we add a new vertex v_1 to the graph with no outgoing edges:

Then, we decrement the four largest degrees by one. The degree sequence is now: (0, 2, 2, 2, 2).

Consequently, we add a new vertex to the graph for each decremented value in the degree sequence and connect it to v_1 :

Then, we decrement the largest degree by its value. That’s 2 at the second position in the sequence. The result is a new sequence: (0, 0, 2, 2, 2). Since the vertex v_2 is already in the graph, we skip the addition step.

Afterward, we decrement the two largest degrees by one and get the sequence (0, 0, 1, 1, 2).

Since the decremented vertices already exist in the graph, we don’t add them. We connect them to v_2 :

We complete the graph after one more iteration:

All zeroes indicate this in the degree sequence.

5. Complexity

Let’s assume the given degree sequence $D = (d(v_1), \ldots, d(v_n))$ is graphical, which means there’s a graph whose nodes $v_1, v_2, \ldots, v_n$ have the degrees $d(v_1), d(v_2), \ldots, d(v_n)$ .

In the worst-case scenario, all vertices are connected. This means that $d(v_1) = d(v_2) = \ldots = d(v_n) = n - 1$ .

The time complexity of finding the largest element in a sequence is $\boldsymbol{O(n)}$ .

In the first iteration, the largest degree has the value n-1 . Hence, we decrement the rest n - 1 degrees after the O(n) work to find the maximum and check the while loop’s condition. We find the rest n-1 degrees in O(n(n-1)) time, which is the total complexity of the first iteration.

The second iteration is similar. The largest degree is n - 2 . We scan to determine that and decrement the rest n - 2 non-zero degrees afterward. Similarly, that takes O(n(n-2)) time.

Consequently, the total time complexity of processing the degree sequence is:

$[O(n(n-1)) + O(n(n-2)) + \ldots + O(n) = O \left( (n^2-n) + (n^2-2n) + \ldots + n \right) = O(n^3)]$

At the same time, we add vertices and edges to the graph. The complexity of constructing a graph grows asymptotically with the number of vertices plus the number of edges of the constructed graph. The number of vertices equals the length of , and the number of edges is equal to $(d(v_1) + \ldots + d(v_n)) / 2$ . Since all the vertices are connected in the worst case, the number of edges is n(n-1)/2 .

Therefore, the worst-case complexity of the Havel-Hakimi algorithm is $\boldsymbol{O(n^3 + n + n(n-1)/2) = O(n^3)}$ .

5.1. Can We Speed This Algorithm Up?

One possible optimization to this algorithm is sorting the sequence at each iteration. The sorting procedure takes $O(n \log n)$ time. As a result, we find the maximum in O(1) time in each iteration by reading the first element and decrement the rest in at most O(n) time. We make iterations (hence, sorts). The overall complexity of this approach is $O(n^2 \log n)$ .

Another optimization would be to sort the non-zero portion of the sequence in each iteration, rather than the entire sequence. The total complexity in this case is $O( \sum_{k=1}^{n}k \log k )$ = O(n^2 log n) . Although the asymptotic complexity is the same as if we sorted the entire sequence, this version will run faster in practice since it does less work.

6. Conclusion

In this article, we showed how to use the Havel-Hakimi algorithm to determine whether a degree sequence is graphical.

We explained the Havel-Hakimi algorithm. It iteratively eliminates the largest degree in the degree sequence and adds the corresponding vertex to the graph, connecting it to its neighbors.

Persistence

REST

Security