第 1 页
Informatique / Recherche operationnelle / Presentation (French) 1 de 3 RECHERCHE OPERATIONNELLE INTRODUCTION La recherche opérationnelle est une discipline dont le but est de fournir des méthodes pour répondre à un type précis de problème, c’est-à-dire à élaborer une démarche universelle pour un type de problème qui aboutit à la ou les solutions les plus efficaces. La particularité de la recherche opérationnelle est que les méthodes proposées sont des démarches rationnelles basées sur des concepts et outils mathématiques et/ou statistiques. Généralement, ces méthodes sont employées sur des problèmes tels que leur utilisation "manuelle" devient impossible. C’est pourquoi, du fait qu’elles sont rationnelles, les démarches proposées par la recherche opérationnelle peuvent être traduites en programmes informatiques. Cette traduction d’une démarche en un programme informatique n’est pas sans difficulté. Tout d’abord, le temps d’exécution du programme résultant et/ou la place occupée dans la mémoire de l’ordinateur peuvent ne pas être acceptables. Ainsi, une méthode en recherche opérationnelle sera jugée sur ces critères de temps et de place. Plus une méthode sera rapide et peu gourmande en mémoire, plus elle sera considérée bonne. Les ordinateurs ont une structure particulière qui fait que toutes les propriétés des mathématiques traditionnelles ne sont pas toujours respectées. Ainsi, une démarche prouvée fonctionner admirablement en théorie peut s’avérer être complètement inexploitable en pratique. Notamment, les nombres réels dans un ordinateur ne peuvent pas être représentés de manière exacte, ils sont arrondis. On voit donc facilement qu’une répétition excessive d’arrondis dans un calcul peut entraîner des erreurs importantes dans les résultats finaux. Les méthodes employées en recherche opérationnelle doivent prendre en compte ce genre de problème. PLAN DU COURS Dans ce cours, nous verrons différents outils de recherche opérationnelle sans apporter de justifications mathématiques très détaillées et rigoureuses. Après quelques exemples qui permettront de mieux cerner le domaine de la recherche opérationnelle, nous introduirons un outil à la fois graphique et théorique: les graphes. Afin de mieux appréhender la complexité d’un problème ou la rapidité d’un algorithme, nous nous intéresserons à la théorie de la complexité. Enfin, nous verrons un autre outil important de la recherche opérationnelle qui est la programmation linéaire. L’avantage de cet outil est d’apporter une solution générique à la résolution de nombreux problèmes. De plus, cet outil est disponible sous différentes formes pour une utilisation informatique. Voici le plan du cours. Présentation Les graphes
第 2 页
Informatique / Recherche operationnelle / Presentation (French) 2 de 3 Les arbres Représentation des graphes Efficacité des algorithmes, complexité des problèmes Recherche du plus court chemin Ordonnancement, recherche du plus long chemin Recherche du flot maximum Programmation linéaire EXEMPLES Chemin le plus court / le plus long Soit un ensemble de villes et des chemins directs reliant ces villes entre elles. Le problème dit "du plus court chemin" consiste à trouver pour une ville de départ donnée et une ville d’arrivée donnée le chemin le plus court qui relie ces deux villes. Le problème peut également être de trouver un chemin le plus court pour chaque couple de villes. Pour certains problèmes, trouver le plus long chemin entre deux points peut être intéressant. Ordonnancement / planification Considérons la gestion d’un grand projet. Il est constitué de différentes étapes à réaliser. Il est logique de penser que certaines tâches doivent être effectuées avant d’autres alors que certaines peuvent très bien être effectuées en même temps. Ainsi, on établit une certaine relation d’ordre entre les étapes. Un premier problème consiste à trouver une planification des tâches qui aboutisse à la réalisation du projet en un minimum de temps. Ensuite, il peut être intéressant de détecter les étapes dites "critiques" dont le moindre retard peut affecter toute la suite du projet. Flot maximum Soit des châteaux d’eau ayant un débit constant. Ils desservent un certain nombre de villes, chacune ayant des besoins quantifiés constants. L’eau est acheminée à travers des conduits dont le débit maximum est connu. Le problème est de trouver un moyen de satisfaire au mieux les demandes de chaque ville. En d’autres termes, essayer d’apporter le plus d’eau possible vers les villes. Flot de coût minimum Il s’agit d’un problème semblable à celui du flot maximum mais on suppose en plus qu’un coût fonction du débit est associé à l’utilisation d’un conduit. Le problème devient alors de satisfaire les villes mais de la manière la moins onéreuse. Sac à dos Un randonneur prépare son sac à dos pour partir en excursion. Bien entendu, il veut
第 3 页
Informatique / Recherche operationnelle / Presentation (French) 3 de 3 éviter d’avoir un sac trop lourd et décide de se limiter dans le choix des objets qu’il emporte afin de ne pas dépasser un certain poids. Cependant, il veut emporter le maximum de choses utiles. Pour cela, il affecte une valeur quantitative à chaque objet en plus de son poids (plus la valeur est importante, plus le randonneur juge l'ob jet important). Le problème peut donc se formuler de la manière suivante: trouver l’ensemble des objets dont la somme des utilités est maximum tout en ne dépassant pas un poids fixé. Affectation Des modifications de postes sont effectuées dans une entreprise. Plusieurs personnes doivent être affectées à de nouveaux postes. Ainsi, chacun classe par ordre de préférence les postes qu’il veut occuper. Le problème ici est d’attribuer à chaque personne un poste tout en essayant de satisfaire au mieux le souhait de chacun. Voyageur de commerce Un voyageur de commerce doit démarcher dans un certain nombre de villes. Il connaît bien entendu la distance qui sépare les villes entre elles. Cependant, le voyageur de commerce veut perdre le moins de temps possible dans ses déplacements. Le problème est donc de trouver un chemin qui passe par toutes les villes une et une seule fois et qui soit le court possible. Dans tous ces exemples, il existe une méthode simple pour résoudre le problème. En effet, il suffit d’énumérer toutes les possibilités et d’en dégager la ou les meilleures. Cependant, on s’aperçoit que plus le problème est compliqué en terme d’éléments mis en jeu, plus le nombre de possibilités croît de manière non pas linéaire (proportionnelle) mais plutôt exponentielle. Par exemple, le problème d’affectation présenté précédemment avec 100 personnes a 100! (100 x 99 x 98 x ... x 1) solutions. Le simple fait de rajouter une personne dans le problème va multiplier par 101 le nombre de solutions. Généralement en recherche opérationnelle, on a souvent à traiter des problèmes dont le nombre de solutions devient rapidement difficile à imaginer. Bien que les exemples vus ici soient petits, il faut bien comprendre qu’en réalité, on sera confronté à des problèmes de taille beaucoup plus importante. Ce qui explique que l’on cherche des méthodes toujours plus efficaces pour résoudre les problèmes. Copyright (c) 1999-2001 - Bruno Bachelet - bachelet@ifrance.com - http://bruno.bachelet.net La permission est accordée de copier, distribuer et/ou modifier ce document sous les termes de la licence GNU Free Documentation License, Version 1.1 ou toute version ultérieure publiée par la fondation Free Software Foundation. Voir cette licence pour plus de détails (http://www.gnu.org).
第 4 页
Informatique / Recherche operationnelle / Les graphes (French) 1 de 10 1. LES GRAPHES DEFINITIONS ET THEOREMES Graphe Un graphe est un ensemble de noeuds qui sont reliés entre eux par des arcs. Mathématiquement, un graphe est représenté par un couple de deux ensembles G = (X;U) où X est l’ensemble des noeuds et U l’ensemble des arcs. Arc Un arc relie deux noeuds entre eux, il sera donc représenté par un couple (x;y) où x et y sont des noeuds. Un arc peut être orienté, c’est-à-dire que l’ordre de x et de y est important dans le couple (x;y). Un arc peut ne pas être orienté et dans ce cas, l’ordre de x et de y dans le couple (x;y) n’a aucune importante, donc (x;y) = (y;x). Les arcs sont représentés de la manière suivante. Arc orienté: Arc non orienté: Remarque Un arc non orienté peut toujours être transformé en une situation où l’on n’a que des arcs orientés. C’est pourquoi, dans la suite du cours, on utilisera le plus souvent des graphes orientés, c’est- à-dire des graphes dont les arcs sont tous orientés. Boucle On appelle boucle un arc dont l’extrémité initiale est égale à son extrémité finale. Par exemple, (x;x) est une boucle. Adjacence
第 5 页
Informatique / Recherche operationnelle / Les graphes (French) 2 de 10 Pour un arc u = (x;y) on dit que: x est adjacent à y, y est adjacent à x, x et y sont adjacents à u, u est adjacent à x et y. Degré Le demi-degré extérieur d’un noeud est le nombre d’arcs adjacents qui en partent. On le note d+(x) et d+(x) = |{u U | u = (x;y) où y X}|. Le demi-degré intérieur d’un noeud est le nombre d’arcs adjacents qui y arrivent. On le note d-(x) et d-(x) = |{u U | u = (y;x) où y X}|. Le degré d’un noeud est le nombre d’arcs qui lui sont adjacents. On le note d(x) et d(x) = d+(x) + d-(x). Exemple Dans le graphe suivant, d+(x) = 3, d-(x) = 2, d(x) = 5. Graphe régulier Un graphe est dit régulier si les degrés de tous ses sommets sont égaux. Graphe complet Un graphe est dit complet si tous les noeuds sont adjacents deux à deux. Autrement dit, (x;y) U (y;x) U.
第 6 页
Informatique / Recherche operationnelle / Les graphes (French) 3 de 10 Exemple Graphe non complet: Graphe complet: Chaîne Une chaîne de x à y est une séquence d’arcs c = ((x;e),(z;e),(z;a)...(s;t),(u;t),(u;y)) où deux arcs qui se suivent sont adjacents et où x doit être une extrémité du premier arc et y une extrémité du dernier. Chemin Un chemin de x à y est une chaîne dans laquelle les arcs sont orientés et tels que: x est l’extrémité initiale du premier arc, y est l’extrémité terminale du dernier arc, l’extrémité terminale d’un arc est l’extrémité initiale de l’arc qui le suit dans la séquence. Exemple
第 7 页
Informatique / Recherche operationnelle / Les graphes (French) 4 de 10 ch1 = ((A;C),(C;E)) est un chemin de A à E. ch2 = ((A;C),(C;F),(F;A),(A;C),(C;E)) est un chemin de A à E. ch3 = ((A;C),(C;F),(F;D),(D;C),(C;E)) est un chemin de A à E. ch4 = ((A;B),(B;D),(D;E)) est une chaîne de A à E. ch5 = ((A;B),(B;D),(D;C),(C;A),(A;B),(B;D),(D;E)) est une chaîne de A à E. ch6 = ((A;B),(B;D),(D;C),(C;F),(F;D),(D;E)) est une chaîne de A à E. Chemin, chaîne simples Un chemin simple est un chemin qui ne contient pas plusieurs fois le même arc. Dans l’exemple précédent, ch1 et ch3 sont des chemins simples mais pas ch2. Une chaîne simple est une chaîne qui ne contient pas plusieurs fois le même arc. Dans l’exemple précédent, ch4 et ch6 sont des chaînes simples mais pas ch5. Chemin, chaîne élémentaires Un chemin élémentaire est un chemin qui ne passe pas plus d’une fois par un noeud. Dans l’exemple précédent, ch1 est un chemin élémentaire mais pas ch2, ni ch3. Une chaîne élémentaire est une chaîne qui ne passe pas plus d’une fois par un noeud. Dans l’exemple précédent, ch4 est un chemin élémentaire mais pas ch5, ni ch6. Connexité, forte connexité On définit la connexité par une relation entre deux noeuds de la manière suivante. x et y ont une relation de connexité il existe une chaîne entre x et y ou bien x = y.
第 8 页
Informatique / Recherche operationnelle / Les graphes (French) 5 de 10 On définit la forte connexité par une relation entre deux noeuds de la manière suivante. x et y ont une relation de forte connexité (il existe un chemin de x à y et un chemin de y à x) ou bien x = y. Graphe connexe, fortement connexe Un graphe est dit connexe si tous ses noeuds ont deux à deux la relation de connexité. Un graphe est dit fortement connexe si tous ses noeuds ont deux à deux la relation de forte connexité. Exemple Graphe non connexe: Graphes connexes mais non fortement connexes: Graphe fortement connexe: Composante connexe, fortement connexe
第 9 页
Informatique / Recherche operationnelle / Les graphes (French) 6 de 10 On appelle composante connexe un ensemble de noeuds qui ont deux à deux la relation de connexité. De plus, tout noeud en dehors de la composante n’a pas de relation de connexité avec aucun des éléments de la composante. De même, on appelle composante fortement connexe un ensemble de noeuds qui ont deux à deux la relation de forte connexité. De plus, tout noeud en dehors de la composante n’a pas de relation de forte connexité avec aucun des éléments de la composante. Dans l’exemple précédent du graphe non connexe, {A,B,C} est une composante fortement connexe du graphe et {D,E} est une composante connexe. Graphe réduit On appelle graphe réduit du graphe G le graphe G’ pour lequel chaque noeud est associé à une composante fortement connexe de G. De plus, un arc relie un noeud x’ à un noeud y’ dans le graphe G’ si il existe un arc qui relie x à y dans G où x appartient à la composante fortement connexe de G associée à x' et où y appartient à la composante fortement connexe de G associée à y'. Exemple Ce graphe G n’est pas fortement connexe, car on ne peut pas trouver de chemin de A à D par exemple. Par contre, on identifie deux composantes fortement connexes A’ = {A,B,C}et B’ = {D,E}. Le graphe réduit du graphe G’ est: Circuit, cycle Un circuit contenant un noeud x est un chemin de x à x. Un circuit est une séquence circulaire d’arcs et donc, contrairement au chemin, un circuit n’a ni début, ni fin. De même, un cycle contenant un noeud x est une chaîne de x à x. Un cycle est également une séquence circulaire d’arcs. Un circuit (ou une chaîne) est élémentaire si le chemin (ou la chaîne) associé(e) est élémentaire.
第 10 页
Informatique / Recherche operationnelle / Les graphes (French) 7 de 10 Sous-graphe, graphe partiel, sous-graphe partiel Soit un graphe G = (X;U), X’ inclu dans X et U’ inclu dans U et U’’ = {(x;y) U | x X’ et y X’}. Le graphe (X’;U’’) est appelé "sous-graphe" de G. Le graphe (X;U’) est appelé "graphe partiel" de G. Le graphe (X’;U’ U’’) est appelé "sous-graphe partiel" de G. En d’autres termes: Un sous-graphe de G, c’est G privé de quelques noeuds et des arcs adjacents à ces noeuds. Un graphe partiel de G, c’est G privé de quelques arcs. Un sous-graphe partiel de G, c’est un graphe partiel d’un sous-graphe de G. Exemple Un graphe G: Un sous-graphe de G: Un graphe partiel de G:
第 11 页
Informatique / Recherche operationnelle / Les graphes (French) 8 de 10 Un sous-graphe partiel de G: COMPOSANTES FORTEMENT CONNEXES Lors de la conception d’un réseau de communication notamment, il peut être intéressant de savoir si la configuration choisie permet une communication de n’importe quel point à n’importe quel autre. Un moyen de le vérifier est de représenter le réseau sous la forme d’un graphe et de vérifier qu’il est fortement connexe. Pour cela, l’algorithme suivant est proposé. Il détermine la composante fortement connexe d’un graphe contenant un point donné. Ensuite, pour le problème énoncé, il suffit de choisir un point au hasard, d’exécuter l’algorithme et de vérifier que la composante fortement connexe trouvée est bien le graphe en entier. Un algorithme permettant de trouver toutes les composantes fortement connexes est également proposé. Recherche d’une composante fortement connexe Cet algorithme recherche la composante fortement connexe d’un graphe G contenant un sommet a. L’idée de cet algorithme est de parcourir le graphe à partir du point a dans le sens direct (i.e. en suivant les flèches des arcs) et de créer un ensemble des noeuds parcourus. La même chose est effectuée dans le sens indirect (i.e. en suivant les flèches des arcs en sens inverse) et de créer un deuxième ensemble des noeuds parcourus. Le premier ensemble regroupe les noeuds accessibles à partir de a et le deuxième ensemble regroupe les noeuds qui peuvent atteindre a. L’intersection de ces deux ensembles donne les noeuds qui à la fois peuvent atteindre a et sont accessibles à partir de a. Cette intersection est donc la composante fortement connexe qui contient a. Algorithme
第 12 页
Informatique / Recherche operationnelle / Les graphes (French) 9 de 10 Titre: ComposanteFortementConnexe Entrées: G = (X;U) un graphe, a un sommet. Sortie: X’ un sous-ensemble de sommets. Variables intermédiaires: X1 et X2 deux sous-ensemble de sommets, examiné() une fonction, x un noeud. Début X1 {a}; pour tout x X faire examiné(x) faux; tant que x X1 | non examiné(x) faire examiné(x) vrai; pour tout u = (x;y) U | y X1 faire X1 X1 {y}; fin tant que; X2 {a}; pour tout x X1 faire examiné(x) faux; tant que x X2 | non examiné(x) faire examiné(x) vrai; pour tout u = (y;x) U | y X2 faire X2 X2 {y}; fin tant que; X’ X1 X2; Fin Recherche de toutes les composantes fortement connexes Pour trouver toutes les composantes fortement connexes d’un graphe, il suffit de choisir au hasard un noeud et de déterminer, grâce à l’algorithme précédent, la composante fortement connexe qui le contient. On obtient alors une première composante fortement connexe X1. Ensuite, parmi les noeuds qui ne font pas partie de X1, on en prend un au hasard pour déterminer la composante fortement connexe qui le contient. On obtient X2. On recommence ainsi jusqu’à ce que tous les noeuds appartiennent à une composante fortement connexe. Algorithme Titre: ComposantesFortementConnexes Entrées: G = (X;U) un graphe. Sortie: C = {C1,...,Cn} un ensemble de composantes connexes. Variables intermédiaires: X’ un sous-ensemble de sommets, i un entier, x un noeud. Début X’ X; i 1; tant que X’ faire choisir x dans X’; Ci ComposanteFortementConnexe(G,x); X’ X’ - Ci; i i + 1; fin tant que; Fin
第 13 页
Informatique / Recherche operationnelle / Les graphes (French) 10 de 10 Copyright (c) 1999-2001 - Bruno Bachelet - bachelet@ifrance.com - http://bruno.bachelet.net La permission est accordée de copier, distribuer et/ou modifier ce document sous les termes de la licence GNU Free Documentation License, Version 1.1 ou toute version ultérieure publiée par la fondation Free Software Foundation. Voir cette licence pour plus de détails (http://www.gnu.org).
第 14 页
Informatique / Recherche operationnelle / Les arbres (French) 1 de 5 2. LES ARBRES DEFINITIONS ET THEOREMES Nombre d'arcs dans un graphe Soit n le nombre de noeuds d’un graphe G = (X;U), n = |X|. Soit m le nombre d’arcs de G, m = |U|. Si G est connexe, m n - 1. Si G est sans cycle, m n - 1. Arbre Un arbre est un graphe connexe sans cycle. Il a donc n - 1 arcs. On peut donc dire qu’un arbre est un graphe qui connecte tous les noeuds entre eux avec un minimum d’arcs. Remarques L’ajout du moindre arc supplémentaire dans un arbre crée un cycle. Un graphe connexe possède un graphe partiel qui est un arbre. Exemple Un graphe connexe: Un arbre extrait du graphe précédent:
第 15 页
Informatique / Recherche operationnelle / Les arbres (French) 2 de 5 Forêt On appelle forêt un graphe dont chaque composante connexe est un arbre. Racine, antiracine Un noeud a d’un graphe G est une racine de G s’il existe un chemin joignant a à chaque noeud du graphe G. Un noeud a d’un graphe G est une antiracine de G s’il existe un chemin joignant chaque noeud du graphe G à a. Exemple A est une racine du graphe. I est une antiracine du graphe. Arborescence, anti-arborescence Un graphe G est une arborescence de racine a si G est un arbre et si a est une racine. Un graphe G est une anti-arborescence d’antiracine a si G est un arbre et si a est une antiracine. ARBRE DE COUT MINIMUM / MAXIMUM
第 16 页
Informatique / Recherche operationnelle / Les arbres (French) 3 de 5 Imaginons que l’on associe une valeur, un poids, à chaque arc d’un graphe G. Le problème de l’arbre de coût maximum consiste à trouver un arbre, graphe partiel de G, dont la somme des poids des arcs est maximum. En pratique, les problèmes se ramène plutôt à trouver l’arbre de coût minimum, ce qui ne change pas fondamentalement le principe des algorithmes proposés ici. Par exemple, minimiser le coût d’installation de lignes électriques entre des maisons peut être modélisé par la recherche d’un arbre de coût minimum. En effet, on veut connecter toutes les maisons entres elles sans avoir de lignes inutiles (d’où la recherche d’un arbre). Ensuite, on veut utiliser le moins de câble possible, aussi on associera à chaque possibilité de connexion la longueur de câble nécessaire et on cherchera à minimiser la longueur totale de câble utilisée. Dans ce cours, deux algorithmes sont proposés. L’efficacité de chacun d’eux dépend du choix de représentation du graphe et de la structure même du graphe. ALGORITHME DE KRUSKAL Le principe de l’algorithme de Kruskal pour trouver un arbre de poids minimum dans un graphe G est tout d’abord de trier les arcs par ordre croissant de leur poids. Ensuite, dans cet ordre, les arcs sont ajoutés un par un dans un graphe G’ pour construire progressivement l’arbre. Un arc est ajouté seulement si son ajout dans G’ n’introduit pas de cycle, autrement dit, si G’ reste un arbre. Sinon, on passe à l’arc suivant dans l’ordre du tri. Algorithme Titre: Kruskal Entrées: G = (X;U) un graphe. Sortie: U’ un ensemble d’arcs. Variables intermédiaires: i un entier. Début trier les arcs de G dans l’ordre croissant des poids; [On les notera u1, u2, ... , um.] U’ ; pour i 1 à m faire si le graphe (X;U’ {ui}) ne contient pas de cycle alors U’ U’ {ui}; fin si; fin tant que; Fin Justification Supposons que l’algorithme est effectué quelques itérations. Considérons maintenant l’ajout de l’arc u = (x;y) dans l’arbre. On suppose que cet ajout n’introduit pas de cycle dans G’. Est-on certain que u permet la construction de l’arbre de coût minimum ? En fait, x et y doivent être connectés d’une manière ou d’une autre. Donc si ce n’est pas u qui les relie, ce
第 17 页
Informatique / Recherche operationnelle / Les arbres (French) 4 de 5 sera une autre chaîne C = (x,s,t,u,y) de x à y comme le montre la figure ci-dessous. Comme u n’introduit pas de cycle, cette autre chaîne n’est pas encore construite, elle le sera plus tard. Cela signifie que tous les arcs de cette chaîne ont un coût supérieur ou égal à celui de u. Donc, le fait de choisir la chaîne C pour connecter x à y est plus onéreuse que de connecter x à y par u. En effet, supprimons n’importe quel arc de la chaîne C et remplaçons le par u. On obtiendra toujours un arbre mais de coût plus faible. Cela justifie le choix de u et donc la démarche globale de l’algorithme de Kruskal. ALGORITHME DE PRIM Le principe de l’algorithme de Prim pour trouver un arbre de poids minimum dans un graphe G est de fusionner, deux par deux les noeuds de G pour obtenir finalement un arbre. Par fusionner, on entend remplacer deux noeuds par un seul. Tous les arcs adjacents à l’un ou l’autre des anciens noeuds deviennent adjacents au nouveau noeud. Le choix des noeuds que l’on fusionne est fait en choisissant au hasard un noeud et en cherchant un arc adjacent (autre qu’une boucle) qui a le coût le plus faible. Ce qui fournit le deuxième noeud de la fusion. Algorithme Titre: Prim Entrées: G = (X;U) un graphe. Sortie: U’ un ensemble d’arcs. Variables intermédiaires: x un noeud, u un arc. Début U’ ; tant que |U’| < n - 1 faire choisir x X; choisir u U | u = (x;y) ou u = (y;x) avec y x et coût(u) = min{coût(v) | v U avec v = (x;y) ou v = (y;x), x y}; U’ U’ {u}; fusionner x et y; [x et y deviennent un seul noeud.] fin tant que; Fin Justification
第 18 页
Informatique / Recherche operationnelle / Les arbres (French) 5 de 5 Tout d’abord, si on choisit un arc u = (x;y) où x et y sont des noeuds qui ne sont pas le résultat d’une fusion, on peut dire que le graphe résultant ({x,y};{u}) est un arbre de poids minimum. Maintenant, si on choisit un arc u = (x’;y’) où x’ et y’ sont des noeuds qui sont le résultat de fusions, la figure ci-dessous peut représenter la situation. En fait, x’ et y’ représentent des arbres de poids minimum (hypothèse de récurrence). Si u’ est l’arc entre x’ et y’ de poids minimum, le graphe ({a,b,c,d,e,f};{(a;c),(b;c),(d;f),(e;f),u}) sera un arbre de poids minimum. Donc à la dernière étape de l’algorithme, on obtiendra bien un arbre de poids minimum qui est un graphe partiel de G. Copyright (c) 1999-2001 - Bruno Bachelet - bachelet@ifrance.com - http://bruno.bachelet.net La permission est accordée de copier, distribuer et/ou modifier ce document sous les termes de la licence GNU Free Documentation License, Version 1.1 ou toute version ultérieure publiée par la fondation Free Software Foundation. Voir cette licence pour plus de détails (http://www.gnu.org).
第 19 页
Informatique / Recherche operationnelle / Representation (French) 1 de 3 3. REPRESENTATION DES GRAPHES MATRICE D'INCIDENCE NOEUD-ARC Un graphe peut être représenté par une matrice n x m (n = |X| et m = |U|), dite d’incidence, pouvant contenir uniquement les valeurs 0, 1, -1. Chaque ligne de la matrice est associée à un noeud et chaque colonne à un arc. Ainsi, une case indique la relation qu’il existe entre un noeud et un arc. 0 signifie que le noeud et l’arc ne sont pas adjacents, 1 signifie que le noeud est l’extrémité initiale de l’arc, -1 signifie que le noeud est l’extrémité terminale de l’arc. Exemple a b c d e f g h 1 1 1 0 0 0 0 0 0 2 -1 0 -1 1 0 0 0 0 3 0 -1 1 0 -1 0 -1 0 4 0 0 0 -1 1 1 0 -1 5 0 0 0 0 0 -1 1 1 Remarques Seulement 2m cases de la matrice sont non nulles sur mn cases. Cette représentation occupe beaucoup de place en mémoire. De plus, son utilisation apporte rarement de bons résultats au niveau des algorithmes. Notamment, pour parcourir le graphe, son emploi est difficile. Par contre, pour quelques problèmes comme le flot de coût minimum, cette matrice a
第 20 页
Informatique / Recherche operationnelle / Representation (French) 2 de 3 une signification directe importante et peut donc s’avérer utile. MATRICE D' ADJACENCE NOEUD-NOEUD Un graphe peut être représenté par une matrice n x n (n = |X|), dite d’adjacence, pouvant contenir uniquement les valeurs 0, 1. Chaque ligne et chaque colonne de la matrice représente un noeud. Ainsi, une case indique la relation qu’il existe entre deux noeuds. 0 signifie que les deux noeuds ne sont pas reliés par un arc, 1 signifie que les deux noeuds sont reliés par un arc orienté. Exemple Le graphe précédent sera représenté par la matrice suivante. 1 2 3 4 5 1 0 1 1 0 0 2 0 0 0 1 0 3 0 1 0 0 0 4 0 0 1 0 1 5 0 0 1 1 0 Remarques Seulement m cases de la matrices sont non nulles sur n2 cases. Cette représentation est efficace au niveau de l’espace mémoire utilisé lorsque le graphe est suffisamment dense (i.e. lorsqu’il y a suffisamment d’arcs). Elle permet d’implémenter assez facilement les algorithmes. Deux arcs ayant les mêmes extrémités ne peuvent pas être représentés avec cette matrice. LISTES Un graphe peut être représenté par des listes. Nous proposons ici une possibilité mais de nombreuses autres peuvent convenir. On définit tout d’abord une liste des noeuds et à chaque noeud, on associe une liste de noeuds successeurs et une liste de noeuds prédécesseurs. Exemple
评论 (0)
暂无评论。快来抢沙发吧！