- Moralisation de graphe
-
Moralisation d'un graphe.
La moralisation d'un graphe consiste à passer d'un graphe orienté à un graphe non orienté. Certains algorithmes nécessitent en effet de disposer d'un graphe non orienté.
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).
Catégorie :- Algorithme de la théorie des graphes
Wikimedia Foundation. 2010.
