Eléments de la théorie des graphes

Eléments de la théorie des graphes

Problème de plus court chemin

Le problème de plus court chemin compte parmi les problèmes les plus classiques de la théorie des graphes et les plus importants dans leurs applications, donc on va essayer dans ce chapitre de définir en premier temps le problème de plus court chemin puis en deuxième temps, on va parler des algorithmes de résolution de ce problème et on va mettre le point sur l’algorithme de Dantzig.

Définition d’un problème de plus court chemin

Le problème de plus court chemin peut être posé de la façon suivante :
• étant donnés un graphe valué G=(X, U, L), on associera à chaque arc u= (i, j) un nombre réel l(u) où appelée la longueur de l’arc. Le problème de plus court chemin entre deux sommets « S » (source ou origine) et « d » (destination) du graphe consiste à déterminer parmi tous les chemins allant de « S » à « d » un chemin noté ∗ dont la longueur total : ( ∗) = ∑ ∈ ∗ ( ) soit minimale.
Condition d’existence de plus court chemin :
Le problème de plus court chemin a une solution si et seulement s’il n’existe pas dans le graphe de circuit de longueur strictement négative pouvant être atteint à partir de l’origine «S».

Algorithmes de résolution

Généralités

Différents problème peuvent être posés autour de la recherche de plus court chemin.Un premier problème A consiste à rechercher le plus court chemin entre deux points donnés, c’est –à-dire déterminer le chemin de plus petit longueur qui relie ces points. Pour résoudre ce problème, on résout le problème B. Ce dernier consiste à déterminer, à partir d’un point donné le plus court chemin pour aller à tous les autres nœuds. Enfin le problème C consiste à trouver, pour n’importe quelle paire de nœuds, le chemin le plus court entre eux.Le problème B peut être résolu de nombreuses manières. Tout dépend des hypothèses émises sur la structure du réseau. Lorsque le réseau est sans circuit, on appliquera l’algorithme de Bellman. Lorsque le réseau n’a que des longueurs positives ou nulles (mais éventuellement avec des circuits), on utilisera la méthode de Dijkstra.Donc selon les propriétés du graphe traité (orienté/non orienté, avec/sans circuit ou longueur positives/quelconques) et selon le problème considéré (recherche de plus court chemin d’un sommet vers tous les autres/entre tous les couples de sommets) il existe nombreux algorithmes permettant l’obtention d’une solution.On S’intéressera ici à l’algorithme de Dantzig (moor-djikstra).

Algorithme de DANTZIG

L’algorithme de dantzig permet de calculer le plus court chemin d’un sommet « s » à un sommet « d » ou d’un sommet « s » à tous les autres sommets dans un graphe de longueur positive.
Algorithme :
Titre : Dantzig
Entrées : R=(X, U, c) un réseau
Sorties : D une matrice contenant les plus courtes distances
Variables intermédiaires : i, j, k des entiers
Début
Pour i ← 1 à n faire
Pour j ← 1 à n faire
Si i = j alors D(i, j) ← 0 ;
Sinon D(i, j) ← +∞ ;
Fin pour ;
Fin pour ;
Pour k ← 1 à n faire
Pour i ← 1 à k − 1 faire
D(k, i) ← min{c(xk, xj) + D(j, i)/ (xk, xj) ϵ U} ; Fin pour ; Pour i ← 1 à k − 1 faire ;
D(i, k) ← min{D(i, j) + c(xj, xk) / (xj, xk)} ϵ U} ;
Fin pour ;
Pour i ← 1 à k − 1 faire Pour j
← 1 à k − 1 faire
D(i, j) ← min{D(i, j), D(i, k) + D(k, j)} ;
Fin pour ;
Fin pour ;
Fin pour ;
Fin

Problème du flot maximal

Le problème du flot maximal consiste à trouver, dans un réseau de transport, un flot maximal depuis une source unique et vers un puits unique. Donc on va définir d’une part le problème de flot maximal et d’autre part son algorithme de résolution.

Réseau de transport

Flots dans un réseau de transport

Définition d’un réseau de transport

Un réseau de transport est un graphe sans boucle où chaque arc est associé à un nombre ( ) > 0, appelé « capacité de l’arc u ».
En outre, un tel réseau vérifie les hypothèses suivantes :
• Il existe un seul nœud « E » qui n’a pas de prédécesseur, tous les autres ont au moins un prédécesseur. Ce nœud est appelé l’entrée (ou la source) du réseau.
• Il existe également un seul nœud « S » qui n’a pas de successeur, tous les autres ont au moins un successeur. Ce nœud est appelé la sortie (ou le puits) du réseau.
EXEMPLE :

Définition d’un flot

Un flot dans un réseau de transport est une fonction qui associe à chaque arc u, ( ) représente la quantité de flot qui passe par cet arc u.
Un flot est vérifié les deux propriétés suivantes :
• ∀ u∈U, 0 ≤ ( ) ≤ ( )
• ∀ x ∈ X, ∑ +( ) ( ) = ∑ −( ) ( ) « loi de conservation du flot »

Valeur du flot

On ajoute un arc de retour « fictif » depuis « S » vers « E », on définit alors la valeur du flot comme celle du flux qui par cet arc fictif.

Flot compatible

Un flot est compatible si pour tout arc u∈U 0 ≤ ( ) ≤ ( ).Autrement dit, pour chaque arc, le flot qui le traverse ne doit pas dépasser la capacité de l’arc.

Flot complet

Un flot complet est un flot compatible pour lequel tout chemin allant de « E » à « S » possède au moins un arc saturé.

Coupe

On appelle coupe séparant E et S un ensemble d’arc de la forme −( ) ou tel que ∈ et

Capacité d’une coupe

La capacité d’une coupe est la somme des capacités des arcs da la coupe C(A)=∑ ∈ − ( ).

Saturation d’un réseau de transport :

Arc saturé

Un arc est saturé par un flot si la valeur du flot sur l’arc égale à sa capacité (, )=(, ).

Chemin saturé

Un chemin est saturé si l’un de ses arcs est saturé.

Algorithme de résolution

L’algorithme le plus connu pour résoudre ce problème est celui de Ford-Fulkerson.

Algorithme de flot compatible :

Soit un flot quelconque :
• i →
• Si ( ) > 0 0 = ( , ) 0 ( 0 ) > 0
Marquer y
Soit u= (i, j), si le sommet i est marqué et le sommet j non marqué,
Marqué le sommet j si :
• Soit il existe un arc u= (i, j) tel que≤ < ( ≠ 0)
• Soit il existe un arc u= (i, j) ou u= (j, i) tel que < <
• Soit il existe un arc u= (j, i) tel que< <
i x e marqué a il ex te un cycle passant par l’arc tel que ⃗
= min( 1, 2) , > 0 avec { 1=+(−)
= ( − )
Si x n’est pas marquer, STOP pas de flot compatible.
Théorème de ford-Fulkerson :
Dans un réseau de transport, la valeur maximale d’un flot est égale à la capacité minimale d’une coupe.

Algorithme de ford-Fulkerson

L’algorithme de Ford-Fulkerson se décompose en deux étapes :
• Procédure de marquage : permet de déterminer s’il existe un chemin de E « source » à S « puits »
• Procédure d’augmentation de flot : permet d’augmenter le flot actuel
La procédure d’augmentation ne s’applique que si « S » est marqué à l’issue de la procédure de marquage.
➢ Soit → ⋯ → → +1 → ⋯ → ← +1 → ⋯ → une chaine de « E » à « S »
➢ Soit +l’ensemble des arcs de la chaine de type ( , +1) « arc avant »
➢ Soit −l’ensemble des arcs de la chaine de type ( , +1) « arc arrière »
➢ Les arcs de + sont tels qu’il est possible d’augmenter la valeur du flux associe d’une quantité + ≥ 0
➢ Les arcs de − sont tels qu’il est possible de diminuer la valeur du flot associe d’une quantité − ≥ 0
➢ Une chaine est dite améliorant si + > 0− > 0
Algorithme : Recherche d’un flot maximal dans un réseau de transport
Partir d’un flot compatible, soit 0 sa valeur.
Appliquer la procédure du marquage suivant :
Marquer la source « E » du réseau
Soit (i, j) un arc de réseau, si le sommet i est marqué, alors marqué j si :
Soit il existe un arc u= (i, j) tel que <
Soit il existe un arc u= (j, i) tel que > 0
Si l’on n’arrive pas à marquer le puits « S » du réseau, alors le flot est maximal, FIN Si l’on marquer le puits « S » du réseau, ce flot n’est pas maximal, il faut passer à l’étape (4)

Le rapport de stage ou le pfe est un document d’analyse, de synthèse et d’évaluation de votre apprentissage, c’est pour cela rapport gratuit propose le téléchargement des modèles gratuits de projet de fin d’étude, rapport de stage, mémoire, pfe, thèse, pour connaître la méthodologie ?avoir et savoir comment construire les parties d’un projet de fin d’étude.

Table des matières

INTRODUCTION
Chapitre 1 : Eléments de la théorie des graphes
1. Concept sur les graphes
1.1 Graphe orienté et Graphe non orienté
1.2 Graphe valué
2. Matrices associées à un graphe
2.1 Matrice d’adjacence
2.2 Matrice d’incidence sommets-arcs
3. Programmation linéaire en nombres binaire
3.1 Modélisation
3.2 Formes d’un programme linéaire
3.3 Méthode du simplexe en deux phases
Chapitre 2 : Problème de plus court chemin
1. Définition d’un problème de plus court chemin
2. Algorithmes de résolution
2.1 Généralités
2.2 Algorithme de DANTZIG
Chapitre 3 : Problème du flot maximal
1. Réseau de transport
1.1 Flots dans un réseau de transport
1.2 Saturation d’un réseau de transport
2. Algorithme de résolution
2.1 Algorithme de flot compatible
2.2 Algorithme de ford-Fulkerson
Chapitre 4 : Résolution du problème de transport urbain
1. Problématique
2. Problème de plus court chemin dans un réseau de transport urbain
2.1 Simulation de l’algorithme de DANTZIG
2.2 Programmation en langage C
2.3 Modélisation d’un problème de plus court chemin
2.4 Simulation de la méthode du simplexe en deux phases
3. Détermination d’un flot maximal dans le réseau de transport urbain
3.1 Simulation de l’algorithme de FORD-FULKERSON (Saturation d’un réseau)
3.2 Programmation en langage C
Conclusion générale
Références