Algorithmique avancée : circuit de poids moyen minimal

Thèmes abordés

Algorithmique avancée, circuit, poid minimal

Résumé du document

Soit G = (S;A) un graphe orienté, de fonction de pondération w : A amène à R

Extraits

[...] Soit c un circuit de poids nul, et soient u et v deux sommets quelconques de c. Soit x le poids du chemin de u ` v le long du circuit c. D´montrez que δ(s, = δ(s, + x. a e (Indication : quel est le poids du chemin de v ` u le long du circuit c a On peut construire un chemin de s ` v en concat´nant un plus court chemin de s ` u (de poids δ(s, a e a avec le chemin de u ` v le long de c (chemin de poids x). [...]

[...] Montrez que, si = il existe un sommet v sur le circuit de poids moyen minimal tel que max δn δk = 0. (Indication : montrez qu'un plus court chemin vers un sommet quelconque du circuit de poids moyen minimal peut ˆtre ´tendu le long du circuit pour cr´er un plus court chemin vers le sommet suivant e e e dans le circuit.) D'apr`s la question le minimum est atteint sur un circuit ´l´mentaire. Soit c un tel circuit. On e ee a donc = 0. [...]

[...] e a 6. Montrez que, si µ = δn δk min max = 0. Cette question est une bˆte combinaison des r´sultats des questions 3 et 5. e e 7. Montrez que si l'on ajoute une constante t au poids de chaque arc de est ´galement augment´ e e de t. Servez-vous de cette propri´t´ pour montrer que ee = min max δn δk . 2 On note w la nouvelle fonction de pond´ration : w = t + w(a). [...]

[...] u ` A chaque arc on rajoute un poids t = On obtient alors comme poids moyen minimal : µ = 0 et, d'apr`s la question pr´c´dente, e e e min δn δk = 0. max Or δn δk = δn δk + D'o`, u min δn δk + ) max = min δn δk . max Pour contourner cette hypoth`se il suffit de rajouter ` G un sommet s et un arc de poids nul de s vers e a chacun des sommets de G pour se ramener dans les hypoth`ses de l'algorithme, cette construction ´tant e e moins ch`re que l'ex´cution de l'algorithme. [...]

[...] Un circuit c pour lequel µ(c) = est appel´ circuit de poids moyen e minimal. Nous ´tudions ici l'algorithme de Karp, qui est un algorithme efficace permettant de calculer . e Nous supposons, sans perte de que chaque sommet v S est accessible ` partir d'un sommet e e e a origine s S. Soit δ(s, le poids d'un plus court chemin de s vers et soit δk le poids d'un plus court chemin de s vers v compos´ exactement de k arcs (si un tel chemin n'existe pas, δk = e 1. [...]