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.
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 .
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]
- David Bellot, « Inferences dans les Reseaux Bayesiens » [PDF]