Algorithme de Havel-Hakimi

Graphe solution d'une liste à 7 éléments tous égaux à 4.

En théorie des graphes, l'algorithme de Havel-Hakimi est un algorithme résolvant le problème de la réalisation d'un graphe, c'est-à-dire, étant donné une liste d'entiers positifs ou nuls, déterminer s'il existe un graphe simple dont les degrés sont exactement cette liste. Si oui, la liste est dite graphique. L'algorithme construit un graphe solution s'il en existe un, ou prouve qu'il n'existe aucun. Cette construction est basée sur un algorithme récursif, publié par Havel en 1955 puis Hakimi en 1962.

L'algorithme

L'algorithme est basé sur le théorème suivant.

Soit $S=(d_1,\dots ,d_n)$ une liste finie et décroissante d'entiers positifs ou nuls. Alors $S$ est graphique si et seulement si la liste $S^{\prime }=(d_2-1,d_3-1,\dots ,d_{d_1+1}-1,d_{d_1+2},\dots ,d_n)$ ne contient que des nombres positifs ou nuls, et est graphique.

En effet, si $S^{\prime }$ est graphique, alors il existe un graphe dont les degrés des sommets sont $S^{\prime }$. En rajoutant à ce graphe un sommet relié aux $d_1$ premiers sommets, on aboutit à un graphe dont les degrés sont $S$.

Inversement, s'il existe un graphe dont les degrés sont $S$, soit $G$ un tel graphe et $x$ un sommet de degré maximal dans $G$. On supposera aussi qu'on a choisi $G$ et $x$ de telle sorte que la somme des degrés des voisins de $x$ soit maximale (c'est possible car il n'y a qu'un nombre fini de graphes de cardinal fixé). Supposons par l'absurde qu'il existe un sommet $y$, non relié à $x$, et de degré strictement supérieur à un voisin quelconque $z$ de $x$. On sait alors qu'il existerait un sommet $t$ (différent des trois autres) tel que $y$ est relié à $t$ mais pas $z$. On peut alors échanger les arêtes $(y,t)$ et $(x,z)$ en $(x,y)$ et $(z,t)$, la liste des degrés obtenus ne changerait alors pas, alors que la somme des degrés des voisins de $x$ a augmenté strictement, ce qui est absurde. Ainsi, éventuellement en réordonnant les sommets (en cas d'égalité), on peut trouver $G$ dont les degrés correspondent à la liste $S$ et tel que les voisins de $x$ sont exactement les premiers sommets de la liste. Le graphe $G^{\prime }$ obtenu alors en supprimant $x$ a des degrés correspondant à la liste $S^{\prime }$.

Ainsi, pour une liste de $S$, on devra appliquer au plus $n-1$ fois l'algorithme en remplaçant simplement $S$ par $S^{\prime }$. Notons qu'il peut-être nécessaire de réordonner cette liste à nouveau au cours de l'algorithme. La liste est graphique si on ne rencontre aucun nombre négatif dans $S$ au cours de l'algorithme.

Exemple d'implémentation en Python

def graphique(liste):
    """Renvoie True si liste est une liste de degrés d'un graphe, et False sinon."""
    li = sorted(liste)
    while li != []:
        d = li.pop()
        if d > len(li):
            return False
        for k in range(len(li)-d, len(li)):
            li[k] -= 1
            if li[k] < 0:
                return False
        li.sort()
    return True