IN302
Graphes et algorithmes Notes de cours et exercices
Michel Couprie
Le 11 janvier 2010
| L’unité Graphes et Algorithmes a son site web! Vous y trouverez le plan du cours, les sujets des TD et des TP, des lectures conseillées, des liens sur d’autres sites parlant de graphes et d’algorithmes |
Table des matières
| 1.2.4 Représentation d’un graphe (E,?) . . . . . . . . . . . . . . . . . . | 5 |
| 1.2.5 Evaluation de la complexité d’un algorithme . . . . . . . . . . . .´ . | 6 |
| 1.3 Graphes orientés et non-orientés . . . . . . . . . . . . . . . . . . . . . . . . | 7 |
| 1.3.1 Le symétrique d’un graphe . . . . . . . . . . . . . . . . . . . . . . . | 7 |
| 1.3.2 Graphe symétrique, graphe antisymétrique . . . . . . . . . . . . . . | 8 |
| 1.3.3 Fermeture symétrique . . . . . . . . . . . . . . . . . . . . . . . . . | 9 |
| 1.3.4 Graphe non-orienté . . . . . . . . . . . . . . . . . . . . . . . . . . . | 9 |
| 1.3.5 Réflexivité, antiréflexivité . . . . . . . . . . . . . . . . . . . . . . . | 10 |
| 1.3.6 Graphe complet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . | 11 |
| 1.4 Chemins, connexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . | 11 |
| 1.4.1 Chemins et chaˆ?nes . . . . . . . . . . . . . . . . . . . . . . . . . . . | 11 |
| 1.4.2 Composante connexe et fortement connexe . . . . . . . . . . . . . . 1.4.3 Calcul des composantes fortement connexes et des composantes | 13 |
| connexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . | 14 |
| 1.4.4 Degrés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . | 16 |
| 1.5 Représentation matricielle . . . . . . . . . . . . . . . . . . . . . . . . . . . | 17 |
1 Notions de base 1
1.1 Première définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Représentation en mémoire . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.1 Représentation d’un sous-ensemble . . . . . . . . . . . . . . . . . . 3
1.2.2 Opérations sur un ensemble . . . . . . . . . . . . . . . . . . . . . . 4
1.2.3 Représentation d’un graphe (E,
1.6 Graphe biparti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2 Arbres et arborescences 21
2.1 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.1.1 Isthme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.1.2 Arbre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.1.3 Racine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.1.4 Arborescences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.1.5 Découpage en niveaux . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.2 Exemples et applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.2.1 Fausse monnaie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.2.2 Arborescence de décision . . . . . . . . . . . . . . . . . . . . . . . . 24
2.2.3 Arithmétique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.2.4 Arborescence ordonnée . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.2.5 Arborescence de recherche . . . . . . . . . . . . . . . . . . . . . . . 26
2.3 Arbre de poids extrémum . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.3.1 Graphe Pondéré . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.3.2 Propriétés des arbres de poids maximum . . . . . . . . . . . . . . . 28
2.3.3 Algorithme de Kruskal 1 . . . . . . . . . . . . . . . . . . . . . . . 30
2.3.4 Algorithme de Kruskal 2 . . . . . . . . . . . . . . . . . . . . . . . 31
2.3.5 Algorithme de Prim . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3 Plus courts chemins 33
3.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.1.1 Réseau . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.1.2 Plus court chemin . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.2 Problématique du plus court chemin . . . . . . . . . . . . . . . . . . . . . 34
3.2.1 Graphe des plus courts chemins . . . . . . . . . . . . . . . . . . . . 35
3.3 Réseaux à longueurs quelconques (Bellman) . . . . . . . . . . . . . . . . . 37
3.3.1 Algorithme en pseudo language . . . . . . . . . . . . . . . . . . . . 37
3.3.2 Justification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.4 Réseaux à longueurs positives (Dijkstra) . . . . . . . . . . . . . . . . . . . 39
3.4.1 Algorithme en pseudo language . . . . . . . . . . . . . . . . . . . . 40
3.4.2 Réseaux à longueurs uniformes . . . . . . . . . . . . . . . . . . . . 41
3.5 Graphes et réseaux sans circuits . . . . . . . . . . . . . . . . . . . . . . . . 41
3.5.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.5.2 Sources et puits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.5.3 Rang et hauteur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.5.4 Partition en niveaux . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.5.5 Algorithme circuit-niveaux . . . . . . . . . . . . . . . . . . . . . . . 43
3.5.6 Plus courts chemins dans les réseaux sans circuits . . . . . . . . . . 44
4 Flots et réseaux de transport 46
4.1 Modélisation du réseau de transport . . . . . . . . . . . . . . . . . . . . . . 46
4.1.1 Modélisation du traffic (flot) . . . . . . . . . . . . . . . . . . . . . . 46
4.1.2 Equilibre global . . . . . . . . . . . . . . . . . . . . . . . . . . . . .´ 47
4.1.3 Equilibre local . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .´ 47
4.1.4 Arc de retour . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.1.5 Flot compatible avec un réseau de transport . . . . . . . . . . . . . 47
4.2 Algorithme de Ford et Fulkerson . . . . . . . . . . . . . . . . . . . . . . . . 48
4.2.1 Réseau d’écart . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.2.2 Algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.2.3 Preuve de l’algorithme de Ford et Fulkerson . . . . . . . . . . . . . 50
5 Résolution de problèmes en intelligence artificielle et optimisation com-
binatoire 52
5.1 Exemple 1 : le problème des 8 reines . . . . . . . . . . . . . . . . . . . . . 52
5.2 Graphe de résolution de problème . . . . . . . . . . . . . . . . . . . . . . . 53
5.3 Exemple 2 : jeu du taquin . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
5.4 Stratégies de recherche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
5.4.1 Stratégie sans mémoire : la recherche arrière (backtrack) . . . . . . 55
5.4.2 Stratégie avec mémoire : la recherche avec graphe (RAG) . . . . . . 55
5.4.3 Algorithmes A et A? . . . . . . . . . . . . . . . . . . . . . . . . . . 56
6 Compléments 58
6.1 Exploration en profondeur . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
6.2 Exploration en largeur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
Bibliographie 60
Chapitre 1
Notions de base
1.1 Première définition
Soit E un ensemble fini. L’ensemble des sous-ensembles d’un ensemble E,également appelé ensemble des parties de E, est noté P(E). Soit par exemple E = {1,2,3}, alors P(E) = {?,{1},{2},{3},{1,2},{2,3},{1,3},{1,2,3}}. La notation S ? P(E) signifie que S est un sous-ensemble de E ; de manière équivalente on peut écrire S ? E.
On appelle graphe sur E un couple G = (E, ?) ou` ? est une application de E ?? P(E).
Exemple 1 : Soit un graphe G = (E,?), avec E = {1,2,3,4} et ? définie par : – ?(1) = {1,2,4}
– ?(2) = {3,1}
– ?(3) = {4}
– ?(4) = ?
Il n’est pas facile de visualiser un graphe donné sous cette forme. Habituellement, on représente un graphe par un dessin tel que celui de la figure 1.1 page suivante. Notons que plusieurs dessins, comme pour cet exemple, peuvent représenter le même graphe.
• Tout élément de E est appelé un sommet.
• Tout couple ordonné (x,y) ? E × E tel que y ? ?(x) est appelé arc du graphe.
• Soit (x,y) un arc, on dit que y est un successeur de x.
• Soit (x,y) un arc, on dit que x est un prédecesseur de y.
Rappel : Dans un couple ordonné (x,y) l’ordre dans l’écriture — x puis y — est important. Ainsi (x,y) 6= (y,x). Si l’ordre n’est pas important, il convient d’utiliser la notation ensembliste : {x,y}. Cette fois, nous avons : {x,y} = {y,x}.
Le graphe G de l’exemple 1 comporte quatre sommets et six arcs. On désigne par ~? l’ensemble des arcs du graphe (E, ?). L’ensemble des arcs est un sous-ensemble du produit
Fig. 1.1 – Graphe de l’exemple 1, dessiné de deux manières
cartésien, autrement dit, ). On peut définir formellement ? par :
Suivant l’exemple précédent : .
Remarque : On peut représenter G par (E,?) ou par , les données de ces deux
informations étant équivalentes. On appellera également graphe le couple (E,~?).
On note |E| le cardinal (nombre d’éléments) de E. Pour un graphe G = (E,~?), on notera habituellement n = |E| et m = |~?|, à savoir, n est le nombre de sommets et m le nombre d’arcs de G.
Un sous-graphe de G = (E,?) est un graphe H = (F,?F) tel que F est un sousensemble de E et ?~F est l’ensemble des arcs de ~? dont les deux sommets sont dans F. On dit que H est le sous-graphe deGinduit parF, et que est la restriction de~? à l’ensembleF.
Un graphe partiel de G est un graphe) tel que est un sous-ensemble de ~?.
Exemple 2 :
Sous graphe Graphe partiel
1.2 Représentation en mémoire
1.2.1 Représentation d’un sous-ensemble
On va chercher à représenter les éléments constituant un sous-ensemble S d’un ensemble donné E ? N.
Liste chaˆ?née - LC
Les éléments présents dans le sous-ensemble sont contenus dans la liste.
Exemple 3 : Prenons le sous-ensemble S = {1,2,4} de N.
Tableau de booléens - TB
En supposant que E = {1 n}, on utilise un tableau de booléens de taille n et tel que la case i du tableau vaut vrai (1) si l’élément i appartient au sous-ensemble S et faux (0) sinon.
Exemple 4 : Prenons E = {1 9} et S = {1,2,4}.
1 2 3 4 5 6 7 8 9
| 1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
1.2.2 Opérations sur un ensemble
Le tableau suivant présente les principales opérations de base sur un ensemble ainsi que leur complexité selon le type de représentation mémoire. Le choix d’une structure de données adaptée est un facteur à prendre en compte lors de la conception d’un algorithme. Nous nous plac¸ons dans la configuration du pire cas ou` |S| = |E| = n.
| Opération | LC | TB | |
| Initialisation | S ? ? | O(1) | O(n) |
| Existence/sélection | ? x ? S? | O(1) | O(n) |
| Recherche | x ? S? | O(n) | O(1) |
| Insertion | S ? S ? {x} | O(n)/O(1) | O(1) |
| Suppression | S ? S \ {x} | O(1) | O(1) |
| Parcours | ?x ? S | O(n) | O(n) |
L’initialisation consiste à mettre en place en mémoire la structure de données correspondante. Pour le TB, il faut initialiser toutes les cases à zéro ce qui impose une complexité en O(n). Pour la LC, il suffit d’écrire NULL dans un pointeur [O(1)].
La sélection permet de prendre un élément quelconque de l’ensemble ou de tester si l’ensemble est vide. Pour la LC il suffit de sélectionner le premier élément de la liste, par contre pour le TB il faut parcourir les cases jusqu’à trouver éventuellement un élément non nul [O(n)].
La recherche permet de savoir si un élément donné est présent dans l’ensemble. Dans un TB il suffit de lire la case correspondante [O(1)], pour une LC il faut parcourir l’ensemble des éléments présents [O(n)].
La suppresion s’effectue en O(1) pour la LC et le TB. Cependant l’insertion qui techniquement s’effectue aussi en O(1) pour ces deux structures, pose un problème pour la LC. En effet, si nous voulons maintenir une liste d’éléments sans multiplicité : {1}?{1} = {1}, il faut avant l’insertion tester la présence de cet élément [O(n)]. Néanmoins, par exemple, si l’on sait que les éléments sont insérés une seule fois dans la liste, l’insertion peut s’effectuer en O(1).
Le parcours est proportionnel au nombre d’éléments presents dans la LC [O(n)] et au nombre de cases allouées dans le TB [O(n)].
1.2.3 Représentation d’un graphe (E,~?)
Double tableau - DT
Cette représentation consiste en deux tableaux I et T de taille , tels que I(j) est le sommet initial de l’arc numéro j et T(j) est le sommet terminal de l’arc numéro j.
Exemple 5 :
| 1 | 1 | 1 | 2 | 2 | 3 |
| 1 | 2 | 4 | 3 | 1 | 4 |
I
T
Représentation de ~? (voir exemple 1)
1.2.4 Représentation d’un graphe (E,?)
Tableau de listes chaˆ?nées - TLC
Cela consiste à prendre un tableau de taille |E| contenant des pointeurs sur des listes chaˆ?nées tel que la i-ème liste chaˆ?née corresponde à ?(i).
Matrice de booléens - MB
Il s’agit de la version bidimensionnelle des tableaux de booléens monodimensionnels (1.2.1). La matrice M est telle que Mij = 1 si et seulement si (i,j) est un arc de G.
La ligne Mi correspond au tableau de booléens monodimensionnel qui représente ?(i).
Exemple 6 :
Matrice de booléens Tableau de listes chaînées
|
?(1)
?(2)
?(3)
?(4)
Deux représentations possibles pour (E,?) (voir exemple 1)
Le choix des structures de données utilisées influe sur la complexité des programmes et donc sur leur efficacité.
Décrivez par des diagrammes, comme dans les illustrations qui précèdent, les représentations possibles en mémoire des graphes de l’exemple 7 (section 1.3.1).
1.2.5 Evaluation de la complexité d’un algorithme´
L’algorithme suivant a pour but de rechercher les successeurs d’une partie X d’un ensemble E.
Soit G = (E,~?), soit X ? E. On définit l’ensemble des successeurs de la partie X ainsi :
succ(
x?X
De la première forme de la définition, on déduit l’algorithme suivant :
Algorithme 1 : SuccPartie 1
Données Résultat :
1 Y ? ? ;
2 pour chaque (x,y) ? ~? faire
3 six ? XalorsY ? Y ? {y};
Selon le choix du type de données pour X et Y , la complexité de l’algorithme précédent peut varier. Prenons par exemple Y sous forme d’un tableau de booléens et X sous forme de liste chaˆ?née.
On note n = |E| et m = |~?|.
L’instruction d’initialisation de Y à la ligne 1 est en O(n). La boucle de la ligne 2 à 6 est executée m fois. Le test d’appartenance ligne 3 est en O(n) car X est sous forme d’une liste chaˆ?née, de plus il est executé m fois. On comptera donc O(mn) pour la ligne 3. L’ajout d’un élément à un tableau de booléens, ligne 4, est en temps constant. On comptera donc pour la ligne 4 : O(m × 1). On peut conclure que la forme de la complexité de cet algorithme est en O(n + m + mn + m) = O(mn).
Choisissons maintenant X sous forme d’un tableau de booléens. L’instruction de la ligne 3 devient en temps constant O(1); le corps de boucle de la ligne 2-6 est en temps constant et est executé m fois. L’algorithme est donc en O(m + n) ce qui est bien meilleur que la
| Exercice 2 Evaluez la complexité de l’algorithme suivant, inspiré de la seconde forme de la définition´ de succ(X), en supposant que Y est représenté par un tableau de booléens. Algorithme 2 : SuccPartie 2 Données : X ? E,? Résultat : Y ? E 1 Y ? ? ; 2 pour chaquex ? Xfaire 3 pour chaquey ? ?(x) faire 4Y ? Y ? {y} ; |
1.3 Graphes orientés et non-orientés
1.3.1 Le symétrique d’un graphe
Soit G = (E,?). On appelle symétrique de G le graphe G?1 = (E,??1) défini par :
?x ? E , ??1(x) = { y ? E | x ? ?(y)}
Il s’agit d’un graphe dont l’orientation des arcs a été inversée par rapport au graphe initial. Cette notation : ??1 est aussi utilisée pour représenter la “fonction prédécesseur”, c’est à dire la fonction qui à tout sommet du graphe fait correspondre l’ensemble de ses
prédecesseurs.
Exemple 7 :
1 1
33
22
Graphe G Symétrique de G
Remarque : y ? ??1(x) ? x ? ?(y)
Algorithme de calcul du symétrique
Algorithme 3 : Sym 1
Données : E,?
Résultat : ??1
1 pour chaquex ? Efaire ??1(x) ? ? ;
2 pour chaquey ? Efaire pour chaquex ? ?(y) faire
Algorithme 4 : Sym 2
Données : ~?
Résultat : ?~?1
1 ?~?1 ? ? ;
2 pour chaque faire
3 ?~?1 ? ?~?1 ? {(y,x)} ;
Evaluez la complexité de ces deux algorithmes.´
1.3.2 Graphe symétrique, graphe antisymétrique
Le graphe G = (E,?) est un graphe symétrique si ??1 = ?. Autrement dit, G est un
graphe symétrique si
?x ? E , ?y ? E , x ? ?(y) ? y ? ?(x)
Un graphe G = (E,?) est antisymétrique si ?x,y ? E , [x ? ?(y) et y ? ?(x)] ? y = xExemple 8 :
1 1
Graphe symétrique Graphe antisymétrique
1.3.3 Fermeture symétrique
Soit G = (E,?). On appelle fermeture symétrique de G le graphe Gs = (E,?s) défini par :
?x ? E , ?s(x) = ?(x) ? ??1(x)
Exemple 9 :
1 1
Graphe G Fermeture symétrique de G
1.3.4 Graphe non-orienté
Définition
On appelle graphe non-orienté sur E un couple G = (E, ?) tel que ? soit un sous-
ensemble de { {x,y} | x ? E, y ? E }. Ainsi ? est de la forme : {{a,b},{c,d},{e,f}, }.
Tout élément de ? : {x,y} est appelé arête du graphe. On dit que l’arête {x,y} est
adjacente au sommet x et au sommet y. A ? on peut associer l’application ?n.o. de E ?? P(E) définie par :
Dans tous les cas, (E,?n.o.) est un graphe symétrique.
Ainsi la donnée d’un graphe symétrique est équivalente a` la donnée d’un graphe nonorienté.
Graphe non-orienté associé à un graphe orienté
Il se peut qu’à partir d’un graphe orienté, l’on cherche à travailler dans un contexte nonorienté. Pour cela nous associons au graphe donné (E,?) sa version non-orientée ( définie par :
ou encore par :
?n.o. = fermeture symétrique (?)
Exemple 10 :
1 1
33
22
Graphe G Graphe non orienté associé à G
1.3.5 Réflexivité, antiréflexivité
Un graphe G = (E,?) est réflexif si ?x ? E , x ? ?(x).
Un graphe G = (E,?) est antiréflexif si ?x ? E , x /? ?(x).
Un arc de la forme (x,x) est appelé une boucle.
Exemple 11 :
et non antiréflexif (sans boucle)
1.3.6 Graphe complet
Un graphe G = (E,~?) est dit complet si pour tout couple de sommets (x,y) distincts, on a (x,y) ? ~?. Un graphe complet est aussi appelé clique à n sommets.
Exemple 12 :
sur trois sommets sur trois sommets sur cinq sommets
| Exercice 4 Soit E = {1,2, ,n,n + 1}. Soit G = (E,?) le graphe complet non-orienté sur E. Décrivez deux fac¸ons différentes de compter les arêtes de G. En déduire l’égalité 1 + 2 +. |
1.4 Chemins, connexité
1.4.1 Chemins et chaˆ?nes
Soit G = (E,?), soient x0 et xk deux sommets de E. Un cheminC de x0 à xk est une séquence ordonnée C = (x0, ,xk) de sommets de E telle que ?i ? [1,k], xi ? ?(xi?1). En d’autres termes, chaque sommet xi du chemin est un sucesseur du sommet xi?1. Une séquence telle que C = (x0) est également appelée chemin de x0 à x0, un tel chemin est qualifié de trivial.
On dit que k est la longueur du chemin : c’est aussi le nombre d’arcs du chemin. La longueur d’un chemin trivial est nulle. Le chemin C est un circuit si x0 = xk, avec k > 0.
Chemin élémentaire
Le chemin C est dit élémentaire si les sommets xi sont tous distincts (sauf éventuellement x0 et xk ).
Proposition : Tout chemin C de x à y dans G contient (au sens d’une suite extraite) un
chemin élémentaire de x à y dans G.
Exercice 5
Démontrez cette proposition.
Proposez un algorithme pour, étant donné un graphe et un chemin C quelconque dans ce graphe liant deux sommets x et y, retourne un chemin élémentaire de x à y extrait de C. Evaluez la complexité de votre algorithme.´
Proposition : Soit G = (E,?), avec |E| = n. La longueur d’un chemin élémentaire dans
G qui n’est pas un circuit est inférieure ou égale à n?1. De même la longueur d’un circuit élémentaire est inférieure ou égale à n.
Chaˆ?nes et cycles
Définition : Soit G = (E,?), et ?s la fermeture symétrique de ?. On appelle chaˆ?ne tout chemin dans (E,?s).
On appelle cycle tout circuit dans (E,?s) ne passant pas deux fois par la même arête.
Exemple 13 :
| - (1,2,1) n’est pas un chemin. | - (1,2,3) est un chemin. |
| - (1,2,3,1,2,4) est un chemin. | - (4,2,1) n’est pas un chemin. |
| - (4,2,1) est une chaˆ?ne. | - (1,2,3,1) est un circuit. |
| - (1,3,2,1) n’est pas un circuit. - (1,3,1) n’est pas un cycle. | - (1,3,2,1) est un cycle. |
Le tableau suivant résume les différents termes employés selon la nature du graphe considéré :
| Graphe orienté | Graphe non-orienté |
| arc | arête |
| chemin | chaˆ?ne |
| circuit | cycle |
1.4.2 Composante connexe et fortement connexe
Définition : Soit G = (E,?) et x ? E. On définit Cx, la composante connexe de G contenant x par :
Cx = {y ? E | il existe une chaˆ?ne de x à y}
Autrement dit, la composante connexe contenant le sommet x est l’ensemble des sommets qu’il est possible d’atteindre par une chaˆ?ne à partir de x.
Remarque : Cette définition sous-entend que l’on travaille toujours dans la version non-
orientée du graphe. Remarquons que x appartient toujours à la composante Cx, en effet il existe une chaˆ?ne de longueur nulle (chaˆ?ne triviale) de x à x.
8
Exemple 14 : 6
– C1 = {1,2,3,4} = C2 = C3 = C4
– C5 = {5}
– C6 = C7 = C8 = {6,7,8}
Composante fortement connexe
Définition : Soit G = (E,?) et x ? E. On définit , la composante fortement connexe de G contenant x par :
il existe un chemin de x à y et il existe un chemin de y à x}
Remarque : Remarquons que x appartient toujours à la composante, en effet il existe
un chemin de longueur nulle (chemin trivial) de x à x.
Exemple 15 : Dans le graphe de l’exemple précédent :
–
–
–
–
–
–
1.4.3 Calcul des composantes fortement connexes et des composantes connexes
Définitions préliminaires
Soit un graphe G = (E,?), on définit la famille d’ensembles de sommets de E :
– ?0(x) = {x}
– ?1(x) = ?(x) – ?2(x) = succ(?1(x)) –
– ?p(x) = succ(?p?1(x)) ou` succ(X) désigne l’ensemble des successeurs de la partie X, autrement dit, succ(X) = ?x?X?(x) (voir aussi la section 1.2.5).
De même, on peut définir pred(X) = ?x?X??1(x) ainsi que la famille ? ) = pred(?
Proposition : il existe un chemin de x à y dans G de longueur p}
il existe un chemin de y à x dans G de longueur p}
On définit, pour tout x ? E,
Proposition :
il existe un chemin de x à y dans G de longueur ? p}
?ˆ?p1(x) = {y ? E , il existe un chemin de y à x dans G de longueur ? p}
On définit aussi ?ˆ?(x) comme l’ensemble des y ? E tel qu’il existe un chemin de x à y dans G, et ?ˆ??1(x) comme l’ensemble des y ? E tel qu’il existe un chemin de y à x dans G.
Proposition : Soit n = |E|, la composante fortement connexe contenant x se
calcule par la formule :
La composante connexe de G contenant x s’écrit :
Cx = [?ˆs]n?1(x) = [?ˆs?1]n?1(x)
ou` ?s est la fermeture symétrique de ?.
Démonstration : par définition nous avons). Soit un chemin de i
à j. Soit le chemin élémentaire associé, c’est un chemin de i à j ayant au plus n ? 1 arcs. Ainsi la connaissance des chemins de longueur n ? 1 est suffisante (puisque cet ensemble contient tous les chemins élémentaires) pour déterminer ?ˆ?(= ?ˆn?1).
Calcul de la composante fortement connexe
Algorithme 5 : CompFoCo
Données : (E,?,??1);a ? ERésultat :
1 ?ˆ?(a) ? ?; T ? {a} ;
2 tant que ?x ? Tfaire
3 T ? T \ {x} ;
4 pour chaquey ? ?(x) tel quey /? ?ˆ?(a) faire
5?ˆ?(a) ? ?ˆ?(a) ? {y} ;
6T ? T ? {y} ;
7 ?ˆ??(a) ? ?, T ? {a} ;
8 tant que ?x ? Tfaire
9 T ? T \ {x} ;
10 pour chaquey ? ??1(x) tel quey /? ?ˆ??(a) faire
11?ˆ??(a) ? ?ˆ??(a) ? {y} ;
12T ? T ? {y} ;
13Ca? ? h?ˆ?(a) ? ?ˆ??(a)i ? {a} ;
Exercice 7
Evaluez la complexité de cet algorithme.´
En vous inspirant de l’algorithme ci-dessus, proposez un algorithme pour tester l’existence d’un circuit passant par un sommet donné x dans un graphe donné.
Proposez une variante permettant de détecter un cycle. Donnez la complexité de ces deux algorithmes.
Calcul de la composante connexe
Algo COMPCO ( Données : (E,?,??1);a ? E ; Résultat :Ca )
1: Ca ? {a}; T ? {a}
2: while ?x ? Tdo
3: T ? T \ {x}
4: for all ) tel que y /? Cado
5: a ? a y
6: T ? T ? {y}
7: end for
8: for all ) tel que y /? Cado
9: a ? a ? {y}
10: T ? T ? {y}
11: end for
12: end while
1.4.4 Degrés
Soit un graphe (orienté) G = (E,?) et un sommet x ? E. On définit le degré exterieur de x, noté d+(x) par : d+(x) = |?(x)|
Le degré extérieur est le nombre de successeurs de x. On définit le degré intérieur de G, noté d?(x) par :
d?(x) = |??1(x)|
Le degré intérieur est le nombre de prédecesseurs de x.
Le degré du sommet x est défini par d(x) = d+(x) + d?(x).
Soit un graphe non-orienté G = (E,?) et un sommet x ? E. On définit le degré de x, noté d(x) par :
En d’autres termes, dans un graphe non-orienté, le degré du sommet x est le nombre d’arêtes adjacentes à x.
Démontrez les deux affirmations suivantes :
– La somme des degrés de tous les sommets d’un graphe G quelconque est paire.
– Dans tout graphe, le nombre de sommets de degré impair est pair.
Peut-on tracer dans le plan cinq droites distinctes, telles que chacune d’entre elles ait exactement trois points d’intersection avec les autres? En modélisant ce problème par un graphe, démontrez que cela n’est pas possible.
Voici une affirmation : “dans toute réunion mondaine, il y a au moins deux personnes ayant le même nombre d’amis présents” (on suppose la relation d’amitié symétrique).
Dans le cadre des graphes, à quelle propriété correspond cette affirmation?
Cette propriété est elle fausse ou vraie? Donnez une preuve de ce que vous avancez.
1.5 Représentation matricielle
Soit G = (E,?), avec |E| = n. On peut représenter G par la matrice booléenne M? = [mij]i,j=1 n, dite matrice d’adjacence de G, telle que :
= 1 si j ? ?(i)
= 0 sinon
Exemple 16 : Soit le graphe G = (E,?) suivant :
On définit le produit booléen de matrices à partir des opérateurs ? (ou) et ? (et).
Soient A = [aij]i,j=1 n et B = [bij]i,j=1 n deux matrices booléennes, alors C = A × B = [cij]i,j=1 n est définie par :
Proposition : Soit Mp = M × × M (p fois), ou` M est la matrice booléenne associée
au graphe G. On a : Mijp = 1 ? il existe un chemin de longueur p dans G de i à j.
Exercice 12
Démontrez cette proposition.
Remarque : Pour tout graphe G, il n’existe pas en général de nombre k ? N tel que
. (Par exemple, il suffit de prendre le graphe formé par deux sommets a et b
et deux arcs (a,b) et (b,a)).
Proposition : Soit Mˆ p = I ? M ? M2 ? Mp., ou` I désigne la matrice identité de la
même taille que M.
On a : Mˆijp = 1 ? il existe un chemin de longueur ? p dans G de i à j.
Remarque : Si |E| = n alors ?p ? n ? 1, Mˆ p = Mˆ n? = Mˆ ?.
| Exercice 13 Soit M la matrice booléenne : 0 1 0 0 0 ? 0 0 1 0 0 M = ?? 0 0 0 1 1 ????? ?? 0 0 0 0 0 1 0 0 0 0 A quoi est égal M2006 ? Justifiez votre réponse. On évitera, autant que possible, les calculs! |
G1 G2
On voit que G1 est biparti avec E1 = {1,4,5} et E2 = {2,3}. Le graphe G2 n’est pas biparti.
Exercice 14
Montrez qu’un graphe est biparti si et seulement si il ne contient pas de cycle impair.
Indication : L’implication“biparti ? sans cycle impair”se démontre facilement (par l’absurde). Dans l’autre sens c’est plus dur. On peut penser à choisir un sommet x arbitrairement et, en supposant le graphe connexe, à considérer les longueurs des chaˆ?nes les plus courtes de x à tout autre sommet du graphe.
20
Chapitre 2
Arbres et arborescences
Dans ce chapitre, on considèrera un graphe G antisymétrique.
2.1 Définitions
2.1.1 Isthme
Soit G = (E,~?), u ? ~?. On dit que u est un isthme si sa suppression de ~? augmente le nombre de composantes connexes de G.
Exemple 18 :
G
L’arc u = (A,B) est un isthme. Aucun autre arc de ce graphe n’est un isthme.
Proposition :. L’adjonction d’un nouvel arc u = (a,b) à G
pour donner un nouveau graphe) a pour effet :
- soit de diminuer de 1 le nombre de composantes connexes, dans ce cas u n’appartient à aucun cycle de G? ;
- soit de laisser inchangé le nombre de composantes connexes, dans ce cas u appartient à un cycle de G?.
Démonstration :
- Si a et b appartiennent à deux composantes connexes distinctes, le nombre de composantes connexes diminue de 1. L’arc u ne peut appartenir à un cycle de G? car si on supprime u dans ce cycle, on aurait une chaˆ?ne joignant les deux composantes connexes dans G.
- Si a et b appartiennent à la même composante connexe, le nombre de composantes connexes reste inchangé. La concaténation de la chaˆ?ne joignant a et b dans G et de u donne un cycle dans G?.
Proposition :u est un isthme ? u n’appartient à aucun cycle de G.
Proposition : Soit G = (E,~?), tel que :
1- G connexe ? m ? n ? 1 2- G est sans cycle ? m ? n ? 1.
2.1.2 Arbre
Un arbre est un graphe connexe sans cycle.
Remarque : Un arbre ne comporte pas de boucles. En effet, toute boucle est un cycle.
Remarque : Dans un arbre, chaque arc est un isthme.
Proposition : Soit G = (E,~?), tel que . Les propriétés suivantes
sont équivalentes :
1. G est connexe et sans cycle,
2. G est connexe et m = n ? 1,
3. G est sans cycle et m = n ? 1,
4. G est sans boucles et il existe une unique chaˆ?ne élémentaire joignant tout couple de sommets a et b distincts.
2.1.3 Racine
Soit G = (E,~?), x ? E. On dit que x est une racine de G si ?y ? E \ {x}, il existe un chemin de x à y.
Exemple 19 :
Ce graphe a pour racine D.
Un graphe G est dit quasi fortement connexe si, pour toute paire de sommets distincts x,y de G, on peut trouver un troisième sommet z tel qu’il existe un chemin de z à x et un chemin de z à y.
Montrer que si G est quasi fortement connexe alors G admet une racine.
2.1.4 Arborescences
Soit G = (E,?) un graphe, soit r ? E. Le graphe G est une arborescence de raciner
si :
1. G est antisymétrique, et
2. G est un arbre, et
3. r est une racine de G.
Un sommet d’une arborescence est appelé une feuille s’il n’a aucun successeur.
Montrez que si un graphe G est une arborescence de racine r, alors aucun autre sommet de G n’est une racine de G.
2.1.5 Découpage en niveaux
Une arborescence peut être découpée en niveaux (voir figure 2.1 page suivante).
Proposez une définition formelle de la notion d’“ensemble de sommets de niveau k”d’une arborescence.
Proposez un algorithme pour afficher les ensembles de sommets correspondant aux différents niveaux d’une arborescence (connaissant sa racine). Evaluez sa complexité.´
2.2 Exemples et applications
2.2.1 Fausse monnaie
Soit 8 pièces de monnaies, dont une est fausse (elle est plus légère que les autres). On possède deux balances. La balance 1 permet de savoir quel plateau est le plus lourd et ne possède que deux états (<,?); la balance 2 possède trois états (>, <, =). On cherche à trouver la fausse pièce en minimisant le nombre de pesées. Pour modéliser la résolution de ce problème, on va utiliser une arborescence.
2.2.2 Arborescence de décision
Soit G = (E,~?) une arborescence de racine r ? E. Soit X un ensemble fini (dont les
éléments représenteront pour nous les“possibilités”). On dit que G est une arborescence de décision sur X s’il existe une application f : E ? P(X) telle que : – f(r) = X
– ?a ? E / ?(a) 6= ?, f(a) = Sb??(a)f(b), – ?a ? E / ?(a) = ?, |f(a)| = 1.
Dans le cas de notre exemple de la balance 1, on pose 4 pièces sur chaque plateau. Un des deux plateaux sera forcément moins lourd car il contient une fausse pièce. On prend le lot de 4 pièces les moins lourdes et on le divise en 2 et ainsi de suite. Le nombre de pesées pour trouver la fausse pièce est égale au nombre de niveau du graphe 2.2 page suivante moins 1, soit ici 3.
On peut suivre la même approche pour la balance 2. On aura alors un arbre à 3 niveaux et une solution en deux pesées.
Fig. 2.2 – Arbre de décision pour la balance 1
2.2.3 Arithmétique
On s’intéresse à l’évaluation d’expressions arithmétiques, en respectant les priorités des différents opérateurs. Soit l’expression arithmétique (A) :
Sur l’arbre de la figure 2.3 page suivante correpondant à l’expression (A), chaque sommet du graphe est soit une donnée (symbolique ou numérique), soit un opérateur. Les opérateurs binaires possédent deux successeurs, les opérateurs unaires en possèdent un. Les données n’ont aucun sucesseur, ce sont les feuilles de l’arbre. Le problème est l’ordre d’évaluation, car a ? b 6= b ? a. Il est donc nécessaire d’ordonner les successeurs d’un
sommet.
2.2.4 Arborescence ordonnée
Soit E un ensemble fini, on note O(E) l’ensemble des k?uplets ordonnés d’éléments de E. Un couple G? = (E,??), ou` ?? est une application de E dans O(E) est appelé un graphe ordonné sur E. Ainsi :
?a ? E, ??(a) = (x1, ,xi)
Fig. 2.3 – Arbre d’évaluation arithmétique
A tout graphe ordonné (E,??), on peut faire correspondre le graphe (E,?) tel que ?(a) = {x1, ,xi} = { éléments du k?uplet ??(a)}. On dit que G? = (E,??) est une arborescence ordonnée (ou arborescence plane) si (E,?) est une arborescence.
2.2.5 Arborescence de recherche
Soit D un ensemble appelé domaine, muni d’une relation d’ordre total (que l’on notera ?). Soit X ? D et n ? D. La question que l’on se pose est de savoir si n appartient à l’ensemble X.
On peut par exemple prendre D égal à l’ensemble des chaˆ?nes de caractères alphabétiques, X une partie de ces chaˆ?nes (par exemple l’ensemble des mots d’un dictionnaire), et ? représentant l’ordre lexicographique usuel. On peut aussi, plus classiquement, considérer le domaine D = N et l’ordre habituel sur les entiers naturels.
Si X est représenté sous forme d’une liste, la résolution du problème n ? X? s’effectue en O(|X|) comparaisons entre éléments de D. Si X est représenté sous forme d’un tableau de booléens, la résolution s’effectue en O(1) comparaisons mais l’encombrement mémoire est en O(|D|) (impraticable si le domaine est très grand). Si X est sous forme d’une arborescence binaire, c’est-à-dire que le nombre de successeurs de tout sommet est compris entre 0 et 2, la recherche peut sous certaines conditions s’effectuer en O(log|X|).
Il faut pour cela imposer les conditions suivantes :
– l’arborescence est ordonnée (cf. section 2.2.4).
– pour tout sommet x, toute valeur située dans la sous-arborescence gauche de x est inférieure à la valeur associée à x, et toute valeur située dans la sous-arborescence droite de x est supérieure à la valeur associée à x.
Une arborescence binaire respectant les conditions ci-dessus est appelée arborescence de recherche.
Il faut de plus que l’arborescence soit équilibrée, autrement la recherche s’effectue dans le pire des cas en O(|X|).
Exemple 20 :
Arborescence de recherche pour la relation ? définie sur le domaine N, avec X = {6,8,9,12,15,13,17}.
Ecrivez en pseudo-langage un algorithme permettant de tester la présence d’une valeur´ donnée v dans une arborescence de recherche.
Ecrivez deux programmes récursifs, l’un permettant d’afficher les valeurs d’une arbores-´ cence de recherche dans l’ordre croissant, l’autre dans l’ordre décroissant.
2.3 Arbre de poids extrémum
2.3.1 Graphe Pondéré
Soit G = (E,~?), un graphe connexe et sans boucles. Soit P une application de ~? ? R. Soit u ? ~?, P(u) est appelé poids de l’arc u.
) est appelé graphe pondéré. Soit ~ ~? un graphe partiel de G, P(??) = Pu?~?? P(u) définit le poids du graphe partiel ??.
Etant donné un graphe non orienté dont les arêtes sont munies d’une valuation, on cherche un graphe partiel de ce graphe qui soit un arbre et qui soit de poids maximum. Puisqu’il s’agit d’un graphe partiel, cet arbre a pour ensemble de sommets E tout entier. On appelle arbre couvrant un tel arbre.
Soit (E,) un graphe partiel de G qui soit un arbre. On dit que (E,) est un arbre de poids maximum sur ? tel que (E,) soit un arbre, on a la relation
suivante :
P(~???) ? P(~??)
Soit (E,~??) un graphe partiel de G qui soit un arbre. On dit que (E,~??) est un arbre de poids minimum sur ~? tel que (E,) soit un arbre, on a la relation
suivante :
P(~???) ? P(~??)
Exemple 21 :
Un graphe pondéré G et des arbres de poids maximum sur G.
Proposition : Un arbre de poids maximum pour) est un arbre de poids
minimum pour
Remarque : On peut se demander combien d’arbres différents on peut construire à partir
de n sommets. Cayley a apporté la réponse en 1889 : on peut construire nn?2arbres couvrant n sommets.
Remarque : Une méthode na¨?ve pour trouver un arbre de poids maximum pour un graphe
G consiste à construire tous les graphes partiels de G qui sont des arbres et à évaluer leur poids. On voit d’après la remarque précédente que cette méthode a une complexité exponentielle.
2.3.2 Propriétés des arbres de poids maximum
Soit (E,~?) un graphe connexe et sans boucle. Soit P l’application de pondération associée à ce graphe. Soit A~ ? ~? tel que (E,A~) soit un arbre.
Soit u = (x,y) un arc appartenant à ~? mais non à A~, on nomme Cu l’ensemble des sommets constituant la chaˆ?ne dans A~ ayant pour extrémités x et y.
Soit v un arc appartenant à A~, on nomme ?v l’ensemble des arcs de ayant leurs extrémités dans les deux composantes connexes de (E,A~ \ {v}).
Proposition : Les deux propriétés suivantes sont équivalentes et caractérisent un arbre
de poids maximum :
1. ?u ? ~? \ A~, P(u) ? min??Cu P(?).
2. ?v ? A~, P(v) ? max???v P(?).
Exemple 22 : On se propose d’étudier le graphe suivant :
On veut vérifier si l’arbre representé par les arcs en pointillés est bien un arbre de poids maximum.
| Cu1 = {v1,v2} | ?v1 = {u1} |
| Cu2 = {v2,v3} | ?v2 = {u1,u2,u3} |
| Cu3 = {v2,v3,v4} | ?v3 = {u2,u3,u4} |
| Cu4 = {v3,v4} | ?v4 = {u3,u4} |
P(u1) = 3 > min??Cu1P(?) = min{5,2} = 2, la propriété 1 n’est pas vérifiée.
P(v2) = 5 < max???v2P(?) = max{3,?1,6} = 6, la propriété 2 n’est pas vérifiée. L’arbre representé n’est donc pas un arbre de poids maximum.
Remarque : L’idée consiste à remplacer l’arête étudiée par celle contredisant la propriété
1 ou 2. Si tel était le cas nous obtiendrions un arbre de poids strictement supérieur.
Démonstration :APMAX ? 1
Supposons que A~ est un APMAX sur (E,) et il existe tel que P(u) > minw?Cu(P(w)). Soit v ? Cu tel que p(v) = minw?Cu(P(w)). Alors est un arbre sur E (sans cycles (facile à justifier) et n?1 arcs) et de plus P(A?) > P(A) : contradiction.
Compléter la démonstration.
Nous allonsétudier des algorithmes qui permettent d’extraire les arbres de poids maximum d’un graphe. La construction d’arbres couvrants de poids minimum relève des mêmes algorithmes, il suffit juste d’utiliser la relation d’ordre inverse.
2.3.3 Algorithme de Kruskal 1
Soit G = (E,~?) un graphe connexe et sans boucle, et P une application de pondération de ~? sur R. On note avec ?i,P(ui) ? P(ui+1) (les sommets sont triés par ordre décroissant).
Proposition : Soit la famille définie par :
si (E,) est sans cycles
sinon
Alors est un arbre de poids maximum.
Démonstration : Chaque se construit en rajoutant un arc ui qui ne fait pas apparaˆ?tre de cycle dans (E,~?i). Par conséquent, le graphe partiel résultant () ne contient pas
de cycle.
Montrons que le graphe partiel (E,) est connexe. Par l’absurde, supposons qu’il y ait k = 2 composantes connexes distinctes (le cas 2 se déduit aisément). Comme ( est connexe, il existe une arête tel que (E,?m ?{u}) soit connexe. Comme par définition cette arête est un isthme dans (E,), elle n’appartient à aucun cycle de
) et a fortiori de (; et aurait duˆ être insérée par l’algorithme, d’ou` une contradiction. Le graphe partiel obtenu est connexe et sans cycle, il s’agit donc d’un arbre.
Il reste à démontrer que cet arbre est de poids maximum.
Compléter la démonstration.
Indication : On pourra raisonner par l’absurde, et utiliser la propriété 2 de la section 2.3.2.
Remarque : Il est inutile de calculer tous les , il suffit de s’arrêter dès lors que
|E| ? 1.
Mise en œuvre
La mise en œuvre de l’algorithme de Kruskal 1 se déroule en deux phases :
– Trier les arêtes par ordre des poids décroissants,
– Tant que l’on n’a pas retenu n?1 arêtes, procéder aux opérations suivantes : considérer dans l’ordre du tri la première arête non examinée. Si elle forme un cycle avec les arêtes précedemment choisies, la rejeter; sinon la garder.
Complexité
Il faut d’abord constituer une liste triée par ordre décroissant des arcs du graphe. Cette opération s’effectue —par des algorithmes de tri classiques [Cormen]— en O(m.log(m)). Le test du caractère sans cycle est en O(n+ m) (voir l’exercice 7) et doit être effectué au pire pour les m arêtes. La complexité de l’algorithme de Kruskal 1 (sous cette forme) est en :
O(m.(n + m) + m.log(m)) = O(m.(n + m))
Exemple 23 :
Un graphe pondéré G et l’unique arbre de poids maximum sur G.
Exécutez “à la main” l’algorithme de Kruskal 1 sur le graphe de l’exemple 23, ou sur un graphe de votre choix.
Remarque : Le test pour savoir si un graphe est sans cycles peut être remplacé par une
recherche de composantes connexes. Pour chaque arête que l’on est en train d’examiner, on regarde dans le graphe en cours de construction si les deux extrémités de l’arête sont dans la même composante connexe ou non. En utilisant une structure de données adaptée (ensembles disjoints, voir [Cormen]) il est possible de réduire le couˆt de ce test à une quasi-constante. La complexité de Kruskal 1 est alors dominée par celle du tri.
2.3.4 Algorithme de Kruskal 2
Cet algorithme procède de fac¸on similaire, mais au lieu de construire un nouveau graphe en ajoutant en priorité les arcs les plus lourds, il procède en enlevant du graphe d’origine les arcs les plus légers, à condition de préserver la connexité.
Dans cette variante, les arcs doivent donc être triés par ordre croissant. La complexité de l’algorithme de Kruskal 2 est la même que celle de Kruskal 1.
On note avec ?i,P(ui) ? P(ui+1) (les sommets sont triés par ordre croissant).
Proposition : Soit la famille définie par :
si (E,) est connexe
sinon
Alors est un arbre de poids maximum.
Exécutez “à la main” l’algorithme de Kruskal 2 sur le graphe de l’exemple 23, ou sur un graphe de votre choix.
Exercice 24
Démontrez cette proposition.
2.3.5 Algorithme de Prim
Définition: Soit (E,?) un graphe, soit X ? E, on considère : - l’ensemble des arcs sortant deX :
??? (X) = { u ? ~? | ?x ? X,?y ? E \ X,u = (x,y)}
- l’ensemble des arcs entrant dansX :
??? (X) = {u ? ~? | ?x ? X,?y ? E \ X,u = (y,x)}
- l’ensemble des arcs frontière deX :
?? ??
?(X) = ? (X) ? ? (X)
Soit (E,?) un graphe connexe sans boucle, n = |E| et x ? E. On considère les familles
(Ei)1?i?n et (~?i)1?i?n définies par :
- E1 = {x}, ?1 = ?
- avec u ? ?(Ei?1) tel que p(u) = max{p(v) | v ? ?(Ei?1)}
- soit y l’extrémité de u non dans Ei?1, Ei = Ei?1 ? {y}
Alors : (E,) est un APMAX
Ecrivez l’algorithme de´ Prim en utilisant le pseudo-langage habituel. Exécutez “à la main” l’algorithme de Prim sur le graphe de l’exemple 23, ou sur un graphe de votre choix. Déterminez sa complexité.
Chapitre 3
Plus courts chemins
On considère dans ce chapitre des graphes orientés.
3.1 Définition
3.1.1 Réseau
Nous allons travailler sur un graphe sans boucle G = (E,~?) et une application l de ~? dans R. L’application l associe à chaque arc u un réel l(u) appelé longueur de l’arc u. Le triplet R = (E,~?,l) est appelé un réseau.
Par simplicité, si u = (x,y), on notera l(x,y) la longueur de u (plutôt que l((x,y)), correct mais lourd).
Soit ? = (x0,x1,···xn) un chemin dans G. On définit la longueur de?(dansR) comme la somme des longueurs des arcs de ?, autrement dit :
l(?) = X? ? l(xi,xi+1)
0?i n 1
3.1.2 Plus court chemin
Soient x et y deux sommets de E. Un chemin ? de x à y dans R est un plus court chemin dexày si pour tout chemin ?? de x à y, on a l(?) ? l(??).
Dans la recherche d’un plus court chemin de x à y, trois cas peuvent se présenter :
– Il n’existe aucun chemin de x à y (par exemple, si x et y appartiennent à deux composantes connexes différentes de G).
– Il existe des chemins de x à y mais pas de plus court chemin.
– Il existe un plus court chemin de x à y.
Exemple 24 :
Il existe des chemins (combien?) de x à y, mais il n’existe pas de plus court chemin de x à y. C’est-à-dire que pour tout chemin ? de x à y, on peut trouver un chemin ?? tel que l(??) < l(?). Il existe un plus court chemin de x à z mais pas de chemin de z à x.
Remarque : Un plus court chemin dans est un plus long chemin dans R? =
, et réciproquement.
Circuit absorbant
Un circuit de longueur négative est appelé circuit absorbant. Dans l’exemple précédent, il existe un circuit absorbant.
Remarque : Si une composante fortement connexe présente un circuit absorbant, alors il
n’existe pas de plus court chemin entre deux sommets quelconques de cette composante.
Proposition : Soit ) un réseau. Soit s ? E, une condition nécessaire et
suffisante pour qu’il existe un plus court chemin entre s et tout sommet de E \ {s} est :
1. s est une racine de (E,~?), et
2. il n’y a pas de circuit absorbant dans R.
3.2 Problématique du plus court chemin
Proposition : Soit R un réseau, soit c = (x0, ,xk) un plus court chemin de x0 à xk et
soit c? = (xi, ,xj), 0 ? i < j ? k, un sous-chemin extrait de c, alors c? est un plus court chemin de xi à xj.
Remarque : Il s’agit ici de la propriété très importante d’optimalité des sous-chemins.
Exercice 26
Démontrez cette proposition :
1) par l’absurde,
2) par une preuve directe.
3.2.1 Graphe des plus courts chemins
Soit) un réseau sans circuit absorbant, soit i ? E. On définit l’application ?i : E ? R ? {?} par :
la longueur d’un plus court chemin de i à x s’il en existe
i( ) =
? sinon
Soit (E,~??) le graphe défini par :
Le graphe (E,) est appelé graphe des plus courts chemins relativement au sommet i. L’ensemble ?? est constitué des arcs faisant partie d’un plus court chemin de i à un sommet de E.
Proposition : Un plus court chemin de i à x dans R est un chemin de i à x dans (E,
Exemple 25 :
On peut construire “à la main” l’application ?x0 :
| x | ?x0(x) |
| x0 | 0 |
| x1 | 3 |
| x2 | ? |
| x3 | 7 |
| x4 | 5 |
| x5 | 6 |
| x6 | 8 |
Le graphe des plus courts chemins est alors :
Arborescence des plus courts chemins
Soit) un réseau sans circuit absorbant. Soit) le graphe des plus courts chemins défini précédemment. On dit que () est une arborescence des plus courts chemins pour R si :
– , et
) est une arborescence de racine i, et
– A ? ??.
Remarque : En général une arborescence des plus courts chemins n’est pas un arbre de
poids minimum.
Exemple 26 :
R APCC APMIN
3.3 Réseaux à longueurs quelconques (Bellman)
Nous allons étudier l’algorithme de Bellman pour calculer les longueurs de plus courts chemins dans un réseau à longueurs quelconques. Cet algorithme calcule la longueur des plus courts chemins d’un sommet inital i à tout autre sommet x du graphe.
But : soit, calculer ?i.
L’idée est qu’un chemin de i à x dans R passe nécessairement par un sommet y? ? ??1(x). La longueur d’un plus court chemin de i à x passant par y? est :
?i(x) = ?i(y?) + l(y?,x)
Et donc, on a la propriété suivante, dite propriété de Bellman.
Proposition :
?i(x) = min {?i(y) + l(y,x)}
y???1(x)
3.3.1 Algorithme en pseudo language
Pour alléger les notations, on notera dans la suite ? = ?i, sauf en cas de nécessité.
Algo BELLMAN ( Données :E,??1,l,i ? E ; Résultats :?,CIRCABS )
1: CIRCABS = FAUX ; ?0(i) = 0; ?1(i) = 0; k = 1
2: for allx ? E \ {i} do
3: ?0(x) = ?
4: ?1(x) = ?
5: end for
6: for allx ? E tel que i ? ??1(x) do
7: ?1(x) = l(i,x)
8: end for
9: whilek < n + 1 et ?x ? E tel que ?k(x) 6= ?k?1(x) do
10: k = k + 1
11: for all
12: ? (x) = min ??1(x),??1(y) + (y,x);y ? ??1(x)
13: end for
14: end while
15: ifk = n + 1 then
16: CIRCABS = V RAI
17: end if
18: ? = ?k
Cet algorithme renvoie également dans la variable CIRCABS un booléen indiquant la présence d’un circuit absorbant.
Complexité
– L’initialisation de la ligne 1 est en temps constant O(1)
– La boucle d’initialisation des lignes 2 à 5 est en O(n)
– La boucle d’initialisation des lignes 6 à 8 est en O(n + m)
– Le corps de boucle principale est executé n + 1 fois au maximum. La complexité de la ligne 9 est en O(n2) et le corps de la boucle 10 à 14 est en O(n(n + m)).
Au total, la complexité de l’algorithme de Bellman est O(n(n + m)).
Remarque : La complexité de l’algorithme de Bellman dans le cas d’un graphe dense
(m ? n2) est donc O(n3). Il existe des variantes plus efficaces, toutefois notons que celle-ci peut facilement être parallélisée.
3.3.2 Justification
L’idée est que la longueur d’un plus court chemin du sommet i à n’importe quel sommet x est imposée par :
?(x) = min {?(y) + l(y,x)}
y???1(x)
Cette formule locale est appliquée jusqu’à convergence (ou jusqu’à n itérations, dans ce cas il y a présence d’un circuit absorbant).
On appelle k?chemin un chemin possédant au plus k arcs. Dans cet algorithme, ?k(x) représente la longueur d’un plus court k?chemin de i à x (s’il en existe, ? sinon). Pour prouver cette proposition, nous allons procéder par récurrence.
La proposition est trivialement vérifiée pour k = 0 et k = 1. Supposons qu’elle est vérifiée jusqu’à l’étape k ? 1 et plac¸ons-nous à l’étape k. Soit Ck l’ensemble des sommets y tels qu’il existe un k?chemin de i à y.
– Si x /? Ck, ?y ? ??1(x), y /? Ck?1. Donc d’après l’hypothèse de récurrence, ?y ? ??1(x)?k?1(y) = ?, d’ou` ?k(x) = ?.
– Si x ? Ck et x 6= i alors ?y ? ??1(x) tel que y ? Ck?1. Donc ?k?1(y) < ?. Tout k?chemin de i à x passe par un y ? ??1(x). Un plus court k?chemin de i à x est composé d’un plus court (k ? 1)?chemin de i à un sommet y ? ??1(x) et de l’arc (y,x). Il a pour longueur ?k?1(y) + l(y,x). La longueur d’un plus court k?chemin de i à x est donc :
min ?k?1(y) + l(y,x)
y???1(x)
De plus, la longueur d’un plus court k-chemin de i à x ne peut être supérieure à celle d’un plus court (k ?1)-chemin de i à x (puisqu’un (k ?1)-chemin est aussi un k-chemin), d’ou` l’instruction de la ligne 12.
On peut facilement voir que s’il existe un plus court chemin ? de i à x alors il existe un plus court chemin de i à x qui est un chemin élémentaire (en effet si ? comporte un circuit de longueur positive ou nulle, alors en ôtant ce circuit de ? on obtient un chemin de longueur inférieure ou égale à l(?)). Or un tel chemin possède au plus n?1 arcs (avec n = |E|). Donc s’il n’existe pas de circuit absorbant, on a ?k ? n, ?k = ?n?1.
Par conséquent, si ?n 6= ?n?1, alors le graphe présente un circuit absorbant.
Remarque : Pour implémenter l’algorithme de Bellman, il suffit de deux tableaux :
?courant et ? précédent.
Proposez un algorithme qui prend en entrée un réseau R et un couple de sommets (i,j), et qui retourne en sortie un chemin (liste ordonnée de sommets) de longueur minimale de i à j s’il en existe.
Indication : On commencera par calculer les longueurs ?i(x) pour tous les sommets x par l’algorithme de Bellman.
3.4 Réseaux à longueurs positives (Dijkstra)
L’algorithme de Dijkstra permet de trouver les longueurs des plus courts chemins d’un sommet donné i à tous les autres sommets dans un réseau (E,?,l) à longueurs positives. Dans un tel réseau on a l’équivalence suivante :
il existe un chemin de x à y ? il existe un plus court chemin de x à y
pour tout couple de sommets (x,y). Cette équivalence est due au fait qu’il n’existe pas de circuit absorbant.
Le principe de l’algorithme est le suivant :
Soit), avec pour tout 0. Soit i ? E sommet initial. On désigne par S l’ensemble des sommets x de E pour lesquels la longueur d’un plus court chemin de i à x a été calculée. Initalement S = {i}, ?(i) = 0.
On appelle S?chemin un chemin partant de i et ayant tous ses sommets dans S sauf le dernier.
Soit Y = E \ S. Pour tout sommet y dans Y , on désigne par ??(y) la longueur d’un plus court S?chemin de i à y. On sélectionne y? dans Y tel que ??(y?) = min{??(y),y ? Y }. On est alors assuré que ??(y?) = ?(y?).
Exercice 29
Expliquez pourquoi cette dernière affirmation est vraie.
3.4.1 Algorithme en pseudo language
Algo DIJKSTRA ( Données :E,?,l,i ? E ; Résultats :?,S )
1:S = {i}, ?(i) = 0, k = 1, x1 = i
2: for allx ? E \ {i} do
3: ?(x) = ?
4: end for
5:whilek < n et ?(xk) < ? do
6: for ally ? ?(xk) tel que y /? Sdo
7: ?(y) = min[?(y),?(xk) + l(xk,y)]
8: end for
9: Extraire un sommet x /? S tel que ?(x) = min{?(y),y /? S} 10:k = k + 1, xk = x, S = S ? {xk}.
Complexité
Nous prendrons S sous la forme d’un tableau de booléens. – Les boucles d’initialisation des lignes 1 et 2 à 4 sont en O(n) – La boucle principale (ligne 5) est executée n fois.
– Les lignes 6 et 7 sont en O(n + m).
– La ligne 9 est en O(n2) (si on l’implémente na¨?vement).
La complexité de l’algorithme de Dijsktra (sous cette forme) est en O(n2). Il est facile, en utilisant une structure de données adaptée (par exemple un arbre de recherche équilibré, voir [Cormen]) pour la ligne 9, de ramener cette complexité à O(nlog(n) + m). Il existe des implémentations encore plus efficaces.
3.4.2 Réseaux à longueurs uniformes
Nous nous plac¸ons dans le cas d’un réseau R = (E,?,l) tel que pour tout arc u dans ~?, la longueur de l’arc soit égale à une constante strictement positive. On prendra l(u) = c = 1.
Comme pour Bellman et Dijkstra, on fixe un sommet initial i. Pour trouver la longueur d’un plus court chemin de i à tout autre sommet x, il existe un algorithme en temps linéaire O(n+m). Cet algorithme s’appuie sur une stratégie d’exploration du graphe dite d’exploration-largeur. Il consiste à parcourir le graphe “par couches successives” à partir de i et de proche en proche en suivant les arcs non déjà utilisés. La longueur du plus court chemin à x est alors le nombre de couches parcourues pour aller de i à x (multiplié par la constante c).
Exercice 31
Ecrivez cet algorithme en pseudo-langage et évaluez sa complexité.´
3.5 Graphes et réseaux sans circuits
3.5.1 Définition
Un graphe sans circuit (ou GSC) est comme son nom l’indique un graphe ne contenant aucun circuit. Si G = (E,?) est un graphe sans circuit alors son symétrique (E,??1) l’est aussi.
Dire qu’un graphe G = (E,?) est un graphe sans circuit équivaut à dire que toutes les composantes fortement connexes de G sont réduites à un seul sommet. C’est une des caractérisations des GSC.
3.5.2 Sources et puits
Soit G = (E,?) un graphe sans circuit et x ? E.
On dit que x est une source de G si d?(x) = |??1(x)| = 0. On dit que x est un puits de G si d+(x) = |?(x)| = 0.
Autrement dit, une source est un sommet sans prédécesseur, et un puits est un sommet
sans successeur.
Proposition : Tout GSC fini possède au moins une source et un puits.
Exercice 32
Démontrez cette propriété, et donnez-en un contre-exemple dans le cas infini.
3.5.3 Rang et hauteur
Soit G = (E,?) un graphe quelconque, et x un sommet de E. Le rang du sommet x, noté r(x) est la longueur maximale d’un chemin élémentaire se terminant par x.
Soit G = (E,?) un graphe quelconque, et x un sommet de E. La hauteur du sommet x, noté h(x) est la longueur maximale d’un chemin élémentaire débutant en x.
Exemple 27 : Soit le graphe G :
Le rang du sommet 2 est 0, le rang du sommet 4 est 3, la hauteur du sommet 4 est 0, la hauteur du sommet 2 est 3.
Dire que r(x) = 0 équivaut à dire que x est une source. De même, si h(x) = 0 alors x est un puits, et réciproquement.
3.5.4 Partition en niveaux
Rappel : Soit E un ensemble quelconque, et E0, ,Ep une famille finie de sous-ensembles de E. On dit que est une partition de et si les Ei sont tous disjoints deux à deux.
Soit G = (E,?) un graphe quelconque. Le graphe G admet une partition en niveaux s’il existe une partition de E telle que :
ou` E0 est l’ensemble des sources de est l’ensemble des sources de (E\[E0?
? Ei?1],~?i), ~?i étant la restriction de G à E \ [E0 ? ? Ei?1] (c’est-à-dire l’ensemble des arcs de ~? ayant leurs 2 extremités dans E \ [E0 ? ? Ei?1]).
Proposition : Un graphe admet une partition en niveaux si et seulement si c’est un
graphe sans circuit.
Proposition : Soit G = (E,?) un graphe. Si elle existe, la partition en niveaux
de G est unique et telle que pour tout sommet x appartenant à Ei, r(x) = i.
Exercice 33
Démontrez ces deux propriétés.
3.5.5 Algorithme circuit-niveaux
Voici un algorithme qui permet de déterminer la partition en niveaux d’un graphe G = (E,?), ou de détecter la présence d’un circuit.
Remarque : Dans la littérature anglo-saxonne, cet algorithme est appelé tri topologique
(topological sort), et les GSC sont appelés DAG (Directed Acyclic Graphs).
Algo CIRCUIT-NIVEAUX ( Données :E,?,??1 ; Résultat :Ei ? E,CIRC )
1:E0 = ?,N = 0,i = 0
2: for allx ? Edo
3: d?(x) = |??1(x)|
4: end for
5: for allx ? E tel que d?(x) = 0 do
6: E0 = E0 ? {x}
7: N = N + 1
8: end for
9:whileN < n et Ei 6= ? do
10: Ei+1 = ?
11: for allx ? Eido
12: for ally ? ?(x) do
13: d?(y) = d?(y) ? 1 14: ifd?(y) = 0 then
15: Ei+1 = Ei+1 ? {y}
16: N = N + 1
17: end if
18: end for
19: end for
20: i = i + 1
21: end while
22: ifN < nthen
23: CIRC = V RAI
24: else
Exécutez “à la main” cet algorithme sur un graphe de votre choix comportant au moins un circuit.
Exercice 36
Evaluez la complexité de cet algorithme.´
3.5.6 Plus courts chemins dans les réseaux sans circuits
Dans le cas d’un réseaux sans circuit, le calcul des longueurs des plus courts chemins depuis un sommet i peut se faire en temps linéaire (complexité O(n + m)) grâce à l’algorithme suivant, dérivé de Bellman. Le calcul des rangs doit être effectué préalablement (algorithme linéaire CircuitsNiveaux), et un tri par dénombrement (voir [Cormen]) des sommets selon les rangs croissants peut être réalisé en temps linéaire également.
Algorithme 6 : BellmanSansCircuit
Données : E = {x1 = i,x2, ,xn},??1,?; avec i racine et les sommets de E triés suivant leur rang croissant Résultat : ?
1 ?(i) ? 0; j ? 2 ;
2 tant quej ? nfaire
Exercice 37
Démontrez que chaque valeur ?(x) calculée par cet algorithme est bien la longueur d’un plus court chemin de i à x.
Chapitre 4
Flots et réseaux de transport
Les applications visées sont par exemple : les réseaux de transport routier, ferroviaire, de marchandises, de gaz, d’eau, de pétrole, d’électricité, d’information
4.1 Modélisation du réseau de transport
Un réseau de transport est constitué par :
– un graphe (E,~?),
– un puits p ? E,
– une source s ? E \ {p},
– une application c de ~? dans R+ ? {?}. Pour tout u dans ?, ) est appelé capacité de u. Typiquement c(u) représente le débit maximal pouvant transiter par l’arc u.
4.1.1 Modélisation du traffic (flot)
Soit f une application . La valeur f(u) représente le débit, supposé constant, sur l’arc u. Si u = (x,y) on note f(u) = f(x,y).
On définit également les applications f+ et f? sur E définies par :
f+(x) = X f(x,y)
y??(x)
f?(x) = X?1 f(y,x)
y?? (x)
4.1.2 Equilibre global´
La propriété d’équilibre global énonce que la somme de toutes les quantités entrantes est égale à la somme de toutes les quantités sortantes, plus précisément :
X? f+(x) = X? f?(x)
x E x E
Remarque : Cette propriété est automatiquement vérifiée pour tout graphe et pour toute
application f.
4.1.3 Equilibre local´
La propriété d’équilibre local énonce que pour tout sommet x de E, la somme des quantités entrant dans x est égal à la somme des quantités sortant de x, soit :
?x ? E f+(x) = f?(x)
La fonction f est un flot sur (E,~?) si elle vérifie la propriété d’équilibre local.
4.1.4 Arc de retour
Soit R = (E,~?,p,s,c) un réseau de transport et f un flot sur (E,~? ? {(p,s)}). L’arc (p,s) est appelé arc de retour. La quantité f(p,s) est appelée valeur du flot. Par la propriété d’équilibre, on voit que la valeur du flot est égale à la quantité qui transite par le réseau de la source jusqu’au puits.
4.1.5 Flot compatible avec un réseau de transport
Le flot f est compatible avec le réseauR si pour chaque arc, le flot passant par cet arc est inférieur ou égal à la capacité de cet arc; autrement dit si ?u ? ~?, f(u) ? c(u).
Exemple 28 :
non maximal compatible avec R
Soit R un réseau de transport. Le problème du flot maximum est de trouver un flot f qui soit compatible avec R et de valeur maximale.
4.2 Algorithme de Ford et Fulkerson
Cet algorithme a pour but de trouver un flot maximal compatible avec un réseau donné R. L’algorithme de Ford et Fulkerson procède par améliorations succesives du flot f, en partant d’un flot compatible. Le flot nul par exemple est compatible et peut servir comme flot initial.
Un arc u ? ~? est dit saturé si f(u) = c(u). On ne peut plus augmenter le flot passant sur cet arc. Un flot est dit complet si tout chemin de s à p passe au moins par un arc saturé. Pour améliorer un flot compatible, on peut chercher s’il un chemin de s à p sur lequel aucun arc n’est saturé.
Supposons qu’il existe un chemin ? de s à p tel qu’aucun arc de ? n’est saturé. On appelle r(?) la valeur résiduelle de ? le nombre :
r(?) = min{c(u) ? f(u),u dans ?}
Le flot f sur le réseau R peut alors être amélioré de r(?) (on augmente f de r(?) sur tous les arcs de ? et sur l’arc de retour (p,s)).
Il est tentant d’affirmer qu’un flot complet est obligatoirement maximal. Avant de lire la suite, essayez de chercher par vous-même un contre-exemple à cette affirmation.
Exemple 29 :
Un réseau R (à gauche) et un flot f compatible (à droite).
Le flot de l’exemple 29 est complet (tous les chemins de s à p ont une valeur résiduelle nulle) mais n’est pas maximal. Il existe un flot de valeur 4 qui lui, est maximal.
On voit par là que le problème de la recherche d’un flot maximal n’est pas facile, en particulier il ne suffit pas de rechercher des chemins composés d’arcs non saturés pour trouver toutes les possibilités d’améliorer un flot.
4.2.1 Réseau d’écart
L’algorithme de Ford et Fulkerson utilise un réseau auxiliaire appelé réseau d’écart pour améliorer le flot courant. Le réseau d’écart associé à R est défini par :
Pour tout arc u = (x,y) ? ~?, on associe au plus 2 arcs dans le réseau d’écart :
• u+ = (x,y) et tel que c(u+) = c(u)?f(u), si u est non saturé. C’est l’arc direct associé à u.
• u? = (y,x) et tel que c(u?) = f(u), si f(u) > 0. C’est l’arc rétrograde associé à u.
Soit ? un chemin de s à p dans le réseau d’écart R. On appelle capacité résiduelle de ? le minimum des capacités c(u) pour tous les arcs u de ?. Tout chemin de s à p dans le réseau d’écart fournit un moyen d’augmenter le flot.
Construire le réseau d’écart associé au réseau et au flot de l’exemple 29. En déduire un flot de valeur supérieure.
4.2.2 Algorithme
Algo FORD & FULKERSON ( Données :R = (E,~?,p,s,c); Résultat :fk )
0. Initialisation
Soit k = 0, et soit f0 un flot compatible avec R (par exemple le flot nul).
1. Recherche d’un moyen d’améliorer le flot courantfk
Soit fk le flot courant. Soit) le réseau d’écart associé à R et fk. On recherche
un chemin ?k de s à p dans le réseau d’écart R. S’il n’existe pas de chemin, alors l’algorithme s’arrête et fk est un flot maximal.
2. Amélioration du flot courant
Soit ?k la capacité résiduelle de ?k, autrement dit ?k = min{c(u),u dans ?k}).
Pour tout arc u dans ?k, on applique les règles suivantes :
– si u+ est un arc direct dans, alors fk+1(u) = fk(u) + ?k, – si u? est un arc rétrograde dans, alors fk+1(u) = fk(u) ? ?k.
Faire fk+1(p,s) = fk(p,s) + ?k ;
Faire k = k + 1; Retourner en 1.
4.2.3 Preuve de l’algorithme de Ford et Fulkerson
Soit G = (E,~?) et F ? E. On note ~?+(F) l’ensemble des arcs sortant de F, et ~??(F) l’ensemble des arcs entrant dans F. Plus précisément,
~?+(F) = {(x,y) ? E × E | x ? F , y /? F}
~??(F) = {(x,y) ? E × E | x /? F , y ? F}
Par conséquent, ~??(F) = ~?+(E \ F).
Soit ) un réseau de transport. On appelle coupe sur R un ensemble d’arcs S~ ? ? de la forme S = ?+(F) avec F ? E, s ? F, p /? F.
On appelle capacité de la coupe S~ la quantité c(S~) = Pu?S~ c(u).
Proposition : Soit) un réseau de transport. Pour tout flot f compatible
avec R et pour toute coupe S sur R, on a
Démontrez cette proposition.
Indication : Utiliser la conservation du flux (propriété d’équilibre local, que l’on généralisera à une partie F de E).
Proposition : Quand l’algorithme de Ford et Fulkerson se termine, le flot courant est
maximum.
Démontrez cette proposition.
Indication : Utiliser la propriété précédente, en utilisant la coupe induite par la partie
F = {x ? E | il existe un chemin de s à x dans R}.
Proposition : Si les capacités sont des multiples entiers d’un réel strictement positif et
s’il existe une coupe de capacité finie, alors l’algorithme de Ford et Fulkerson se termine après un nombre fini d’itérations.
Démontrez cette proposition.
La proposition suivante a une importance particulière puisqu’elle permet de montrer l’équivalence de deux problèmes : la recherche d’un flot maximum et celle d’une coupe minimum. Elle se déduit facilement de ce qui précède.
Proposition : (théorème de la coupe minimum)
Soit R = (E,~?,p,s,c) un réseau de transport. La valeur maximum de f(p,s) pour un flot f compatible est égale à la capacité d’une coupe de capacité minimum.
Exercice 42
Démontrez cette proposition.
Chapitre 5
Résolution de problèmes en intelligence artificielle et optimisation combinatoire
Cette partie est plus informelle que les précédentes. Elle vise à donner un avant-gouˆt de ces applications de la théorie des graphes, mais ne prétend nullement faire le tour de la question. Pour aller plus loin, on se reportera à [Nilsson].
5.1 Exemple 1 : le problème des 8 reines
On se place dans le cas d’un échiquier standard (de taille 8×8). Le problème est de placer 8 reines sur cet échiquier de telle sorte qu’aucune reine ne peut se faire prendre par une autre (une reine peut capturer toutes les pièces se trouvant sur sa rangée, sa colonne ou ses diagonales).
La figure 5.1 page suivante présente le placement de 2 reines sur un échiquier. On voit que le nombre de cases disponibles pour le placement de 6 autres reines est très restreint.
Voici deux approches possibles pour le placement des huit reines :
1. Recherche aveugle : On place la n-ième reine sur une case choisie aléatoirement parmis les cases libres (une case est dite libre si elle n’est ni occupée, ni “menacée” par une reine). A un moment, il n’y aura plus de cases libres pour le placement des reines. S’il reste des reines à placer, il y aura alors remise en cause d’un ou de plusieurs choix faits précédemment (retour arrière).
2. Recherche heuristique : On place la n-ième reine sur une des cases restées libres, de telle manière que le nombre de cases “menacées” (susceptibles d’être prises par cette reine) soit minimal. Autrement dit, on cherche à maximiser à chaque étape le nombre de cases libres restantes.
Fig. 5.1 – Exemple de placement pour le jeu des 8 reines
5.2 Graphe de résolution de problème
Les problèmes que l’on cherche à résoudre par cette approche consistent à faire évoluer un système, d’un état dit initial à l’un des états dits terminaux ou buts, au moyen d’un ensemble de règles.
Dans l’exemple précédent, le système est un échiquier portant un certain nombre de reines. L’état initial est l’échiquier vide, les états terminaux sont les configurations de 8 reines ne se menac¸ant pas mutuellement.
Un graphe de résolution de problème ou GRP est un graphe dont les sommets sont les états possibles du problème. Il y a un arc u = (i,j) dans le graphe si une règle permet de passer de l’état i à l’état j. On associe un couˆt c(u) à cet arc. On doit distinguer le sommet initial et les sommets terminaux.
Formellement, un graphe de résolution de problème est un quintuplet (S,?~ ,d,B,c) :
– S est l’ensemble des sommets du graphe (ou états du problème),
– ?~ l’ensemble des arcs,
– d ? S le sommet de départ (état inital du problème),
– B ? S l’ensemble des sommets buts,
– c : ? ??~ R, ou` c(i,j) est le couˆt de l’application de la règle permettant de passer de l’état i à l’état j.
Pour un même problème, on peut en général associer plusieurs GRP.
Dans l’exemple des 8 reines, on peut prendre pour états toutes les combinaisons de 0,1,2, ,8 reines telles que les reines ne se menacent pas mutuellement. Le nombre de telles configurations est de l’ordre du million.
Toutefois, on peut voir que l’on ne réduit pas la généralité du modèle en contraignant la première reine placée à se trouver sur la première rangée, la seconde sur la seconde rangée, etc, puisqu’une solution doit obligatoirement comporter une reine sur chaque rangée.
Les états sont nettement moins nombreux avec ce second modèle, leur nombre est de l’ordre de quelques milliers.
Un graphe de résolution de problème est souvent énorme, parfois même infini, ainsi le but de la recherche heuristique est d’explorer partiellement le graphe pour aboutir à une
solution (c’est à dire trouver un plus court chemin de i à un sommet s ? B), en cherchant à limiter le plus possible la partie explorée.
5.3 Exemple 2 : jeu du taquin
Le jeu du taquin est un jeu de plateau dans lequel il faut passer d’une configuration de départ à une configuration d’arrivée sachant que les cases numérotées ne peuvent se déplacer que sur une case vide immédiatement adjacente.
| 1 | 3 | 1 | 2 | 3 | ||
| 7 | 5 | 8 | 4 | 5 | ||
| 4 | 2 | 6 | 6 | 7 | 8 |
Configuration de départ Configuration d’arrivée
Fig. 5.2 – Jeu de taquin
Les contraintes étant :
– Passer de la configuration de départ à la configuration d’arrivée
– Minimiser le nombre de déplacements
Un graphe de résolution de problème possible associé à ce jeu est celui tel que :
– les sommets du GRP sont les états possibles du jeu
– le sommet initial est la configuration de départ
– le sommet but (unique) est la configuration d’arrivée
– il existe un arc de la configuration x à la configuration y si un mouvement autorisé permet de passer de x à y.
Remarque : Ce GRP possède à la fois des cycles : il peut exister 2 chemins différents pour
passer d’un sommet x à un sommet y ; et des circuits : les règles permettent aussi de passer d’une configuration x à y puis de revenir à x.
5.4 Stratégies de recherche
5.4.1 Stratégie sans mémoire : la recherche arrière (backtrack)
Cette stratégie consiste à explorer le GRP via un chemin issu de d jusqu’à atteindre
– le but (c’est gagné)
– un puits (c’est perdu)
– une profondeur limite fixée d’avance
Si le but n’est pas atteint, on revient au dernier choix effectué chronologiquement (en oubliant la partie venant d’être explorée). Pour eviter les circuits on mémorise les états du graphe se trouvant sur le chemin courant. Tout nouvel état atteint est comparé à la liste des états du chemin.
Cette stratégie pose toutefois des problèmes : si le but ne peut être atteint dans la limite de profondeur fixée, il faut augmenter celle-ci et tout recommencer.
5.4.2 Stratégie avec mémoire : la recherche avec graphe (RAG)
On a un GRP qui est défini implicitement, en général trop grand pour être representé en mémoire et être exploré en totalité.
On va développer (c’est à dire représenter explicitement) une partie du GRP suffisante pour trouver le sommet but. On évitera ainsi les explorations redondantes.
Méthode (d’après [Nilsson])
1. Créer un graphe de rechercheG qui consiste uniquement en un sommet de départ d. Mettre d sur une liste appelée OUVERT.
2. Créer une liste appelée FERME qui est initialement vide.
3. BOUCLE, si OUVERT est non-vide, sinon échec.
4. Sélectionner le premier sommet d’OUVERT, l’enlever d’OUVERT, et le mettre dans FERME, Appeler ce sommet n.
5. Sinest un sommet but, terminer la procédure avec succès.
6. Développer le sommetn, produisant l’ensemble M de ses successeurs et les mémoriser comme successeurs de n dans G.
7. Mémoriser un pointeur versnà partir des éléments deM qui n’étaient pas déjà dans G (c’est à dire pas déjà dans OUVERT ou FERME). Ajouter ces éléments de M à OUVERT. Pour chaque élément de M qui était déjà dans OUVERT ou FERME, décider si l’on redirige ou non le pointeur vers n (voir ci-dessous). Pour chaque membre de M déjà dans FERME, décider pour chacun de ses descendants dans G si l’on redirige ou non le pointeur.
8. Réordonner la liste OUVERT, soit arbitrairement, soit selon des heuristiques.
9. Aller à BOUCLE
Les pointeurs dont il est question à l’étape 7 servent à retrouver, lorsqu’un sommet but b est atteint, un plus court chemin de d à b. Il suffit de “remonter” à partir de b en suivant les pointeurs.
Les heuristiques utilisées à l’étape 8 peuvent s’appuyer sur des connaissances spécifiques au problème.
5.4.3 AlgorithmesAetA?
Dans la recherche avec graphe (RAG), le choix de la fonction d’évaluation f pour le tri de OUVERT s’avère être un point crucial. Dans le cas de la méthode appelée algorithme A, on choisit f telle que pour tout sommet n du GRP, f(n) estime le couˆt d’un chemin optimal de d à un but passant par n.
L’application f peut se mettre sous la forme :
f(n) = g(n) + h(n)
– g(n) estime le couˆt d’un chemin optimal de d à n.
– h(n) estime le couˆt d’un chemin optimal de n à un but.
Posons g?(n) le couˆt d’un chemin optimal dans le GRP de d à n et h?(n) le couˆt d’un chemin optimal de n à un but. On a f?(n) = g?(n) + h?(n). On veut que f estime (au mieux) f?.
Pour g(n) il est naturel de prendre le couˆt de d à n dans le graphe de recherche (partie du GRP déjà developpé). Pour h(n) on s’appuie sur l’information spécifique au problème. On nomme h fonction heuristique.
Par exemple dans le cas du jeu de Taquin, on pourra prendre :
– g(n) = distance (nombre d’arcs) de d à n dans le graphe de recherche.
– h(n) = nombre de cases mal placées par rapport à la configuration but.
Si pour tout sommet n, h(n) ? h?(n), alors on démontre que l’algorithme A trouvera un chemin optimal de d à un but (s’il en existe). Dans ce cas, on parle d’algorithme A?. Dans le cas particulier ou` h = 0, on a bien un algorithme A? qui n’est autre que l’exploration en largeur.
57
Chapitre 6
Compléments
6.1 Exploration en profondeur
Algo EXPLORATION-PROFONDEUR ( Données : arborescence =(E,?) , r racine )
1: L = (r)
2: whileL 6= ? do
3: x = PREM(L)
4: if ?(x) = ? then
5: L = RESTE(L)
6: else
7:
8:
9: end if
10: end while
Cet algorithme ne construit pas de résultat. Il explore tous les sommets d’une arborescence en se dirigeant vers le premier sommet fils (par rapport au sommet courant) non encore exploré. Lorsque plus aucun sommet fils ne reste à explorer, l’algorithme remonte à un sommet parent ayant des sommets fils non encore explorés.
La liste L correspond en fait à une pile, les opérations en ligne 5 et 7 correspondent à un POP et un PUSH. La complexité de ces opérations est trivialement en O(1).
La condition en ligne 4 correspond à l’absence de sommets fils à explorer. Si cette dernière est vraie, l’action consécutive est une remontée et une descente dans le cas contraire.
Cet algorithme est une sorte de modèle (patron serait le terme exact) autour duquel peuvent être construites de nombreuses autres méthodes importantes. En effet, il est possible d’adapter très facilement cet algorithme pour qu’il parcoure l’ensemble des arêtes d’un graphe. Cette nouvelle version consiste à éviter de repasser par un sommet déjà exploré. Par exemple, cette modification permet de mettre en place un algorithme simple et efficace de recherche de circuits dans un graphe.
6.2 Exploration en largeur
Algo EXPLORATION-LARGEUR ( Données : arborescence =(E,?) , r racine )
1: S = (r), T = ?
2: whileS 6= ? do
3: for allx ? Sdo
4: for all do
5: = y
6: end for
7: end for
8: S = T;
9: T = ?
10: end while
Cet algorithme ne construit pas de résultat. Il explore tous les sommets d’une arborescence en les parcourant par niveau croissant. Les listes S et T correspondent à deux piles stockant les sommets restant à parcourir. L’une sert à parcourir les sommets du niveau courant, l’autre rec¸oit les sommets du niveau suivant et à la ligne 8 le niveau suivant devient le niveau courant. Cet algorithme est un classique à partir duquel peuvent être dérivées de multiples solutions algorithmiques.
Bibliographie
[Cormen] T.H. Cormen, C.E. Leiserson, R.L. Rivest, Introduction à l’algorithmique, Dunod.
[Gondran] M. Gondran, M. Minoux, Graphes et algorithmes, Eyrolles.
[Nilsson] N. Nilsson, Principes d’Intelligence artificielle, Cépadues.
Index
adjacent, 9 algorithme A, 56 algorithme A*, 56
antiréflexif, 10 antisymétrique, 8 arborescence, 23 arborescence de décision, 24 arborescence de recherche, 27 arborescence des plus courts chemins, 36
arborescence ordonnée, 26 arbre, 22 arbre couvrant, 28 arbre de poids maximum, 28 arbre de poids minimum, 28
arc, 1
arc de retour, 47
arc direct, 49
arc rétrograde, 49
arc saturé, 48
arête, 9
Bellman (algorithme), 37 biparti, 18
boucle, 10
capacité, 46
chaˆ?ne, 12 chemin, 11 chemin trivial, 11 chemin élémentaire, 11 circuit, 11 circuit absorbant, 34 Circuit-Niveaux (algorithme), 43
clique, 11
composante fortement connexe, 14
15 coupe, 50
cycle, 12
degré, 16 degré exterieur, 16 degré intérieur, 16
Dijkstra (algorithme), 40
Exploration-Largeur (algorithme), 59
Exploration-Profondeur (algorithme), 58
fermeture symétrique, 9 feuille, 23 flot, 47 flot compatible, 47 flot complet, 48 Ford & Fulkerson (algorithme), 50
graphe, 1 graphe complet, 11 graphe de résolution de problème, 53
graphe des plus courts chemins, 35 graphe non-orienté, 9 graphe ordonné, 25
graphe partiel, 2
graphe pondéré, 27
graphe sans circuit, 41
graphe symétrique, 8
GRP, 53
GSC, 41
hauteur, 42
isthme, 21
Kruskal 1 (algorithme), 29 Kruskal 2 (algorithme), 31 longueur, 11, 33
matrice d’adjacence, 17
partition, 42 partition en niveaux, 42
plus court chemin, 33 poids, 27
poids du graphe partiel, 27
Prim (algorithme), 32
prédecesseur, 1
puits, 42
racine, 22 rang, 42
Recherche Avec Graphe (procédure), 55
restriction, 2 réflexif, 10 réseau, 33 réseau d’écart, 49
sommet, 1 source, 41
sous-graphe, 2
sous-graphe induit, 2
successeur, 1
symétrique, 7
valeur du flot, 47 valeur résiduelle, 48
.6 Graphe biparti
On dit qu’un graphe G = (E,?) est biparti si l’ensemble E des sommets peut être partitionné en deux sous-ensembles distincts E1 et E2 de telle sorte que :
Exemple 17 :
