Theorie Des Graphes

1

Chapitre 1 Introduction Le but de ce chapitre est de mettre en place les notions fondamentales sur les graphes afin de partir sur des bases saines.

1.1

Définitions fondamentales

Il existe plusieurs manières de caractériser un graphe, nous allons en parcourir quelques unes. Notons immédiatement qu’il existe deux grands types de graphes : les graphes orientés et les graphes non orientés. Nous allons commencer notre étude par les graphes orientés puis nous traiterons des différences avec le cas non orienté dans une section spécifique. 1.1 Définition (Graphe) Un graphe est caractérisé par 2 ensembles nommés X et E et respectivement nommés Sommets et Arcs, avec :

(

jX j = n jE j = m

les sommets seront numérotés de 1 à n les arcs seront numérotés de 1 à m

Par définition, E est composé de couples e = (i;

j) 2 X  X .

On appelle respectivement i et j l’ origine et la destination de l’arc e. Si la notation ensembliste des graphes est la seule qui soit rigoureuse, ces derniers valent surtout par leur représentation graphique. En effet, soit le graphe G =

(X; E ) =

(

X = f1; 2; 3; 4g E = f(1; 2) ; (2; 1) ; (2; 2) ; (2; 3) ; (2; 3) ; (4; 3) ; (4; 1)g 2

Ce même graphe peut être associé aux deux représentations suivantes et même d’autres. Du coup, n’oubliez jamais la règle suivante : Ne vous fiez pas à l’aspect visuel de deux graphes pour les comparer. Seule la comparaison des ensembles de sommets et d’arcs est fiable !

a 1

c

2

1

3

b b d

g

g

e

e

d a

f 4

3

4

2 c

f

F IG. 1.1: Deux représentations « graphiques » du même graphe A cela, nous allons ajouter quelques définitions supplémentaires : 1.2 Définition (Boucle) On appelle boucle un arc (i;

i)

Par exemple, dans le graphe de la figure (1.1), l’arc (2; 1.3 Définition (Sommets adjacents) Les sommets i et j du graphe G = (X; (i; j ) ou l’arc (j; i) appartiennent à E .

2) est une boucle.

E ) sont dits adjacents si et seulement si, l’arc

Par exemple, dans le graphe de la figure (1.1), les sommets (grâce à l’arc (4; 1)), alors que les sommets 2 et 4 ne le sont pas.

1 et 4 sont adjacents

1.4 Définition (Graphe simple) Un graphe G = (X; E ) est dit simple si et seulement si :

1. Pour tout couple (i; 2.

8 i 2 X;

l’arc (i;

j ) 2 X  X , il existe au plus un arc (i; j ) 2 E

i) n’existe pas 3

De manière plus littéraire : un graphe simple est un graphe sans boucle ni arcs multiples entre les même sommets. Par exemple, le graphe de la figure (1.1) n’est pas un graphe simple car il contient à la fois la boucle (2; 2) et 2 arcs (2; 3). Remarque : Il existe une bijection entre l’ensemble des graphes simples et l’ensembles des relations binaires sur X , les propriétés sur les relations s’étendant donc aux graphes. 1.5 Définition (Graphe planaire)

On qualifie de planaire tout graphe pouvant être dessiné sans que ses arcs ne se croisent. Une fois de plus, il convient de ne pas oublier qu’il ne faut jamais se fier à la représentation visuelle d’un graphe. Par exemple, le graphe de la figure suivante n’apparaît pas planaire sur sa représentation de gauche. Toutefois, si vous modifiez sa représentation graphique comme montré à droite il est évident qu’il est bel et bien planaire.

F IG. 1.2: Exemple de graphe planaire

1.2

Les graphes non orientés

1.6 Définition (Graphe non orienté) On appelle graphe non orienté tout graphe où les arcs nables. 4

(i; j ) et (j; i) sont

indiscer-

Le vocabulaire change un peu : on appelle habituellement arête un arc dans le cas non orienté.

1.3

Cocycles, degrés

Soit G = (X; E ) un graphe orienté. On appelle cocycle d’un sommet l’ensemble des sommets qui lui sont adjacents ou l’ensemble des arcs qui lui sont incidents. On note :

8 ,+ (i) > > < ,, (i) + > > : !!, ((ii))

fj 2 X j(i; j ) 2 E g fk 2 X j(k; i) 2 E g f(i; j ) 2 E g f(k; i) 2 E g

= = = =

Les cocycles , sont des cocycles de sommets, alors que les cocycles ! sont des cocycles d’arcs. Les deuxièmes se révèlent beaucoup plus utiles dans le cas général. Si nous reprenons le graphe de la figure (1.1), nous avons, par exemple :

8 ,+ (2) > > < ,, (1) + > > : !!, (2) (3)

= = = =

f1 ; 2 ; 3g f2 ; 4g fb ; c ; d ; eg fd ; e ; f g

= ,, = , et, réciproquement, !+ = !, = !.

Dans le cas non orienté, l’on a ,+

Notons qu’il existe un autre système de notation :

(

,+ , , ,, , ,,1

Les degrés sont des quantités attachées au sommet et qui expriment la cardinalité des cocycles. On notera :

(

d+G (i) = j,+ (i)j = j!+(i)j d,G (i) = j,, (i)j = j!,(i)j

demi degré extérieur/suprérieur de i dans G demi degré intérieur/inférieur de i dans G

En gros, le demi degré extérieur compte le nombre d’arcs qui sortent d’un sommet alors que le demi degré intérieur compte le nombre d’arcs qui entrent en un sommet.

, On appelle degré du sommet i et l’on note dG (i) = d+ G (i) + dG (i). , Dans le cas non orienté, l’on a : dG (i) = d+ G (i) = dG (i) Si l’on revient au cas orienté, on a un résultat intéressant. Soit G = (X;

X

i2X

d+G (i) = 5

X

i2X

d,G (i)

E ), on a :

car chaque arc possède exactement une extrémitié initiale et une extrémité finale. D’où :

X

d+G (i) =

i2X avec m nombre d’arcs du graphe. Finalement :

1.4

d(G) =

X i2X

X i2X

d+G (i) +

d,G (i) = m

X i2X

d,G (i) = 2m

Matrices associées aux graphes

Il y a deux matrices typiquement associées aux graphes : la matrice d’incidence arc-sommet et la matrice d’adjacence sommet-sommet.

1.4.1

Matrice d’incidence arc-sommet



La matrice d’incidence est de taille n m, les sommets sont associés aux lignes, les arcs aux colonnes. Notons i (G) la matrice d’incidence associée au graphe G = (X; E ). Pour pouvoir l’écrire, nous devons numéroter les arcs du graphe. On obtient alors :

A

8 > <1 aij = > ,1 :0

si le sommet i est le sommet initial de l’arc j si le sommet i est le sommet terminal de l’arc j partout ailleurs

Cette notation est très lourde car la matrice est très creuse. En effet sur une même colonne seuls deux éléments ne sont pas nuls : ceux qui correspondent au sommet initial (1) et au sommet terminal (-1) de l’arc. Sur une même ligne, le nombre d’éléments égal à 1 nous donne le demi degré supérieur alors que le nombre d’éléments égal à -1 nous indique le demi degré inférieur du sommet. Dans le cas non orienté, on ne place que des 1 et la somme d’une ligne indique le degré du sommet. Cette matrice est inexpoitable du point de vue algorithmique mais elle est extrèmement importante du point de vue théorique car elle permet de faire le lien, par exemple, entre la théorie des flots et la programmation linéaire.

6

1.4.2

Matrice d’adjacence sommet-sommet



C’est une matrice n n telle que aij = 1 pour tout arc (i; j ) appartenant au graphe, tous les autres éléments étant nuls. Lorsqu’un graphe est dense, c’est à dire lorsque m est proche de n2, cette matrice constitue un moyen de stockage efficace au point de vue place mémoire mais elle s’avère délicate à utiliser algorithmiquement. Dans le cas non orienté, la matrice d’adjacence est symétrique. En effet, pour la construire on considère chaque arête du graphe comme 2 arcs opposés, lesquels servent de base à la construction de la matrice.

1.4.3

Expression des matrices

Nous allons expliciter les deux matrices sur le graphe suivant. Afin d’éviter toute ambiguité entre les sommets et les arcs ces derniers ont été «numérotés» par des lettres.

2 d a 1

c

4

b e 3 F IG. 1.3: Graphe d’exemple pour l’expression des matrices d’incidence et d’adjacence

1 2 3 4

a b c d e 1 1 0 0 0 ,1 0 1 1 0 0 ,1 ,1 0 1 0 0 0 ,1 ,1 Incidence

1 2 3 4

1 0 0 0 0

2 1 0 0 0

3 0 1 0 0

Adjacence

7

4 0 1 1 0

1.5

Chemins, Chaînes, Circuits, Cycles

Les notions de chemin et de circuit dans les graphes orientés ainsi que leurs homologues dans les graphes non orientés, respectivement chaîne et cycle, sont absolument fondamentales. Après les définitions générales de ces notions, nous examinerons 2 cas particuliers des plus intéressants.

1.5.1

Définitions générales

1.7 Définition (Chemin) On appelle chemin depuis un sommet

( ( ( (

s vers un sommet t une suite d’arcs : s = i0 ; i1 ) i1 ; i2 ) i2 ; i3 ) ::: ::: ik,1 ; ik = t ) 2 d

a 1

c

4

b e 3 F IG. 1.4: Exemple de chemin (en trait gras) du sommet 1 au sommet 4 De manière plus littéraire, un chemin est une succession d’arcs qui permet de relier un sommet s à un sommet t en empruntant chaque arc dans le bon sens, c’est à dire de son origine vers sa destination. La figure (1.4) illuste la notion de chemin depuis le sommmet 1 vers le sommet 4. Les arcs utilisés sont dessinés en gras. L’on voit immédiatement qu’ils sont toujours parcourus depuis leur origine vers leur destination. Ainsi la destination d’un arc est l’origine de son successeur dans le chemin. 8

Si l’on relache cette dernière contrainte, c’est à dire que l’on s’autorise à emprunter un arc à l’endroit ou à l’envers, on parle alors de chaîne. 1.8 Définition (Chaîne) Une chaîne est un chemin sur lequel on a relaché la contrainte d’orientation. La notion de chaîne est la seule à avoir une signification dans le cas des graphes non orientés. La figure (1.5) illustre la notion de chaîne. Dans ce cas, on voit clairement que l’arc c est parcouru à contre-courant.

2 d a 1

c

4

b e 3 F IG. 1.5: Exemple de chaine (en trait gras) du sommet 1 au sommet 4 1.9 Définition (Circuit, Cycle) Un circuit est un chemin dont l’origine et la destination sont confondues.

Dans le cas non orienté, on parle de cycle. La figure suivante illustre ces deux notions. Notez l’inversion du sens de l’arc

d

entre les deux dessins. 1.10 Définition (Chemin simple) Un chemin qui ne passe qu’une seule fois par chacun des arcs qu’il emprunte est dit simple 1.11 Définition (Chemin élémentaire) Un chemin qui ne passe qu’une seule fois par chacun des sommets qu’il traverse est dit élémentaire

9

2

2 d

a 1

d

a c

4

1

b

c

4

b e

e

3

3

Cycle

Circuit

F IG. 1.6: Exemple de chemin (en trait gras) du sommet 1 au sommet 4

Corollaire immédiat : Un chemin élémentaire est nécessairement simple. 1.1 Théorème

Tout chemin de s vers t contient un chemin élémentaire de s vers t. La démonstration de cette propriété est laissée en exercice. Dans la suite de ce cours, on ne s’intéressera désormais plus qu’aux chemins élémentaires. Aussi, à partir de maintenant, la notion de chemin devra être comprise comme chemin élémentaire.

1.5.2

Chemin Eulérien, chemin Hamiltonien

Ces deux types particuliers de chemin et de cycle, que l’on retrouve dans les cas orientés ou non orientés sont particulièrement intéressants car on les retrouve dans de nombreux problèmes appliqués. 1.12 Définition (Chemin Eulérien) On qualifie d’Eulérien un chemin qui passe une et une seule fois par chaque arc du graphe qui lui sert de support. En outre, si l’on impose que l’origine et la destination du chemin soit confondues, on parle de circuit Eulérien.

10

L’application industrielle la plus spectaculaire est connue sous le nom de problème du postier chinois et consiste à chercher le circuit Eulérien de longueur minimale sur un graphe aux arcs valués. 1.13 Définition (Chemin Hamiltonien) On qualifie d’Hamiltonien un chemin qui passe une et une seule fois par chaque sommet du graphe qui lui sert de support. En outre, si l’on impose que l’origine et la destination du chemin soit confondues, on parle de circuit Hamiltonien. A présent, valuons chaque arc du graphe et recherchons le circuit Hamiltonien de longueur minimale sur le graphe. On obtient le problème ultra classique du Voyageur de Commerce.

1.6 1.6.1

Sous graphes, graphes partiels Définitions générales

Soit G = (X; E ) un graphe. On va désormais définir les notions importantes de sous graphe et de graphe partiel. Afin d’illustrer notre propos, nous nous servirons du graphe suivant comme base :

4 d

i h

a

1

2

c b e

5 f

6

3 g

F IG. 1.7: Graphe de base pour l’illustration des graphes partiels et sous graphes 1.14 Définition (Graphe partiel) Soit Ep E un sous ensemble des arcs de G.



E de G, Gp = (X; Ep) est un graphe partiel 11

4

4

d

h

a

1

d

i 2

1

h

a

2

c b e

5 f

6

5

3

6 f

3

g

g

Sélection d’arcs (en gras)

Graphe partiel obtenu

F IG. 1.8: Exemple d’extraction d’un graphe partiel En résumé, on obtient un graphe partiel de G en supprimant certains arcs. Par exemple, dans la figure (1.8), et à partir du graphe de la figure (1.7), si l’on ne retient que les arcs marqués en gras sur la partie de gauche, l’on obtient le graphe partiel de la partie de droite. Les raisons de travailler sur des graphes partiels sont légion. Par exemple, l’on pourrait vouloir se limiter aux arcs présentant certaines caractéristiques importantes. Considérons un problème de recherche d’itinéraires où chaque axe routier est représenté par un arc. Si l’on ne désire emprunter que des autoroutes, on peut extraire le graphe partiel associé aux autoroutes. 1.15 Définition (Sous graphe) Soit Xp X un sous ensemble des sommets tout graphe Gs = (Xp ; E (Xp Xp)).



\



X de G. On appelle sous graphe de G

De manière plus littéraire, on obtient un sous graphe en extrayant un sous ensemble des sommets de G et en ne retenant que les arcs qui relient ces sommets, tel qu’illustré sur la figure (1.8).

12

4 d

i h

a

1

2

a

1

c

2

b e

5 f

b

6

3

e 3

g Sélection de sommets (en gras)

Sous graphe obtenu

F IG. 1.9: Exemple d’extraction d’un sous graphe

1.6.2

Cliques, Stables, Coloration

Deux sous graphes particuliers ont une importance toute particulière dans le monde de la théorie des graphes : les cliques et les stables. Comme nous allons le voir immédiatement, ces deux notions sont totalement opposées. 1.16 Définition (Clique) On appelle clique sur un graphe G tout sous graphe complet. 1.17 Définition (Stable) Un stable sur un graphe G est un sous graphe sans arc. Remarque : Un sommet isolé est à la fois une clique et un stable. 1.18 Définition (Coloration) On appelle Coloration une partition en stables d’un graphe. Ce dernier vocabulaire est lié au problème classique de coloration d’une carte. Soit une carte géographique représentant plusieurs pays. On souhaite colorier chaque pays de manière à ce qu’il n’ait pas la même couleur que chacun de ses voisins. Ce problème peut être résolu en cherchant une partition en stables du graphe obtenu en associant chaque pays à un sommet et chaque arc à une frontière commune entre 2 pays. Il suffit alors d’associer une couleur à chaque stable obtenu. Remarque : on essaye le plus souvent de déterminer le nombre minimal de couleurs nécessaires. Il a été démontré que l’on peut toujours colorier un graphe planaire avec, au plus, 3 couleurs. 13

Chapitre 2 Arbres et parcours 2.1

Notion d’arbre

2.1.1

Définitions fondamentales

La notion d’arbre est fondamentale en recherche opérationnelle. Après avoir donné une première définition, nous énumèrerons plusieurs propriétés équivalentes à cette définition. Notons immédiatement que la notion d’arbre est non orientée : elle s’applique aussi bien au cas qu’au cas non orienté. 2.1 Définition Un arbre est un graphe connexe et sans cycle (propriété 0). Les propriétés suivantes (qui s’appliquent à un graphe comptant n sommets) sont équivalentes à la définition précédente :

, 1 arcs Un arbre est un graphe sans cycle qui compte exactement n , 1 arcs. On parle

1. Un arbre est un graphe connexe qui compte exactement n 2.

de graphe acyclique minimal 3. Un arbre est un graphe sans cycle tel que si l’on rajoute un arc quelconque, on crée un cycle 4. Un arbre est un graphe connexe tel que la suppression d’un arc quelconque engendre la séparation en 2 composantes connexes. On parle de graphe connexe maximal 5. Dans un arbre, tout couple de sommets est relié par une et une seule chaîne. 14

2.1.2

Démonstration de l’équivalence des définitions sur les arbres

La démonstration de l’équivalence de ces propositions nécessite un théorème intermédiaire. 2.1 Théorème Soit G = X;

f E g un graphe quelconque, alors :

– Si G est sans cycle, alors m  n , 1 – Si G est connexe, alors m  n , 1 La démonstration de ce théorème se fait de manière constructive. En effet, considérons un graphe G On ajoute alors les arcs 1 par 1.

= fX; E g, jX j = n dont l’on retire tous les arcs.

A un instant donné, la situation peut être telle que représentée par la figure (2.1).

F IG. 2.1: Construction d’un arbre : situation de base Lorsque l’on rajoute un arc, 2 cas peuvent se présenter : 1. L’arc réunit 2 sommets de la même composante connexe (2.2.a). – Le nombre de composantes connexes du graphe ne change pas – On crée un cycle dans la composante connexe 2. L’arc réunit 2 sommets appartenant à des composantes connexes différentes (2.2.b). – Le nombre de composantes connexes diminue de 1 – On ne rajoute pas de cycle dans le graphe 15

(a)

(b) F IG. 2.2: Construction d’un arbre : opérations élémentaires

Appliquons ce principe de construction à la démonstration du théorème précédent. Si l’on désire que le graphe soit sans cycle, il nous faut procéder par la deuxième méthode d’ajout d’arc. Initialement, comme il n’y a pas d’arcs, il y a n composantes connexes. A chaque ajout d’arc, le nombre de composantes connexes diminue de 1 unité. Après avoir ajouté n 1 arcs par cette méthode, il ne reste qu’une seule composante connexe, le graphe est donc connexe. Si maintenant, l’on construit un graphe par l’un ou l’autre principe de construction, il faut ajouter au moins (n-1) arcs avant d’obtenir une seule composante et donc un graphe connexe. D’où la seconde partie du théorème. En vertu du premier principe de construction, tout ajout d’arc rajoutera un cycle, ce qui démontre la première partie du théorème.

,

16

Une fois le théorème démontré, les implications suivantes sont évidentes :

8(0) ) (1) > > <(0) ) (2) > ) (4) > :(1) (2) ) (3)

Pour démontrer l’équivalence des propriétés sur les arbres, nous allons créer la boucle d’implications suivante (les implications non encore démontrées sont en gras) :

8(0) ) (2) > > > (2) ) (3) > <(3) ) (1) > (1) ) (4) > > (5) > :((45)) ) ) (0) Démonstration

3)1

Supposons que H soit un arbre non connexe. Il possède donc au moins 2 composants connexes. En appliquant la règle de construction numéro 2, il est possible d’ajouter un arc sans créer de cycle, ce qui entraîne une contradiction. Moralité : un arbre est un graphe connexe et sans cycle qui possède exactement n 1 arcs.

,

Démonstration

4)5

Supposons qu’il existe deux chaînes distinctes permettant de joindre un couple de sommets (i; j ). Alors, il existe au moins un arc (k; l) appartenant à la première chaîne mais pas à la seconde. Supprimons cet arc, il existe encore une chaîne permettant de joindre i à j . Le graphe est toujours connexe après suppression d’un arc ce qui contredit la proposition 4. Démonstration

5)0

Supposons qu’il existe un cycle, alors, il est possible d’obtenir 2 chaînes reliant chaque sommet du cycle à un autre. En outre, l’existence d’une chaîne permettant de relier chaque couple du graphe est la définition même de la propriété de connexité.

17

Ainsi se termine la démonstration d’équivalence des propriétés d’un arbre ! 2.1 Corollaire Ajouter un arc à un arbre créée un et un seul cycle 2.2 Corollaire Tout graphe connexe contient un graphe partiel qui est un arbre. Ce second corollaire est évident à démontrer par construction. Supprimons toutes les arêtes du graphe avant de les réintroduire sans créer de cycle : nous venons bien de créer un graphe partiel qui est un arbre !

2.1.3

Démonstrations complémentaires

2.2 Définition (Racine) Soit un graphe orienté G. Le sommet s est dit racine de X s il existe un chemin de s vers x. si, x

8 2 nf g

G = (X; E ) si et seulement

2.3 Définition (Arborescence) Un arbre orienté admettant une racine est une arborescence C’est un abus de langage commun que d’appeler arbre une arborescence. La figure suivante illuste 2 arbres, l’un est une arborescence, l’autre non.

Arborescence

Arbre

F IG. 2.3: Arborescence ou pas?

18

Chapitre 3 Plus courts chemins 3.1

jX j

Notations

Ce chapitre suppose que l’on travaille sur un graphe orienté = n et E = m. Chaque arc (i; j ) est muni d’un coût cij .

j j

Dans la suite on notera Pts un chemin depuis un sommet sommet t (la destination).

G = (X; E ),

avec

s (la source) vers un

3.1 Définition (Longueur d’un chemin)

On appelle longueur d’un chemin P et on note l(P ) la quantité

l(P ) =

X

(i;j )2P

cij

(3.1)

Un chemin d’un sommet vers lui même sera toujours de longueur nulle. 3.2 Définition (Plus court chemin) Un plus court chemin de s vers t est un chemin de s vers t dont la longueur est minimale parmi tous les chemins de s vers t. Dans la suite on notera Pts un tel chemin. 3.3 Définition (Fonction de marquage, potentiel) On appelle fonction de marquage ou potentiel une application de X dans R. En clair, cela revient à valuer, ou porter une valeur, sur chacun des sommets du graphe. 3.4 Définition (Plus courtes distances) On appelle plus courte distance de s à i et l’on note ds (i) la fonction de marquage égale à la longueur du plus court chemin de s vers i. Par abus de notation, et une fois la source s fixée, on écrira d(i) pour ds (i). 19

3.1 Remarque (Représentation d’un chemin) Il existe deux grandes manières de représenter un chemin. La première consiste à donner la suite des arcs qui le composent. Ainsi, un chemin Pts peut s’écrire :

Pts = ((s = i1; i2) ; (i2; i3) ; (i3; i4) ; : : : ; (ip,1; ip = t)) Plus simplement, et comme nous ne travaillons que sur des graphes simples, on peut noter un chemin par la succession des sommets rencontrés. Ainsi, le chemin précédent peut désormais s’écrire :

Pts = (s = i1; i2; i3 : : : ; ip,1; ip = t) 3.1 Théorème (Condition d’optimalité des distances) Soit d(:) la plus courte distance depuis la source s vers un sommet quelconque du graphe. Alors :

8 (i; j ) 2 G

d(j ) 6 d(i) + cij

En effet supposons qu’il existe deux sommets i et j tels que d(j ) > d(i) + cij . Ceci implique notament que l’arc (i; j ) n’est pas utilisé dans le chemin Pj associé à d(j ). Soit Pi le plus court chemin vers i. Par définition sa longueur est d(i). Si on lui ajoute l’arc (i; j ), on obtient un chemin de longueur d(i) + cij < d(j ). D’où la contradiction car d(j ) est sensée être la plus courte distance pour aller en j .

3.2

Le problème

Rechercher un plus court chemin de s vers t revient à rechercher un chemin de s vers t de longueur minimale s’il existe. Les conditions d’existence sont les suivantes : 1. Il existe au moins un chemin de s vers t 2. Aucun chemin de s vers t ne contient de circuit absorbant i.e. de circuit de longueur négative. En effet, si un tel circuit existait, l’on pourrait le parcourir indéfiniment pour abaisser la longueur du chemin. Dans la suite de cet exposé nous supposons : 1. Il existe un chemin depuis un sommet s vers tous les autres sommets du graphe. 2. Il n’existe pas de circuit absorbant dans le graphe. 20

3.1 Propriété (Propriété de sous optimalité) Soit Pts = (s = i1; i2 ; i3; : : : ; ip,1; ip = t) un plus court chemin de s vers t. Alors, j 2::p 1, le sous chemin Pisj = (s = i1; i2; : : : ; ij ) est un plus court chemin de s vers ij .

8 2

,

En effet, soit P un plus court chemin de s vers t passant par le sommet k . Appelons P1 le sous chemin de s à k et P3 le sous chemin de k à t. On a P = P1 P3. Supposons que P1 ne soit pas optimal. Alors il existe un chemin P2 = P1 entre s et k tel que l(P2) < l(P1). Dans ce cas P2 P3 est un chemin de s vers t de longueur inférieure à celle de P1 P3 = P ce qui contredit l’hypothèse.

6

[

[

[

P1 s

k

P3

t

P2 F IG. 3.1: Démonstration de la propriété de sous optimalité Soit P  un plus court chemin de la source

s vers un sommet quelconque t.

– Par définition de la plus courte distance (3.4), d(t) = l(P ). – Par application de la propriété précédente, d(i) = l(Pis ) pour chacun des sommets i P  , où Pis est la restruction de P  entre s et i.

2

Conséquence : Pour chaque arc i;

j 2 P , on a d(j ) = d(i) + cij .

La réciproque de cette propriété fondamentale fait l’objet du théorème suivant : 3.2 Théorème Soit un chemin P = Pts tel que pour chaque arc Alors P est un plus court chemin de s vers t.

(i; j ) 2 P

l’on ait

d(j ) = d(i) + cij .

Dans cette démonstration, on utilise la notation P = (s = i1; i2; i3 ; : : : ; ip,1 ; ip = t). On part de d(t), plus courte distance de s à t que l’on décompose de manière à faire apparaître le coût des arcs composant P et le tour est joué.

d(t) = d(ip) =

(d(ip) , d(ip,1)) + (d(ip,1) , d(ip,2)) + (d(ip,2) , d(ip,3)) .. .

+ (d(i2) 21

.. .

,

d(i1))

avec d(i1) = d(s) = 0 (hypothèse 2). Or, par hypothèse, pour tout arc (i;

concerne ici : cij

j ) 2 P , d(j ) = d(i) + cij ou, pour ce qui nous

= d(j ) , d(i) Ce qui nous donne : X X d(t) = d(j ) , d(i) = cij = l(P ) (i;j )2P

(i;j )2P

La plus courte distance au sommet t étant égale à la longueur du chemin est un plus court chemin de s vers t. 3.2 Propriété Soit G0 = (X; E 0 ), où E 0 est l’ensemble des arcs G0 contient une arborescence enracinée en s.

P , celui-ci

(i; j ) tels que cij = d(j ) , d(i). Alors,

Démonstration : Pour chaque sommet t, il existe un plus court chemin de s à t dans

G0. Réciproquement, il suffit de construire une arborescence dans G0 pour obtenir un plus court chemin depuis parcours.

3.3

s vers tout autre sommet à l’aide d’un algorithme de

Les algorithmes de plus court chemin

Selon les caractéristiques du graphe que l’on étudie, il existe 3 grandes familles de recherche de plus courts chemins depuis un sommet s vers tous les autres sommets du graphe.

3.3.1

Graphe acyclique

3.2 Remarque (Précision importante concernant le vocabulaire) Dans le cas des graphes non orientés, le terme acyclique décrit un graphe sans cycle, alors que si l’on traite des graphes orientés, on appelle acyclique tout graphe sans circuit. Lorsqu’un graphe ne comporte pas de circuit, les arcs traduisent une relation d’ordre partiel sur le graphe. Ce qui veut dire que l’on peut numéroter les sommets de G de telle manière que (i; j ) G i < j . Une telle numérotation s’appelle un tri topologique sur G. Le calcul d’un tri topologique (ou ordre topologique) sur un réseau se fait par un algorithme de complexité maximale en O(m).

2

)

Dès lors qu’il existe un circuit sur le graphe, il devient impossible de créer un tel ordre car tout sommet membre d’un circuit est l’un de ses propres prédécesseurs. 22

L’algorithme suivant permet de déterminer un ordre topologique sur un graphe. Algorithme de tri topologique

8 i 2 X (i) 0 8 (i; j ) 2 G (j ) (j ) + 1 Liste fi 2 X = (i) = 0g

suivant 0 Tant Que (Liste = ) Retirer un sommet i de la liste suivant suivant + 1 ordre[i] suivant

6 ;

8 (i; j ) 2 !+ (i)

(j ) (j ) , 1 Si ( (j ) = 0)

Alors Liste Liste j Fin Si Fin Fin Tant Que Si (suivant < n) Alors Le réseau contient au moins un circuit Sinon Le tableau ordre indique l’ordre topologique Fin Si

[f g

8

Le principe de cet algorithme est simple et repose sur l’élimination progressive des arcs sortant de chaque sommet. Nous utilions les variables  (i) indiquant à chaque instant, combien d’arcs non encore biffés du réseau entrent dans le sommet i. Initialement,  (i) = !, (i) , i X et la liste contient l’ensemble des sommets qui n’ont pas de prédécesseurs et qui sont donc directement numérotables. A chaque fois que l’on examine un sommet, on coupe les arcs qui en sortent et on place dans la liste les sommets qui n’ont plus d’arc entrant. Ainsi, on est sûr d’examiner tous les prédécesseurs d’un sommet avant de le numéroter.

j

j8 2

Une fois cet ordre topologique connu, le calcul des plus courts chemins est très simple. En effet, supposons que l’on cherche à calculer d(k ) et que l’on connaisse les plus courtes distances pour tous les sommets de rang topologique inférieur à celui de k. De par la définition de l’ordre topologique, tous les arcs arrivant en k proviennent de sommets de rang inférieur, c’est-à-dire de sommets pour lesquels on connaît déjà les plus courtes distances (de par l’hypothèse). Alors, pour connaître d(k ) (et, par la

23

même occasion, un plus court chemin joignant s à k ), il suffit de considérer :

j d(k)

= arg (i;k min (d(i) + cik ) )2G = d(j ) + cjk pred[k ] = j où j est le sommet prédécesseur de k de distance minimale par rapport à s. On obtient alors l’algorithme suivant initialisé en s, seul sommet sans prédécesseur par définition. Algorithme de Bellmann

d(s) 0 8 i 2 X n fsg d(i)

+1

Renuméroter les sommets dans l’ordre topologique Pour k variant de 1 à n j arg i : (min (d(i) + cik ) i; k)2X d(k) d(j ) + cj k pred[k ] j Fin Pour

3.3.2

Arcs à coûts positifs, algorithme de Dijkstra

Lorsque le réseau contient des circuits, il n’est plus possible d’utiliser l’algorithme précédent qui s’appuie sur un tri topologique. Toutefois, il est toujours possible de tirer profit de la non négativité des coûts sur les arcs. Pour ce faire on partitionne l’ensemble des sommets en deux ensembles S et S . Les sommets de S sont dits fixés et ceux de S temporaires. On utilise une fonction de

marquage d(:) que nous appellerons distance et qui à la fin de l’algorithme sera égale à la distance minimale depuis s vers chaque sommet. A chaque étape, la définition de d est la suivante :

d(i) est la longueur

d’un plus court chemin de sommets intermédiaires sont dans S . Initialement, i = s.

8 6

s vers i dont tous les d(s) = 0 et d(i) = +1,

L’algorithme repose sur le postulat suivant : Les distances aux sommets fixés (c’est-à-dire les sommets de S ) sont minimales. 24

A chaque itération, le sommet temporaire de plus petite distance est transféré directement dans S et l’on met à jour les distances de tous ses successeurs. La complexité temporelle de l’algorithme de Dijkstra sous cette forme simple est O(n2). En effet, à chaque étape, on transfère un nœud de S vers S , ce qui nous fait n itérations. A l’intérieur de chaque itération, on recherche le sommet de S qui possède la plus petite distance temporaire, opération en O(n) dans le pire des cas. Toutefois, des structures de données performantes (telles que les Tas de Fibonnacci) permettent de rabaisser significativement cette complexité (O(m + n log n)). Algorithme de Dijkstra (forme simple)

S ; S X d(s) 0 pred[s] 0 d(i) +1 8 i 2 X n fsg Tant que (S 6= ;) i arg min(d(j )) j 2S S S [ fig S S n fig 8 (i; j ) 2 !+ (i) Si (d(j ) > d(i) + cij ) Alors

d(j )

d(i) + cij pred[j ] i

Fin Si Fin Fin Tant que

8

Démonstration de l’algorithme : Elle se fait par récurrence sur la taille de S .

3.3.3

Le cas général, algorithme de Ford

Dans le cas général, la seule solution consiste à regarder itérativement les arcs en modifiant les distances jusqu’à ce que la condition du théorème (3.1) soit vérifiée pour chacun d’entre eux.

25

L’algorithme général de Ford (dit Label-correcting) est le suivant :

d(s) d(i)

Algorithme de Ford (forme simple)

0 +1 8 i 2 X n fsg Tant que 9 (i; j ) 2 G avec d(j ) > d(i) + cij d(j ) d(i) + cij pred[j ] i Fin tant que

Cet algorithme est très intéressant car il converge quelle que soit la méthode de sélection de l’arc violant les conditions d’optimalité. Notons que cet algorithme permet de détecter la présence d’un circuit négatif lorsqu’une distance devient inférieure à nC avec C = (i;j max cij . )2G

,

j j

La preuve de cet algorithme est immédiate. En effet, à l’issue de l’algorithme, il suffit de remonter la chaîne des prédécesseurs stockée dans le tableau pred pour obtenir des chemins de s vers tous les autres sommets du graphe uniquement constitués d’arcs vérifiant la condition (3.1). Le théorème (3.2) nous garantissant que de tels chemins sont bien des plus courts chemins de s vers les autres sommets. Sous cette forme directe, l’algorithme de Ford est informatiquement inexploitable. C’est pourquoi l’on a recours à l’algorithme modifié qui repose sur l’utilisation d’une liste de sommets. Cette dernière contient les sommets dont les distances ont été modifiées et qui sont donc susceptibles de créer des arcs violant la condition (3.1). Algorithme de Ford modifié

d(s) 0 d(i) +1 8 i 2 X n fsg LISTE fs g Tant que LISTE 6= ; Retirer un sommet i de la liste 8 (i; j ) 2 !+ (i) Si (d(j ) > d(i) + cij ) Alors

d(j )

d(i) + cij pred[j ] i Si j 62 LISTE

LISTE Fin si Fin si Fin Fin tant que

8

26

LISTE

[ fj g

La même remarque s’impose : la convergence est assurée quelle que soit la politique de gestion de la liste. Les performances de cet algorithme sont très intéressantes dans deux cas particuliers : Gestion File : C’est la forme la plus répandue car elle permet, moyennant des astuces algorithmiques non négligeables que nous ne détaillerons pas ici, de détecter les circuits de coût négatif. Les sommets sont retirés dans l’ordre où ils sont introduits dans la liste. En pratique, on insère les sommets en fin de liste pour les retirer en tête de liste. Sa complexité est O(nm). Gestion Dequeue : C’est l’algorithme (en pratique !) le plus performant pour résoudre les problèmes de plus court chemin dans le cas général. Si l’on retire toujours les sommets en tête de liste, ils sont insérés en fin de liste lors de leur première insertion et en tête de liste s’ils doivent être examinés une nouvelle fois. Il existe une autre variante qui utilise deux listes couplées l’une à l’autre. Très performantes, ces deux implémentations peuvent néammoins avoir un comportement non polynômial sur des réseaux pathologiques.

27

Chapitre 4 Le problème de l’ordonnancement 4.1

Introduction

Soit un projet complexe composé d’un ensemble de tâches que l’on souhaite fixer dans le temps de manière à ce que le projet se termine au plus vite.

4.2

Le problème

On suppose le projet composé de n tâches numérotées de 1 à n chacune dotée d’une durée di supposée connue (la terminologie Anglo-Saxonne est processing time, laquelle est souvent notée pi ). Le problème de l’ordonnancement consiste à affecter à chaque tâche i une date de début ti . On suppose que le projet commence à t0 = 0. Divers types de contraintes peuvent se greffer sur le noyau dur du problème : Les contraintes temporelles portent sur les dates de début et de fin des tâches Les contraintes d’allocation de ressources spécifient qu’une ressource critique (e.g., la grue dans un chantier de BTP) ne peut être utilisée par plus d’un certain nombre de tâches à la fois L’objectif est de minimiser la durée totale du projet (makespan en Anglais), c’est-àdire, calculer la date de fin au plus tôt du projet. 4.1 Définition (Date de fin au plus tôt) On appelle date de fin au plus tôt et l’on note projet permettant de respecter les contraintes. 28

L la durée minimale d’exécution du

4.2.1

Les contraintes temporelles (ou contraintes de potentiel)

Elles sont essentiellement de 3 types : 1. La tâche i ne peut commencer avant la date t0i dite date de disponibilité :

ti > t0i

2. La tâche i ne peut terminer après la date ti dite date d’échéance :

ti + di 6 ti

3. Contraintes de précédence, la tâche j ne peut commencer avant la fin de la tâche i:

ti + di 6 tj

On peut généraliser ces dernières contraintes à une contrainte plus générale de R et telle que : potentiel entre les tâches i et j en introduisant la quantité aij

2

ti + aij 6 tj Notons que les notations et termes Anglais sont les suivants :

(

4.2.2

t0i ri ti di

release time deadline

Les contraintes cumulatives

Elles permettent de traiter certaines contraintes d’allocation de ressources. Soit une ressource Rk dont la quantité totale disponible pour le projet à l’instant t est ,k (t). On note ik (i ; t) la quantité de l’instant t sachant que la ti = i .

Rk nécessaire à l’accomplissement de la tâche i à

La contrainte cumulative relative à la ressource k et à l’instant t s’écrit :

X

i=1::n

ik (i; t) 6 ,k (t)

Ce genre de contraintes est pénible à traiter car il nécessite de connaître la date de début de chacune des tâches ... ce qui est le but final du problème. Choisir ,k et ik constants au cours du temps ne simplifie pas énormément le problème car il est toujours nécessaire de connaître les dates de départ pour traiter la contrainte. 29

4.2.3

Contraintes disjonctives

Ces contraintes permettent de spécifier que 2 tâches ne peuvent pas avoir lieu en même temps (par exemple, les entrepreneurs qui en sont chargés ne s’entendent pas). La première méthode pour modéliser cette contrainte consiste à utiliser un ou logique sur les deux contraintes de potentiel suivantes :

ti + di 6 tj tj + dj 6 ti Aussi élégante soit elle, cette méthode n’est guère recevable car elle entraîne des difficultés algorithmiques non négligeables. En particulier, le nombre de cas à traiter séparément explose lorsque l’on augment le nombre de disjonctions. L’autre méthode consiste à introduire une contrainte d’allocation de ressource entre ces deux tâches. De toute manière, le traitement de ces contraintes est malaisé dans le cas général. Dans la suite de cet exposé, nous ne considérerons que des contraintes de potentiel simples.

4.3

Un exemple simple : le chantier

Soit un chantier constitué des tâches suivantes :

N0 1 2 3 4 5

Description Terrassement Installation de la grue Coulage des Fondations Branchement électrique Gros œuvre de maçonnerie

Durée 10 jours 2 jours 5 jours 3 jours 6 jours

Les contraintes de précédence sont les suivantes : – 1, 2, et 4 précèdent 3 – 2 précède 5 4.2 Définition (Date au plus tôt) On appelle Date au plus tôt et on note i la date minimum à laquelle on peut démarrer la tâche i. Il est clair que ti > i et que tn+1 = L.

On pose 0

= 0. 30

4.3 Définition (Date au plus tard) On appelle Date au plus tard et on note i la date maximale à laquelle on peut démarrer la tâche i sans retarder l’exécution du projet ou violer une contrainte. Il est clair que ti 6 i avec tn+1 = L. 4.4 Définition (Marge) La marge d’une tâche i (notée mi) est la différence entre les dates au plus tard et au plus tôt, soit :

mi = i , i

4.5 Définition (Ordonnancement au plus tôt (tard)) On appelle Ordonnancement au plus tôt (tard) l’ordonnancement du projet correspondant aux dates au plus tôt (tard).

4.4

Représentation du problème d’ordonnancement

Il existe trois grands modèles pour représenter les ordonnancements.

4.4.1

Diagramme de Gantt

C’est le modèle le plus ancien où l’on représente une tâche par un rectangle dont la longueur représente la durée. L’axe horizontal représente le temps. Ce graphe n’est d’aucune utilité pour optimiser le projet car il ne permet pas de faire apparaître les contraintes. En revanche, il est intéressant pour suivre le projet une fois l’optimisation réalisée. Il est à noter que, bien que ce diagramme soit en 2 dimensions, la dimension verticale ne sert qu’à séparer les tâches car elle n’est associée à aucune grandeur du problème.

4.4.2

Le modèle PERT (Program Evaluation and Review Technique)

C’est un graphe où les tâches et les contraintes de précédence sont représentées par des arcs. Les sommets correspondent à des instants privilégiés du déroulement du processus : les dates de début et de fin de chaque tâche. Les arcs représentant les tâches ont pour coût di alors que les arcs de précédence ont un coût nul. On rajoute deux sommets fictifs représentant respectivement les dates de début et de fin du projet. 31

T â c h e 2 T â c h e 4

T â c h e 3 T â c h e 5

T â c h e 1

F IG. 4.1: Diagramme de Gantt associé au problème du chantier

Le «réseau» PERT est très proche du diagramme de Gantt mais permet de modéliser les contraintes. Il a été mis au point aux Etats-Unis pour résoudre les problèmes liés à la construction de sous-marins nucléaires.

Tâche 1 Début

Tâche 3 Tâche 2

Fin

Tâche 5 Tâche 4

Transitions

F IG. 4.2: Réseau PERT associé au problème du chantier

4.4.3

Le modèle Potentiel-tâches

Ici les tâches sont représentées par des sommets et les arcs trahissent les contraintes de précédence. Ainsi la contrainte i précède j est elle symbolisée par un arc entre les sommets i et j et de longueur di . Le graphe Potentiel-tâches est sans doute plus lourd que le réseau PERT mais il permet de modéliser plus de contraintes et de prendre en compte des cas « tordus »

32

1

10

0 3

3 D

0

5

4

0

F 2

2

5

6

2

F IG. 4.3: Réseau Potentiel-Tâches associé au problème du chantier

4.5

Résolution

Que ce soit en utilisant le modèle PERT ou le modèle Potentiel-Tâches, la solution du problème d’ordonnancement est donnée par la résolution d’un problème de plus long chemin (donné par l’algorithme de Bellmann) entre le début et la fin du projet. En effet, si l’on recherche le plus long chemin, celui-ci va utiliser le plus grand nombre de tâches possibles en suivant les arcs les plus longs. Le graphe ne contient pas de circuit car les contraintes de précédence fournissent un ordre partiel sur les tâches. On utilisera donc une forme adaptée de l’algorithme de Bellmann pour calculer les plus longs chemins. 4.6 Définition (Chemin critique) On appelle chemin critique tout plus long chemin entre le début et la fin du projet. 4.1 Théorème (Résultats sur le graphe Potentiel-tâches) Soit un graphe potentiel-tâches modélisant l’ordonnancement des tâches d’un projet complexe.

Soit : a)

L la longueur du plus long chemin entre le début et la fin du projet.

b) pi la longueur du plus long chemin entre le début du projet et la tâche i. c) qi la longueur du plus long chemin entre la tâche i et la fin du projet Alors : 1. La durée minimale du projet est L 33

2.

i = pi

3. i

= L , qi

Conséquence Voici le modus operandi pour calculer les différentes grandeurs associées à un projet d’ordonnancement : – On calcule L et l’ordonnancement au plus tôt en résolvant un problème de plus long chemin sur le graphe potentiel-tâches à partir du sommet correspondant au début du projet. – On calcule l’ordonnancement au plus tard en résolvant un problème de plus long chemin sur le graphe potentiel-tâches dont l’on a préalablement inversé les arcs et à partir du sommet correspondant à la fin du projet.

34

Chapitre 5 Introduction aux problèmes de flot 5.1

Notion de réseau

On appelle réseau un graphe sur lequel on va faire transiter un flot.

G = (X; E ) un graphe orienté avec jX j = n et jE j = m. Chaque arc est doté de deux grandeurs positives ou nulles, l et u, respectivement dénommées capacité Soit

minimale et capacité maximale et telles que :

8(i; j ) 2 G

0 6 lij 6 uij

Chaque nœud est doté d’une contribution au flot b(i). On appelle source tout sommet i créant du flot, c’est à dire, tel que b(i) > 0 et puits tout sommet i; b(i) < 0 où le flot est « consommé ». Un flot sur le réseau G est un vecteur x

X k:(j;k)2G

2 Rm, indicé sur les arcs, tel que :

lij 6 xij 6 uij X xjk , xij = b(j ) 8 j 2 X i:(i;j )2G

(5.1) (5.2)

1. La condition (5.1) spécifie que le flot est borné inférieurement et supérieurement par les capacités des arcs. 2. L’équation (5.2), qui n’est pas sans rappeler la première loi de Kirchoff (ou loi des nœuds) en électricité, traduit la conservation du flot en chaque sommet du réseau. En effet, de façon plus littéraire, on peut la traduire par la phrase suivante : La quantité de flot sortant d’un sommet moins la quantité de flot entrant dans le même sommet est égale à la contribution de ce sommet. 35

Bien entendu, pour que le problème ait une solution, la somme des contributions doit être égale à 0, soit :

X

i2X

b(i) = 0

Exprimé ainsi, on voit immédiatement que les problèmes de flot permettent de modéliser directement les problèmes réels d’écoulement d’un liquide dans un ensemble de canalisations (le flot est alors le débit de liquide dans chaque tuyau) ou de circulation du courant électrique dans un réseau, le flot étant ici égal à l’intensité de courant passant dans un fil. La figure suivante illustre un réseau et un flot réalisable sur celui-ci. Les triplets figurant au dessus des arcs sont de la forme (l; u; x).

(0,2,1) (1,2,2)

(0,2,2) (1,4,3)

+4

(2,2,2)

(0,1,1)

-4

(2,3,2)

(2,3,2) (0,4,3) F IG. 5.1: Exemple de réseau portant un flot

5.2

Les simplifications du problème

Plusieurs aménagements d’un réseau de flot quelconque permettent de simplifier le traitement algorithmique du problème. Nous allons en considérer quelques unes. De plus amples informations sont disponibles dans [2], [4], [3] ou [1].

36

5.2.1

Travailler avec une seule source et un seul puits

Il est possible de ne travailler qu’avec une seule source et un seul puits. Ainsi, il est inutile de garder en mémoire la liste des contributions des sommets en dehors de celles de la source et du puits. On crée un sommet noté s et appelé super source ou tout simplement source. Ensuite, pour chaque sommet i tel que b(i) > 0, on ajoute un arc (s; i) de capacité maxiP b(i). male b(i) et le tour est joué. Finalement, on pose b(s) = i2X b(i)>0 Réciproquement, on crée un sommet t (le puits) et une collection d’arcs P b(i). chaque sommet de contribution négative et l’on pose b(s) = i2X b(i)>0

(i; t) pour

La figure suivante montre comment appliquer ce principe sur un exemple simple.

(2)

(2)

(2)

(2) +3

-1 (2)

(1)

(2)

+5

(1) -5

(2)

(2) +2

-4 (2)

(1)

(3)

(2)

(4) (2)

(3)

(3)

F IG. 5.2: Exemple de suppression de sources et puits multiples

5.2.2

Eliminer les arcs avec des capacités minimales non nulles

L’utilisation de capacités minimales entraîne des lourdeurs algorithmiques non négligeables. Aussi, il peut être judicieux de les éliminer avant le traitement du problème. Insistons néanmoins sur le fait que le procédé que nous allons expliciter peut conduire à un graphe si grand qu’il n’en justifie plus l’intérêt. Aussi, on pourra se reporter à [1] pour les techniques permettant de traiter directement les réseaux à capacités minimales non nulles. On peut considérer un arc (i; j ) de capacité inférieure lij > 0 comme un arc de capacité supérieure uij lij reliant un puits de contribution b(i) = lij à une source de contribution b(j ) = lij .

,

,

37

En effet, on remplace la contrainte de passage d’un minimum de flot sur cet arc par la disparition de la même quantité de flot en entrée et sa restitution en bout d’arc. La deuxième partie de l’opération consiste à éliminer le nouveau puits et la nouvelle source ainsi crées par l’opération précédente. Cette technique est illustrée sur la figure suivante :

(3) +2

(2) (1, 2)

(2)

-2

Ajout d’une source et d’un puits

-1

(3)

Etape 1 :

+2

(4)

(2) -2

(1) (2)

+1

(4)

Etape 2 : suppression de la source et du puits excédentaires

(1) (3) +3

(2)

(2) (2)

(1) (2)

-3

(4) (1)

F IG. 5.3: Exemple de suppression des arcs de capacité inférieure non nulle

5.2.3

Cas des capacités sur les sommets

Dans certains modèles de situations réelles, il est possible d’avoir des capacités sur les sommets. Par exemple, dans un nœud de répartition EDF, les équipements de rectification de la tension ne peuvent absorber plus d’une certaine quantité d’électricité. Ceci peut se modéliser par la contrainte suivante :

X i:(i;j ) 2 G

xij 6 (j )

8j 2 X

où (j ) est la capacité maximale du sommet j . Afin de ne pas rajouter cette contrainte dans le système, on la remplace par une contrainte de capacité sur un arc en dédoublant le sommet j en j0 et j " et en ajoutant l’arc (j 0; j ") de capacité (j ). 38

5.3 5.3.1

Quelques problèmes de flot classiques Le problème de flot maximal

De tous les problèmes de flot dans les réseaux, le problème du flot maximal (ou flot max pour les intimes) est assurément le plus simple. Il consiste à tenter de faire circuler sur le réseau la plus grande quantité de flot possible. Pour ceci, on fixe arbitrairement la contribution de la source à + . Une alternative consiste à supprimer les contributions des sommets s et t et à rajouter un arc (t; s) de capacité infinie et appelé arc de retour.

1

On appelle valeur du flot et l’on note habituellement v la somme du flot sortant de la source (ou entrant au puits). Soit donc :

v= 5.3.2

X

i:(s;i) 2 G xsi

=

X

j :(j;t) 2 G xjt

Le problème du flot de coût minimum

Ici, chaque arc est muni d’un coût cij dit coût unitaire par unité de flot et le problème consiste à trouver un flot x sur le réseau tel que le coût du flot :

X

(i;j ) 2 G

xij  cij

soit minimal. Le plus souvent, nous serons à la recherche d’un flot maximal à coût minimal. Les algorithmes les plus performants travaillent alors en deux temps. D’une part, la recherche du flot maximal permet de fixer sa valeur. Il est alors possible, soit de rechercher ex nihilo un nouveau flot de coût minimal, soit de modifier le flot obtenu précédemment afin de le rendre minimal. Ce problème est d’une importance cruciale en recherche opérationnelle. En effet, comme nous le verrons plus tard, il sert à modéliser de nombreux cas concrets. Longtemps considéré comme un problème difficile, la démonstration de sa polynomialité par Edmonds et Karp ouvrit en son temps de nouveaux horizons en recherche opérationnelle.

39

5.4 5.4.1

Quelques techniques utilisées sur les réseaux Le graphe d’écart

Lorsque l’on travaille sur les flots, il est souvent intéressant d’utiliser un graphe spécial, dérivé du graphe initial, nommé graphe d’écart et noté G(x) = (X; E (x)). Soit (i; j ) un arc de G de capacités minimale et maximale respectives lij et uij et portant le flot xij . Il est alors possible soit : – d’ajouter encore jusqu’à uij

, xij unités de flot depuis i vers j .

,

– de retirer jusqu’à xij lij unités de flot depuis i vers j , ce qui peut ête vu comme l’ajout d’autant d’unités de flot depuis j vers i. Le graphe d’écart

G(x) va donc

proposer deux arcs mettant en avant ces deux

possibilités :

(i; j ) (j; i)

de capacité résiduelle de capacité résiduelle

rij = uij , xij rji = xij

arc direct de (i; j ) arc opposé de (i; j )

En outre, seuls les arcs de capacité résiduelle non nulle sont présents dans le graphe d’écart. Notez le cas intéressant où lij = uij . Nécessairement, tout flot compatible est tel que xij = lij = uij . Alors, le graphe d’écart ne contient ni l’arc (i; j ), ni l’arc (j; i) car ils ont tous deux une capacité résiduelle nulle.

5.4.2

La notion de coupe

On appelle coupe la partition de l’ensemble des nœuds d’un réseau en deux ensembles notés S et S . Une telle coupe est notée [S; S ] et devient une st-coupe si s S et t S . Deux ensembles d’arcs sont à étudier en particulier :

2

2

8 n o < (S; S ) = (i; j ) 2 G = i 2 S et j 2 S = !+ (S ) : (S; S ) = n(i; j ) 2 G = i 2 S et j 2 S o = !, (S )

On définit la capacité de la st-coupe [S;

S ], et l’on note u([S; S ]), la quantité : X uij u([S; S ]) = (i; j )2(S;S )

5.1 Définition (Coupe minimum) On appelle coupe minimum, la st-coupe de capacité minimale. 40

5.1 Théorème (Théorème flot-max / coupe-min) La valeur maximale du flot pouvant circuler sur un réseau est égale à la capacité de la coupe minimum. Cette notion sera étudiée plus en détails lors de la présentation de l’algorithme de Ford et Fulkerson pour la recherche du flot max.

5.5

Quelques exemples de problèmes modélisables par les flots

Tous les problèmes qui mettent en jeu un flux physique de matière, d’électricité ou d’information se modélisent naturellement par les flots. Toutefois, il est d’autres catégories de problèmes qui les mettent en jeu de manière moins triviale.

5.5.1

Problèmes faisant intervenir le flot maximal

Le problème des représentants Soit une entreprise comptant n employés E1, E2 , : : : , En . Ceux-ci sont répartis dans m corps de métiers et r catégories socio-professionnelles ; un employé pouvant appartenir à plusieurs corps de métiers mais à une et une seule catégorie socioprofessionnelle. Lors des élections des représentants du personnel (modèle grand-breton), chaque corps de métier doit désigner 1 représentant pour le bureau sachant que chaque catégorie socio-professionnelle j ne peut avoir plus de uj membres siégeant. La question que l’on va résoudre en utilisant un flot maximal est la suivante : Existe-t-il un bureau compatible avec ces contraintes? Pour répondre à cette (légitime) interrogation, on va utiliser le graphe suivant. On associe à chaque corps de métier Ci un sommet ci et un arc (s; ci ) de capacité maximale 1 représentant le fait que chaque corps de métier désigne 1 représentant. A l’autre bout du graphe, chaque catégorie socio-professionnelle Pj se voit représentée par un sommet pj auquel on associe immédiatement l’arc (pj ; t) de capacité maximale uj , nombre maximal de membres de la catégorie professionnelle autorisés à siéger au bureau. 41

Finalement chaque employé Ek est modélisé par le sommet correspondant ek . L’appartenance d’un employé à ses corps de métier est représentée par des arcs du type (ci; ek ) de capacité maximale 1, alors que son appartenance à une catégorie socioprofessionnelle est trahie par un arc unique du type (ek ; pj ). Le bureau est réalisable s’il existe un flot de valeur

P implique que uj > m.

m compatible avec le réseau

ainsi constitué, ce qui Un tel flot, s’il existe, pourra être obtenu en résolvant un problème de flot maximum sur le réseau, car n est une borne max pour la valeur du flot. La figure suivante illustre un réseau modélisant ce problème de représentation. e 1 1 c 1 1

s

1

1

1 e 2

1

c 2

1

1

p e 3

1

u

1

1

1

1 c 3

1

t p 2

u

2

e 4 1 1

e

5

F IG. 5.4: Modélisation du problème des représentants dans un réseau

Le problème de l’arrondi cohérent

n  m matrice de nombres réels. On note respectivement i; i 2 1::n et j ; j 2 1::m les sommes des éléments sur les lignes et les colonnes. Soit D une

Le but de ce problème est d’arrondir chacun des nombres stocké dans la matrice de manière à ce que, pour chaque ligne et pour chaque colonne, la somme des nombres arrondis soit l’arrondi de la somme. En d’autres termes, et si l’on note  l’arrondi du 42

nombre  , on doit avoir :

8 m P > <8 i 2 1::n j=1 dij =i n > :8 j 2 1::m P dij = j i=1

Contrairement à de nombreuses applications où l’arrondi est imposé à l’entier le plus proche, ici   est choisi librement parmi  et  .

bc de

Il est possible de modéliser ce problème très facilement à l’aide d’un réseau. Il suffit de considérer, en plus des sommets s et t, deux ensembles de sommets et C modélisant respectivement les lignes et les colonnes de la matrice.

L

2 L est ainsi associé à la ième ligne de la matrice. Les arcs (s; li) ont pour capacités le couple (bi c; di e). Réciproquement, chaque sommet cj 2 C étant associé à la jème colonne de D, les arcs (cj ; t) ont pour capacités (b j c; d j e). Chaque sommet li

Reste à modéliser chacun des éléments de la matrice par un arc reliant sa ligne et sa colonne. Ainsi, l’élément dij est représenté par l’arc (li ; cj ) de capacités (  ;  ).

bcde

D’ordinaire, il existe plusieurs solutions à ce problème, chacune étant associée à un flot compatible sur ce réseau. Toutefois, le flot max est associé à la solution utilisant le plus de valeurs supérieures alors que le flot min est associé à la solution utilisant le plus de valeurs inférieures. La figure suivante illustre ce modèle sur un exemple simple. Données de la matrice :

3; 1 6; 8 7; 3 9; 6 2; 4 0; 7 3; 6 1; 2 6; 5 Sommes des lignes :

17; 2 12; 7 11; 3 Sommes des colonnes :

16; 3 10; 4 14; 5 F IG. 5.5: Modélisation du problème de l’arrondi cohérent d’une matrice par un réseau

43

5.5.2

Application du problème de flot de coût minimal

Problème de transport simple Soit n sites de fabrication Fi de m produits Pk devant être acheminés vers q sites de consommation Cj . Chaque couple (Fi ; Pk ) est caractérisé par la capacité de production fik . Réciproquement, chaque couple (Cj ; Pk ) est muni de la demande djk en produit Pk sur le site Cj . Finalement, chaque couple Fi; Cj est défini par le coût d’acheminement ckij d’un produit depuis son site de fabrication vers le lieu de consommation ainsi que par lijk et ukij , quantités respectives minimales et maximales et par produit devant être délivrées d’un site à l’autre. Ces quantités modélisent des contraintes qui peuvent être du type contractuel (pour les limites inférieures) ou bien refléter la saturation des lignes de transport. Ce problème ultra classique se modélise aisément comme un problème de flot de coût minimum par le réseau suivant. 1. Tout d’abord, chaque site de fabrication contribution :

8 i 2 1::n

Fi

est représenté par une source de

b(Fi) =

m X k=1

fik

2. A l’autre bout du réseau, chaque site de consommation est représenté par un puits de contribution :

8 j 2 1::q

b(Cj ) = ,

m X k=1

djk

3. Les produits sont, quand-à-eux, représentés par deux ensembles de sommets : – Le premier modélise les associations fabricant/produit. Chaque sommet Fi est relié au sommet fpik si et seulement si il fabrique le produit Pk . La capacité de ces arcs est fixée à fik , capacité maximale de fabrication du produit k par i.

– Le second modélise les associations consommateur/produit. Chaque sommet Cj est relié aux sommets cpjk associés aux produits qu’il consomme par des arcs de capacité djk . Finalement les arcs de transport relient les sommets fpik aux sommets cpjk de k et uk alors que leur coût est fixé à ck . même produit Pk . Leurs capacités sont lij ij ij

44

La recherche du flot maximal à coût minimal sur ce réseau garantit l’optimalité de la solution. Il suffit alors de suivre les chaînes de flot pour retracer le trajet des marchandises. La figure suivante montre un cas à trois fabricants, deux produits et deux consommateurs. Il est à noter que la taille du graphe peut devenir très importante avec le nombre d’acteurs mis en jeu. f 11

fp 11

f 12

fp 12

f 1 d

cp 11

d f 21

fp 21

cp 12

f 22

fp 22

cp 21

11 12

c 1

f 2 d d f 31

cp 22

fp 31

21 c 22

2

f3 f 32

fp 32

(

2 2 2 l , u , c 32 32 32

)

F IG. 5.6: Modélisation du problème de transport simple par un réseau

5.6

L’algorithme de Ford & Fulkerson

L’algorithme de Ford & Fulkerson est le premier à avoir été spécialement conçu pour la résolution du problème de flot maximal. De nombreuses variantes destinées à accroître ses performances ont depuis vu le jour. Bien que les algorithmes de type Preflow Push dûs à Karzanov lui soient très supérieurs en performances, l’algorithme de Ford & Fulkerson est une base théorique indiscutable.

45

5.6.1

Capacité résiduelle dans le cas général

Dans le cas simple où l’on exclue le fait que les arcs (i; simultanément, la capacité résiduelle de l’arc (i; j ) s’écrit :

j ) et (j; i) soient présents

rij = uij , xij Dans le cas général, on peut étendre cette définition en prenant en compte la valeur du flot passant sur l’arc opposé, soit :

rij = uij , xij + xji En effet, il est toujours possible de «gagner» du flot dans le sens le flot présent sur l’arc (j; i).

5.6.2

i ! j en retirant

Démonstration du théorème Flot max / Coupe min

La capacité résiduelle r[S; S] d’une st-coupe [S; S] s’écrit :

r[S; S] = Soit ainsi :

X

(i; j ) 2 (S; S)

rij

v la valeur du flot. Mettant à profit la notion de coupe, nous pouvons l’écrire 2 3 X X4 X X v= xsj = xij , xji5 i 2 S j :(i; j ) 2 G

j (s; j ) 2 E

j :(j; i) 2 G

Soient maintenant 2 sommets p et q appartenant tous deux à S . Il est possible de simplifier l’expression précédente en remarquant que xpq et xqp vont apparaître des deux côtés du signe , une fois lors de la somme portant sur p et une fois lors de la somme portant sur q .

,

Aussi, l’on peut réécrire v :

v=

X (i; j ) 2 (S; S)

xij ,

X  S) (i; j ) 2 (S;

xij

où l’on notera :

8 X > > < (i; j) in (S; S) xij X > xij > :  (i; j ) in (S; S )

S] Flot arrière de la coupe [S; S] Flot avant de la coupe [S;

46

La valeur du flot

v est donc égale au flot net de la coupe [S; S].

On a :

X (i; j ) 2(S; S)

X

xij 6

(i;j ) 2(S; S)

uij

et comme :

X

xij > 0

 S) (i; j ) 2(S;

alors :

v 6

X (i;j ) 2(S; S)

uij = u[S; S]

On obtient donc que la valeur du flot est inférieure ou égale à la capacité de toute st-coupe du réseau. Par extension, si l’on découvre un flot de valeur égale à la capacité d’une coupe, alors : 1. Le flot est maximal 2. La coupe est de capacité minimale

5.6.3

Augmentation maximale du flot

Connaissant une valeur de flot v et considérant une st-coupe quelconque [S; S], de quelle valeur
v peut-on encore espérer augmenter v ? Supposons donc qu’il existe un flot x0 de valeur v l’on a :

v +
v 6

+
v. Par la relation précédente,

X (i;j ) 2(S; S)

uij

pour toute st-coupe [S; S]. Or, nous avons vu dans la démonstration précédente que v est égal au flot net dans la coupe, soit :

47

v=

X (i; j ) 2 (S; S)

xij ,

X  S) (i; j ) 2 (S;

xij

qui est aussi égal à :

v=

X (i; j ) 2 (S; S)

xij ,

X  S) (i; j ) 2 (S;

xji

d’où :

v +
v , v 6

X (i;j ) 2(S; S)

uij ,

X (i; j ) 2 (S; S)

xij +

X  S) (i; j ) 2 (S;

xij

soit :


v 6

X (i;j ) 2(S; S)

(uij , xij ) +

X  S) (i; j ) 2 (S;

xij

où encore :


v 6

X (i;j ) 2(S; S)

(uij , xij ) +

X  S) (i; j ) 2 (S;

xij

Soit finalement :


v 6

X (i; j ) 2(S; S)

rij +

X  S) (i; j ) 2 (S;

xij

Or, comme un flot est une quantité positive, l’on en déduit donc que l’augmentation maximale est bornée par la capacité résiduelle de la coupe.

48

5.6.4

Forme naïve de l’algorithme de Ford & Fulkerson

Cette forme est intéressante car elle est facile à appliquer manuellement. Algorithme de Ford & Fulkerson sous forme manuelle Faire xij 0 sur tous les arcs du réseau G Calculer le réseau résiduel G(x) Tant qu’il existe un chemin depuis s vers t sur Calculer r min rij (i;j ) 2 C

C

G(x)

Pour chaque arc (i; j ) de G(x) : rij rij r xij xij + r sur l’arc direct rji rji + r xij xij + r sur l’arc opposé Supprimer (i; j ) si rij = 0 Fin Pour Fin Tant que

,

5.6.5

Une implémentation possible de l’algorithme de Ford & Fulkerson

Voici l’algorithme tel qu’on le programme habituellement : Algorithme de Ford & Fulkerson sous forme programmable Marquer t Faire xij 0 sur tous les arcs du réseau G Calculer le réseau résiduel G(x) Tant que t est marqué : Supprimer les marques de tous les sommets pred[i] i X marquer s et faire Liste s Tant que Liste = et t non marqué Retirer un sommet i de la liste (i; j ) !+ (i) tel que j non marqué marquer j pred[j ] i Liste Liste j Fin Fin Tant Que Si t est marqué Augmenter le flot sur le chemin de s à t contenu dans pred Mettre à jour G(x) Fin Si Fin Tant que

;

8 2 6 ;

8

fg

2

8

[f g

49

L’algorithme se termine lorsque l’on ne peut pas marquer le sommet t. Soit donc S l’ensemble des nœuds marqués. On pose tout naturellement : S = X S .

(

Par construction :

n

s2S t 2 S

donc, [S; S] est une st-coupe. Si l’on n’a pas pu marquer t cela signifie que l’algorithme ne peut plus marquer de sommets de S depuis S . On en déduit donc que :

rij = 0 8 (i; j ) tel que i 2 S et j 2 S or, par définition du graphe d’écart :

rij = (uij , xij ) + xji En outre, par définition d’un flot :

(

xij 6 uij

donc

(uij , xij )> 0 xji >0

rij est donc une somme nulle de termes positifs ou nuls, ce qui signifie immédiatement que les deux termes sont nuls ! Donc :

xij = uij 8 (i; j ) 2 (S; S)  S) xij = 0 8 (i; j ) 2 (S; or :

v=

en appliquant xij

X (i; j ) 2 (S; S)

 S) : = 0 8 (i; j ) 2 (S;

v= et comme xij

xij ,

X  ) (i;j ) 2 (S;S

X

(i; j ) 2 (S; S)

xij

xij

= uij 8 (i; j ) 2 (S; S), on obtient finalement : X v= uij (i; j ) 2 (S; S)

On est donc dans une situation où le flot est égal à la capacité de la coupe. Ce qui veut dire que nous sommes dans le cas flot max/coupe min. On a donc réussi ! Ce qui nous conduit au théorème suivant : 5.2 Théorème (Condition d’optimalité d’un flot maximal) Le flot x est maximal sur le réseau G si et seulement si le réseau résiduel contient pas de chemin depuis s vers t. 50

G(x) ne

En effet, s’il existait un tel chemin, ce serait un chemin augmentant sur lequel on pourrait pousser du flot. Réciproquement, supposons que G(x) ne contienne pas de chemin. L’ensemble S des sommés marqués par l’algorithme de Ford & Fulkerson forme une st-coupe dont la capacité est égale au flot, d’où l’optimalité.

5.6.6

Une amélioration possible

Il est possible d’ameliorer significativement les performances de l’algorithme de Ford & Fulkerson en mettant à profit une idée de Edmonds & Karp : Plutôt que de choisir un chemin augmentant au hasard, il faut systématiquement considérer le plus court chemin de s vers t au sens du nombre d’arcs dans le chemin. Cette modification garantit la terminaison de l’algorithme sur tout réseau non dégénéré !

51

Chapitre 6 Le problème des arbres couvrants de poids minimal 6.1

Définitions

6.1 Définition (Arbre Couvrant) Soit G un graphe non orienté muni d’une fonction c de valuation sur les arcs. On appelle Arbre Couvrant tout sous graphe connexe et sans cycle qui recouvre tous les sommets.

Le coût d’un tel arbre est :

C (T ) =

X (i;j ) 2 T

cij

Par définition des arbres, un Arbre Couvrant est composé de n

, 1 arcs.

6.2 Définition (Arbre Couvrant de Poids Minimal) On appelle Arbre Couvrant de Poids Minimal (souvent abrégé ACM) l’arbre couvrant qui minimise la somme des coûts des arcs qui le constituent. Par exemple, l’arbre des plus courts chemins depuis un sommet autres sommets constitue un arbre couvrant sur un graphe orienté.

s vers tous les

Il est néanmoins important de bien différencier les deux problèmes. Les éléments suivants peuvent vous y aider : 1. Le problème de plus courts chemins est le plus souvent traité sur un graphe orienté alors que la notion d’arbre de recouvrements est fondamentalement non orientée. Vous retiendrez qie rechercher les plus courts chemins est une opération plus compliquée et plus coûteuse que la mise en évidence d’un ACM. 52

2. Les deux problèmes travaillent avec des fonctions objectif différentes. Dans le cas des plus courts chemins. On recherche un chemin de longueur minimale pour chaque couple (s; i) i G. Alors que dans le cadre de l’ACM on minimise le coût total de l’arbre (en tant que somme des longueurs de ses arêtes) ce qui n’est absolument pas la même chose !

8 2

6.2

Applications des ACM

6.2.1

Les problèmes de conception d’architectures

C’est une vaste famille de problèmes mettant en jeu des interactions entre divers composants d’un système où l’on désire proposer un service ou assurer des communications au moindre coût. Il est important de voir que l’on se place ici du point de vue du concepteur et non point de celui de l’utilisateur. Le plus souvent cette famille revient à connecter physiquement les composants en supprimant les redondances pour avoir un système le plus simple possible : un arbre. 1. Construction d’autoroutes pour relier des grandes villes avec le plus faible kilométrage total. Ici, la dualité entre le point de vue du constructeur et celui de l’utilisateur est la plus forte. En effet, ce qui intéresse l’utilisateur c’est de pouvoir se rendre depuis son point d’entrée sur le réseau vers chacune de ses destinations et ce, le plus rapidement possible. Le sous graphe qui l’intéresse est donc l’arborescence enracinée sur son point d’entrée. A l’autre bout de la chaîne, le concepteur du réseau veut minimiser ses frais d’installation et donc construire le réseau qui permet d’assurer le service (c’est à ) dire l’interconnexion entre toutes les villes) mais dont la longueur totale soit minimale. Il choisit donc l’ACM. 2. La construction d’un réseau de télécommunication entre les divers établissements d’une entreprise ; chaque site étant équipé de son propre sous réseau, il suffit ici de créer un arbre reliant l’ensemble des sites. 3. Créer un réseau d’ordinateurs avec des lignes à haute capacité genre Liaison Spécialisée à Haut Débit.

53

4. L’ACM se révèle le meilleur compromis pour construire les circuits électriques à haute fréquence : (a) Il est important de réduire la longueur totale du circuit afin d’éviter les effets d’induction de ligne à retard et de parasitage (b) Tous les composant doivent néanmoins être connectés.

6.2.2

Le problème des agents secrets

Soit un groupe d’agents secrets infiltrés dans un pays à surveiller. On construit un graphe où les agents secrets sont les nœuds et les arcs représentent un couple d’agents secrets qui se connaissent et peuvent donc se transmettre un message. Le but est d’établir un moyen de passer un message entre tous les agents secrets en minimisant le risque de voir celui-ci passer à l’ennemi. Pour On note pij la probabilité de voir passer le message à l’ennemi lors de la transmission entre l’agent i et l’agent j. On cherche donc à minimiser :

1,

Y (i;j ) 2 T

(1 , pij )

Cette formule n’étant pas directement utilisable, on doit transformer ce produit en somme. Pour ceci, nous passons au logarithme. Ainsi :

max devient :

Y

(i;j ) 2 T

(1 , pij )

0 1 Y max log @ (1 , pij )A (i; j ) 2 T

soit encore :

max

X (i;j ) 2 T

log(1 , pij )

Le problème se résume donc à rechercher un arbre de recouvrement de poids maximal après passage au log des poids sur les arcs. Regrouper des données en amas Il s’agit ici de résoudre un problème de classification de données très courant en analyse de données. L’un des secteurs d’activité le plus friand de ce type de problème est assurément celui de la médecine. 54

En effet, considérons un ensemble de patients présentant tous la même maladie (pour le moment inconnue) mais avec des examents cliniques différents. Le but est de regrouper les patients en paquets afin de rattacher leur syndrôme à quelque chose de «connu». La méthodologie retenue consiste à créer un graphe complet où les patients sont les sommets et les arcs sont valués conformément à une distance qui peut être, par exemple, le nombre de critères différents ou bien encore des fonctions de pondération sur chacun des critères cliniques retenus. On peut définir des amas en créant un ACM puis en coupant les arcs de plus fort coût. Le plus compliqué est de savoir à partir de quelle limite de coût on ne doit plus retenir d’arcs. Nous verrons que l’algorithme de Kruskal est le mieux adapté pour cet exemple.

6.3

Les conditions d’optimalité d’un ACM

Il y a deux conditions d’optimalité parfaitement duales et amenant chacune un algorithme de résolution du problème. La première porte sur les coupes, la seconde sur les chemins.

6.3.1

La condition d’optimalité de coupes

En préliminaire, il est important de préciser que l’on entend ici par coupe associée à un sous graphe H de G un couple (S; S ) sans arête entre S et S . 6.1 Théorème (Condition d’optimalité de coupes d’un ACM) Soit T  un arbre de couverture du graphe G. T  est un ACM si et seulement si :

8 (i; j ) 2 T 

cij 6 ckl 8 (k; l) 2 [S; S ] formée en retirant (i; j ) de T .

La condition est nécessaire

l) 2 [S; S ] tel que ckl < cij . Formons alors l’arbre T = T nf(i; j )g [ f(k; l)g. Si nous appelons C (T ) le coût d’un arbre T , nous avons : C (T ) = C (T ) , cij + ckl Supposons qu’il existe un arc (k;

55

S S

T* i

j

l k

F IG. 6.1: Illustration de la coupe pour l’ACM or comme ckl < cij , il en suit que laquelle T  était optimal.

C (T ) < C (T ) ce qui contredit l’hypothèse selon

La condition est également suffisante En effet, soit T  un arbre satisfaisant la condition précédente et que T  = T 0. Soit alors (i; j ) un arc de T  T 0.

6

62

T 0 un ACM tel

2

2

Si l’on supprime (i; j ) de T , on crée une coupe [S; S ] telle que i S et j S . 0 Ajoutons maintenant cet arc (i; j ) dans T . Il va alors y avoir création d’un cycle qui contient nécessairement un arc (k; l) avec k S et l S .

(

Or :

T T0

2

Vérifie la condition d’optimalité, d’où : Est optimal, d’où :

56

2

cij 6 ckl ckl 6 cij

on en déduit immédiatement que cij = ckl . On peut donc remplacer (i; j ) par (k; l) dans T  sans altérer la propriété. En outre, T  et T 0 ont un arc commun de plus. Itérer ce processus jusqu’à ce que T  = T 0 conclut la démonstration.

6.3.2

La condition d’optimalité de chemin

6.2 Théorème (Condition d’optimalité de chemins d’un ACM) Un arbre de recouvrement T  est un ACM de G si et seulement si :

8 (k; l) 2 G n T  cij 6 ckl pour tout arc (i; j ) du chemin qui connecte k à l dans T. La condition est nécessaire En effet, si ckl < cij , alors le remplacement de (i; j ) par meilleur arbre ce qui contredit l’hypothèse d’optimalité.

(k; l) permet d’obtenir un

La condition est suffisante La preuve de suffisance de cette condition utilise la condition sur les coupes, ce qui permet de mettre en évidence la connection forte entre ces deux notions. Soit T  un arbre satisfaisant la condition et (i; j ) un arc quelconque de cet arbre. Supprimons le, on crée alors une coupe [S; S ] avec i S et j S ].

2

Soit l’arc un arbre :

2

(k; l) appartenant à [S; S ] mais n’appartenant pas à T . Comme T  est

1. Il existe une chemin unique dans T  permettant de joindre k à l 2.

(i; j ) était le sul arc joignant S à S et appartenant à T .

On en déduit que (i; j ) appartient au chemin joignant vérifie la condition on en déduit que cij 6 ckl .

k à l dans T . et comme T 

Comme nous n’avons posé aucune condition particulière sur le choix de l’arc (k; l), ce raisonnement s’applique à chaque arc de [S; S ]. On en déduit donc que T  vérifie la condition de coupe : il est donc optimal !

57

6.4 6.4.1

Les algorithmes de recherche d’un ACM L’algorithme de Kruskal

Cet algorithme construit l’arbre en ajoutant à chaque itération l’arbre de plus petit coût n’ajoutant pas de cycle. Comme il n’ajoute pas nécessairement des arcs sur des sommets contigüs, cet algorithme peut être vu comme le regroupement progressif d’une forêt (donc chaque arbre ne contient initialement qu’un seul sommet) en un seul arbre en ajoutant les arcs de plus faible coût.

6.4.2

L’algorithme de Prim

Très différente de l’algorithme de Kruskal, la méthode de Prim construit une coupe et rajoute l’arc de poids minimal sortant de la coupe rajoutant ainsi dans la coupe le sommet issu de cet arc.

6.4.3

Illustration par l’exemple

Nous allons successivement dérouler le fonctionnement des algorithmes de Kruskal et de Prim sur le graphe de la figure (6.2);

2

10

4

25

20

30

3

15

5

35 1 40

F IG. 6.2: Graphe d’exemple pour l’illustration des algorithmes de Kruskal et Prim

Les figures (6.3) et (6.4) illustrent respectivement les algorithmes de Kruskal et de Prim. A chaque étape, l’arc ajouté est désigné par une flèche. Les arcs déja présents dans l’arbre sont signalés par un trait en pointillés.

58

2

10

4

35 1

10

4

25

20

30

35 25

20

30

1

40

40 3

15

5

3

15

5

2

10

4

2

10

4

25

20

30

3

15

5

2

10

4

25

20

30

3

15

5

35 1

2

35 25

20

30

1

40

40 3

15

5

Ici, on ne peut sélectionner ni (2,3) ni (4, 5) car ils créeraient un cycle. On se rabat donc sur (1, 2) et l'algorithme est terminé !

35 1 40

F IG. 6.3: Fonctionnement de l’algorithme de Kruskal sur le graphe (6.2)

59

2

10

4

35 1

20

30

1

40

4

25

20

30

40 3

15

5

3

15

5

2

10

4

2

10

4

25

20

30

3

15

5

35

35 25

20

30

1

40

40 3

15

5

2

10

4 A chaque étape, les sommets de S sont ceints d'un trait épais. Remarquez que l'on ne part du sommet 1 que par pure convénience. A chaque étape on marque en gras les arcs avants de la coupe qui n'induisent pas de cycle

35 1

10

35 25

1

2

25

20

30

3

15

5

40

F IG. 6.4: Fonctionnement de l’algorithme de Prim sur le graphe (6.2)

60

Bibliographie [1] R.K. Ahuja, T.L. Magnanti, and J.B. Orlin. Network Flows : Theory, Algorithms, and Applications. Prentice Hall, New York, 1993. [2] M. Gondran and M. Minoux. Graphes et Algorithmes. Eyrolles, Paris, 1979. [3] M. Minoux and G. Bartnik. Graphes, Algorithmes et Logiciels. Eyrolles, Paris, 1986. [4] M. Sakarovitch. Optimisation Combinatoire, Tome 1 : Graphes et Programmation Linéaire ; Tome 2 : Optimisation Combinatoire. Hermann, Paris, 1984.

61