Moralisation de graphe

Moralisation d'un 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

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 .

Un graphe orienté acyclique.
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

Algorithme de la théorie des graphes (57)
Dernière mise à jour du contenu le .
Droit d'auteur : le texte de l'article est disponible sous la licence CC BY-SA 3.0.
Les détails concernant les licences et crédits des images sont disponibles en cliquant sur l'image.
Le site Wikimonde est un agrégateur d'articles encyclopédiques, il n'est pas à l'origine du contenu des articles, ni des images.
Le contenu de cet article est une copie de l'article d'origine (//fr.wikipedia.org/wiki/Moralisation_de_graphe) publié sur Wikipédia (wiki collaboratif publié sous licence libre).
Le contenu des articles n'est pas garanti.
Le texte des articles n'est pas modifié par Wikimonde. Des modifications mineures de mise en page et des liens internes (pour faciliter la navigation) peuvent être effectués automatiquement.
Des crédits concernant les images peuvent être ajoutés automatiquement selon les informations fournis par le site d'origine.
Les images sont chargées depuis des sites externes, certaines peuvent ne pas s'afficher.
Auteurs de cet article « Moralisation de graphe » :
LeFit, Roll-Morton, Léna, ManiacParisien, ChrisJ, DainDwarf, MathsPoetry, Tejgad, Aubertinp, Uruloce, 1 utilisateur non enregistré.