Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

IUT Info 2 GI Ann´ ee 2007-08 P´ eriode 1 et 2 Cours sur les graphes : petit co

IUT Info 2 GI Ann´ ee 2007-08 P´ eriode 1 et 2 Cours sur les graphes : petit contrˆ ole Florent Madelaine Nom :Corrig´ e Pr´ enom : L’algorithme de Bellman-Ford On rappelle l’algorithme vu en cours ci-contre. a- Expliquer comment faire pour stocker les plus courts chemins calcul´ es ? On m´ emorise pour chaque sommet, son pr´ ed´ ecesseur sur un chemin de- puis la source s. Ainsi ` a chaque fois qu’on relˆ ache un arc (u, v), cela signiﬁe que le chemin de s ` a v passe dor´ enavant par u, autrement dit le pr´ ed´ ecesseur de v est maintenant le sommet u. On peut par exemple stocker ces pr´ ed´ ecesseurs dans un tableaux index´ e par les sommets du graphe. b- Am´ eliorer le pseudo-code ci-contre pour mettre en place ce stockage des plus courts chemins. c- Donner un exemple de graphe orient´ e valu´ e pour lequel il y a un chemin entre deux sommets s et t mais il n’y a pas de plus court chemin de s ` a t. On peut consid´ erer par exemple un graphe pour lequel il y a un chemin non-´ el´ ementaire entre les deux sommets s et t, chemin qui a donc un circuit qu’on choisira en plus de poids total n´ egatif (par exemple −1). Algorithme 1 : Bellman-Ford Donn´ ees − → G un graphe orient´ e valu´ e sans circuit de longueur strictement n´ egative s un sommet de − → G Variables locales L tableau des distances depuis s /* index´ e par les sommets */ Pred tableau des pr´ ed´ ecesseurs sur un plus court chemin depuis s (u, v) un arc d´ ebut initialisation L[s] := 0 pour tous les sommet v ̸= s faire L[v] := +∞ tant que L change faire /* relaxation de l’arc (u, v) */ pour chaque arc (u, v) de − → G faire si L(v)>L(u)+length((u, v, − → G)) alors L(v) :=L(u)+length((u, v, − → G)) Pred[v] :=u ﬁnsi ﬁnprch ﬁntq ﬁn Sorties : L, le tableau des distances des plus court chemins de s Pred, le tableau des pr´ ed´ ecesseurs sur un plus court chemin depuis s 1 Les Algorithmes Cours sur les graphes d- En plus de calculer des plus courts chemins d’une source ` a tous les autres sommets dans un graphe sans circuit de poids n´ egatif, quelle autre fonc- tion peut remplir l’algorithme de Belman-Ford dans un graphe quelconque ? On peut d´ ecider si le graphe a un circuit de poids n´ egatif. En eﬀet, on a vu en cours que l’algorithme eﬀectue au plus n-1 it´ erations de la boucle Tant Que dans un graphe sans circuit n´ egatif. Donc, pour un graphe quelconque, il suﬃt de faire une ni` eme it´ eration et de v´ eriﬁer si oui ou non lors de cette ultime it´ eration le tableau L a chang´ e. Variante de Bellman Ford Soit − → G un graphe orient´ e et valu´ e sans circuit n´ egatif. On veut calculer la distance des plus courts chemins de n’importe quel sommet de − → G ` a un sommet particulier t. On veut aussi calculer un plus court chemin depuis chaque sommet vers le sommet t. e- En proc´ edant de mani` ere similaire ` a l’algorithme de Bellman Ford, donnez le pseudo-code d’un algorithme pour r´ ealiser cette tˆ ache. f- Expliquer comment faire pour stocker les plus courts chemins calcul´ es ? On m´ emorise pour chaque sommet, son successeur sur un chemin vers t. Ainsi ` a chaque fois qu’on relˆ ache un arc (u, v), cela signiﬁe que le chemin de u ` a t passe dor´ enavant par v, autrement dit le successeur de u est maintenant le sommet v. On peut par exemple stocker ces successeurs dans un tableaux index´ e par les sommets du graphe. Algorithme 2 : Variante de Bellman-Ford Donn´ ees − → G un graphe orient´ e valu´ e sans circuit de longueur strictement n´ egative t un sommet de − → G Variables locales L tableau des distances depuis un sommet ` a t Succ tableau des successeurs sur un plus court chemin ` a t (u, v) un arc d´ ebut initialisation L[t] := 0 pour tous les sommet v ̸= t faire L[v] := +∞ tant que L change faire /* relaxation de l’arc (u, v) */ pour chaque arc (u, v) de − → G faire si L(u)>L(v)+length((u, v, − → G)) alors L(u) :=L(v)+length((u, v, − → G)) Succ[u] :=v ﬁnsi ﬁnprch ﬁntq ﬁn Sorties : L, le tableau des distances des plus court chemins ` a t Succ, le tableau des successeurs sur un plus court chemin ` a t 2 Les Algorithmes Cours sur les graphes Techniques de preuves sur les graphes a- Qu’est-ce qu’une preuve par l’absurde ? Il s’agit d’une preuve pour laquelle on suppose le contraire de ce qu’on veut montrer et on montre qu’on obtient une contradiction. Ainsi, on peut conclure que ce qu’on veut montrer est bien vrai. b- Qu’est-ce qu’une preuve par r´ ecurrence ? Il s’agit d’une preuve pour laquelle on montre une propri´ et´ ee qui d´ e- pend d’une variable n, qu’on note P(n). Par exemple dans le cas de graphes, n est le nombre de sommets, ou bien le nombre d’arˆ etes, ou encore le nombre de fois ou une variable est r´ ep´ et´ ee dans un chemin non-´ el´ ementaire. La preuve a alors 3 ´ etapes. (i) D’abord on montre que P est vrai pour la premi` ere valeur de n (par exemple P(0) est vraie). (ii) Ensuite, on montre que si P(n) est vraie, alors P(n + 1) est vraie. (iii) Finalement, on peut conclure que P est vraie pour tout n puisque : P(0) est vraie ⇒P(1) est vraie ⇒P(2) est vraie ⇒. . . etc. c- Faire au choix l’une des deux questions suivantes. (1) Soit − → G un graphe orient´ e valu´ e. Soient s, m et t trois sommets distincts de − → G. Soit C un circuit de poids −1 passant par m. Soit P1 un chemin de s ` a m et P2 un chemin de m ` a t de poids respectifs 1 et 2. Montrer par l’absurde qu’il n’y a pas de plus court chemin de s ` a t. (2) Soit G un graphe (non-orient´ e). Soient s et t deux sommets de G. Mon- trez par r´ ecurrence que si il existe un chemin de s ` a t alors il existe un chemin ´ el´ ementaire de s ` a t (1) On suppose qu’il y a un plus court chemin P de s ` a t de longueur ℓ. Soit P′ le chemin de s ` a t de la forme suivante : P1 puis q fois C puis P2. La longueur totale de ce chemin est 1 −q + 2. Si on choisit q suﬃsamment grand, on obtient une contradiction puisque P′ est un chemin plus court que la longueur du plus court chemin P. Par exemple, on peut choisir q > 3 −ℓet alors on a bien 1 −q + 2 < ℓ. (2) Soit P un chemin de s ` a t. On prouve le r´ esultat par r´ ecurrence sur le nombre de ( ( boucles ) ) dans P (ici, une boucle est une r´ ep´ etition d’un sommet dans le chemin P) en montrant la propri´ et´ ee suivante. P(n) Si il existe un chemin de s ` a t avec au plus m boucles, alors il existe un chemin ´ el´ ementaire de s ` a t (sans boucle). (i) n = 0. Le chemin est d´ ej` a ´ el´ ementaire et il n’y a rien ` a montrer. (ii) On suppose P(n) vraie. Montrons P(n + 1). Le chemin P a n+1 boucles. En particulier il a une boucle autour d’un sommet x, c’est-` a-dire que P est de la forme : s, . . . , s′, x, . . . , x, t′, . . . , t. Consid´ erons le chemin P′ obtenu en enlevant cette boucle, il est de la forme s, . . . , s′, x, t′, . . . , t et n’a plus que n boucles. Comme P(n) est vraie, il existe donc un chemin ´ el´ ementaire de s ` a t. (iii) Conclusion : la propri´ et´ ee est vraie pour tout n et on a bien montr´ e le r´ esultat demand´ e. 3 uploads/Religion/ algorithme-controle.pdf