Havel–Hakimi algorithm

The Havel–Hakimi algorithm is an algorithm in graph theory solving the graph realization problem, i.e. the question if there exists for a finite list of nonnegative integers a simple graph such that its degree sequence is exactly this list. For a positive answer the list of integers is called graphic. The algorithm constructs a special solution if one exists or proves that one cannot find a positive answer. This construction is based on a recursive algorithm. The algorithm was published by Havel (1955), and later by Hakimi (1962).

The algorithm

The algorithm is based on the following theorem.

Let S=(d_1,\dots,d_n) be a finite list of nonnegative integers that is nonincreasing. List S is graphic if and only if the finite list S'=(d_2-1,d_3-1,\dots,d_{d_1+1}-1,d_{d_1+2},\dots,d_n) has nonnegative integers and is graphic.

If the given list S graphic then the theorem will be applied at most n-1 times setting in each further step S:=S'. Note that it can be necessary to sort this list again. This process ends when the whole list S' consists of zeros. In each step of the algorithm one constructs the edges of a graph with vertices v_1,\cdots,v_n, i.e. if it is possible to reduce the list S to S', then we add edges \{v_1,v_2\},\{v_1,v_3\},\cdots,\{v_1,v_{d_1+1}\}. When the list S cannot be reduced to a list S' of nonnegative integers in any step of this approach, the theorem proves that the list S from the beginning is not graphic.

See also

References

    This article is issued from Wikipedia - version of the Thursday, February 18, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.