Algorithme de construction d'une forêt maximale

L'algorithme de construction d'une forêt maximale est un algorithme de la théorie des graphes.

Histoire

Sept ponts de Köningsberg

Cet algorithme est apparu avec la théorie des graphes, ayant pour origine le XVIII^e siècle avec le problème des sept ponts de Königsberg. Leonhard Euler résolut ce problème en caractérisant les graphes, faisant naître la théorie des graphes et la notion de graphes "eulériens". Ainsi il démontra qu'aucune solution n'existait à ce problème. Le problème consiste à partir d'une des rives de la rivière puis de revenir au point de départ en passant par tous les ponts une seule fois (voir le schéma ci-contre du problème des sept ponts de Königsberg).

Usages

L'algorithme sert à trouver un chemin entre plusieurs points sans jamais repasser une fois par le même point (il ne doit pas y avoir de cycles). Le seul moyen de repasser par un point déjà franchi serait de revenir en arrière (faire demi-tour).

Démonstration

L'algorithme suivant crée une forêt maximale :

Initialement, tous les arcs du graphe sont incolores. La méthode consiste à examiner successivement tous les arcs du graphe (dans n'importe quel ordre) et à les colorer soit en rouge soit en vert. À une étape quelconque, <math>Gc</math> est le graphe partiel engendré par les arcs colorés (rouges ou verts) et <math>Gr</math> le graphe partiel engendré par les arcs rouges. Chaque fois qu'un nouvel arc <math>a</math> incolore est examiné :

• Soit il passe par <math>a</math> un cycle élémentaire <math>h</math> dont tous les arcs (autres que <math>a</math>) sont rouges; on colore alors l'arc en vert, le nombre de connexité de <math>Gc</math> et de <math>Gr</math> reste constant.

• Soit un tel cycle n'existe pas, auquel cas l'arc <math>a</math> permet de connecter deux sommets qui n'étaient pas encore connectés dans <math>Gc</math> ; on colore l'arc <math>a</math> en rouge, le nombre de connexité de <math>Gc</math> et de <math>Gr</math> décroît de 1.

Pour montrer que le graphe partiel <math>Gr</math> obtenu est bien une forêt maximale de G, il suffit d'observer qu'à tout instant, le graphe <math>Gr</math> est sans cycle (c'est donc bien une forêt de G); à la fin de la procédure, elle est bien maximale pour l'inclusion car, en ajoutant un arc vert quelconque à <math>Gr</math>, on crée un cycle.

Complexité

Une forêt maximale de G est une forêt de G maximale pour l'inclusion (l'ajout d'une seule arête supplémentaire du graphe à cette forêt crée un cycle). Une forêt est un graphe acyclique non-connexe . Nous devons donc créer un maximum d'arêtes entre les points sans pour autant créer un cycle dans le graphe. Par conséquent dans notre graphe <math>G=(V,E)</math> :

• <math>V</math> représente l'ensemble de sommets.
• <math>E</math> l'ensemble d'arêtes.

On peut dire qu'au rang k le graphe est cyclique, on passe au rang k-1 en retirant une arête et le graphe devient acyclique. La complexité ou "originalité" de cet algorithme est qu'il ne tient pas compte du poids (pas de poids minimum), le nombre d'arêtes ne doit pas créer un cycle dans le graphe ainsi elles doivent être choisies de façon précise.

Variantes

Il existe plusieurs variantes de l'Algorithme de construction d'une forêt maximale provenant de la théorie des graphes. En effet les graphes de la théorie des graphes utilisent des forêts minimales ou maximales. Ainsi on peut construire un algorithme de forêt minimale tel que l'algorithme de Kruskal débouchant sur un arbre couvrant de poids minimal.

• 

  Algorithme de Kruskal

Voir aussi

• Théorie des graphes

Vous pouvez voir ces Algorithmes sur leurs pages Wikipédia respectives :

• Algorithme de Kruskal
• Algorithme de Borůvka

Vous pouvez aussi voir les sources dans la bibliographie.

Bibliographie

• http://algo.developpez.com/faq/?page=graphes#cycle
• http://www.discmath.ulg.ac.be/cours/main_graphes.pdf
• http://pagesperso.g-scop.grenoble-inp.fr/~szigetiz/articles/chapitre_arbres.pdf

Notes et références

Article publié sur Wikimonde Plus