11.10 Travaux pratiques
345
P : (i, j) ∈ S → P (i, j) ∈ R
Par la suite, on conviendra que P (i, j) = 0 d` es lors que (i, j) ∈ A n’est pas
une arrˆ ete du graphe. Le probl` eme de la coupe de poids maximum revient `
a
trouver une partition de l’espace des sommets x ∈ {0, 1}
S qui maximise la
fonction suivante :
V (x) =
(i,j)∈S 2
P (i, j) x(i) (1 − x(j))
(11.15)
Avec ces notations, une coupe correspond ` a une arrˆ ete (i, j) ∈ A telle que
x(i) = 0 et x(j) = 1 ou inversement. On notera que la donn´ ee d’une application x ∈ {0, 1}
S conduit ` a la partition
S 0 := x
−1 ({0}) = {i ∈ S : x(i) = 0}
et
S 1 := x
−1 ({1}) = {i ∈ S : x(i) = 1}
Dans la litt´ erature de la th´ eorie des graphes, la quantit´ e V (x) est aussi appel´ ee
la capacit´ e C(S 0 , S 1 ) de la coupe. On remarquera aussi que les termes non nuls
dans la somme (11.15) sont n´ ecessairement li´ es ` a des arˆ etes avec des sommets
dans des parties diff´ erentes de la partition. Plus formellement, nous avons
P (i, j) x(i) (1 − x(j)) = 0 =⇒ ∀(i, j) ∈ (S 0 × S 1 ) ∪ (S 1 × S 0 )
Examinons enfin la situation o` u les pond´ erations sont constantes sur les
arˆ etes du graphe, disons
(i, j) ∈ A ←→ P (i, j) = 1
Dans ce cas, le probl` eme de d´ ecoupage optimal du graphe revient ` a trouver
une partition de l’ensemble des sommets avec un maximum d’arˆ etes entre les
deux.
Inversement, on peut rechercher les coupes du graphe `
a poids minimal.
11.10 Travaux pratiques
Le probl` eme du voyageur de commerce est un grand classique de l’optimisation combinatoire. Il peut se d´ efinir de la fa¸ con suivante. On se donne un
ensemble fini
V = {v 1 , . . . , v N }
de N ≥ 1 villes ainsi que la distance mutuelle entre chaque ville. Ce qui revient
` a se donner une distance d : V × V → R + . Le voyageur de commerce partant
de la ville v 1 doit trouver une permutation
345
P : (i, j) ∈ S → P (i, j) ∈ R
Par la suite, on conviendra que P (i, j) = 0 d` es lors que (i, j) ∈ A n’est pas
une arrˆ ete du graphe. Le probl` eme de la coupe de poids maximum revient `
a
trouver une partition de l’espace des sommets x ∈ {0, 1}
S qui maximise la
fonction suivante :
V (x) =
(i,j)∈S 2
P (i, j) x(i) (1 − x(j))
(11.15)
Avec ces notations, une coupe correspond ` a une arrˆ ete (i, j) ∈ A telle que
x(i) = 0 et x(j) = 1 ou inversement. On notera que la donn´ ee d’une application x ∈ {0, 1}
S conduit ` a la partition
S 0 := x
−1 ({0}) = {i ∈ S : x(i) = 0}
et
S 1 := x
−1 ({1}) = {i ∈ S : x(i) = 1}
Dans la litt´ erature de la th´ eorie des graphes, la quantit´ e V (x) est aussi appel´ ee
la capacit´ e C(S 0 , S 1 ) de la coupe. On remarquera aussi que les termes non nuls
dans la somme (11.15) sont n´ ecessairement li´ es ` a des arˆ etes avec des sommets
dans des parties diff´ erentes de la partition. Plus formellement, nous avons
P (i, j) x(i) (1 − x(j)) = 0 =⇒ ∀(i, j) ∈ (S 0 × S 1 ) ∪ (S 1 × S 0 )
Examinons enfin la situation o` u les pond´ erations sont constantes sur les
arˆ etes du graphe, disons
(i, j) ∈ A ←→ P (i, j) = 1
Dans ce cas, le probl` eme de d´ ecoupage optimal du graphe revient ` a trouver
une partition de l’ensemble des sommets avec un maximum d’arˆ etes entre les
deux.
Inversement, on peut rechercher les coupes du graphe `
a poids minimal.
11.10 Travaux pratiques
Le probl` eme du voyageur de commerce est un grand classique de l’optimisation combinatoire. Il peut se d´ efinir de la fa¸ con suivante. On se donne un
ensemble fini
V = {v 1 , . . . , v N }
de N ≥ 1 villes ainsi que la distance mutuelle entre chaque ville. Ce qui revient
` a se donner une distance d : V × V → R + . Le voyageur de commerce partant
de la ville v 1 doit trouver une permutation