Problème de réalisation de graphe

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

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

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

↑ Fabien Viger, « Génération de graphes connexes aléatoires avec séquence de degrés donnée »
↑ (cs) « 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)
↑ (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)

Portail de l'informatique théorique

Portail des mathématiques

[1] Fabien Viger, « Génération de graphes connexes aléatoires avec séquence de degrés donnée »

[2] (cs) « 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)

[1]

[2]

[3]