informatique (MP2I/MPI) · Chapitre 13 · Application directe du cours

Problème — Quelles suites de degrés sont réalisables ?

Le modèle des graphes · niveau 3 (difficile)

É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é de la question 1

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$ .

Question 2 : comment l'IA t'aide

2. 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.

Élève

Le sens réciproque est facile, en ajoutant un sommet. Pour le sens direct, je retire $s_{1}$ d'un graphe réalisant $D$ , mais rien ne dit que ses voisins sont exactement $s_{2}, \dots, s_{d_{1} + 1}$ .

C'est le cœur de la preuve. Plutôt que de prendre n'importe quel graphe réalisant $D$ , peux-tu le modifier, sans changer aucun degré, pour que $s_{1}$ ait davantage de voisins parmi $s_{2}, \dots, s_{d_{1} + 1}$ ?

Élève

Si $s_{1}$ est relié à un $s_{j}$ avec $j > d_{1} + 1$ mais pas à un $s_{i}$ avec $i \leq d_{1} + 1$ , je remplace l'arête $s_{1} s_{j}$ par $s_{1} s_{i}$ . Mais alors $s_{i}$ gagne un degré et $s_{j}$ en perd un.

Comment compenser ces deux variations par une seconde modification d'arêtes, sans toucher à $s_{1}$ ? Et quelle hypothèse sur la suite te garantit l'existence de ce qu'il te faut pour le faire ?

L'IA ne donne pas la réponse : elle pose la question qui fait avancer. À toi de continuer.

Continue cet exercice avec l'IA

Reprends la question 2 là où le dialogue s'arrête, puis la suite de l'exercice.

Continuer avec l'IA — gratuit, sans inscription

Gratuit, sans inscription. L'IA te guide pas à pas, sans te donner la réponse.

Le cours du chapitre · Tous les exercices du chapitre

Continuer avec l'IA, gratuit →