Moralisation de graphe

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Moralisation d'un graphe.

La moralisation d'un graphe consiste à passer d'un graphe orienté à un graphe non orienté dont les parents d'un même sommet sont liés par une arête. Certains algorithmes nécessitent en effet de disposer d'un tel graphe.

Méthode[modifier | modifier le code]

Pour moraliser le graphe, on doit marier les parents d'un même sommet, puis désorienter le graphe[1]. Cette étape peut s'effectuer en temps linéaire .

Le graphe moral correspondant. Les nouvelles arêtes sont en rouge.

Utilisations[modifier | modifier le code]

Cette opération est utilisée dans l'algorithme de l'arbre de jonction.

Notes et références[modifier | modifier le code]