Recherche Opérationnelle Série 3 PDF

# Mathématiques II - Série 3 ## Exercice 1 On considère la matrice suivante: ``` 0 1 1 1 0 1 1 0 1 1 1 1 1 1 0 1 1 0 M = 1 1 1 0 1 1 0 1 1 1 0 1 1 1 0 1 1 0 ``` 1. Construire un graphe non orienté *G*, dont *M* est sa matrice d'adjacence. 2. Calculer *d(3)*. 3. Montrer que *G* n'admet pas de cyc...

# Mathématiques II - Série 3 ## Exercice 1 On considère la matrice suivante: ``` 0 1 1 1 0 1 1 0 1 1 1 1 1 1 0 1 1 0 M = 1 1 1 0 1 1 0 1 1 1 0 1 1 1 0 1 1 0 ``` 1. Construire un graphe non orienté *G*, dont *M* est sa matrice d'adjacence. 2. Calculer *d(3)*. 3. Montrer que *G* n'admet pas de cycle Eulérien. 4. Montrer que *G* admet une chaîne Eulérienne. Déterminer une telle chaîne. 5. Calculer *M²*, et déduire le nombre des chaines de longueur 2, qui relient les sommets 3 et 5. ## Exercice 2 Soit le graphe orienté valué suivants ``` 20 23 17 19 3 8 21 5 35 11 6 ``` 1. Appliquer l'algorithme de Dijkstra sur ce graphe. 2. Justifier pourquoi ce graphe peut être vu comme un réseau. 3. En utilisant l'algorithme de Ford-Fulkerson, calculer le flot maximal qui peut circuler dans ce réseau. ## Exercice 3 On considère le graphe orienté valué *G* suivant : ``` 1 13 2 9 18 34 8 10 9 4 7 5 17 19 6 ``` 1. Donner la matrice d'adjacence *M* du graphe *G*. 2. Calculer *d⁺(2)* et *d⁻(5)*. 3. Calculer *M²*, et déduire le nombre de chemins de longueur 2 qui relient les sommets 1 et 5. 4. Dans cette question on regarde *G* comme un graphe non-orienté: montrer que *G* n'admet pas de cycle Eulérien mais il admet une chaîne Eulérienne. Déterminer une telle chaîne. 5. En utilisant l'algorithme de Dijkstra, Donner les plus courts chemins allant de 1 aux autres sommets. 6. Justifier pourquoi on peut considérer *G* comme un réseau. 7. En utilisant l'algorithme de Ford-Fulkerson, calculer le flot maximale qui peut circuler dans ce réseau, et déterminer une coupe minimale dans ce cas. ## Exercice 1 suivi 3. *d(3) = 5* ⇒ *G* n'est pas cycle Eulérien 4. *d(B) = 5* et *d(D) = 5* et *d(A) = d(C) = d(E) = 4* donc *G* admet une chaîne Eulérien qui est *(B,A,F,B,C,A,D,F,E,B ,D,C,E,D)* ## Exercice 2 Série 1. *d = (0,23,00,20,00,00)*, *P = (1,1,Nil,1,Nil,Nil)*, *S = {}*, *T = {2,3,4,5,6}* *It 1* : *i = 4* *S = {1,48}* *T = {2,3,5,6}* *d(4) + m45 = 20 + 21 = 41* < *d(j) = d(5) = ∞* *d(5) = ∞* *φ(5) = 4* *d = (0,23,00,20,41,∞)*, *P = (1,1,Nil,1,4,Nil)* *It 2* : *i = 2* *S = {1,4,23}* *T = {3,5,6,3}* *j = 4* *d(2) + m24 = 23 + 17 = 40* < *d(4) = 20* *j = 3* *d(2) + m23 = 23 + 19 = 42* < *∞* *d(3) = 42, φ(3) = 2* *d = (0,23,42,20,41,∞)*, *P = (1,1,2,1,4,Nil)* *It 3* : *i = 5* *S = {1,4,2,53}, *T = {3,6,3}* *j = 3* *d(5) + m53 = 41 + 8 = 49 * > *42* *j = 6* *d(5) + m56 = 41 + dd = 52* < *∞* *d(6) = 52, φ(6) = 5* *d = (923, 42, 20, 41, 52)*, *P = (1,1, 2, 4, 5)*, *S = {1,4,2,53}, *T = {3,6,3}* *j= 3* *d(3) + m36 = 42 + 35 = 77* > *52* *It 9*: *S = {1,1,2, 5, 3, 63}, T = { }, d = 0, 83, 42, 20, 41, 528, P = (1, 1, 2, 1, 4, 5)* 2) Ce graphe est muni d’une valuation *C:A→ Rt* et est orienté et il a une source (1) et un puits (6) donc il peut être considéré comme réseau. *It 1*: * (4, 4, 5, 6) E = min (20, 21, 11) = 11, 2f(1)= 11* *It 2*: * (1, 2, 3, 6) E = min (23, 19, 35) = 19, 2f(2)= 19* *It 3*: * (1, 4, 5, 3, 6) E = min (9, 10, 8, 14) = 8, 2f(3)= 38 flot maximale* X = { 1, 2, 4, 5 } C(X, X) = 2 + 1 - 1 + 8 + 19 = 38 ≅ 2f(f) *M2 = 0 1 1 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 * d⁺(2) = 3* *d⁺(5) = 3* *M² = 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0* 4) *d(3) = d(4) = 23* et *d(a) = d(6) = 2* et *d(5) = d(2) = 4* donc admet chaine Eulérien *(3, 521, 3, 2, 4, 5, 694)* 5) *d = (0, 13, 18, 00, 00, 00)*, *P = (^_^, Nil, Nil, Nil, Nil, Nil)*, *S = { }, T = {2, 3, 4, 5, 6}* *It 1*: *i = 2* *j = 4* *d(2) + m24 = 13+10 = 23* < *d(f) = 20* *d(4) = 23* *φ(4) = 2* *j = 5* *d(2) + m25 = 13+8 = 21* < *d(5) = 20* *d(5) = 21* *φ(5) = 2* *S = {1, 2}, T = {3, 4, 5, 6}, d = (0, 13, 18, 23, 21, 00), P = (1, 1, 1, 2, 2, 1)* *It 2*: *S = {1, 2, 3}, T = {3, 4, 5, 6}* *It 3*: *i = 5, j = 6 * *d(5) + m56 = 21+13 = 40* < *d(6) = 200* *d(6) = 40, φ(6) = 5* *S = {1, 2, 3, 5}, T = {4, 63}, d = (0, 13, 18, 23, 21, 40), P = (1, 1, 1, 2, 2, 5)* *it 4*: *S = { 1, 2, 3, 4, 5 }, T = {6, 3 }* *It 5*: *d = (0, 13, 18, 23, 21, 40), P = (1, 1, 1, 2, 2, 5), S = {1, 2, 3, 4, 5, 6}, T = { }* *d = (0, 13, 18, 23, 21, 40), pc (1, 1, 2, 2, 2, 5)* Fin Les chemins les plus courts: 1 -> 2 -> 3 *d(3) = 13* 1 -> 2 -> 4 *d(4) = 18* 1 -> 2 -> 5 *d(5) = 21* 1 -> 2 -> 5 -> 6 *d(6) = 40* 6) Ce graphe est orienté et il a une source (1) et un puit (6) donc c’est un réseau 7) Initialisation *f= 20 (f= 0)* *(1, 2, 4, 6) E = min(13, 10, 17)=10* *2f(1)= 10* *(1, 3, 5, 6) E = min(18, 7, 19)=7* *2f(2)= 17* *(1, 3, 2, 5, 6) E = min(11, 6, 8, 12)=6* *2f(3)= 23* *(1, 2, 5, 6) E = min(3, 2, 6) = 2* *2f(4) = 25* X={1, 2, 3}, X={4, 5, 6} C(X, X) = 7 + 8 + 10 = 25 ≅ 2f(f)