Moralisation de graphe
Un article de Wikipédia, l'encyclopédie libre.
 |
Cet article est une ébauche concernant les mathématiques.
Vous pouvez partager vos connaissances en l’améliorant. (Comment ?).
|
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é.
[modifier] 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).
