Probleme – Quelles suites de degrés sont réalisables ?

Exercice · niveau 3 (difficile) · informatique (MP2I/MPI), chapitre 13 — Le modèle des graphes

Énoncé

Le lemme des poignées de main donne une condition nécessaire. On cherche la condition exacte.

Donner deux conditions nécessaires pour qu'une suite $(d_{1} \geq d_{2} \geq \dots \geq d_{n})$ soit la suite des degrés d'un graphe non orienté simple.
Démontrer le théorème de Havel-Hakimi : la suite est réalisable si et seulement si la suite obtenue en retirant $d_{1}$ et en diminuant de $1$ les $d_{1}$ termes suivants l'est.
En déduire un algorithme, et sa complexité.
Éprouver sur des exemples.

Corrigé

1. Deux conditions nécessaires.

$\sum_{i} d_{i}$ est paire — lemme des poignées de main.
$d_{1} \leq n - 1$ : dans un graphe simple, un sommet a au plus $n - 1$ voisins, une boucle et les arêtes multiples étant exclues.

Aucune des deux, ni les deux ensemble, ne suffit. Mesuré : la suite $(3, 3, 1, 1)$ a une somme paire et $d_{1} = 3 \leq 3$ , et pourtant aucun graphe ne la réalise — vérifié par énumération exhaustive de tous les graphes à quatre sommets. La raison est visible : les deux sommets de degré $3$ doivent être reliés à tous les autres, donc chacun des deux derniers a déjà un degré $\geq 2$ .

2. Le théorème de Havel-Hakimi. Soit $D = (d_{1} \geq d_{2} \geq \dots \geq d_{n})$ et

$D^{'} = (d_{2} - 1, d_{3} - 1, \dots, d_{d_{1} + 1} - 1, d_{d_{1} + 2}, \dots, d_{n}) .$

Alors $D$ est réalisable si et seulement si $D^{'}$ l'est.

$(\Leftarrow)$ Facile. Soit $G^{'}$ réalisant $D^{'}$ sur les sommets $s_{2}, \dots, s_{n}$ . Ajoutons un sommet $s_{1}$ relié à $s_{2}, \dots, s_{d_{1} + 1}$ . Ces $d_{1}$ sommets gagnent chacun un degré, retrouvant $d_{2}, \dots, d_{d_{1} + 1}$ ; les autres sont inchangés ; et $s_{1}$ a le degré $d_{1}$ . Le graphe obtenu réalise $D$ .

$(\Rightarrow)$ C'est ici que se trouve l'idée. Soit $G$ réalisant $D$ . Rien ne dit que $s_{1}$ y est relié aux $d_{1}$ sommets de plus grand degré — il faut le fabriquer, par un échange d'arêtes.

Supposons qu'il existe $i \leq d_{1} + 1$ et $j > d_{1} + 1$ tels que $s_{1}$ soit relié à $s_{j}$ mais pas à $s_{i}$ . Comme la suite est décroissante, $d_{i} \geq d_{j}$ . Posons

$A = N (s_{i}) ∖ {s_{1}, s_{j}}, B = N (s_{j}) ∖ {s_{1}, s_{i}} .$

Alors $∣ A ∣ > ∣ B ∣$ . En effet, si $s_{i}$ et $s_{j}$ ne sont pas voisins, $∣ A ∣ = d_{i}$ — le sommet $s_{1}$ n'est pas voisin de $s_{i}$ — et $∣ B ∣ = d_{j} - 1$ , d'où $∣ A ∣ \geq d_{j} > ∣ B ∣$ ; et s'ils sont voisins, $∣ A ∣ = d_{i} - 1$ et $∣ B ∣ = d_{j} - 2$ , d'où encore $∣ A ∣ > ∣ B ∣$ . Il existe donc un sommet $s_{k} \in A ∖ B$ : il est voisin de $s_{i}$ , non voisin de $s_{j}$ , et distinct de $s_{1}$ , $s_{i}$ et $s_{j}$ . Remplaçons alors les arêtes ${s_{1}, s_{j}}$ et ${s_{i}, s_{k}}$ par ${s_{1}, s_{i}}$ et ${s_{j}, s_{k}}$ . Aucun degré ne change : $s_{1}$ perd $s_{j}$ et gagne $s_{i}$ , $s_{i}$ perd $s_{k}$ et gagne $s_{1}$ , $s_{j}$ perd $s_{1}$ et gagne $s_{k}$ , $s_{k}$ perd $s_{i}$ et gagne $s_{j}$ . Mais le nombre de voisins de $s_{1}$ parmi $s_{2}, \dots, s_{d_{1} + 1}$ a augmenté de $1$ .

Ce nombre est borné par $d_{1}$ : en répétant l'échange, on obtient en un nombre fini d'étapes un graphe réalisant $D$ où $s_{1}$ est relié exactement à $s_{2}, \dots, s_{d_{1} + 1}$ . Retirer $s_{1}$ donne alors un graphe réalisant $D^{'}$ .

3. L'algorithme. Le théorème se lit comme une récurrence :


Entrée  : une suite d'entiers positifs.
Sortie  : vrai ssi elle est la suite des degrés d'un graphe simple.

  tant que la suite n'est pas nulle :
      trier par ordre décroissant
      retirer le premier terme d1
      si d1 > nombre de termes restants : rendre FAUX
      diminuer de 1 les d1 premiers termes restants
      si un terme est devenu négatif : rendre FAUX
  rendre VRAI

Terminaison : le variant est $\sum_{i} d_{i}$ , qui décroît strictement de $2 d_{1} > 0$ à chaque tour tant que la suite n'est pas nulle. Correction : par le théorème, chaque tour préserve la réalisabilité dans les deux sens ; la suite nulle est réalisée par le graphe sans arête. Complexité : au plus $n$ tours, chacun en $O (n lo g n)$ pour le tri, soit $O (n^{2} lo g n)$ — et $O (n^{2})$ en remplaçant le tri par un tri par comptage, les degrés étant bornés par $n$ .

L'algorithme est de plus constructif : en gardant trace des arêtes ajoutées à chaque remontée, on obtient un graphe réalisant la suite, et pas seulement une réponse booléenne.

4. Les épreuves. Mesuré, chaque réponse confrontée à une énumération exhaustive quand la taille le permet :

suite	somme	Havel-Hakimi	vérification exhaustive
$(3, 3, 3, 3)$	$12$	réalisable	réalisable ( $K_{4}$ )
$(3, 3, 3, 3, 3, 3, 3)$	$21$	non	somme impaire
$(2, 2, 2)$	$6$	réalisable	réalisable (triangle)
$(1, 1, 1, 1, 1, 1)$	$6$	réalisable	réalisable (3 arêtes)
$(4, 4, 4, 4, 4)$	$20$	réalisable	--- ( $K_{5}$ )
$(5, 3, 3, 3, 3, 3)$	$20$	réalisable	---
$(3, 3, 1, 1)$	$8$	non	non
$(4, 3, 2, 1, 0)$	$10$	non	non
$(2, 2, 2, 2, 1)$	$9$	non	somme impaire

Les deux colonnes concordent partout. Les deux lignes en gras sont les cas intéressants : somme paire, $d_{1} \leq n - 1$ , et pourtant irréalisables. La suite $(4, 3, 2, 1, 0)$ le montre bien : le premier sommet doit être relié aux quatre autres, dont celui de degré $0$ — impossible. Havel-Hakimi le découvre en un tour.

Ce que ce problème illustre. Le lemme des poignées de main est une condition locale — une somme. La réalisabilité est une condition globale, et le passage de l'une à l'autre demande un argument d'échange, technique récurrente en théorie des graphes : on ne construit pas la solution, on montre que toute solution peut être déformée vers une forme normale sans changer ce qui compte.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.