Lecture
The Havel–Hakimi algorithm — an algorithm in graph theory that solves the graph realization problem. That is, it answers the following question: given a finite list of non-negative integers in non-increasing order, does there exist a simple graph whose degree sequence matches this list exactly? A simple graph contains no multiple edges or loops. A degree sequence is a list of numbers in non-increasing order indicating the number of edges incident to each vertex of the graph. If a simple graph exists for a precisely given degree sequence, the list of integers is called graphic. The Havel–Hakimi algorithm constructs a specific solution if a simple graph exists for the given degree sequence, or proves that no positive answer can be found. This construction is based on a recursive algorithm.
The Havel–Hakimi algorithm — a recursive algorithm that makes it possible to determine whether a given list of integers appears as the list of all valencies of some finite simple graph. If the answer to this question is positive, the list is called graphic.
The algorithm was proposed by Václav Havel in 1955 and rediscovered by Louis Hakimi in 1962.
The algorithm is based on the following theorem.
Let 
be a finite list of non-negative integers in non-increasing order. The list is graphic if and only if the list 
is graphic.
The described operation should be applied repeatedly, alternating with sorting the list. If at some point we obtain a list of zeros, then the initial list was graphic. If, however, a negative number appears in the list, then the initial list was not graphic.
. We repeatedly apply the theorem and the sorting. The fact that the result is a list of zeros means that the list is graphic.
. The fact that the result is a list containing negative numbers means that the list is not graphic.
Comments