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[1]. Cette étape peut s'effectuer en temps linéaire .
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.
Notes et références
- David Bellot, « Inferences dans les Reseaux Bayesiens » [PDF]
Portail de l'informatique théorique
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons – Attribution – Partage à l’identique. Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.