Graphes et algorithmes

Sommaire et contenu du livre "Graphes et algorithmes"

Chapitre 1

Généralités sur les graphes 1

1.
Définitions et concepts de base 2

1.1.
Graphes : concepts orientés 2

1.2.Graphes
et applications multivoques 2

1.3.
Graphes : concepts non orientés 3

lA.
Principales définitions 4

2.
Matrices associées à un graphe 6

2.1.
Matrice d'incidence sommets-arcs 6

2.2.Matrice
d'incidence sommets-arêtes 7

2.3.
Matrice d'adjacence ou : matrice d'incidence sommets-sommets 8

204 . Les différentes représentations d'un graphe 9

204.1.
À partir de la matrice d'adjacence 9

204.2.
À partir de la matrice d'incidence sommets-arcs ou sommets-arêtes II

204 .3. Passages entre les différentes représentations 13

3.
Connexité 14

3.1.Chaîne.
Chaîneélémentaire.Cycle.Cycleélémentaire 14

3.2.Chemin.Cheminélémentaire.
Circuit.Circuitélémentaire 14

3.3.Connexité.Nombredeconnexité
15

~ 304. Point d'articulation, k-connexité, k-arête-connexité 19

~ 3.5. Graphe fortement connexe. Composantes fortement connexes 22

~ 4. Cycles et cocycles. Nombre cyclomatique 27

~B 4.1. Définition 27

~ 4.2.Vecteur associé à un cycle. Somme de deux cycles 27

~ 4.3. Cycles indépendants. Base de cycles 27

.
~ 4.4. Cocycles. Vecteur associé à un cocycle 28

oî 5. Quelques graphes particuliers 29

.
5 5.]. Les graphes sans circuits 29

1

5.2.Les
graphes planaires 30

5.3.Lesgraphesauxarêtesetlesgraphesauxarcs
32

504 . Les graphes parfaits 34

6.
Les hypergraphes 36

7.
Graphes aléatoires et connexité 41

Exercices 43

Références bibliographiques 47

Chapitre 2

Le problème du plus court chemin 49

1.
Définitions et exemples 50

Conditions d'existence 51

2.
Les algorithmes 51

2.1.
Algorithme de Moore-Dijkstra (/(u) ~ 0) 52

Queues de priorité 56

2.2.Cas
où !(lI) = l, Vu E U. 57

2.3.
Graphe G et longueurs !(u) quelconques 58

2.4.
Cas des graphes sans circuit 65

2.5.Algorithmes
matriciels 69

2.6.
Problèmes voisins 74

2.6.1.
Recherche d'un circuit de longueur moyenne minimum 74

2.6.2.
Recherche d'un circuit de longueur moyenne pondérée minimum 75

2.6.3.
Recherche du k-ième plus court chemin d'un sommet 1

à tous les autres 76

2.6.4.
Plus court chemin avec longueur des arcs dépendant du temps 77

2.6.5.
Plus court et plus long chemins élémentaires 77

2.6.6.
Recherche de circuit de longueur négative 81

3.
Le problème central de l'ordonnancement 81

3.1.
Le graphe potentiels-tâches 82

3.2.
Le graphe potentiels-étapes 85

3.3.Quelques
compléments pratiques 86

Exercices 89

Références bibliographiques lOI

Chapitre 3

Algèbres de chemins et dioïdes 105

1.
L'algèbre du plus court chemin 105 ~
2.
Définitions et propriétés 107 §
2.1.
Une classe d'algèbres de chemins: les dioïdes 107 :
2.2.Matrice
d'incidence généralisée d'un graphe 109 1llB
2.3.
Quelques théorèmes de convergence . . . . . . . . ........................... III ~

3.
Quelques exemples " 116 ~
3.1.Problèmesd'existenceetdeconnexité
" 116 'gg.
3.2.Problèmesd'énumération
117 ~
a.
3.3.Chemin
de capacité maximum " 11 9 j
1

o' •••••••••••••3.4. Chemin de nombre d'arcs minimum ]] 9 ID "in
3.5.
Plus court chemin . . .. . . . . . . . . . . .. . . . . . . . .. . . . . .. . . . . . . . . .. . . . .. . . .. 1]9 .~
3.6.
Plus long chemin 120 @
3.7.
Chemin de fiabilité maximum 120

3.8.
Les problèmes multicritères 120

3.9.
Problèmes de dénombrement. 122

3.10.
Chaînes de Markov 122

3.11.Fiabilité
d'un réseau 123

3.12.
Les problèmes de k-ième chemin 123

3.13.
Les chemins Tl-optimaux 125

4.
Algorithmes généraux 126

4.1.
Algorithme de Jacobi 128

4.2.
Algorithme de Gauss-Seidel 130

4.3.
Algorithme de Jordan pour la quas i-inversion d'une matrice 133

5.
Algèbres de chemins dans un graphe sans circuit 137

6.
Un dioïde parti culier. 139

7.
Les dioïdes à gauche et à droite 141

8.
Généralisation des algèbres de chemins 144

8.1.L'algèbre
des endomorphismes 144

8.2.Quelques
exemples 146

8.3.Quelques
algorithmes 148

9.
Théorie des dioïdes et applications 152

9.1.
Solution d'équations non linéaires dans un dioïde 152

9.2.Dépendancelinéaireetindépendancedanslesdioïdes.Bidéterminants
153

9.3.
Valeurs propres et vecteurs propres 156

Exercices 158

Références bibliographiques 162

Chapitre 4

Arbres et arborescences ___ 165

1.
Arbres. Définitions et propriétés _ 165

1.1.Définitions
165

1.2.Propriété
1 168

1.3.Algorithme
de construction d'une forêt maximale d'un graphe 168

1.4.
Théorème 1 170

1.5.
Coarbre. Définition 171

2.
Le problème de l'arbre de poids minimum 172

'
"c:
~
2.2.
Théorème 4 173

"2.3.Algorithme
primai de Kruskal 174e
s ~
2.4.Algorithme primai avec arcs dans ledésordre 175 :; c: 2.5. Algorithme dual de Kruskal 175
e
ac: 2.6. Algorithme dual avec arcs dans le désordre , 176
,5,"
a 2.7. Algorithmes pour G connexe 176
s
s: êi 2.8.Arbre de poids maximum 178
0.
j 2.9. Recherche des chaînes de section maximale (ou minimale) 178

1

Qi2.10.
Arbre de poids minimum et classification hiérarchique sous dominante , 179 -;;;
-~
2.11.
Arbre de condensation et arbre de classification 182

---'
@ 2.12. Structure algébrique des classifications hiérarchiques 185

3.
Arborescences......................................................... 187

3.1.
Définition 187

3.2.Théorème
7 190

3.3.
Le problème de l'arborescence de poids minimum 192

3.4.
Algorithme de recherche d'une arborescence de po ids minimum 194

3.5.
Exemple 195

Exercices 198

Références bibliographiques 206

Chapitre 5

Flots et réseaux de transport 209

1.
Définitions et propriétés 210

1.1.
Définition 210

1.2.
Définition algébrique des flots 211

1.3.
Cycles élémentaires et flots élémentaires 211

1.4.
Décomposition d'un flot en somme de cycles élémentaires " . " 212

1.5.
Le lemme des arcs colorés 213

1.6.
Décomposition en circuits d'un flot positifou nul. 214

2.
Le problème du flot maximum dans un réseau de transport 215

2.1.
Définition. Position du problème 215

2.2.
Exemple: affectation de p tâches à q machines 216

2.3.
Définition des coupes. Capacité d'une coupe 216

2.4.
Le théorème du flot maximum et de la coupe minimale 217

2.5. Graphe
d'écart. Définition 218

2.6.
Algorithme de recherche d'un flot maximum 219

2.7.
Extensions diverses 222

2.8.Algorithme
de Ford et Fulkerson avec bornes inférieures de capacité 226

3.
Le problème du flot compatible. Théorème de compatibilité 227

3.1.
Une condition nécessaire d'existence 227

3.2.Algorithme
2 : recherche d'un flot compatible 227

4.
Flots et connexité 230

4.1.
La k-arête connexité 230

4.2.La
k-arc-connexité 233

4.3.
La k-connexité " 234

4.4.
La k-forte connexité 235 ~
"
5.
Flots à coût minimum 236 ~
oe 5.1. Le problème général du flot à coût minimum. "*
'5
Méthode des arcs non conformes (algorithme primai-dual) 236 '§
5.2. Graphes
sans borne de capacité : problème de transbordement, transport ~

et dérivés. Algorithme prirnal-dual 244 ;
5.3. Flots à coût minimum avec bornes inférieures et bornes supérieures i
de capacité (algorithme primai) 250
0­
5.4.
Flots à coût minimum avec bornes inférieures nulles (algorithme dual) 253 .5

5.5.Spécialisationsdela méthodedusimplexeaux problèmesdeflots
255 "*1
Exercices 255 ~
Références bibliographiques 280 @

Chapitre 6

Flots avec multiplicateurs. Multiflots 285

1.
Flots avec multiplicateurs 285

1.1.
Définitions 285

1.2.
Le problème du flot à perte minimale 286

1.3.
Le problème du flot avec multiplicateurs et de coût minimum 288

lA.Chaînes
augmentantes, chaînes génératrices et chaînes absorbantes 289

1.5.
Caractérisation des flots avec multiplicateurs à composantes positives.
Théorème de décomposition 294

1.6. Graphed'écartassociéàun
flot
1.7.
Algorithmes pour les problèmes de flots à perte minimale 301

1.8.
Algorithmes pour les problèmes de flots avec multiplicateurs
de coût minimum 304

2.
Problèmes de multiflots 312

2.1.
Définitions et exemples 312

2.2.Formulation
sommets-arcs des problèmes de multiflots 315

2.3. Formulationarcs-cheminsdes problèmesde multiflots
317

2.4.
Étude du problème du multiflot compatible 321

Définition 323

2.5. Multiflotscompatiblesetde
coûtminimum:une méthodede décomposition
par affectation de capacités 327

Exercices 335

Références bibliographiques 349

Chapitre 7

Couplages et b-couplages 353

1.
Le problème du couplage maximum 353

1.1.
Définition et exemples 353

1.2.
Définitions 355

1.3.Chaînes
alternées 356

lA.
Théorème 1 357

2.
Algorithme de recherche d'un couplage maximum 358

2.1.
Lemme 2 358

2.2
.Lemme 3 360

2.3. Recherchedeschaînesalternéesd'originefixée: arbresalternés 360

~ 2.4 . Algorithme 1 : Construction d'un arbre alterné 362
c
~ 2.5 . Algorithme 2 : recherche d'un couplage maximum 366

'"
.
$ 2.6. Exemple 367

~ Éclatement d'une orbite 369

~
g 2.7. Description du graphe G'
: sommets et pseudo-sommets 370

~ 2.8.Tableaudescriptif du couplage K 373
'ë.
§ 2.9. Examen des arêtes à l'étape courante de l'algorithme 1 374
l 2.10. Complexité de l'algorithme de couplage maximum 375

~ 3. Couplage de poids maximum 376

3.1.
Définitions 376

3.2.Théorème
3 377

3.3.
Théorème 4 ""'7 0
4.
Un algorithme pour le problème du couplage de poids maximum 379

4.1.
Lemme 4 379

4.2.
Lemme 5 379

4.3.Corollaire
3 380

4.4.
Algorithme 3 : Couplage de poids maximum 382

4.5.
Complexité de l'algorithme 3 387

5.
b-Couplages. b-Couplage maximum et b-couplage de poids maximum 388

5.1.
Définitions 388

5.2.
Graphe d'écart. 389

5.3.
Chaînes alternées 390

Exercices 391

Références bibliographiques 404

Chap itre 8

Parcours eulériens et hamiltoniens 407

1.
Cycles et chaînes eulériens 408

1.1.
Définitions 408

1.2.Théorème
1 408

1.2.Algorithme
de recherche d'une chaîne eulérienne 409

2.
Le problème du « Postier chinois » (non orienté) 411

2.1.
Lemme 1 412

2.2.
Lemme 2 412

2.3.
Lemme 3 413

2.4.Théorème
2 413

2.5.
Exemple 414

3.
Circuits et cycles hamiltoniens 416

3.1.
Défin itions 416

3.2.Conditions
nécessaires d'existence de cycles hamiltoniens 418

3.3.
Conditions suffisantes d'existence d'un cycle hamiltonien 419

3.4.
Conditions suffisantes d'existence d'un circuit hamiltonien 426

Exercices 431

Références bibliograhiques 447

Chapitre 9

Matroïdes 451 :0;
"C
:> ûj
1. Définitions et résultats fondamentaux 451 C
1.1.
Introduction 451 Q) Q)
1.2.
Définitions et exemples 452 ~ 'B
lU
1.3. Rang 453 :>
11
1.4.Clôture 454
.
~
1.5.Stigmes
455 Co ~
1.6.
Autres exemples de matroïdes 456 o J:: Co
1.7.
Axiomatiques des matroïdes 457 j
1

1.8.
Matroïdes orientés 459 li):§
2.
Dualité 460 ~
2.1.Théorème
3 460 ~
2.2.Propriété
1 462

2.3.
Opérations de réduction et de contraction 462

2.4.
Dualité pour les matroïdes orientés 463

3.
Le problème du sous-ensemble indépendant de poids maximum:
l'algor ithme glouton 465

3.1.
Définition d'un ordre lexicographique 466

3.2.Théorème
5 466

3.3.
L'algorithme glouton « primai» 467

3.4.
Exemple des matroïdes graphiques : le problème de l'arbre
de poids maximum 468

3.5.
Exemple des matroïdes matriciels : le problème de la base
de poids maximum 468

3.6.
L'algorithme glouton dual : algorithme 2 469

3.7.
Polyèdres matroïdaux 470

4.
Intersection de matroïdes 473

4.1.
Couplage dans un graphe biparti 473

4.2.
Arborescences de poids maximum 474

4.3.
Intersection de deux matroïdes matriciels 474

4.4.Un
problème de coloration des arêtes d'un graphe 474

4.5.Séquences
alternées et graphe d'alternance 475

4.6.
Un algorithme pour le problème de l'intersection de cardinalité maximale 480

4.7.
Intersections maximales et couvertures de rang minimal 482

4.8.
Le problème de l'intersection de poids maximum. Algorithme 4 482

4.9.Intersectiondedeuxpolyèdresmatroïdaux.Algorithme5(primaidual)
484

4.10.
Intersections de k matroïdes (k > 3) 487

5.
Matroïdes avec conditions de parité et généralisations 489

5.1.
Le problème du couplage dans un graphe quelconque 489

5.2.
Formulation en termes de matroïdes avec conditions de par ité 489

5.3.Généralisation
aux matroïdes quelconques. Lien avec les problèmes
d'intersection de deux matroïdes 490

5.4.
Problèmes de matroïdes avec conditions de k-parit é 491

6.
Polymatroïdes 493

6.1.
Définitions et exemples 493

6.2.Polyèdres
polymatroïdaux 496

Propriété 2 496

6.3.
Problèmes de couplages dan s les polymatroïdes 500

6.3.1.
Recherche d'un sous-ensemble indépendant de poids maximum
dans un matroïde 500

6.3.2.
Intersections de matroïdes 500

6.3.3.
Couplages dans les graphes 501

6.3.4.
Matroïdes avec conditions de k-parit é 501

6.3.5.
Recherche d'une forêt maximale d'un hypergraphe 3-uniforme 501

6.3.6.
Ensemble stable d'un graphe 502

6.4.Minimisation
exacte, en temps polynomial, d'une fonction
sous-modulaire générale 503

Exercices 508

Références bibliographiques 514

Chapitre 10

Les problèmes difficiles de la classe NP 519

1.RéductionsctRelationsd'équivalenceentreproblèmes
519

Réduction et équivalence au sens faible 520

Réduction et équivalence au sens fort. 521

Formulation par un programme en nombres entiers 521

Formulation par une fonction d'ensemble 522

Formulation par recherche d'applications entre ensembles finis discrets 522

2.
Partition et recouvrement d'un hypergraphe 522

2.1. Définitions
et exemples 522

2.2.Les
problèmes de sélection (recouvrement) 525

2.2.1.
Sélection des fichiers dans une banque de données 525

2.2.2.
Localisation de services 526

2.2.3.
Simplification d'expressions booléennes 526

2.3.
Les problèmes d 'affectation (partition et quelquefois recouvrement) 527

2.3.1.
Le problème de rotation des équipages 527

2.3.2.
L'habillage des horaires des lignes d'autobus 528

2.3.3.
Les problèmes de tournées 529

2.4.
Cas particuliers de problèmes polynomiaux 529

2.4.1.
Le cas de la matrice d'incidence sommets-arêtes d'un graphe 530

2.4.2.
Le cas d'un hypergraphe d'intervalles 530

3.
Le problème du couplage d'un hypergraphe 532

3.1.
Formalisation du problème 532

3.2.
Quelques cas particuliers 533

4.
Coloration d'un graphe et d'un hypergraphe 536

4.
I. Coloration des sommets d'un graphe 537

4.2.Cas
particulier de la coloration des arêtes 540

4.3.Quelques
problèmes concrets 542

4.3.1.
Problèmes d'emploi du temps 542

4.3.2.
Problèmes de classification 543

5.
Le problème du sac à dos multidimensionnel 543

5.I.
Quelques exemples concrets 544

5.1.1.
Le choix des investissements 544

5.1.2.
Le chargement d'un bateau, d'un avion 544

5.1.3.
Lesproblèmesderecouvrementetdecouplaged'hypergraphes 544

5.1.4.
Les problèmes de découpe industrielle (« cutting-stock ») 545

5.2.
Un théorème d'équivalence 545

5.3.
Un algorithme pseudo-polynomial 547

5.4.
Le problème d'affectation généralisée 549

6.
Les problèmes de coûts fixes et les fonctions d'ensemble 550

6.1.
Le problème de la localisation 551

6.2.Leproblèmedel'optimisationd'unréseau
553

6.3.Quelques
propriétés de sous-modularité 553

7.
Les problèmes d'ordonnancement 555

7.1.
Le problème du voyageur de commerce 555

7.2.
Quelques variantes du problème du voyageur de commerce 556

7.3.Ordonnancementàcontraintesdisjonctives
557

8.
Quelques autres problèmes concrets 559

8.1.Legraphe partielsanscircuitdepoidsmaximum
559

8.2.Minimisationd'unefonctionquadratique
559

9.
Problèmes NP-complets et réductions entre problèmes 561

9.1.RéductionsfaiblesetproblèmesNP-complets
561

9.2.Lesfortesréductions
564

Exercices 567

Références bibliographiques 587

Chapitre Il
Les algorithmes d'énumération par séparation-évaluation
et propagation de contraintes 591

1.
Un exemple d'exploration par séparation, évaluation et propagation 592

2.
Les procédures d'exploration par séparation et évaluation 595

2.1.
Évaluation par défaut 596

2.2.Règles
de séparation et pénalités 597

2.3.Bonne
solution réalisable 599

204.
Implications par propagation de contraintes 599

2.5.Déplacement
dans l'arborescence 600

3.
Deux exemples d'applications 602

3.1.Unproblèmed'ordonnancementd'atelier.
602

3.1.1.
Énoncé 602

3.1.2.
Soluti on 603

3.2.Unproblèmedecircuithamiltonien
606

3.2.1.
Énoncé 606

3.2.2.
Solution 607

4.
Évaluation par défaut et pénalités 611

4.1.
Solution conti nue 6Il
4.2.Amélioration
de la solution continue 613

4.3.Relaxation
lagrangienne 615

5.
« A LICE » 620

5.1.
Représentation des problèmes 621

5.2.
Le langage d'entrée d'« Alice » 623

5.3.
Les heuristiques 624

SA . Liste de problèmes résolus par « Alice » et résultats 624

~
w Exercices 627

w .~ Références bibliographiques 646

~
~
g Chapitre 12

w
.
~ Algorithmes approchés et métaheuristiques 651

B.g l. Les algorithmes itératifs de voisinage 652

.
5 1.1. Principe général d'un algorithme itératif de voisinage 652

1

1.2.Lesalgorithmesprocédantparrelaxationssuccessives
656

1.3.
Fiabilité d'un algorithme itératif de voisinage 656

lA.
La métaheuristique du « recuit simulé» 658

1.5.
La métaheuristique de « recherche Tabou » 661

1.6.Autres
algorithmes itératifs aléatoires 663

2.
Les algorithmes gloutons 665

2.1.
Critère du coût moyen et extensions 665

2.2.Le critèreducoûtmarginalpourlesfonctions d'ensemble
668

2.3.
Critère du regret maximum 671

2.4.
Algorithmes gloutons aléatoires (AGAT) 674

2.4.1.
Algorithme glouton aléatoire RLFO 676

2.4.2.
Deux algorithmes gloutons aléatoires pour le problème
de recouvrement 677

3.
Les métaheuristiques inspirées de la biologie 681

3.1.
Les algorithmes génétiques 681

3.2.
Les algorithmes de colonies de fourmis 683

4.
Régularisation des coûts 685

4.1.
Les transformations idéales 685

4.2.
Interprétation économique des coûts régularisés 687

5.
Optimalité des algorithmes approchés 688

5.1.
Optimalité a priori 689

5.2.
Optimalité a posteriori 690

5.2.1.
Vérifications de l'optimalité 690

5.2.2
. Vérification de l's-optimalit é 691

5.2.3.
Conditions suffisantes d'optimalité 691

Exercices 691

Références bibliographiques 704

Annexe 1

Programmation linéaire 709

1.
Définitions et résultats fondamentaux 709

1.1.
Forme standard d'un programme linéaire 709

1.2.
Définitions 711

1.3.
Rappels sur les ensembles convexes et les polyèdres 711

1.4.
Bases, bases réalisables, solutions de base 712

1.5.
Caractérisation des bases optimales 714

2.
La résolution des programmes linéaires 717

2.1.
L'algorithme primaI du « simplexe » (forme révisée) 717 ~
2.3.
Matrices de changement de base et forme produit de l'inverse 719 §ûi
2.4.Base
de départ 720 .il
2.5.Formecanoniqueet
tableau simplexe 721 "§
3.
La notion de dualité 724 ~
c
3.1
. Dual d'un progamme linéaire sous forme standard 724 ~
3.2.
Définition du dual dans le cas général 725 .~
o
3.3.
Le théorème de la dualité 725 ~
a.
3.4.Variablesdualesetcoûtsmarginaux
727 ~
4.
Algorithmes dual et primai-dual 728 "* 1

4.1.
L'algorithme dual 728 .~
...J
4.2
. L'algorithme primaJ-dual 731 @
5.
Une application de la dualité: le théorème de Farkas et Minkowsky 734

Références bibliographiques 735

Annexe 2

Programmation linéaire en nombres entiers 737

1.
Polyèdres de sommets entiers 738

2.
Un algorithme de coupes 739

3.
La méthode des congruences décroissantes 741

4.
Développements récents : combinatoire polyédrique 743

Références bibliographiques 744

Annexe 3

Relaxation lagrangienne et résolution du problème dual 747

1.
Définition du problème primaI. 747

2.
Définition du problème dual et propriétés 749

3.
Résolution du problème dual par programmation linéa ire 752

4.
Résolution du problème dual par une méthode de sous-gradient 754

Références bibliographiques 759

Annexe 4

Programmation dynamique 761

1.
Méthodes et exemples 761

2.
Améliorations de la programmation dynamique 765

Références bibliographiques 767

Annexe 5

Les problèmes de ratio minimum 769

1.
Les algorithmes itératifs 770

2.
L'algorithme par dichotomie 771

Références bibliographiques 775

Index 777