The Havel–Hakimi algorithm is an algorithm in graph theory solving the graph realization problem. That is, it answers the following question: Given a finite list of nonnegative integers in non-increasing order, is there a simple graph such that its degree sequence is exactly this list? A simple graph contains no double edges or loops. The degree sequence is a list of numbers in nonincreasing order indicating the number of edges incident to each vertex in the graph. If a simple graph exists for exactly the given degree sequence, the list of integers is called graphic. The Havel–Hakimi algorithm constructs a special solution if a simple graph for the given degree sequence 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).
Algorithm The Havel–Hakimi algorithm is based on the following result. Theorem. Let A = ( s , t 1 , . . . , t s , d 1 , . . . , d n ) {\displaystyle A=(s,t_{1},...,t_{s},d_{1},...,d_{n})} be a finite list of nonnegative integers that is nonincreasing. Let A ′ = ( t 1 − 1 , . . . , t s − 1 , d 1 , . . . , d n ) {\displaystyle A'=(t_{1}-1,...,t_{s}-1,d_{1},...,d_{n})} be a second finite list of nonnegative integers that is rearranged to be nonincreasing. List A {\displaystyle A} is graphic if and only if list A ′ {\displaystyle A'} is graphic. If the given list A {\displaystyle A} is graphic, then the theorem will be applied at most n − 1 {\displaystyle n-1} times setting in each further step A := A ′ {\displaystyle A:=A'} . Note that it can be necessary to sort this list again. This process ends when the whole list A ′ {\displaystyle A'} consists of zeros. Let G {\displaystyle G} be a simple graph with the degree sequence A {\displaystyle A} : Let the vertex S {\displaystyle S} have degree s {\displaystyle s} ; let the vertices T 1 , . . . , T s {\displaystyle T_{1},...,T_{s}} have respective degrees t 1 , . . . , t s {\displaystyle t_{1},...,t_{s}} ; let the vertices D 1 , . . . , D n {\displaystyle D_{1},...,D_{n}} have respective degrees d 1 , . . . , d n {\displaystyle d_{1},...,d_{n}} . In each step of the algorithm, one constructs the edges of a graph with vertices T 1 , . . . , T s {\displaystyle T_{1},...,T_{s}} —i.e., if it is possible to reduce the list A {\displaystyle A} to A ′ {\displaystyle A'} , then we add edges { S , T 1 } , { S , T 2 } , ⋯ , { S , T s } {\displaystyle \{S,T_{1}\},\{S,T_{2}\},\cdots ,\{S,T_{s}\}} . When the list A {\displaystyle A} cannot be reduced to a list A ′ {\displaystyle A'} of nonnegative integers in any step of this approach, the theorem proves that the list A {\displaystyle A} from the beginning is not graphic.
… excerpt ends here. Continue reading the full article.
