Algorithme de Havel-Hakimi

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

Soit ${\displaystyle S=(d_{1},\dots ,d_{n})}$ une liste finie et décroissante d'entiers positifs ou nuls. Alors ${\displaystyle S}$ est graphique si et seulement si la liste ${\displaystyle S'=(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 ${\displaystyle S'}$ est graphique, alors il existe un graphe dont les degrés des sommets sont ${\displaystyle S'}$. En rajoutant à ce graphe un sommet relié aux ${\displaystyle d_{1}}$ premiers sommets, on aboutit à un graphe dont les degrés sont ${\displaystyle S}$.

Inversement, s'il existe un graphe dont les degrés sont ${\displaystyle S}$, soit ${\displaystyle G}$ un tel graphe et ${\displaystyle x}$ un sommet de degré maximal dans ${\displaystyle G}$. On supposera aussi qu'on a choisi ${\displaystyle G}$ et ${\displaystyle x}$ de telle sorte que la somme des degrés des voisins de ${\displaystyle 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 ${\displaystyle y}$, non relié à ${\displaystyle x}$, et de degré strictement supérieur à un voisin quelconque ${\displaystyle z}$ de ${\displaystyle x}$. On sait alors qu'il existerait un sommet ${\displaystyle t}$ (différent des trois autres) tel que ${\displaystyle y}$ est relié à ${\displaystyle t}$ mais pas ${\displaystyle z}$. On peut alors échanger les arêtes ${\displaystyle (y,t)}$ et ${\displaystyle (x,z)}$ en ${\displaystyle (x,y)}$ et ${\displaystyle (z,t)}$, la liste des degrés obtenus ne changerait alors pas, alors que la somme des degrés des voisins de ${\displaystyle x}$ a augmenté strictement, ce qui est absurde. Ainsi, éventuellement en réordonnant les sommets (en cas d'égalité), on peut trouver ${\displaystyle G}$ dont les degrés correspondent à la liste ${\displaystyle S}$ et tel que les voisins de ${\displaystyle x}$ sont exactement les premiers sommets de la liste. Le graphe ${\displaystyle G'}$ obtenu alors en supprimant ${\displaystyle x}$ a des degrés correspondant à la liste ${\displaystyle S'}$.

Ainsi, pour une liste de ${\displaystyle S}$, on devra appliquer au plus ${\displaystyle n-1}$ fois l'algorithme en remplaçant simplement ${\displaystyle S}$ par ${\displaystyle S'}$. 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 ${\displaystyle S}$ au cours de l'algorithme.

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Havel–Hakimi algorithm » (voir la liste des auteurs).