Théorie des graphes Karima Belmabrouk Ing2-2023/2024
Chapitre IV. Problèmes de cheminement
1. Recherche des composantes connexes
Déterminer si un graphe est connexe est une question fondamentale en théorie des graphes. En
pratique, on s'intéresse souvent à une seule composante connexe à la fois, ce qui revient à analyser un
graphe connexe. Divers algorithmes existent pour identifier les sommets appartenant à une même
composante connexe. Ce document présente une version simple et non récursive de l'un de ces
algorithmes, celui de recherche de la composante connexe contenant un sommet donné (Trémeaux
1882, Tarjan 1972).
1.1. Présentation des objectifs
Les principaux objectifs de la recherche des composantes connexes sont :
Définir les composantes connexes : Comprendre le concept de composantes connexes dans les
graphes non orientés et leur importance dans l'analyse de graphes.
Maîtriser l'algorithme de Tarjan-Tarjan : Appréhender les mécanismes et les étapes
d'implémentation de l'algorithme de Tarjan-Tarjan pour identifier les composantes connexes.
Appliquer l'analyse des composantes connexes : Reconnaître les diverses applications de
l'analyse des composantes connexes dans différents domaines.
1. 2. Algorithme de Trémeaux-Tarjan
L'algorithme de Tarjan-Tarjan est un algorithme efficace pour identifier les composantes connexes dans
un graphe non orienté. Il fonctionne en utilisant la recherche en profondeur (DFS) et en exploitant des
structures de données pour suivre les sommets visités et leurs ancêtres potentiels.
Concepts clés
Composante connexe C : Un sous-graphe où tous les sommets sont connectés deux à deux par un
chemin.
Sommet u visité : Un sommet qui a été exploré par l'algorithme DFS.
dfn[u] (découverte de u): Un entier unique attribué à u lors de sa première visite par DFS,
représentant l'ordre de découverte.
low[u] : Le plus petit dfn[v] rencontré jusqu'à présent par DFS, où v est un descendant de u dans
l'arbre DFS, y compris u lui-même.
Structures de données
low : Tableau d'entiers initialisé à l'infini (représentant une valeur non définie). Taille = nombre de
sommets du graphe.
dfn : Tableau d'entiers initialisé à -1 (représentant un sommet non visité). Taille = nombre de sommets
du graphe.
stack : Pile utilisée pour suivre les sommets explorés par DFS et potentiellement appartenant à la
même composante connexe.
L'algorithme de Trémeaux-Tarjan est un algorithme linéaire en temps et en espace pour identifier les
composantes connexes dans des graphes non orientés. Il utilise la recherche en profondeur (DFS) pour
explorer le graphe et maintient des structures de données pour suivre les informations de découverte et
d'ancêtre pour chaque sommet.
Étapes de l'algorithme :
1. Initialisation : Attribuer un numéro de découverte (low) et un numéro d'ancêtre (dfn) à chaque
sommet, respectivement à -∞ et -1. Créer une pile vide.
2. Exploration DFS : Pour chaque sommet non visité u, effectuer une exploration DFS : a. Marquer
u comme visité : Définir dfn[u] = current_time et low[u] = current_time. Incrémenter
current_time. b. Pousser u sur la pile : Ajouter u à la pile. c. Explorer les voisins non visités : Pour
chaque voisin non visité v de u : i. Explorer v récursivement : Si dfn[v] = -1, appeler récursivement
DFS(v). Sinon, mettre à jour low[u] à min(low[u], low[v]). d. **Dépop
19
Théorie des graphes Karima Belmabrouk Ing2-2023/2024
2. Recherche du plus court chemin
2.1. Présentation des conditions
s’il existe un chemin entre deux sommets u et v contenant un circuit de coût négatif, alors (u, v)
= -, et il n’existe pas de plus court chemin entre u et v. Un circuit négatif est appelé un circuit
absorbant.
2.2. Algorithme de Moore-Dijkstra
Un graphe pondéré connexe G (les poids sont tous positifs)
Un sommet d'entrée E
Entrées
Résultat Les plus courtes distances du sommet E à chacun des sommets.
Attribuer la marque +∞ à tous les sommets.
Attribuer la marque 0 au sommet d'entrée E.
TANT QU' il reste des sommets non sélectionnés :
Sélectionner, parmi les sommets non-sélectionnés, le sommet A ayant la marque la plus petite.
Pour chaque sommet B adjacent à A et non déjà sélectionné:
oCalculer p = (marque de A) + (poids de l'arête A-B).
oSI p < marque de B
ALORS remplacer marque de B par p
SINON conserver marque de B.
Traitement FIN TANT QUE
Remarque :
1. Au premier tour de boucle, c'est le sommet E qui est sélectionné (puisqu'il porte la marque
0 et les autres la marque +∞).
2. Si l'objectif est de calculer la distance du sommet E à un sommet S, on peut stopper
l'algorithme dès que S est parmi les sélectionnés.
3. Si on veut connaître le chemin à suivre pour la plus courte distance, on ajoute à chaque
étape une mémorisation du "parent" d'un sommet.
Exemple :
Voici un graphe pondéré connexe. On cherche le plus court chemin emmenant du sommet E au sommet
S.
20
Théorie des graphes Karima Belmabrouk Ing2-2023/2024
On peut présenter la mise en oeuvre de l'algorithme de Moore-Dijkstra de la manière suivante (chaque
ligne correspond à une étape de l'algorithme):
Pour déterminer le résultat, on lit la chaîne à l'envers (en partant du sommet S) en se rendant dans la
colonne du sommet de provenance.
Ainsi, la chaîne à l'envers est :
S (poids total = 7 en venant de D)
D (poids = 5 en venant de A)
A (poids = 3 en venant de E)
E (sommet d'entrée)
La chaîne de poids minimal est donc E-A-D-S
3. Recherche d'un arbre de poids extrémum
3.1. Présentation des objectifs
Arbre couvrant de poids minimum (MST) et Arbre couvrant de poids maximum (MST) sont deux
algorithmes fondamentaux en théorie des graphes avec des objectifs distincts. Ils visent tous deux à
trouver un sous-ensemble d'arêtes dans un graphe connexe qui relie tous les sommets tout en satisfaisant
des conditions de poids spécifiques.
Arbre couvrant de poids minimum (MST)
L'objectif principal de la recherche d'un MST est d'identifier le sous-ensemble d'arêtes dans un graphe
connexe qui relie tous les sommets tout en minimisant le poids total des arêtes. Ce sous-ensemble
d'arêtes forme un arbre, qui est un graphe acyclique connexe.
Applications du MST:
Conception de réseaux: Le MST est largement utilisé dans la conception de réseaux pour trouver
le moyen le plus rentable de connecter tous les nœuds d'un réseau, en minimisant la longueur
totale du câble ou le coût.
Clustering: Le MST peut être appliqué dans les algorithmes de clustering pour regrouper des
points de données similaires, en minimisant la distance entre les points dans chaque cluster.
Segmentation d'images: Le MST peut être utilisé dans la segmentation d'images pour identifier
les limites entre les objets d'une image, en minimisant la longueur totale des bords de la
segmentation.
Arbre couvrant de poids maximum (MST)
Contrairement au MST, l'objectif de la recherche d'un MST est d'identifier le sous-ensemble d'arêtes dans
un graphe connexe qui relie tous les sommets tout en maximisant le poids total des arêtes. Ce sous-
ensemble d'arêtes forme également un arbre.
21
Théorie des graphes Karima Belmabrouk Ing2-2023/2024
Applications du MST:
Réseaux de communication: Le MST peut être utilisé dans les réseaux de communication pour
trouver le chemin avec la bande passante la plus élevée entre tous les nœuds, en maximisant la
capacité globale de transmission de données.
Réseaux de transport: Le MST peut être appliqué aux réseaux de transport pour identifier
l'itinéraire avec la plus longue distance qui relie toutes les villes, en maximisant la longueur totale
du réseau de transport.
Arbres phylogénétiques: Le MST peut être utilisé pour construire des arbres phylogénétiques en
biologie pour représenter les relations évolutives entre les espèces, en maximisant la longueur
totale des branches de l'arbre.
3.2. Algorithme de Kruskal 1956
L’algorithme date de 1956. Kruskal (1928-2010) a aussi travaillé dans d’autres domaines : statistique et
linguistique notamment. Même si, il est surtout célèbre pour son algorithme de calcul d’un arbre couvrant
minimal.
Algorithme
pre : Un graphe G = (S, A, poids) pondéré non orienté
post : Un ACM (arbre couvrant minimal) de G
fonction kruskal(G)
E := ∅
L := liste triée des arcs de A, par ordre croissant des poids.
pour {x, y} ∈ L dans l’ordre croissant faire
si x et y ne sont pas reliées dans le graphe (S, E) alors
E := E ∪ {{x, y}}
retourner E
Exemple 1 :
22
Théorie des graphes Karima Belmabrouk Ing2-2023/2024
Exemple 2
L'exemple détaille les différentes itérations de l'algorithme :
23
