Graphes et optimisation

Accueil > Annales > Examen du 26 Février 2005

Examen du 26 Février 2005

Première session 2004-2005

mardi 19 juillet 2005, par

Exercice 1 : les bases (8 points)

Soit le graphe G=(S,A) avec S={A,B,C,D,E,F,G,H,I,J,K} et A={AC,BA,BB,BD,CB,CE,DC,DF,EC,EH,FF,FG,FH,FI,GI,HI,IJ,JK,KJ}
G est-il connexe ? fortement connexe ?

Donnez trois représentations de G : liste de sommets et d’arcs, matrice d’adjacence, matrice d’incidence. Ne notez pas les zéros dans les matrices.

En utilisant l’ordre alphabétique, donnez un ordre de parcours de G en largeur, puis les deux ordres de parcours en profondeur : ordre de pré-traitement, puis ordre de post-traitement.

Faire un graphe réduit de G.

Donnez un arbre recouvrant de G.

Exercice 2 : les flots (7 points)

Question 1

En utilisant le marquage de FORD-FULKERSON, trouver un moyen pour augmenter le flot sur ce graphe, sans tenir compte des coûts.

Montrez que le flot obtenu est maximal.

Question 2

Utiliser le résultat obtenu à la question 1 comme point de départ, et trouver un moyen de diminuer le coût du flot obtenu. Faire une seule modification, sans aller jusqu’au flot de coût minimal.

Exercice 3 : circuit (5 points)

Extrait d’un atlas routier :

Un voyageur de commerce doit effectuer une tournée le menant dans ces villes. Il utilise l’algorithme de Little pour calculer le plus court chemin sur sa tournée.

Afin de simplifier les notations, on note A, B, C, D, E, F respectivement les villes Amiens, Beaune, Besançon, Bordeaux, Boulogne sur mer. On représente donc le problème initial sous forme de la matrice suivante :

+∞ 910 470 510 720 130
910 +∞ 770 880 190 990
470 770 +∞ 110 580 600
510 880 110 +∞ 690 620
720 190 580 690 +∞ 800
130 990 600 620 800 +∞

On commence alors l’algorithme, jusqu’à trouver un premier chemin et terminer la « branche » correspondante. A un moment donné, on se trouve dans la situation décrite par l’arborescence suivante. Terminez la branche , en envisageant d’aller dans la ville suivante, et de ne pas y aller. Vous referez tous les calculs nécessaires à la compréhension de l’algorithme. Le MAX à ce niveau de l’algorithme est de 2530.


Il manque deux images : une est nécessaire à la compréhension : il s’agit du flot de l’exercice 2 ; l’autre est superflu : il s’agit de l’extrait d’un atlas routier,
Heureusement, le fichier PDF est complet, lui.