Aller au contenu

Problème de réalisation de graphe

Un article de Wikipédia, l'encyclopédie libre.

Le problème de réalisation de graphe est un problème algorithmique. Étant donné une liste de nombres entiers, il consiste à décider s'il existe un graphe dont la liste des degrés est égale à la liste donnée en entrée.

Définition

[modifier | modifier le code]

On dit qu'un graphe non orienté réalise une certaine liste de nombres entiers, si la suite des degrés de graphe est égale à la liste en question.

Le problème de réalisation d'un graphe consiste, étant donné une liste, à décider s'il existe un graphe qui réalise cette liste[1].

Algorithmes et propriétés

[modifier | modifier le code]

L'algorithme de Havel-Hakimi résout le problème en temps polynomial[2],[3].

Le théorème d'Erdős-Gallai (en) donne une caractérisation des suites qui sont réalisables.

Notes et références

[modifier | modifier le code]
  1. Fabien Viger, « Génération de graphes connexes aléatoires avec séquence de degrés donnée »
  2. (cs) [1] « A remark on the existence of finite graphs » de Havel Václav, 1955, dans « Časopis pro pěstování matematiky » vol. 80 (pages 477 à 480)
  3. (en) « On realizability of a set of integers as degrees of the vertices of a linear graph » de S. L. Hakimi, 1962, dans Journal of the Society for Industrial and Applied Mathematics vol. 10 (pages 496 à 506)