Moralisation de 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.

Moralisation d'un graphe.

Méthode

Pour moraliser le graphe, on doit marier les parents d'un même sommet, puis désorienter le graphe. Cette étape peut s'effectuer en temps linéaire $O(n)$.

Un graphe orienté acyclique.

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

Utilisations

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