Graphes et Applications Partie N : 1 Réalisé par SifiSami 6 mai 2014 T  

Graphes et Applications Partie N : 1 Réalisé par SifiSami 6 mai 2014 T     1 Introduction à la théorie des graphes 2 1.1 Introduction : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Définition : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Représentations d’un graphe . . . . . . . . . . . . . . . . . . . . . 4 1.3.1 Matrice d’adjacence . . . . . . . . . . . . . . . . . . . . . . 4 1.3.2 Matrice d’incidence sommets-arcs . . . . . . . . . . . . . . 4 1.3.3 Listes d’adjacence . . . . . . . . . . . . . . . . . . . . . . . 4 1.4 Coloration des sommets d’un graphe : . . . . . . . . . . . . . . . . 5 1.4.1 Un algorithme de coloration . . . . . . . . . . . . . . . . . 6 1.4.2 Histoire . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.5 Problème de plus court chemin : . . . . . . . . . . . . . . . . . . . 9 1.5.1 Définitions et propriétés : . . . . . . . . . . . . . . . . . . 9 1.5.2 Le Cas des graphes sans circuits : Algorithme de Roy (Rang). 9 1.5.3 Le cas des poids positifs : Algorithme de Dijkstra . . . . . 12 1.5.4 Le cas où les poids sont de signe quelconque : Algorithme de Ford-Bellman . . . . . . . . . . . . . . . . . . . . . . . 14 1.5.5 Le plus court chemin entre les différents couples sommets d’un graphe : Algorithme de Floyd . . . . . . . . . . . . . 14 1.6 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.6.1 Affectation du personnel d’une compagnie de transport . . 15 1.6.2 Construction d’un réseau routier . . . . . . . . . . . . . . . 16 1.6.3 Application 3 . . . . . . . . . . . . . . . . . . . . . . . . . 17 1 1. I          1.1. Introduction : D’une manière générale, les graphes permettent de représenter les structures et les connexions d’un ensemble complexe en exprimant les relations entre ses éléments. Les graphes constituent donc, une méthode de penser qui permet de modéliser une grande variétés de problèmes en se basant sur l’étude des sommets et des arcs. Exemples : — La recherche d’un plus court chemin. (Réseau routier, Internet...) — La distribution optimale d’un flot sur un réseau. (Communication, eau po- table...) — Optimisation de la compilation : Un processeur a un nombre limité de re- gistres où il peut stocker ses données. Étant donné un certain nombre de variables utilisées dans un programme, il faut trouver un moyen d’affecter les variables dans les registres de façon à maximiser l’utilisation des registres et de minimiser les accès à la mémoire. Ce problème est résolu grâce à la co- loration de graphes, attribuant à chaque noeud / variable une "couleur", de sorte que deux sommets adjacents (variables utilisées dans le même temps à un programme) n’ont pas la même couleur. Il s’agit d’un problème NP- complet. — La planification d’une conférence ou examens...(coloration de graphes). — Le parcours optimal de distribution : - Le problème du postier chinois consiste à trouver un plus court chemin dans un graphe connexe non orienté qui passe exactement une fois par chaque arête du graphe et revient à son point de départ (Cycle eulérien, Théorème d’Euler : Un graphe (resp : orienté fortement) connexe est Eulérien si et seulement si chacun de ses sommets est de degré pair (resp : est l’extrémité initiale et terminale du même nombre d’arêtes).(http ://fr.wikipedia.org/wiki/Problème_du_postier_chinois) 2 - Le problème du voyageur de commerce consiste à trouver un plus court chemin dans un graphe connexe non orienté qui passe exactement une fois par chaque sommet du graphe et revient à son point de départ (Cycle Hamiltonien). — Gestion de projets : Pert. 1.2. Définition : 1. Un graphe simple G est un couple formé de deux ensembles : - Un ensemble X dont les éléments sont appelés sommets. - Un ensemble A dont les éléments sont appelés arêtes. On notera G = (X, A). Les éléments de A sont de type a = (i, j) avec i et j ∈IN∗. (a) est l’arête d’extrémités i et j. 2. Graphe orienté : l’ordre de i et j est important. Dans ce cas les éléments de A sont appelés : arcs 3. Deux sommets sont adjacents s’ils ont un arc en commun. Deux arcs (arêtes) sont adjacents s’ils ont un sommet en commun. 4. Si un arc est orienté de i vers j on dit que : - i est un prédécesseur de j - j est un successeur de i 5. Un chemin est une succession de sommets adjacents. Une chaine est un che- min dans un graphe non orienté. Un circuit est un chemin dont les extrémités coïncident. 6. Graphe non orienté connexe : ∀(i, j) ∈G; ∃une chaîne reliant i et j.(Pareil pour composante connexe). 7. Graphe orienté fortement connexe : il existe un chemin de i vers j et un autre je vers i.(Pareil pour composante fortement connexe). 8. Un stable de G est un sous-ensemble de sommets deux-à-deux non-adjacents. 9. Degrés : -Le demi-degré extérieur de (i), d+(i), est le nombre d’arcs ayant (i) comme extrémité initiale. -Le demi-degré intérieur de (i), d−(i), est le nombre d’arcs ayant (i) comme extrémité finale. -Le degré de (i) est d(i) = d+(xi) + d−(xi). Le degré d’un sommet d’un graphe non orienté est le nombre d’arêtes qui lui sont incidentes. Propriétés Graphe non orienté :  x∈G d(x) ? = f(#arˆ etes)? Graphe orienté :  x∈G d+(x) ? =  x∈G d−(x) = f(#arcs)? 1.3. Représentations d’un graphe Dans l’aspect algorithmique de la théorie des graphes, on cherche à conce- voir un processus efficace pour traiter un problème faisant intervenir un graphe. Les principaux critères d’efficacités d’un processus sont le temps nécessaire pour obtenir la réponse et l’espace que le processus consomme dans son travail. Un certain nombre de représentations existent pour décrire un graphe. On distingue principalement la représentation par matrice d’adjacence, par matrice d’incidence sommets-arcs (ou sommets-arêtes dans le cas non orienté) et par listes d’adjacence. 1.3.1. Matrice d’adjacence C’est une matrice booléenne qui traduit l’existence ou non d’un arc (i, j ) entre les sommets (i) et (j). Place mémoire utilisée : n2 (pour un graphe composée de n sommets) Remarque : pour des graphes valués on remplace « 1 » par la valeur numérique de l’arc. 1.3.2. Matrice d’incidence sommets-arcs Ligne← →sommet ; colonne ← →arc. Si u = (i, j) ∈U, on notera : aiu = 1 : aju = -1 ; tous les autres termes sont nuls. 1.3.3. Listes d’adjacence l’avantage de la représentation par listes d’adjacence, par rapport à celle par matrice d’adjacence, est le gain obtenu en place mémoire ; ce type de représenta- tion est donc mieux adapé pour une implémentation. Le but est de représenter chaque arc par son extrémité finale, son extrémité initiale étant définie implicite- ment. Tous les arcs émanant d’un même sommet sont liés entre eux dans une liste. A chaque arc sont donc associés le nœud destination et le pointeur au prochain sommet dans la liste. Sommet Pointeur Extrémité finale Arc 1 1 2 u1 2 3 3 u3 3 5 1 u2 3 u4 - - Place mémoire utilisée : n + m. Remarque Si l’on veut connaître l’existence d’une arête entre deux sommets, la matrice d’adjacence permet d’obtenir un résultat immédiatement, ce que l’on appelle en θ(1). En revanche, une opération de base telle que trouver le voisin d’un sommet est en O(n) sur une matrice d’adjacence : dans le pire des cas, il faudra scanner la totalité de la colonne pour s’apercevoir qu’il n’y a pas de voisin. Pour la liste d’adjacences, trouver un uploads/Ingenierie_Lourd/ chap-1-2-graphes.pdf

Tags
Ingénierie graphe sommets chemin court algorithme
Documents similaires
  • 25
  • 0
  • 0
Afficher les détails des licences
Licence et utilisation
Gratuit pour un usage personnel Attribution requise
Partager