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é. Certains algorithmes nécessitent en effet de disposer d'un graphe non orienté.

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. Cette étape peut s'effectuer en temps linéaire O(n).

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