suivant:
Introduction
Introduction
Définitions fondamentales
Les graphes non orientés
Cocycles, degrés
Matrices associées aux graphes
Matrice d'incidence sommet-arc
Matrice d'adjacence sommet-sommet
Expression des matrices
Chemins, Chaînes, Circuits, Cycles
Définitions générales
Chemin Eulérien, chemin Hamiltonien
Sous graphes, graphes partiels
Définitions générales
Cliques, Stables, Coloration
Connexité, forte connexité
Connexité
Forte connexité
Arbres
Notion d'arbre
Définitions fondamentales
Démonstration de l'équivalence des définitions sur les arbres
Démonstration
Démonstration
Démonstration
Plus courts chemins
Notations
Le problème
Les algorithmes de plus court chemin
Graphe acyclique
Arcs à coûts positifs, algorithme de Dijkstra
Le cas général, algorithme de Ford
Le problème de l'ordonnancement
Introduction
Le problème
Les contraintes temporelles
Les contraintes cumulatives
Contraintes disjonctives
Un exemple simple : le chantier
Représentation du problème d'ordonnancement
Diagramme de Gantt
Le modèle PERT
Le modèle Potentiel-tâches
Résolution
Conséquence
Introduction aux problèmes de flot
Notion de réseau
Les simplifications du problème
Travailler avec une seule source et un seul puits
Eliminer les arcs avec des capacités minimales non nulles
Cas des capacités sur les sommets
Quelques problèmes de flot classiques
Le problème de flot maximal
Le problème du flot de coût minimum
Quelques techniques utilisées sur les réseaux
Le graphe d'écart
La notion de coupe
Quelques exemples de problèmes modélisables par les flots
Problèmes faisant intervenir le flot maximal
Le problème des représentants
Le problème de l'arrondi cohérent
Application du problème de flot de coût minimal
Problème de transport simple
L'algorithme de Ford & Fulkerson
Capacité résiduelle dans le cas général
Démonstration du théorème Flot max / Coupe min : le début
Augmentation maximale du flot
Forme naïve de l'algorithme de Ford & Fulkerson
Une implémentation possible de l'algorithme de Ford & Fulkerson
Une amélioration possible
Le problème des arbres couvrants de poids minimal
Définitions
Applications des ACM
Les problèmes de conception d'architectures
Le problème des agents secrets
Regrouper des données en amas
Les conditions d'optimalité d'un ACM
La condition d'optimalité de coupes
La condition est nécessaire
La condition est également suffisante
La condition d'optimalité de chemin
La condition est nécessaire
La condition est suffisante
Les algorithmes de recherche d'un ACM
L'algorithme de Kruskal
L'algorithme de Prim
Démonstration unifiée
Application à l'algorithme de Prim
Application à l'algorithme de Kruskal
Illustration par l'exemple
Bibliographie
À propos de ce document...
Bruno Garcia 2000-12-17
