Graphes et optimisation

Accueil > Annales > Correction de 09/2005

Correction de 09/2005

Il y a beaucoup de remise en forme à faire sur la page ; consultez les documents pdf.

dimanche 25 septembre 2005, par

Exercice 1 : les bases (8 points)

Soit un graphe orienté G=(S,A), avec S=A,B,C,D,E,F,G,H,I,J,K et
A=AB,BA,BB,DC,DD,DE,EF,FC,FD,GF,GG,GH,GI,HI,IJ,JJ,JK,KI
Quelles sont les composantes connexes de G ? Ses composantes fortement connexes ?

Composantes connexes : A,BC,D,E,F,G,H,I,J,K

Composantes fortement connexes : A,BCD,E,FGHI,J,K

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.

Liste de sommet et d’arcs :

- A : AB
- B : BA, BB
- C :
- D : DC, DD, DE
- E : EF
- F : FC, FD
- G : GF, GG, GH, GI
- H : HI
- I : IJ
- J : JJ, JK
- K : KI

Matrice d’adjacence

|A|=18, il y a donc 18 “1” dans le tableau

A
B
C
D
E
F
G
H
I
J
K
A

1

B
1
1

C

D

1
1
1

E

1

F

1
1

G

1
1
1
1

H

A

1

1

I

1

J

1
1
K

1

Matrice d’incidence
Il y a quatre boucles, BB, DD, GG et JJ et 14 autres sommets ; il ya donc “1” dans le tableau.

AB
BA
BB
DC
DD
DE
EF
FC
FD
GF
GG
GH
GI
HI
IJ
JJ
JK
KI
A
1
1

B
1
1
1

C

1

1

D

1
1
1

1

E

1
1

F

1
1
1
1

G

1
1
1
1

H

1

1

I

1
1
1

1
J

1
1
1

K

1
1

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.

En largeur : ABCDEFGHIJK

En profondeur

pre-visite : ABCDEFGHIJK

post-visite : BACFEDKJIHG

Faire un graphe réduit de G.

Les composantes fortement connexes de G sont C1=A,B, C2=C, C3=D,E,F, C4=G, C5=H, C6=I,J,K.

Le graphe réduit est GR=(SR,AR) avec SR=C1,C2,C3,C4,C5,C6 et
AR=C1C1,C3C2,C3C3,C4C3,C4C4,C4C5,C4C6,C5C6,C6C6

Donnez un arbre recouvrant de G’=(S,A’) avec
A’=AB,BC,CD,DF,DE,FG,GH,GI,IJ,IK

Exercice 2 (6 points)

Soit un graphe orienté valué aux arêtes G=(A,S,f) avec A=A,B,C,D,E,F,G,
S=AB,AC,AD,BC,BF,BG,CE,CF,DC,DE,DH,EG,EH,FE,FG,GH et f telle que :
Trouver un plus court chemin de A à H en détaillant l’algorithme de votre choix.
On utilise l’algorithme de Dijkstra : à chaque étape on fixe le sommet non fixé de distance à A minimale.
Fixe
A
B
C
D
E
F
G
H
DÉBUT
0
+∞
+∞
+∞
+∞
+∞
+∞
+∞
A
0
3
2
1

D

3
2

8

14
C

3

5
7

14
B

5
6
18
14
E

6
12
14
F

11
14
G

13
H
0
3
2
1
5
6
11
13

Le plus court chemin de A à H est ABFGH de longueur 13.

Exercice 3 (6 points) - problème de transport

Résoudre le problème de transport donné par la matrice suivante :
Première étape calcule d’un solution de base non dégénérée ; on utilise la méthode de Balas-Hammer.
Calcul des regrets :
Le plus gran regret est pour la seconde colonne (24) : on attribue donc le maximum possible au minimum de cette colonne : soit 44 en C2L3. La colonne C2 est terminée, on recalcule les regrets.

Le plus gran regret est pour la colone 5, on affecte 60-44=16 en C5L3. La ligne 3 est terminée, on recalcule les regrets.
Le plus grand regret est pour la ligne 1, le minimum en colonne 3, on peut y affecter 69. La colonne 3 est terminée.
Dans la seconde ligne, première colonne, on peut affecter 75. La première colonne est terminée.
Dans la première ligne, on affecte 33 à la collonne 4 qui est terminée. Il ne reste qu’ à finir.

Deuxième étape : On améliore la solution initiale : calcul des potentiels. Le graphe est bien connexe sans cycle.
On envisage toutes les relations non utilisées :
XA : potentiel de A en utilisant XA : -23+36=13 > 10 ; ce n’est pas intéressant.
XB : 69-23=46 > 45
YB : 69-20=49 > 45
YC : 24-20=4 > 1

YD : 42-20=22 > 13
ZA : 24 > 10
ZC : 39 > 1
ZD : 24 > 13
Aucune relation ne permet d’améliorer le coût, la méthode de Balas-Hammer nous a donc donné directement la bonne solution.