Graphes et algorithmes notes de cours et exercices

Operations sur un ensemble

Le tableau suivant presente les principales operations de base sur un ensemble ainsi que leur complexité selon le type de repr´esentation m´emoire. Le choix d’une structure de donn´ees adaptee est un facteur `a prendre en compte lors de la conception d’un algorithme. Nous nous pla¸cons dans la configuration du pire cas o`u |S| = |E| = n.
L’initialisation consiste `a mettre en place en m´emoire la structure de donn´ees correspon-dante. Pour le TB, il faut initialiser toutes les cases a` z´ero ce qui impose une complexit´ en O(n). Pour la LC, il suffit d’´ecrire NULL dans un pointeur [O(1)].
La s´election permet de prendre un el´ement quelconque de l’ensemble ou de tester si l’en-semble est vide. Pour la LC il suffit de s´electionner le premier el´ement de la liste, par contre pour le TB il faut parcourir les cases jusqu’`a trouver ´eventuellement un el´ement non nul [O(n)].
La recherche permet de savoir si un el´ement donn´e est pr´esent dans l’ensemble. Dans un TB il suffit de lire la case correspondante [O(1)], pour une LC il faut parcourir l’ensemble des el´ements pr´esents [O(n)].
La suppresion s’effectue en O(1) pour la LC et le TB. Cependant l’insertion qui technique-ment s’effectue aussi en O(1) pour ces deux structures, pose un probl`eme pour la LC. En effet, si nous voulons maintenir une liste d’´el´ements sans multiplicit´e : {1} ∪ {1} = {1}, il faut avant l’insertion tester la pr´esence de cet el´ement [O(n)]. N´eanmoins, par exemple, si l’on sait que les el´ements sont ins´er´es une seule fois dans la liste, l’insertion peut s’effectuer en O(1).
Le parcours est proportionnel au nombre d’´el´ements presents dans la LC [O(n)] et au nombre de cases allou´ees dans le TB [O(n)].

Representation d’un graphe (E, )

Double tableau – DT
Cette repr´esentation consiste en deux tableaux I et T de taille | |, tels que I (j) est le sommet initial de l’arc num´ero j et T (j) est le sommet terminal de l’arc num´ero j.

Representation d’un graphe (E, )

Tableau de listes chaˆın´ees – TLC
Cela consiste `a prendre un tableau de taille |E| contenant des pointeurs sur des listes chaˆın´ees tel que la i-`eme liste chaˆın´ee corresponde a` (i).
Matrice de bool´eens – MB
Il s’agit de la version bidimensionnelle des tableaux de bool´eens 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´eens monodimensionnel qui repr´esente (i).
Le choix des structures de donn´ees utilis´ees influe sur la complexit´ des programmes et donc sur leur efficacit´.
Exercice 1
D´ecrivez par des diagrammes, comme dans les illustrations qui pr´ec`edent, les repr´esen-tations possibles en m´emoire des graphes de l’exemple 7 (section 1.3.1).

Evaluation de la complexité d’un algorithme

L’algorithme suivant a pour but de rechercher les successeurs d’une partie X d’un en-semble E.
Soit G = (E, ), soit X ⊂ E. On d´efinit l’ensemble des successeurs de la partie X ainsi :
succ(X ) = { y ∈ E | ∃x ∈ X , (x, y) ∈ } = (x) x∈X
De la premi`ere forme de la d´efinition, on d´eduit l’algorithme suivant :
Algorithme 1 : SuccPartie 1
Donn´ees : X ⊂ E,
R´esultat : Y ⊂ E
1 Y ←∅;
2 pour chaque (x, y) ∈ faire
3 si x ∈ X alors Y ← Y ∪ {y};
Selon le choix du type de donn´ees pour X et Y , la complexit´ de l’algorithme pr´ec´edent peut varier. Prenons par exemple Y sous forme d’un tableau de bool´eens et X sous forme de liste chaˆın´ee.
On note n = |E| et m = | |.
L’instruction d’initialisation de Y `a la ligne 1 est en O(n). La boucle de la ligne 2 a` 6 est execut´ee m fois. Le test d’appartenance ligne 3 est en O(n) car X est sous forme d’une liste chaˆın´ee, de plus il est execut´ m fois. On comptera donc O(mn) pour la ligne 3. L’ajout d’un el´ement a` un tableau de bool´eens, 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´eens. 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 complexit´ pr´ec´edente.
Evaluez la complexit´ de l’algorithme suivant, inspir´e de la seconde forme de la d´efinition de succ(X ), en supposant que Y est repr´esent´ par un tableau de bool´eens.
Algorithme 2 : SuccPartie 2
Donn´ees : X ⊂ E,
R´esultat : Y ⊂ E
1 Y ←∅;
2 pour chaque x ∈ X faire
3 pour chaque y ∈ (x) faire
4Y ← Y ∪ {y} ;

Graphes orientes et non-orient´es

Le symetrique d’un graphe

Soit G = (E, ). On appelle sym´etrique de G le graphe G−1 = (E, −1) d´efini par :
∀x ∈ E , −1(x) = { y ∈ E | x ∈ (y)}
Il s’agit d’un graphe dont l’orientation des arcs a et´ invers´ee par rapport au graphe initial. Cette notation : −1 est aussi utilis´ee pour repr´esenter la “fonction pr´ed´cesseur”, c’est a` dire la fonction qui a` tout sommet du graphe fait correspondre l’ensemble de ses pr´edecesseurs.

Graphe non-orienté

D´efinition
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 el´ement de : {x, y} est appel´ arˆete du graphe. On dit que l’arˆete {x, y} est adjacente au sommet x et au sommet y. A on peut associer l’application n.o. de E −→ P(E) d´efinie par :
y ∈ n.o.(x) ⇔ {x, y} ∈
Dans tous les cas, (E, n.o.) est un graphe sym´etrique.
Ainsi la donn´ee d’un graphe sym´etrique est ´equivalente a` la donn´ee d’un graphe non-orient´.
Graphe non-orient´ associ´e `a un graphe orient´
Il se peut qu’`a partir d’un graphe orient´e, l’on cherche a` travailler dans un contexte non-orient´. Pour cela nous associons au graphe donn´e (E, ) sa version non-orient´ee (E, )

1 Notions de base 
1.1 Premi`ere d´efinition
1.2 Repr´esentation en m´emoire
1.3 Graphes orient´es et non-orient´es
1.4 Chemins, connexit´e
1.5 Repr´esentation matricielle
1.6 Graphe biparti
2 Arbres et arborescences 
2.1 D´efinitions
2.2 Exemples et applications
2.3 Arbre de poids extr´emum
3 Plus courts chemins 
3.1 D´efinition
3.2 Probl´ematique du plus court chemin
3.3 R´eseaux `a longueurs quelconques (Bellman)
3.4 R´eseaux `a longueurs positives (Dijkstra)
3.5 Graphes et r´eseaux sans circuits
4 Flots et reseaux de transport 
4.1 Mod´elisation du r´eseau de transport
4.2 Algorithme de Ford et Fulkerson
5 Resolution de problemes en intelligence artificielle et optimisation combinatoire 
5.1 Exemple 1 : le probl`eme des 8 reines
5.2 Graphe de r´esolution de probl`eme
5.3 Exemple 2 : jeu du taquin
5.4 Strat´egies de recherche
6 Compl´ements 
6.1 Exploration en profondeur
6.2 Exploration en largeur
Bibliographie