44
Théorie et algorithmique des graphes Guillaume Moreau Ecole Centrale de Nantes EI1 - eLOGRA, mai 2006

Theorie Des Graphes - G. Moreau

  • Upload
    amlo01

  • View
    1.948

  • Download
    8

Embed Size (px)

Citation preview

Page 1: Theorie Des Graphes - G. Moreau

Théorie et algorithmique des graphes

Guillaume MoreauEcole Centrale de Nantes

EI1 - eLOGRA, mai 2006

Page 2: Theorie Des Graphes - G. Moreau

2

Page 3: Theorie Des Graphes - G. Moreau

Table des matières

1 Eléments de théorie des graphes 51.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.2 Graphes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.2.1 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . 81.2.2 Voisins - Degrés . . . . . . . . . . . . . . . . . . . . . . 81.2.3 Sous-graphes, graphes partiels. . . . . . . . . . . . . . . 91.2.4 Graphes non-orientés. . . . . . . . . . . . . . . . . . . . 9

1.3 Chemins, chaînes, cycles. . . . . . . . . . . . . . . . . . . . . . 101.4 Composantes fortement connexes - fermeture transitive. . . . . . 13

1.4.1 Composantes fortement connexes. . . . . . . . . . . . . 131.4.2 Fermeture transitive. . . . . . . . . . . . . . . . . . . . 131.4.3 Graphes fortement connexes. . . . . . . . . . . . . . . . 14

2 Ensembles particuliers dans les graphes 152.1 Nombre de stabilité. . . . . . . . . . . . . . . . . . . . . . . . . 152.2 Nombre d’absorption. . . . . . . . . . . . . . . . . . . . . . . . 162.3 Noyau - fonctions de Grundy. . . . . . . . . . . . . . . . . . . . 16

2.3.1 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . 162.3.2 Exemple de calcul de fonction de Grundy. . . . . . . . . 17

2.4 Nombre chromatique. . . . . . . . . . . . . . . . . . . . . . . . 17

3 Familles de graphes possédant des propriétés particulières 193.1 Graphes planaires. . . . . . . . . . . . . . . . . . . . . . . . . . 193.2 Graphes hamiltoniens et eulériens. . . . . . . . . . . . . . . . . 20

3.2.1 Graphes hamiltoniens. . . . . . . . . . . . . . . . . . . . 203.2.2 Graphes eulériens. . . . . . . . . . . . . . . . . . . . . . 21

4 Algorithmique des graphes 234.1 Représentation en mémoire. . . . . . . . . . . . . . . . . . . . . 23

4.1.1 Matrice d’adjacence. . . . . . . . . . . . . . . . . . . . 234.1.2 Tableaux d’arcs. . . . . . . . . . . . . . . . . . . . . . . 244.1.3 Tableaux de successeurs. . . . . . . . . . . . . . . . . . 244.1.4 Listes chaînées. . . . . . . . . . . . . . . . . . . . . . . 24

3

Page 4: Theorie Des Graphes - G. Moreau

4 TABLE DES MATIÈRES

4.2 Parcours de graphes. . . . . . . . . . . . . . . . . . . . . . . . . 254.2.1 Parcours des arbres. . . . . . . . . . . . . . . . . . . . . 25

4.3 Algorithmes de plus court chemin. . . . . . . . . . . . . . . . . 264.3.1 Algorithme de Ford-Bellman. . . . . . . . . . . . . . . . 264.3.2 Algorithme de Moore ou de Dijkstra. . . . . . . . . . . . 274.3.3 Algorithmes de Bellmann. . . . . . . . . . . . . . . . . 28

4.4 Problème du flot maximal. . . . . . . . . . . . . . . . . . . . . . 314.4.1 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . 314.4.2 Résolution du problème de flot maximal. . . . . . . . . . 324.4.3 Algorithme de Ford-Fulkerson et exemple. . . . . . . . . 34

4.5 Flot maximal à coût minimal. . . . . . . . . . . . . . . . . . . . 384.5.1 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . 384.5.2 Algorithme de Roy. . . . . . . . . . . . . . . . . . . . . 384.5.3 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . 39

5 Démonstrations 43

Page 5: Theorie Des Graphes - G. Moreau

Chapitre 1

Eléments de théorie des graphes

1.1 Introduction

Les graphes constituent une des façons les plus naturelles de représenter bon nom-bre de problèmes de la vie courante comme de celle d’un ingénieur. Ils sont aussireprésentatifs des résultats les plus fondamentaux de l’algorithmique.

Prenons un exemple simple : nous devons nous déplacer de Nantes à Marseilleen utilisant la route. Dans un premier temps, on ne prend en compte que quelquesgrandes villes comme le montre la figure1.1. Les chiffres sont bien sûr assez loinde la réalité. Comme il n’existe pas sur ce graphe de route directe entre Nantes etMarseille, la première question qu’on peut se poser est biensûr celle de l’existenced’un itinéraire entre Nantes et Marseille. On introduit icila notion de fermeturetransitive d’un graphe qui sera étudiée en1.4.2.

Nantes

StrasbourgParis

Bordeaux

Marseille

350

500

350

450

800

800

Figure 1.1: Calculer un itinéraire de Nantes à Marseille

5

Page 6: Theorie Des Graphes - G. Moreau

6 CHAPITRE 1. ELÉMENTS DE THÉORIE DES GRAPHES

Intuitivement, on trouve assez facilement que sur ce graphe, le chemin le pluscourt entre Nantes et Marseille ne passe naturellement pas par Strasbourg. Ici, lechemin le plus court passe par Bordeaux et fait 800 kilomètres, comme le met enévidence la figure1.2. Le problème est résoluble manuellement et intuitivementsur un petit nombre de villes et de routes. Pour construire les navigateurs GPSembarqués dans les voitures, ou pour calculer les itinéraires comme sur le sitehttp://www.viamichelin.com en prenant en compte les quelques dizainesde milliers de communes de France, cette approche n’est évidemment plus tenable.On entre dans les algorithmes dits deplus courts cheminsque l’on étudiera auchapitre4 de ce document.

Nantes

StrasbourgParis

Bordeaux

Marseille

350

500

350

450

800

800

Figure 1.2: Le chemin le plus court de Nantes à Marseille

On peut rendre ce problème un peu plus complexe en tenant compte de la naturedes routes qui relient les différentes de villes. Il va de soiqu’on roulera en généralplus vite sur une autoroute que sur une petite route de campagne. Encore que cecipeut s’avérer faux au moment des départs en vacances... On introduira donc aussiles problèmes de flots dans les graphes.

Il existe encore un autre type de problème que nous n’avons pas abordé. Ilne fait pas partie des problèmes de graphes a priori mais peuts’exprimer aussisous forme de graphe. C’est un des problèmes fondamentaux del’algorithmiquethéorique, il est usuellement utilisé enthéorie de la complexitépour introduirela classe des problèmesNP-complets. On l’appelle le problème du voyageur decommerce : il s’agit, toujours dans le même graphe, de déterminer l’itinéraire idéald’un voyageur de commerce qui doit passer une et une seule fois par chaque ville,tout en minimisant le nombre de kilomètres parcourus. On montre qu’il n’existe

Page 7: Theorie Des Graphes - G. Moreau

1.1. INTRODUCTION 7

pas d’algorithme en temps polynomial1 pour résoudre le problème.D’autres types de problèmes utilisent les graphes, en informatique comme

dans d’autres disciplines des sciences de l’ingénieur. Parexemple, si on con-sidère une carte de France comme celle de la figure1.3 coloriée de façon à ceque deux départements adjacents aient une couleur différente, quel est le nombrede couleurs minimal à utiliser ? On montrera dans la section3.1 consacrée auxgraphes planaires qu’il faut au minimum 4 couleurs.

Figure 1.3: Colorier une carte de France

Le dernier exemple de cette introduction concerne la gestion de projet. Dansun projet, un certain nombre de tâches peuvent s’effectuer en même temps qued’autres tandis qu’au contraire, il est indispensable que certaines tâches aient étécomplétées avant que d’autres ne commencent. Cette fois encore, ces dépendancesentre tâches peuvent exprimées sous forme de graphes. Cetteapproche est valablepour une recette de cuisine comme pour un planning de PEI maisaussi pour la pro-grammation parallèle : en effet, pour calculer une moyenne générale, on a besoinque toutes les moyennes aient été calculées, mais a contrario, pour calculer un pro-duit matriciel certaines parties peuvent se dérouler en parallèle : dans l’expression

(cij)1≤i,j≤n=

n∑

k=1

aikbkj (1.1)

le calcul decij est indépendant de celui deci′j′ ; ils peuvent donc être calculés

1c’est-à-dire que le temps d’exécution du programme ne peut pas être une fonction polynomialedu nombre de sommets du graphe

Page 8: Theorie Des Graphes - G. Moreau

8 CHAPITRE 1. ELÉMENTS DE THÉORIE DES GRAPHES

indépendamment les uns des autres. Par contre, le calcul d’un cij nécessite que lescalculs de tous lesaikbkj aient été effectués pour tous les valeurs dek. On appelleces graphes des graphes de dépendance.

1.2 Graphes

1.2.1 Définitions

Définition 1.2.1 Un grapheG = (X,U) est le couple constitué d’un ensembledénombrable de sommetsX et d’une familleU d’éléments deX2 appelés arcs.

Dans ce cours, nous n’aborderons que les cas oùX est fini. On représente lessommets par des points et les arcs correspondant à un couple de sommets(x, y)par une ligne joignantx à y, portant une flèche dex versy. On dit alors quex estl’origine de l’arc, tandis quey est son extrémité.

Un exemple de graphe est représenté figure1.4.

E

F

D

B

C

A

Figure 1.4: Exemple de graphe

S’il existe deux arcs reliant les mêmes sommets, on parle de graphes multiplesou multigraphes comme celui représenté sur la figure1.5. Dans ce cours, nousnous intéresserons essentiellement aux graphes simples etsouvent sans boucles.

1.2.2 Voisins - Degrés

Soient un grapheG = (X,u) et un couple(x, y) ∈ U . y est alors appelé unsuccesseur dex, etx un prédécesseur dey. On note :

• Γ+(x) l’ensemble des successeurs dex

• Γ−(y) l’ensemble des prédécesseurs dey

Γ(x) = Γ+(x) ∪ Γ−(x) représente les voisins dex, ou encore les sommetsadjacents àx. Dans le graphe de la figure précédente,Γ+(A) = {E,D,B} etΓ+(A) = 0.

Page 9: Theorie Des Graphes - G. Moreau

1.2. GRAPHES 9

E

F

D

B

C

A

Figure 1.5: Exemple de multigraphe

Remarque : (X,Γ+) suffit à définir complètement le graphe...Γ+ = ∪x∈XΓ+(x)Le demi-degré extérieurd’un sommetx, notéd+(x), est le nombre d’arcs issus

de x, c’est-à-dire qued+(x) = |Γ+(x)|. De la même façon, on définit ledemi-degré intérieur, notéd−(x), comme étant le nombre d’arcs incidents àx, c’est-à-dire qued−(x) = |Γ−(x)|. Le degré d’un sommet est alors la somme de sesdemi-degrés intérieur et extérieur.

On dit qu’un graphe estcompletsi et seulement si∀x, y ∈ X alors(x, y) ∈ U ,c’est-à-dire si et seulement si tous les sommets sont reliésdeux à deux (dans lesdeux sens). Dans le cas d’un graphe complet àn sommets, tous les demi-degrésintérieurs et extérieurs sont égaux àn − 1.

1.2.3 Sous-graphes, graphes partiels

Définition 1.2.2 On appelle sous-graphe deG = (X,U) le grapheG′ = (X ′, UX′)engendré par un ensemble de sommetsX ′ ⊂ X où UX′ représente les arcs deUayant leur origine et leur extrémité dansX ′.

Définition 1.2.3 De la même manière on appelle graphe partiel deG = (X,U)engendré parU ′, le grapheG′ = (X,U ′) oùU ′ ⊂ U , c’est-à-dire qu’on conservetous les sommets mais qu’on supprime certains arcs.

Les deux graphes de la figure1.6représentent respectivement le graphe partielde l’exemple de la figure1.4 engendré par les sommets{A,D,E,F} et le sous-graphe de ce même exemple dans lequel on a supprimé les arcs(E,D) et (D,E)et (E,F ).

1.2.4 Graphes non-orientés

Pour étudier certaines propriétés d’un graphe, on n’a pas toujours besoin de faireréférence à l’orientation, par exemple si on veut seulementsavoir si deux sommets

Page 10: Theorie Des Graphes - G. Moreau

10 CHAPITRE 1. ELÉMENTS DE THÉORIE DES GRAPHES

E

F

D

A

E

F

D

B

C

A

Figure 1.6: Exemple de sous-graphe et de graphe partiel

sont reliés ou non. Dans ce cas, on considère des arêtes(x, y) et non plus des arcs(x, y). Les notions de voisins et de degrés subsistent bien entendu. La figure1.7présente un exemple de graphe non-orienté.

Théorème 1.2.1SoitG = (X,E) un graphe non-orienté. Le nombre de sommetsde degré impair est pair.

Démonstration

F

BA

DE C

Figure 1.7: Exemple de graphe non orienté

Définition 1.2.4 G1 = (X1, U1) et G2 = (X2, U2) sont dits isomorphes si etseulement si il existe une bijectionf : X1 −→ X2 telle que(x, y) ∈ U1 ⇐⇒(f(x), f(y)) ∈ U2.

Le problème de décider si deux graphes sont isomorphes est unproblème al-gorithmiquement difficile.

1.3 Chemins, chaînes, cycles

Définition 1.3.1 On appelle chemin d’un grapheG = (X,U) toute suite d’arcsµ = (u1, ..., up) vérifiant ∀i < p, l’extrémité deui est l’origine deui+1. Si, enplus, l’extrémité deup est égale à l’origine deu1, µ est un circuit.

Page 11: Theorie Des Graphes - G. Moreau

1.3. CHEMINS, CHAÎNES, CYCLES 11

Dans le graphe de la figure1.8, ((A,E), (E,D)) est un chemin et(E,F ), (F,D)(D,E)est un circuit. Naturellement,(E,F ), (F,D)(D,E) est aussi un chemin. Dans lesgraphes non-orientés, on définit de manière analogue les chaînes et les cycles.

E

F

D

B

C

A

Figure 1.8: Exemple de chemin et de circuit

Le nombre d’arcs constitue la longueur de la chaîne ou du chemin. Si le cheminpasse une seule fois par chaque arc, il est ditsimple, s’il passe une seule fois parchaque sommet, il est ditélémentaire.

Définition 1.3.2 G = (X,U) est connexe si et seulement si∀x, y ∈ X il existeune chaîne dex à y.

Propriété 1.3.0.1 La relation R définie parxRy si et seulement si il existe unechaîne dex à y est :

• réflexive

• symétrique

• transitive

Démonstration

C’est donc une relation d’équivalence dont les classes sontappelées lescom-posantes connexesdeG.

Définition 1.3.3 G = (X,U) est dit fortement connexe si et seulement si∀x, y ∈X il existe un chemin dex à y et un chemin dey à x.

Propriété 1.3.0.2 La relation R′ définie parxR′y si et seulement si il existe unchemin dex à y et un chemin dey à x est :

• réflexive

• symétrique

Page 12: Theorie Des Graphes - G. Moreau

12 CHAPITRE 1. ELÉMENTS DE THÉORIE DES GRAPHES

• transitive

Démonstration

C’est donc une relation d’équivalence dont les classes sontappelées lescom-posantes fortement connexesdeG.

La figure1.9 propose un exemple de graphe sur lequel sont représentées sescomposantes fortement connexes. Sur ce graphe, il n’y a par contre qu’une seulecomposante connexe, composée de tous les sommets.

Propriété 1.3.0.3 Un graphe fortement connexe est connexe, mais la réciproqueest fausse (voir figure1.9).

A

CD

B

Figure 1.9: Exemple de graphe connexe mais pas fortement connexe

Définition 1.3.4 G = (X,U) est un graphek-connexe si et seulement si∀A ⊂ Xavec|A| < k, le sous-graphe engendré parX \ A est connexe. La connectivité deG est alors le plus grandk tel queG soitk-connexe, notéK(G).

On peut voir lak-connectivité comme le nombre minimum de sommets qu’ilfaut enlever pour disconnecter le graphe. On remarque queK(G) ≤ minx∈X |Γ(x)| =δ. En effet, si on enlève lesδ voisins dux qui réaliseδ, x n’est plus connecté aureste du graphe.

Théorème 1.3.1(Menger)G est k-connexe si et seulement si∀(x, y) ∈ X2 ilexistek chaînes élémentaires disjointes 2 à 2 intérieurement (sommets) qui relientx ety.

Corollaire 1.3.0.1 SiG k-connexe,x ∈ X, A ⊂ X avec|A| ≥ k, alors il existekchaînes élémentaires disjointes 2 à 2 dex à A.

Page 13: Theorie Des Graphes - G. Moreau

1.4. COMPOSANTES FORTEMENT CONNEXES - FERMETURE TRANSITIVE13

1.4 Composantes fortement connexes - fermeture transi-tive

1.4.1 Composantes fortement connexes

SoitG = (X,U) un graphe. L’algorithme suivant calcule la composante fortementconnexe associée au sommetx0 ∈ X.

marquer le sommet x0 avec ⊕ et ⊖Répéter

marquer avec ⊕ tout successeur non marqué ⊕ d’un sommet ⊕marquer avec ⊖ tout prédécesseur non marqué ⊖ d’un sommet ⊖

jusqu’à ce qu’il n’y ait plus de marquage possible

Les sommets marqués⊕ et ⊖ forment la composante fortement connexe dex0. On peut trouver toutes les composantes fortement connexesen réappliquantl’algorithme à tous les sommets n’appartenant pas encore à une composante forte-ment connexe.

1.4.2 Fermeture transitive

Définition 1.4.1 La fermeture transitive du grapheG = (X,U) est le grapheτ(G) = (X, τ(U)) où (x, y) ∈ τ(U) si et seulement si il existe un chemin dex versy dansG.

Si G est fortement connexe, sa fermeture transitive est le graphe complet.

Figure 1.10: Exemple de graphe avec sa fermeture transitive

Définition 1.4.2 Deux graphesG1 etG2 sont ditsτ -équivalents si et seulement siils ont même fermeture transitive.

On vérifie facilement que la relation deτ -équivalence est une relation d’équivalence.

Page 14: Theorie Des Graphes - G. Moreau

14 CHAPITRE 1. ELÉMENTS DE THÉORIE DES GRAPHES

Définition 1.4.3 On dit queG = (X,U) estτ -minimal si et seulement si∀u ∈ U ,τ(G) 6= τ(G \ {u}).

Pour un graphe donné, il n’existe pas a priori de grapheτ -minimal unique.

Théorème 1.4.1Si G est un graphe sans circuits, alors le grapheτ -minimal estunique.

1.4.3 Graphes fortement connexes

Lorsque qu’un grapheG est fortement connexe, lamatrice d’adjacencede sa fer-meture transitive ne comporte que des 1, en dehors de la diagonale.

Théorème 1.4.2G = (X,U) fortement connexe⇐⇒∀A ⊂ X, A 6= 0 etA 6= X,Γ+(A) 6= A.

Démonstration

Page 15: Theorie Des Graphes - G. Moreau

Chapitre 2

Ensembles particuliers dans lesgraphes

2.1 Nombre de stabilité

Définition 2.1.1 SoitG = (X,U) un graphe non orienté. Un sous-ensembleS ⊂X est dit stable si et seulement si 2 sommets distincts deS ne sont jamais reliés(adjacents), c’est-à-dire si∀x ∈ S, Γ(x)

S = 0.

Figure 2.1: Exemple de stables dans un graphe

SoitS la famille des ensembles stables deG. On a évidemment0 ∈ S et pourtoutS ∈ S avecA ⊂ S, alorsA ∈ S.

Définition 2.1.2 S0 est un stable maximal si et seulement si∀S1 ∈ S et S1 6= S0

alorsS0 6 ⊂S1.

Définition 2.1.3 On appelle nombre de stabilité deG = (X,U), l’entier définipar α(G) = maxS∈S |S|.

Un ensemble stableS ⊂ X qui vérifie |S| = α(G) sera dit stable maximum.Il n’y a pas forcément unicité...

15

Page 16: Theorie Des Graphes - G. Moreau

16 CHAPITRE 2. ENSEMBLES PARTICULIERS DANS LES GRAPHES

Les ensembles stables trouvent leur application dans le problème des huit reines.Il s’agit de placer huit reines sur un échiquier sans qu’elles puissent être deux àdeux en prise (même rangée, même colonne ou même diagonale).On construitalors un graphe à 64 sommets correspondant aux 64 cases de l’échiquier et on relieles cases qui se trouvent sur la même ligne, la même colonne oula même diag-onale. Le problème des huit reines se ramène alors à l’existence d’un stable à 8sommets. Celui-ci n’est d’ailleurs pas unique.

Il n’existe pas d’algorithme polynomial pour résoudre les problèmes de con-struction d’ensemble stable (le nombre d’étapes ne peut pasêtre borné parO(np)).

2.2 Nombre d’absorption

Définition 2.2.1 Soit un grapheG = (X,U). Un ensembleA ⊂ X est absorbantsi et seulement si∀x /∈ A, Γ+(x)

A 6= 0.

On appelleA la famille des ensembles absorbants deA. Si A ∈ A etA ⊂ A′,alorsA′ ∈ A.

Symétriquement à la notion de stable maximal et maximum, on peut définir unabsorbant minimal et un absorbant minimum (non unique). Le nombre d’absorption,notéβ(G) est bien sûr le cardinal du plus petit absorbant.

2.3 Noyau - fonctions de Grundy

2.3.1 Définitions

Définition 2.3.1 Soit un grapheG = (X,U). Un ensembleA ⊂ X est un noyausi il est à la fois stable et absorbant.

Il existe des graphes sans noyaux, ainsi que des graphes à plusieurs noyaux.

Théorème 2.3.1Un noyau est un stable maximal et un absorbant minimal.

Théorème 2.3.2Un graphe simple, sans circuits, admet un noyau. Ce noyau estunique.

Définition 2.3.2 Soit un grapheG = (X,U) un graphe simple sans boucles. Unefonction f : X −→ N est une fonction de Grundy si et seulement si pour toutsommetx, g(x) est le plus petit entier positif ou nul qui n’apparaît pas dans{g(y), y ∈ Γ+(x)}.

Là encore, il n’y a pas forcément existence ou unicité. SiG admet une fonctionde Grundy, il admet un noyau dont les sommets sont les 0 de la fonction de Grundy.

Page 17: Theorie Des Graphes - G. Moreau

2.4. NOMBRE CHROMATIQUE 17

x1 x2 x3 x4 x5 x6 x7 x8

x1 0 0 1 0 0 0 0 0x2 1 0 1 1 1 1 1 1x3 0 0 0 1 1 0 0 0x4 0 0 0 0 1 0 1 0x5 0 0 0 0 0 0 1 1x6 1 0 1 0 0 0 0 0x7 0 0 0 0 0 0 0 1x8 0 0 0 0 0 0 0 0

2.3.2 Exemple de calcul de fonction de Grundy

On cherche à calculer la fonction de Grundy du graphe défini par la matrice d’adjacencesuivante :

On commence par choisirg(x8), x8 est le seul sommet qui n’ait pas de suc-cesseur. il n’y a donc pas de contraintes surg(x8). On lui donne alors la valeur0. De la même façon,x7 a un seul successeur,x8. Pour construire la fonctionde Grundy, on construit le tableau suivant qui contient les successeurs de chacundes sommets et la valeur de la fonction de Grundy pour ceux-ciet la valeur de lafonction de Grundy de chacun des sommets. Dès que la valeur dela fonction deGrundy est définie pour tous les successeurs d’un sommet, on peut définir celle dusommet considéré.

Γ(xi) g(Γ(xi)) g(xi)

x1 x3 1 0x2 x1, x3, x4, x5, x6, x7, x8 0, 1, 2 3x3 x4, x5 0, 2 1x4 x5, x7 2, 1 0x5 x7, x8 0, 1 2x6 x4, x3 1, 0 2x7 x8 0 1x8 0

Table 2.1: Calcul de la fonction de Grundy

2.4 Nombre chromatique

Définition 2.4.1 Une k-coloration des sommets est une partition enk stables(S1, ..., Sk)de l’ensembleX des sommets (à un stable correspond une couleur).

Définition 2.4.2 Le nombre chromatique deG = (X,U) est le plus petit nombre

Page 18: Theorie Des Graphes - G. Moreau

18 CHAPITRE 2. ENSEMBLES PARTICULIERS DANS LES GRAPHES

de couleurs nécessaire pour colorierG de sorte que 2 sommets adjacents soient decouleur différente. On le noteχ(G).

Le problème le plus courant est celui dit des 4 couleurs: peut-on colorier toutecarte de géographie avec 4 couleurs seulement de sorte que deux régions de lacarte qui ont une frontière commune soient de couleur différente ? chaque régionest représentée par un sommet, les arcs rendant compte de l’existence d’une fron-tière commune. On a alors un graphe planaire (les arêtes ne secoupent pas), et laréponse est oui.

Théorème 2.4.1G planaire=⇒ χ(G) ≤ 4

Page 19: Theorie Des Graphes - G. Moreau

Chapitre 3

Familles de graphes possédantdes propriétés particulières

3.1 Graphes planaires

Définition 3.1.1 Un graphe est planaire s’il est possible de le représenter sur unplan sans que deux de ses arcs ne se rencontrent en dehors de leurs extrémités.

Figure 3.1: Exemple de graphes planaires

Définition 3.1.2 On appelle face toute région du plan limitée par des arêtes telleque deux points arbitraires peuvent être reliés par un traitcontinu ne rencontrantni sommet ni arêtes. On appelle alors frontière de la face l’ensemble des arêtesincidentes à celle-ci. Deux faces sont adjacentes si et seulement si elles ont unearête commune.

Il y a toujours une face illimitée...

Théorème 3.1.1(formule d’Euler)G planaire connexe possédantn sommets,marcs etf faces. Alorsf = m − n + 2.

On rappelle qu’un graphe planaire est 4-colorable.

19

Page 20: Theorie Des Graphes - G. Moreau

20CHAPITRE 3. FAMILLES DE GRAPHES POSSÉDANT DES PROPRIÉTÉS PARTICULIÈRES

3.2 Graphes hamiltoniens et eulériens

3.2.1 Graphes hamiltoniens

Définition 3.2.1 Soit G = (X,U) un graphe simple, connexe, sans boucles ànsommets. On appelle cycle hamiltonien deG un cycle élémentaire àn sommets(passant une et une seule fois par chaque sommet).

Définition 3.2.2 Un graphe qui admet au moins un cycle hamiltonien est appelégraphe hamiltonien.

Le graphe complet est hamiltonien.

Théorème 3.2.1SiG est hamiltonien,G est 2-connexe.

La réciproque est fausse. Il est algorithmiquementdifficile de déterminer uncycle hamiltonien dans un graphe. On dispose par contre d’uncertain nombre deconditions suffisantes.

Théorème 3.2.2(Dirac) Soit G = (X,U) un graphe àn sommets. Si∀x ∈ Xd(x) ≥ n

2 , alorsG admet un cycle hamiltonien.

C’est un cas particulier du théorème suivant.

Théorème 3.2.3(Ore) SoitG = (X,U) un graphe àn sommets. Si∀x, y ∈ Xtels que(x, y) /∈ U , d(x) + d(y) ≥ n, alorsG est hamiltonien.

Ce sont deux corollaires d’un théorème plus général, le théorème de Bondy-Chùatal.

Définition 3.2.3 Soit G un graphe àn sommets,k ≤ n un entier, on appelle k-fermeture deG le plus petit grapheH à n sommets contenantG tel que six et yne sont pas adjacents dansH, dH(x) + dH(y) < k.

On obtient cette k-fermeture en reliant récursivement les paires de sommetsdont la somme des degrés est supérieure ou égale àk.

Théorème 3.2.4(Bondy-Chùatal) SoitG = (X,U) un graphe àn sommets,G lan-fermeture deG. G est hamiltonien si et seulement siG est hamiltonien.

On peut définir la notion de chaîne hamiltonienne dans un graphe non-orienté.

Page 21: Theorie Des Graphes - G. Moreau

3.2. GRAPHES HAMILTONIENS ET EULÉRIENS 21

3.2.2 Graphes eulériens

Définition 3.2.4 On appelle cycle (resp. chaîne) eulérien un cycle (resp. chaîne)qui passe par toutes les arêtes une et une seule fois.

Définition 3.2.5 On appelle graphe eulérien, un graphe qui admet au moins uncycle eulérien.

Ce cycle n’est pas forcément élémentaire. L’exemple courant est celui dit des«7 ponts du Königsberg» représenté figure3.2. La question est de déterminer si unpiéton peut faire une promenade en traversant une et une seule fois tous les ponts.Ce problème revient à déterminer si il existe un cycle eulérien dans le graphe dontles sommets sont les îlots et les arcs les ponts.

a

b

d

c

Figure 3.2: Le problème des 7 ponts du Königsberg

Théorème 3.2.5Un multigraphe connexeG admet un cycle eulérien si et seule-ment si ses sommets sont de degré pair.

On peut donc répondre par la négative au problème des 7 ponts du Königsberg.

Page 22: Theorie Des Graphes - G. Moreau

22CHAPITRE 3. FAMILLES DE GRAPHES POSSÉDANT DES PROPRIÉTÉS PARTICULIÈRES

Page 23: Theorie Des Graphes - G. Moreau

Chapitre 4

Algorithmique des graphes

L’objectif de ce chapitre est d’introduire l’algorithmique des graphes, c’est-à-direles principaux algorithmes que l’on utilise avec es graphesen pratique : le pluscourt chemin, les flots dans les graphes... On commencera paraborder les prob-lèmes de représentation des graphes en mémoire.

4.1 Représentation en mémoire

4.1.1 Matrice d’adjacence

Soit un grapheG = (X,U), composé den sommetsx1, ..., xn. Ces sommetsvont nous servir à composer une matrice booléenne carréeA = (aij)1≤i,j≤n définiepar

∀1 ≤ i, j ≤ n, aij =

{

1 si (xi, xj) ∈ U0 sinon

(4.1)

E

F

D

B

C

A

Figure 4.1: Exemple de graphe

23

Page 24: Theorie Des Graphes - G. Moreau

24 CHAPITRE 4. ALGORITHMIQUE DES GRAPHES

Dans le graphe de la figure4.1, la matrice d’adjacence s’écrit donc ainsi :

A =

0 1 0 1 1 00 0 1 0 0 00 1 0 1 0 00 0 0 0 1 00 0 0 1 0 10 0 0 1 0 0

(4.2)

Si le graphe considéré est non-orienté (ou symétrique), on se contentera d’unematrice triangulaire supérieure. On remarque par ailleursque la complexité spa-tiale de cette représentation est enO(n2).

4.1.2 Tableaux d’arcs

Une alternative à cette représentation lorsque le nombre desommets est impor-tant par rapport au nombre d’arcs consiste à créer deux vecteurs contenant chacunl’origine et l’extrémité des arcs. Ainsi la matrice précédente se réécrirait ainsi :

TA =

[

A A A B C C D E E FB D E C B D F D F D

]

(4.3)

La complexité spatiale est cette fois enO(m) où m est le nombre d’arcs. Amoins de choisir une convention d’ordre, cette représentation n’est pas unique...

4.1.3 Tableaux de successeurs

Il s’agit cette fois de construire deux tableaux :

• Le premier tableau contient successivement les successeurs du premier som-met, du second sommet...

• Le second tableau contient la place dans la liste ci-dessus du premier suc-cesseur de chaque sommet.

T1 =[

B D E C B D F D F D]

(4.4)

T2 =[

1 4 5 7 8 10]

(4.5)

La complexité spatiale de cette représentation est alors deO(n + m).

4.1.4 Listes chaînées

Les représentations précédentes sont faciles à mettre en œuvre mais sont mal adap-tées aux transformations élémentaires des graphes comme ajouter ou supprimer dessommets et des arcs. On utilise souvent des listes chaînées de pointeurs associéesà chaque sommet.

Page 25: Theorie Des Graphes - G. Moreau

4.2. PARCOURS DE GRAPHES 25

4.2 Parcours de graphes

La plupart des algortithmes de graphes utilisent des notions deparcoursde graphesc’est-à-dire qu’ils vont effectuer un traitement sur l’ensemble des sommets ou desarcs d’un graphe. Evidemment dans un certain nombre de cas, l’ordre de parcoursdes sommets ou des arcs n’est pas innocent sur le résultat. Les algorithmes deparcours dépendront aussi naturellement de la structure dedonnées adoptée. Dansles paragraphes qui suivent, nous nous intéresserons d’abord au parcours des arbresque nous généraliserons ensuite aux algorithmes de parcours d’abres.

4.2.1 Parcours des arbres

Il existe deux idées principales pour le parcours des sommets d’un arbre : le par-cours en largeur d’abord (breadth-first)et le parcours en profondeur d’abord (depth-first).

Dans le cas du parcours en largeur d’abord, le principe est devisiter les som-mets dans l’ordre de gauche à droite puis de haut en bas comme le montre la fig-ure 4.2 ; les sommets sont visités dans l’ordre suivant : A, B, C, D, E,F, G, H,I.

A

B C D

E F G H I

Figure 4.2: Parcours en largeur d’abord

Inversement, dans le parcours en profondeur d’abord, on visite la racine, puisson premier fils, puis le fils de ce fils etc. La visite est terminée lorsqu’on a visitétous les successeurs d’un sommet. La figure4.3 illustre ce mécanisme.

A

B C D

E F G H I

Figure 4.3: Parcours en largeur d’abord

Page 26: Theorie Des Graphes - G. Moreau

26 CHAPITRE 4. ALGORITHMIQUE DES GRAPHES

4.3 Algorithmes de plus court chemin

Les algorithmes de plus court chemin ont un objectif assez explicite : étant don-née une fonction de coût (une distance pour commencer) associé à chaque arc,déterminer le plus court chemin entre deux sommets. Etant donné un grapheG = (X,U), on associe à chaque arc(x, y) ∈ U une fonction de coûtc(x, y)à valeurs réelles. Le problème de plus court chemin entre deux sommetsa et b deX consiste donc à déterminer le cheminC = (x1, ..., xk) avecx1 = a et xk = bqui minimise la somme desc(xi, xi+1) pour0 ≤ i < k.

Il existe trois algorithmes à vocation assez générale, mêmesi ce domaine faittoujours l’objet de recherches actives dans la communauté informatique. En ef-fet, la complexité des algorithmes les rend peu utilisablessi l’on s’intéresse à descalculs de plus courts chemins prenant en compte l’ensembledes routes françaisespour déterminer le meilleur chemin entre Landivisiau et Aubagne !

4.3.1 Algorithme de Ford-Bellman

L’algorithme, qui calcule l’ensemble des plus courts chemins d’un sommets aureste du graphe, comprend une étape d’initialisation et uneboucle. La premièreétape d’initialisation établit un ensembleS = {s} des sommets déjà traités, unefonction de distanceπ et un ensembleA du meilleur prédécesseur pour venir del’origine.

S = {s}, π(s) = 0, A(s) = ǫTantQue ∃x /∈ S avec Γ−1(x) ⊂ S Faire

π(x) = miny∈Γ−1(x) [π(x) + c(x, y)]

Soit y un sommet tel que π(x) = π(y) + c(y, x)A(x) = y et S = S ∪ {x}

finTantQue

1

2

3

6

5

74

3

2

-2

2

2

-15

3

2

3

4

2

Figure 4.4: Exemple de graphe

Nous allons calculer le plus court chemin entre 1 et 7. Le tableau4.1représenteles différentes itérations de l’algorithme de Ford-Bellman.

Page 27: Theorie Des Graphes - G. Moreau

4.3. ALGORITHMES DE PLUS COURT CHEMIN 27

ǫ 1 2 2 3 2,5 51 2 3 4 5 6 700 30 3 10 3 1 50 3 1 5 30 3 1 5 3 50 3 1 5 3 5 7

Table 4.1: Tableau des itérations de l’algorithme

Une fois l’algorithme arrivé à son terme, on retrouve le chemin optimal dansA en partant de la fin. Le sommet 7 a pour meilleur prédécesseur 5, qui a lui-même comme prédécesseur 3... Le chemin optimal est donc le chemin 1-2-3-5-7de longueur 7.

4.3.2 Algorithme de Moore ou de Dijkstra

L’algorithme suivant dû à Moore (1957), a été redémontré parDijkstra en 1959.Il est basé sur une hypothèse restrictive par rapport à l’algorithme précédent : lafonction de coût est positive.

π(s) = 0, ∀x 6= s, π(s, x) = c(s, x) si l’arc (s, x) existe et +∞ sinonP = {s}, T = X − {s}, A(s) = ǫTantQue T 6= 0 Faire

Soit x0 ∈ T tel que π(x0) = minx∈T π(x)T = T − {x0}P = P ∪ {x0}PourTout x ∈ T Faire

Si π(x) > π(x0) + c(x0, x) Alorsπ(x) = π(x0) + c(x0, x)A(x) = x0

FinSiFinPour

finTantQue

Nous nous intéressons en guise d’exemple au graphe de la figure 4.5 où nouscherchons le chemin de longueur minimale dex1 àx6.

Le tableau4.2représente l’étape d’initialisation de l’algorithme.A la première itération, on sélectionne la valeur la moins élevée (le 3 associé

à x2 ici) et on exécute le contenu de l’algorithme. Cela nous mèneau second

Page 28: Theorie Des Graphes - G. Moreau

28 CHAPITRE 4. ALGORITHMIQUE DES GRAPHES

1

2

3

5

6

43

6

3

2

5

11

6

6

3

Figure 4.5: Exemple de graphe

A ǫ x1 x1 x1

x1 x2 x3 x4 x5 x6

init. 0 3 6 +∞ 3 +∞

Table 4.2: Initialisation de l’algorithme de Dijkstra

tableau4.3 où seule la valeur temporaire du plus court de chemin menant àx4 aété modifiée : en passant parx2, on peut rejoindrex4 avec un coût de 9.

A ǫ x1 x1 x2 x1

x1 x2 x3 x4 x5 x6

init. 0 3 6 +∞ 3 +∞

0 3 6 9 3 +∞

Table 4.3: Première itération de l’algorithme de Disjkstra

Le tableau4.4présente les autres itérations de l’algorithme.

4.3.3 Algorithmes de Bellmann

On s’intéresse maintenant à des algorithmes un petit peu moins restrictifs : plutôtde considérer des graphes à fonction de coût positives, on considère des graphessans circuits absorbants. Un circuit absorbant est un circuit dont le coût total estnégatif. Dès lors, n’importe quel chemin empruntant ce circuit une infinité de foisaura un coût infiniment petit.

On présente tout d’abord la version standard de l’algorithme de Bellman.

π1(s) = 0

Page 29: Theorie Des Graphes - G. Moreau

4.3. ALGORITHMES DE PLUS COURT CHEMIN 29

A ǫ x1 x5 x3 x1 x5,x4

x1 x2 x3 x4 x5 x6

init. 0 3 6 +∞ 3 +∞

0 3 6 9 3 +∞

0 3 5 9 3 80 3 5 6 3 80 3 5 6 3 7

Table 4.4: Autres étapes de l’algorithme de Disjkstra

π1(x) = c(s, x),∀x 6= sPour m = 1 à n − 2 Faire

πm+1(x) = minx 6=s [πm(x),miny 6=x [πm(y) + c(y, x)]]FinPour

A la fin de l’algorithme,πm−1(x) contient la valeur du chemin optimal des àx.

1

2

3

5

6

43

6

3

-2

5

1

1

6

6

-3

Figure 4.6: Exemple de graphe

L’application de l’algorithme sur le graphe de la figure4.6 se traduit dans letableau4.5.

La validité de l’algorithme se montre de la façon suivante : on veut montrer queπm(x) est la valeur du chemin optimal des àx comportant au plusm arcs. On vachercher à montrer (récurrence) que cette propriété reste vraie pourπm+1(x). Onconsidère donc un chemin de valeur minimale des àx comportant au plusm + 1arcs :

• s’il ne contient pas plus dem arcs, sa valeur est bienπm(x) ;

Page 30: Theorie Des Graphes - G. Moreau

30 CHAPITRE 4. ALGORITHMIQUE DES GRAPHES

x1 x2 x3 x4 x5 x6

π1 0 3 6 +∞ 3 +∞

π2 0 3 0 7 3 8π3 0 3 0 1 3 8π4 0 3 0 1 3 2π5 0 3 0 1 3 2

Table 4.5: Fonctionnement de l’algorithme de Bellman

• s’il en contientm + 1, sa valeur estπm(xk) + c(xk, x) qui est bien égale àminy 6=x [πm(y) + c(y, x)].

Donc on a bien

πm+1(x) = min

[

πm(x),miny 6=x

[πm(y) + c(y, x)]

]

(4.6)

qui est la valeur du chemin optimal des àx comportant au plusm + 1 arcs.Si l’on cherche tous les plus courts chemins entre deux quelconques des som-

mets du graphe, on aboutit à des algorithmes enO(n4). L’algorithme matricieldéveloppé dans ce paragraphe est une reprise de l’algorithme de Roy-Warshalldéveloppé pour la détermination de la fermeture transitive. Il s’initialise ainsi :

Π(0)ij =

valeur de l’arc s’il existe0 si i = j+∞ sinon

(4.7)

L’algorithme est alors le suivant :

Pour m de 1 à n FairePour i de 1 à n Faire

Pour j de 1 à n Faire

Π(m)ij = min{Π

(m−1)ij ,Π

(m−1)im + Π

(m−1)mj }

FinPourFinPour

FinPour

Π(m)ij représente la longueur du chemin optimal dei à j dont les sommets

intermédiaires appartiennent à{1, ...,m}.Nous disposons ainsi d’un algorithme enO(n3) qui donne la longueur des

chemins optimaux entre deux sommets quelconques du graphe.L’application de l’algorithme sur le graphe de la figure4.6 se traduit dans les

matrices suivantes.

Page 31: Theorie Des Graphes - G. Moreau

4.4. PROBLÈME DU FLOT MAXIMAL 31

1

2

3

4

5

1

1

2

4

1

3

1

Figure 4.7: Exemple de graphe

A =

0 1 2 +∞ +∞+∞ 0 1 4 +∞+∞ +∞ 0 1 3+∞ +∞ +∞ 0 1+∞ +∞ +∞ +∞ 0

(4.8)

A2 =

0 1 2 3 5+∞ 0 1 2 4+∞ +∞ 0 1 2+∞ +∞ +∞ 0 1+∞ +∞ +∞ +∞ 0

(4.9)

A3 =

0 1 2 3 5+∞ 0 1 2 3+∞ +∞ 0 1 2+∞ +∞ +∞ 0 1+∞ +∞ +∞ +∞ 0

(4.10)

4.4 Problème du flot maximal

4.4.1 Définitions

On s’intéresse maintenant à faire circuler des quantités dans un graphe et à max-imiser la quantité circulant entre 2 ou plusieurs arcs de ce graphe. Les applicationssont immédiates : il peut s’agir de transporter le maximum demonde entre deuxpoints de l’espace en utilisant plusieurs routes mais aussid’acheminer des fluidesvia des canalisations1 ou des informations dans un réseau. Le paragraphe suivants’intéressera au même problème mais en visant à minimiser lecoût de ce transport.

1La cas des canalisations est particulier puisqu’en plus d’avoir une capacité maximale, les canal-isations peuvent nécessiter une capacité minimale, par exemple une pression de gaz minimale.

Page 32: Theorie Des Graphes - G. Moreau

32 CHAPITRE 4. ALGORITHMIQUE DES GRAPHES

Définition 4.4.1 Soit un grapheG = (X,U). On appelle capacitécij associée àl’arc (i, j) un réel positif ou nul représentant la quantité maximale pouvant circulersur un arc. On appelle flotxij sur l’arc (i, j) le réel représentant la quantitécirculant réellement sur l’arc, en vérifiant la contrainte0 ≤ xij ≤ cij . On appelleflot surG l’ensemble des flots associés à chaque arc du grapheG.

Pour être valide (on dira admissible), le flot dans un graphe doit vérifier une loide conservation simple définie par analogie avec la loi de Kirchhoff en électricité: tout flot entrant dans un nœud doit en ressortir. Elle est valable en tout nœudd’un graphe sauf dans deux nœuds particulierss et t qu’on appellera respective-ment source et puits du graphe. Au niveau de la source, il y acréation de flot,tandis qu’au niveau du puits il y aabsorption. Sur les autres nœudsi, la loi deconservation s’écrit ainsi :

j∈Γ−(i)

xij =∑

k∈Γ+(i)

xik (4.11)

On représente un graphe avec le flot et la capacité associés comme sur la fig-ure4.8.

s

1

2

3

4

t

1 [3]

2 [2]

1 [2]0 [1]

0 [1

]

1 [1

]

2 [2]

1 [2]

2 [3]

Figure 4.8: Représentation d’un flot dans un graphe

Pour vérifier la loi de conservation de façon générale, on va ajouter un arc deretour fictif entret et s et on appellera valeur du flot la quantité circulant sur l’arc(t, s), comme le montre la figure4.9.

Dès lors, on peut définir le problème de flot maximal comme étant la maximisa-tion dexts sous les contraintes de respect des capacités et de la loi de conservation.On remarquera qu’il s’agit d’une forme particulière de programme linéaire.

4.4.2 Résolution du problème de flot maximal

Définition 4.4.2 On définit une chaîne augmentanteu des à t pour un flot admis-sible donné comme une chaîne des à t respectant les contraintes suivantes :

• xij < cij pour tout arc dirigé des verst

Page 33: Theorie Des Graphes - G. Moreau

4.4. PROBLÈME DU FLOT MAXIMAL 33

s

1

2

3

4

t

1 [3]

2 [2]

1 [2]

0 [1]

0 [1

]

1 [1

]

2 [2]

1 [2]

2 [3]

3

Figure 4.9: Représentation d’un flot dans un graphe avec un arc de retour fictif

• xij > 0 pour tout arc dirigé det verss

La chaîneµ définie sur la figure4.10est une chaîne augmentante de l’exemplede graphe précédent. On appelleµ+ l’ensemble des arcs deµ dans le sens desverst, µ− ceux qui sont dans l’autre sens.

s

1 3

4

t

1 [3]

1 [2]

1 [1

]

1 [2]

Figure 4.10: Exemple de chaîne augmentante

Le flot peut alors être augmenté du flot circulant sur la chaîneaugmentante ;on notera qu’en tenant compte du sens des arcs, la loi de conversation se vérifie surl’ensemble des arcs de la chaîne. L’augmentationα du flot correspondante est alorsdu minimum des capacités résiduelles (la capacité de l’arc moins le flot circulantdéjà) pour les arcs des verst et le minimum des flots circulant effectivement pourles arcs det verss.

α = min

[

min(i,j)∈µ+

(cij − xij), min(i,j)∈µ−

xij

]

(4.12)

Pour augmenter le flot, on ajouteα au flux des arcs deµ+ et on retrancheα auflux des arcs deµ−.

Page 34: Theorie Des Graphes - G. Moreau

34 CHAPITRE 4. ALGORITHMIQUE DES GRAPHES

Définition 4.4.3 On dit que le flot est complet lorsque tout chemin des à t com-porte au moins un arc saturé ((i, j) est saturé lorsquexij = cij).

Définition 4.4.4 Une coupe associée à un grapheG = (X,U) est une partitiondeX en deux ensemblesS et T telle ques ∈ S et t ∈ T . On appelle capacité dela coupec(S, T ) =

i∈S,j∈T cij .

Théorème 4.4.1Un flotx des à t est maximal s’il n’existe pas de chaîne augmen-tante des à t.

On en déduit en corollaire :

Propriété 4.4.2.1 Soit un grapheG = (X,u). Quelle que soit la coupe(S, T ),quel que soit le flot admissiblex, alors la valeur du flotx est inférieure ou égale àla capacité de la coupe(S, T ).

Théorème 4.4.2(Ford-Fulkerson) La valeur du flot maximal est égal à la capacitéde la coupe de capacité minimale.

On en déduit l’algorithme de recherche du flot maximal : il consiste à exhiberune chaîne augmentante et à augmenter le flot de la valeur de lachaîne augmentantetant qu’il existe des chaînes augmentantes.

4.4.3 Algorithme de Ford-Fulkerson et exemple

Soit x un flot admissible, marquer + le sommet sRépéter

Si i est marqué et j non marqué AlorsSi (i, j) est un arc non saturé Alors

marquer j avec +FinSiSi (j, i) est un arc tel que xij > 0 Alors

marquer j avec -FinSi

FinSiJusqu’à ce qu’on ne puisse plus marquer de sommetsSi t est marqué Alors

il existe une chaîne augmentante de s à taugmenter le flot et recommencer

Sinonle flot est maximal

FinSi

Page 35: Theorie Des Graphes - G. Moreau

4.4. PROBLÈME DU FLOT MAXIMAL 35

s

A

B

C

D

E

F

t

15 [35]

35 [35]

30 [40]

5 [20]

20 [25]

20 [20]

20 [20]

30 [30]

30 [60]

15 [15]

10 [20]

0 [5]

10 [10]80

Figure 4.11: Flot initial pour l’algorithme de Ford-Fulkerson

s

A

B

C

D

E

F

t

15 [35]

35 [35]

30 [40]

5 [20]

20 [25]

20 [20]

20 [20]

30 [30]

30 [60]

15 [15]

10 [20]

0 [5]

10 [10]

+

+s +A

+B

+C-D

+s

Figure 4.12: Marquage pour l’algorithme de Ford-Fulkerson

Page 36: Theorie Des Graphes - G. Moreau

36 CHAPITRE 4. ALGORITHMIQUE DES GRAPHES

Faisons maintenant fonctionner l’algorithme sur un exemple, celui du graphede la figure4.11. On notera que ce graphe comporte un flot initial non nul afin deréduire le nombre d’itérations de l’algorithme.

Après marquage, le graphe devient celui de la figure4.12.A partir des marquages, on retrouve la chaîne augmentante dela figure4.13.

Elle nous permet d’augmenter le flot de 5, ce qui donne le nouveau flot représentéfigure4.14.

s

A

B

D

F

t

15 [35]

5 [20]

30 [60]

15 [15]

0 [5]

Figure 4.13: Chaîne augmentante

s

A

B

C

D

E

F

t

20 [35]

35 [35]

30 [40]

10 [20]

20 [25]

20 [20]

20 [20]

30 [30]

35 [60]

10 [15]

10 [20]

5 [5]

10 [10]

85

Figure 4.14: Nouveau flot après augmentation de 5

Une nouvelle procédure de marquage aboutit au graphe de la figure 4.15. Lesommett n’est pas marqué, donc l’algorithme est terminé et le flot estmaximal.

Page 37: Theorie Des Graphes - G. Moreau

4.4. PROBLÈME DU FLOT MAXIMAL 37

La ligne verte sépare les deux ensembles de la coupe de capacité minimale.

s

A

B

C

D

E

F

t

20 [35]

35 [35]

30 [40]

10 [20]

20 [25]

20 [20]

20 [20]

30 [30]

35 [60]

10 [15]

10 [20]

5 [5]

10 [10]

85

+

+s +A

-D

+s

+B

Figure 4.15: Fin de l’algorithme

La complexité de l’algorithme se détermine difficilement : la procédure demarquage nécessite deux examens et est donc enO(m). Le nombre d’itérationsdépend quand à lui largement de la valeur du flot et de la chaîneaugmentantechoisie, d’où l’intérêt de ne pas prendre un flot nul au départ. Si on considèrel’exemple de la figure4.16 qu’on augmente systématiquement en passant par labranche centrale (dans le bon sens pour les itérations impaires et dans l’autre senspour les itérations paires), le nombre d’itérations est alors de 100000 alors qu’endeux itérations mieux choisies, le flot aurait été maximal.

s

1

t

2

0 [1

0000

0]

0 [100000] 0 [1

0000

0]

0 [100000]

0 [100000]

s

1

t

2

1 [1

0000

0]

0 [100000] 1 [1

0000

0]

0 [100000]

1 [100000]

s

1

t

2

1 [1

0000

0]

1 [100000] 1 [1

0000

0]

1 [100000]

0 [100000]

Figure 4.16: Mauvais choix des chaînes augmentantes

Théorème 4.4.3Si chaque augmentation de flot est faite suivant une chaîne aug-mentante de longueur minimale, alors le flot maximal est obtenu après moins de

Page 38: Theorie Des Graphes - G. Moreau

38 CHAPITRE 4. ALGORITHMIQUE DES GRAPHES

mn2 itérations, soit une complexité totale enO(m2n).

4.5 Flot maximal à coût minimal

4.5.1 Définitions

Nous nous intéressons maintenant au même problème de détermination d’un flotmaximal sauf que nous allons ajouter pour être plus réalistes un coût unitaire surchacun des arcs. Il s’agira donc de déterminer le flot maximalà coût minimal. Onconsidère toujours un grapheG = (X,U) comportant une sources et un puitspassociant à chaque arc(i, j) ∈ U une capacitécij et un flot0 ≤ xij ≤ cij vérifianten outre les contraintes de la loi de conservation. On ajoutealors à chaque arc(i, j) ∈ U un coût unitairedij .

Le problème du flot maximal à coût minimal consiste donc à parcourir tous lesflots maximaux et à trouver celui qui minimise

(i,j)∈U xijdij .

Définition 4.5.1 On définit le graphe d’écartG = (X,U e) associé àG = (X,U)vérifiant(i, j) ∈ U e si et seulement si :

• (i, j) ∈ U etxij < cij (1)

• (j, i) ∈ U etxij > 0 (2)

Alors la capacité et le coût de(i, j) ∈ U e seront respectivement de

• cij − xij et+dij dans le cas (1)

• xij et−dij dans le cas (2)

4.5.2 Algorithme de Roy

L’algorithme que nous allons décrire est dû à Roy, il consiste à partir d’un flotnul (donc de coût minimal) à augmenter le flot progressivement en conservant lapropriété de coût minimal. D’autres algorithmes (Bennington par exemple) partentd’un flot maximal dont ils vont chercher à minimiser le coût.

x0 = (0, ..., 0), k = 0Construire le graphe d’écart Ge

k

Tantque il existe un chemin de s à t dans Gek

k = k+1Soit µk le plus court chemin de s à tSoit c la plus petite capacité des arcs de µk

Calculer un nouveau flot xk+1

xk+1(i, j) = xk(i, j) + c si (i, j) ∈ µk

xk+1(i, j) = xk(i, j) − c si (j, i) ∈ µk

xk+1(i, j) = xk(i, j) sinon

Page 39: Theorie Des Graphes - G. Moreau

4.5. FLOT MAXIMAL À COÛT MINIMAL 39

on obtient un nouveau flot augmenté de cFinTantQue

Propriété 4.5.2.1 A chaque étapek de l’algorithme, le flotxk est de coût minimal.

4.5.3 Exemple

On considère le graphe de la figure4.17.

s

a

b

c

d

e

f

t[4] (3)

[3] (2) [4] (1)

[3] (2)

[5] (2)

[5] (2)

[3] (1)

[3] (4)

[4] (3)[2] (3)

[1](5)

Figure 4.17: Exemple et premier graphe d’écart

Compte tenu de la définition vue plus haut, le premier graphe d’écart (construità flot nul) est le graphe lui-même. On commence donc par cherche le plus courtchemin entres et t. On considère donc le chemin(s, b, e, t) dont la capacité mini-male est 3. On augmente alors le flot de 3 et on construit le second graphe d’écartde la figure4.18où les nouveaux arcs et les modifications sont portées en rouge.

s

a

b

c

d

e

f

t[1] (3)

[3] (-2)

[1] (1)

[3] (2)

[5] (2)

[5] (2)

[3] (1)

[3] (4)

[4] (3)[2] (3)

[1](5)

[3] (-3) [3] (-1)

Figure 4.18: Second graphe d’écart

Page 40: Theorie Des Graphes - G. Moreau

40 CHAPITRE 4. ALGORITHMIQUE DES GRAPHES

Le plus court chemin dans ce second graphe d’écart est le chemin (s, c, f, t), sacapacité minimale est de 3. On peut augmenter le flot de 3 et construire le troisièmegraphe d’écart de la figure4.19où les nouvelles modifications sont portées en bleu.Le plus court chemin est cette fois le chemin(s, a, d, t) et on peut encore augmenterle flot de 3, ce qui nous mène au quatrième graphe d’écart où lesmodifications sontportées en vert. Le plus court chemin est alors(s, b, f, t), on peut augmenter le flotde 1, ce qui donne le cinquième graphe d’écart de la figure4.21où les modificationssont portées en mauve.

s

a

b

c

d

e

f

t[1] (3)

[3] (-2)

[1] (1)

[3] (2)

[2] (2)

[5] (2)

[3] (-1)

[3] (4)

[1] (3)[2] (3)

[1](5)

[3] (-3) [3] (-1)

[3] (-2)

[3] (-3)

Figure 4.19: Troisième graphe d’écart

s

a

b

c

d

e

f

t[1] (3)

[3] (-2)

[1] (1)

[3] (-2)

[2] (2)

[2] (2)

[3] (-1)

[3] (-4)

[1] (3)[2] (3)

[1](5)

[3] (-3) [3] (-1)

[3] (-2)

[3] (-3)

[3] (-2)

Figure 4.20: Quatrième graphe d’écart

Page 41: Theorie Des Graphes - G. Moreau

4.5. FLOT MAXIMAL À COÛT MINIMAL 41

s

a

b

c

d

e

f

t[4] (-3)

[3] (-2)

[1] (1)

[3] (-2)

[2] (2)

[2] (2)

[3] (-1)

[3] (-4)

[4] (-3)[1] (3)

[1](5)

[3] (-1)

[3] (-2)

[3] (-2)

[1] (-3)

Figure 4.21: Cinquième graphe d’écart

Page 42: Theorie Des Graphes - G. Moreau

42 CHAPITRE 4. ALGORITHMIQUE DES GRAPHES

Page 43: Theorie Des Graphes - G. Moreau

Chapitre 5

Démonstrations

Démonstration du théorème1.2.1Soit a ∈ U une arête deG. Alors, oua est une boucle autour d’un sommetx

deG et intervient pour 2 dans le degré dex, oua = (x, y) intervient pour 1 dansle degré dex et pour 1 dans le degré dey. On a donc

x∈X

d(x) = 2|U | (5.1)

x∈X d(x) est donc un nombre pair. Si on appelleX le sous-ensemble deXtel que lesx ∈ X ont un degré impair, alors

x∈X

d(x) = 2|X| =∑

x∈X

d(x) +∑

x∈X−X

d(x) (5.2)

Le membre de gauche de l’équation est pair, le second terme dunombre dedroite est pair aussi, donc le nombre

x∈X d(x) est pair, ce qui est alors néces-sairement le cas de|X|.

Démonstration de la propriété1.3.0.1R est évidemment réflexive. Soit(ui)1≤i≤n une chaine deU reliant x à y.

Alors la suite des(u′i) définie paru′

i = un−i est aussi une chaine deU et constituebien une chaine dey àx. R est donc bien symétrique. Enfin, sixRy et yRz, c’estbien qu’il existe deux suites deU menant respectivement dex à y et dey à z. Laconcaténation de ces deux suites fournit une chaine évidente entrex et z, d’où latransitivité deR. R est donc bien une relation d’équivalence.

Démonstration de la propriété1.3.0.2R′ est évidemment réflexive et symétrique. Enfin, sixR′y et yR′z, c’est bien

qu’il existe deux suites deU menant respectivement dex ày et dey àz (ainsi quedey àx et dez ày). La concaténation de ces deux suites fournit un chemin évidententrex et z (resp. entrez et x), d’où la transitivité deR′. R′ est donc bien unerelation d’équivalence.

43

Page 44: Theorie Des Graphes - G. Moreau

44 CHAPITRE 5. DÉMONSTRATIONS

Démonstration du théorème1.4.2=⇒ S’il existeA 6= 0 et A 6= X tel queΓ+(A) = A et uny 6 ∈A, alors il n’y

aura pas de chemin jusqu’ày.⇐= Soientx et y donnés, on construitA0 = {x} et la suite desAi par la

relation de récurrence suivante :Ai = Ai−1 ∪ Γ+(Ai−1). X étant fini, il existe uni tel quey ∈ Ai, ce qui implique qu’il existe un chemin entrex ety.