ChronoMath, une chronologie des MATHÉMATIQUES
à l'usage des professeurs de mathématiques, des étudiants et des élèves des lycées & collèges

 Vocabulaire et notions élémentaires de la théorie des graphes

Initiée par Euler, avec le célèbre problème des 7 ponts de Königsberg, les applications de la théorie des graphes et de la recherche opérationnelle sont aujourd'hui immenses tant au plan civil que militaire  : aide à la décision, stratégie, optimisation (plus court chemin, GPS, coût minimal), réseaux de transports : chemins de fer, métropolitain, lignes aériennes, électricité, gaz, oléoducs (transport de l'énergie), Internet (réseau de l'information), ports et aéroports, ordonnancement des tâches, etc.

La théorie des graphes n'est pas une branche indépendante des mathématiques, elle se rattache à la programmation linéaire, la programmation convexe (où le concept plus général de fonction convexe remplace les fonctions linéaires et affines), la topologie, le calcul des probabilités. Depuis l'année 2002, une initiation à la théorie des graphes est donnée en classe Terminale ES dans son enseignement de spécialité.

Contemporains de Berge, R. Faure et A. Kaufmann en France, F. Harary, Ford Lester Randolph Jr. aux États-Unis, le polonais Kuratowski et le hongrois Erdös, sont également considérés comme les leaders du développement de la théorie des graphes et de ses applications au 20è siècle.

Sommets, ordre, arêtes, arcs, graphe orienté ou non  :       

Abstraitement, un graphe est la donnée d'un certain nombre de points du plan, appelés sommets, certains étant reliés par des segments de droites ou de courbes (simples) appelés arêtes, la disposition des sommets et la forme choisie pour les arêtes n'intervenant pas. Le nombre de sommets du graphe est son ordre. Si on nomme X l'ensemble des sommets et U l'ensemble des arêtes, un graphe G peut se noter G = (X, U).

Il s'agit donc ici de graphes plans mais tout ce qui suit peut s'appliquer à des graphes définis sur une sphère que l'on peut identifier à R2 par projection stéréographique. On ne confondra pas un graphe plan avec un graphe planaire.

Par courbe simple, on entend un tracé continu sans point double : notion introduite par Jordan. Des arêtes peuvent se croiser, un sommet n'étant pas indiqué à l'intersection. Mais cela peut être ambigu si le graphe a une allure "exotique" comme ci-dessous : à droite, l'arête DC coupe l'arête DE par deux fois et il ne s'agit pas d'en profiter pour filer vers E... Les deux graphes sont cependant licites et équivalents.

Avoir l'esprit tordu n'est pas nécessairement une tare, cependant cela peut entraîner des situations illicites : ci-dessous, l'arête DC possède deux points doubles : c'est illégal !

Si deux sommets consécutifs A et B sont reliés par une arête, on dira que l'on peut passer de A à B, à moins qu'un sens de parcours soit imposé. Dans ce cas, on parle de graphe orienté, les arêtes sont alors fléchées dans le sens de parcours autorisé et on parle d'arcs pouvant s'interpréter comme un couple (A,B) à distinguer de (B,A).

Graphe symétrique, graphe antisymétrique, graphe d'une relation binaire :    

Ci-contre, graphe 2, on peut parler de l'arête (A,B) mais pas de (B,A). Lorsque (A,B) U entraîne  (B,A) U, le graphe est dit symétrique. Un graphe non orienté s'interprète comme un graphe symétrique.

Lorsque (A,B) U entraîne  (B,A) U, le graphe est dit antisymétrique.

Dans un graphe défini comme étant orienté, on doit faire apparaître les sens de parcours sur chaque arête. Sauf indication contraire, un graphe sera considéré comme non orienté et les arêtes peuvent être parcourues dans les deux sens. Ce type de graphe peut se présenter dans des problèmes élémentaires de type combinatoire. La plupart des applications de cette théorie conduisent à des graphes orientés.

Arêtes et arcs doubles :       

Dans le cas d'un graphe orienté, le parcours entre deux sommets peut être à double sens. On pourrait coder ce double sens comme sur le graphe2b et  parler de l'arête AC, d'origine A, d'extrémité C en convenant de distinguer l'arc AC de l'arc CA (comme pour les couples ou les vecteurs) mais il est d'usage d'utiliser deux arcs afin d'éviter toute ambigüité.

Ce qui s'avère d'ailleurs indispensable par exemple dans le cas concret d'un trajet aller-retour sur deux routes différentes. Il peut aussi s'agir de débits aller-retour dans un pipe-line, etc.

Dans le dénombrement des arêtes d'un graphe conduisant à des conclusions sur la nature et les propriétés du graphe, le sens de parcours n'interviendra pas, sauf mention contraire explicite. Les deux arcs AC et CA représentées ci-dessus à droite sont comptabilisés comme une arête unique. Cependant, on peut également concevoir deux arcs distincts reliant deux sommets :

C'est le cas du problème des ponts de Königsberg, problème de cheminement posé par Euler en 1735, où il s'agit de distinguer les deux ponts reliant l'ile (secteur B) aux secteurs A et C de la ville. La question étant :

Partant d'un point de la ville, peut-on se promener, en revenant à son point de départ,
en passant une seule fois par tous les ponts ?

 

Vérifier que le graphe de la situation se résume à quatre sommets. Il est non orienté puisque le promeneur peut circuler dans les deux sens (ce qui pourrait ne pas être le cas aujourd'hui, en voiture, avec la présence de sens uniques...). Les secteurs A et C sont de degré 3 (correspondant à 3 ponts chacun), l'île B est de degré 5 (elle reçoit 5 ponts) et D de degré 3.

Réponse à ce problème, graphe eulérien :

Sommets adjacents, graphe complet, degré d'un sommet, chaîne, longueur, chemin :        

Deux sommets d'un graphe sont dits adjacents s'il existe une arête (ou un arc) qui les relie.

Un graphe est dit complet si deux quelconques de ses sommets sont adjacents.

Cela revient à dire que l'une au moins des deux proposition (A,B) U et (B,A) U est vraie.


Le degré d'un sommet est le nombre d'arêtes auxquelles il est relié.

Propriété 1:       

Dans un graphe non orienté, la somme des degrés des sommets est égale au double du nombre d'arêtes du graphe.

Une chaîne de longueur n est une suite ordonnée finie (liste) de n + 1 sommets adjacents (n est donc le nombre d'arêtes de la chaîne).

  Par contre BCA est une chaîne du graphe 5 ci-contre bien que les sens de parcours sur BC et AC soient en opposition.

On appelle chemin une chaîne dont les sens de parcours successifs ne présentent pas d'opposition. Sur le graphe 5, ACDEB est un chemin.

Distance, diamètre :       

On appelle distance entre deux sommets distincts la longueur de la plus courte chaîne qui les relie. La plus grande distance entre deux sommets est le diamètre du graphe.

Boucle, chaîne fermée, chaîne élémentaire, chaîne simple, cycle, circuit, arbre :

Dans des problèmes d'états transitoires (et/ou probabilistes) d'un système, deux sommets adjacents peuvent représenter deux états possibles du système à des instants différents. On peut envisager un état stationnaire pour signifier que le système conserve le même état : il "boucle". Afin de représenter cette situation sur un graphe, on utilise un arc circulaire (une boucle) dont l'origine et l'extrémité ont le même sommet. C'est le cas pour le sommet B du graphe 5.

Noter qu'une chaîne peut contenir plusieurs fois une même arête (ou un même arc) : comme ADEADC ou ADECDA dans le graphe 4.

On peut aussi donner un nom aux arêtes (pratique dans un problème concret où une arête s'apparente par exemple à une voie de communication, un flux, etc.). Ci-contre, cas du graphe 6, la chaîne AEDCB peut s'écrire a/e/d/c.

Une chaîne est dite fermée si son origine coïncide avec son extrémité.

Une chaîne est dite élémentaire (resp. simple) si aucun de ses sommets (resp. arcs) n'apparaît plus d'une fois.

On appelle cycle une chaîne fermée et simple (constituée d'arêtes distinctes). La chaîne a/e/d/c/b du graphe 6 est un cycle.

Un cycle peut rencontrer des arcs en opposition (sens de parcours opposé).

On appelle arbre un graphe orienté ne possédant aucun cycle. Un graphe possédant plusieurs arbres disjoints (graphe non connexe) prend le nom de forêts. Cette définition d'un arbre est celui connu des élèves de 1ères et terminales, relatif au calcul des probabilités, et permettant d'obtenir une représentation logique du problème rencontré.   graphe pondéré.

Bayes et probabilités conditionnelles :

On appelle circuit un cycle dont les sens de parcours successifs ne présentent pas d'opposition : chemin fermé et simple.

Les diagrammes sagittaux des relations binaires ne sont autres que des graphes. On peut le constater sur cet exemple (relation d'équivalence entre 4 points du plan). Les boucles sont la représentation de la réflexivité :

Rappelons encore ici que dans le dénombrement des arêtes d'un graphe conduisant à des conclusions sur la nature et les propriétés du graphe, le sens de parcours n'interviendra pas, sauf mention contraire explicite comme dans le cas des 7 ponts. Une boucle n'est ni une arête ni un arc.

Graphe eulérien ou chaîne eulérienne :

Ainsi baptisé en l'honneur de Euler car il se rattache au contre-exemple célèbre de la situation des 7 ponts de Königsberg (1735), il s'agit d'une chaîne contenant une fois et une seule toutes les arêtes du graphe (ou les arcs dans le cas orienté). Si la chaîne est un cycle (resp. circuit), on parlera de cycle (resp. circuit) eulérien. Euler établit alors ce résultat énoncé ici en termes actuels :

Propriété 2 :        

Un graphe connexe admet une chaîne eulérienne (resp. un cycle eulérien) si et seulement si
le nombre de sommets de degré impair est 0 ou 2 (resp. tous ses sommets sont de degré pair).


En utilisant la propriété P2, vérifier que l'on doit répondre par la négative au problème des 7 ponts.

Graphe hamiltonien ou chaîne hamiltonienne :

Ainsi baptisé en l'honneur de Hamilton, il s'agit d'un chemin d'un graphe orienté contenant une fois et une seule tous les sommets du graphe. Si la chaîne est un cycle (resp. circuit), on parlera de cycle (resp. circuit) hamiltonien (l'origine et l'extrémité sont alors considérés comme un seul sommet).

Posé en 1859, le problème est de trouver des conditions afin qu'un graphe orienté contienne un chemin hamiltonien. Par exemple : 

Théorème de Koenig-Redei :          

Tout graphe complet admet un chemin hamiltonien.

  Dénes König (ou Koenig, 1884-1944) et Laszlo Rédei (1900-1980) sont des mathématiciens hongrois issus de l'université de Budapest. Le premier obtint son doctorat (1907) portant sur les groupes de rotations dans des espaces multidimensionnels sous la direction de Minkowski. Cherchant à élucider le célèbre problème des 4 couleurs ( Cayley), il en vient à s'intéresser à la théorie des graphes qui deviendra l'objet principal de ses travaux. On lui doit en particulier Théorie des graphes finis et infinis (Theorie der endlichen und unendlichen Graphen, 1936). Le second s'intéressa principalement aux structures algébriques (semi-groupes) et à la théorie des corps de nombres.

   Chemin hamiltonien sur un polyèdre

Graphe connexe, sous-graphe, graphe partiel :

Un graphe est dit connexe (ou simplement connexe) si deux sommets quelconques et distincts du graphe admettent au moins une chaîne qui les relie (il n' y a pas de sommet isolé).

On parle également de connexité forte pour exprimer que par deux sommets quelconques il passe au moins un circuit.

Il peut être utile de distinguer certaines parties d'un graphe : on appelle sous-graphe d'un graphe G = (X,U) un graphe G' = (X',U') où X' est un sous-ensemble de X et U' l'ensemble de toutes les arêtes de U reliant les points de X', sommets de G'. On parle de graphe partiel lorsqu'un sous-graphe est privé d'un certain nombre d'arêtes.

Composantes connexes :

La relation binaire définie sur l'ensemble X des sommets d'un graphe G = (X,U) par :

A s B (A = B) ou (il existe une chaîne entre A et B)

est une relation d'équivalence (réflexive, symétrique et transitive). Les éléments de l'ensemble quotient X/s des classes d'équivalence sont les composantes simplement connexes de G. elles constituent une partition de X.

Il en est de même de la relation :

A f B (A = B) ou (il existe un circuit entre A et B)

dont les classes d'équivalence sont les composantes fortement connexes de G, constituant également. une partition de X.

Graphes planaires, face d'un graphe :

L'arc BD du graphe ci-contre rencontre l'arc AC. Cette intersection est virtuelle car à l'intersection, il n'y a pas de sommet indiqué. En quelque sorte l'arc BD passe au-dessus (ou au-dessous) de l'arc AC.

En déplaçant D, on obtient une représentation planaire (graphe obtenu ci-dessous) :

on qualifie ainsi un graphe pouvant être représenté dans le plan par changement de position : déplacement "élastique" éventuel d'un ou plusieurs sommets (on parle plus précisément, comme en topologie, d'homéomorphisme) de sorte que :


  rappelons ici encore que deux arcs orientés, comme AD et DA constituent une même arête !

Face d'un graphe :     

On appelle face d'un graphe G tout cycle de G de longueur au moins égale à 3 ne contenant en son intérieur aucun sommet et aucune arête. Par convention, le contour extérieur d'un graphe connexe planaire est considéré comme une face, dite face extérieure ou face infinie.

Théorème de Fary (1948) :      

Si un graphe s'avère planaire, il a été prouvé que les arêtes, qui peuvent être en zig-zags, en lignes brisées, etc. (courbes de Jordan), peuvent se réduire à des segments de droites. C'est en fait un résultat de topologie différentielle

  Istvan Fary, mathématicien hongrois, 1922-1984. On trouvera sur le site Numdam quelques publications en français de ce mathématicien


Vérifier par déplacement des sommets que le graphe ci-dessous, d'aspect "cubique", est planaire :


C'était trop facile ! Vérifier par déplacement des sommets que le graphe ci-dessous est planaire 


Ce graphe complet, noté K5, est-il planaire ? 

Vous l'avez sans doute compris ou prouvé, le graphe ci-dessus, n'est pas planaire. On le nomme K5, en l'honneur de Kuratowski. Un autre graphe non planaire fondamental, souvent appelé graphe des 3 villas ou graphe des 3 sources ou des 3 usines, est le graphe classé K3,3 :

Il s'agit concrètement d'alimenter trois villas A, B et C depuis, par exemple trois sources D, E et F sans que les conduites ne se croisent. L'expérience montre que l'on arrive à tracer 8 arcs non sécants mais jamais 9 comme il le faudrait...

Kuratowski et reconnaissance d'un graphe planaire :

Théorème :       

Le nombre chromatique de tout graphe planaire est au plus égal à 5
(et si on admet le théorème des 4 couleurs, ce nombre se réduit à 4)

On pourra prouver que K3,3 est non planaire de façon tout à fait similaire à celle donnée pour K5, en notant que dans ce cas, un graphe planaire candidat devra posséder au moins 4 arêtes. En effet si une face ne possède que 3 arêtes, deux d'entre elles seront soit des villas, soit des sources. Or la configuration exclut tout arc entre les villas et entre les sources.

   Chemin hamiltonien sur un polyèdre et graphe planaire

Formule d'Euler pour les graphes :

1/  Si un graphe planaire possède c composantes simplement connexes, s sommets, f faces et a arêtes, alors :

s - a + f = c + 1

où S, F et A désignent respectivement le nombre de sommets, de faces et d'arêtes.

2/  Si le graphe est simplement connexe (c = 1), on a la formule de Euler pour les graphes, semblable à celle pour les polyèdres convexes :

s - a + f = 2

  le nombre f tient ici compte de la face infinie, sinon, la formule s'écrit s - a + f = 1. On pourra s'exercer à vérifier la formule en considérant les nombreux graphes de cette "page".

Sous-graphe transitoire d'un graphe orienté :       

Dans le cas d'un graphe orienté, il existe des chemins tels qu'en "entrant" dans un graphe partiel, on ne puisse plus en sortir ! On obtient alors un sous-graphe transitoire :

Nombre chromatique d'un graphe :

Ce concept remonte à la célèbre conjecture de Guthrie (1852) relatif au coloriage des cartes géographiques à la Société Mathématique de Londres et rappelé en 1872 par Cayley : il suffirait de quatre couleurs pour que, quelle que soit la configuration géopolitique, deux pays ayant une frontière commune soient de couleurs différentes. Une carte s'identifie ici à un graphe G = (X,U) non orienté dont les diverses frontières communes des pays constituent les arêtes.

On appelle nombre chromatique d'un graphe le nombre minimal de couleurs à utiliser afin que chaque sommet du graphe soit colorié de sorte que deux sommets adjacents soient de couleurs différentes.

Propriété 3 :       

Le nombre chromatique d'un graphe complet est égal au nombre de ses sommets (c'est à dire l'ordre du graphe).

Propriété 4 :         

Si un graphe G contient un sous-graphe complet G', alors le nombre chromatique de G est au moins égal à l'ordre chromatique de G'.

Propriété 5 (très utile dans la pratique):         

Le nombre chromatique d'un graphe est au plus égal à k + 1, k désignant le plus haut degré des sommets.

  Une application du nombre chromatique (planning)

Matrice associée à un graphe non orienté :

Dans le cas d'un graphe non orienté G d'ordre n, dont les sommets sont ordonnés selon S1, S2, ..., Sn, on appelle matrice de G la matrice carrée M d'ordre n (n lignes, n colonnes) dont l'élément ai,j placé en i-ème ligne et j-ème colonne est égal au nombre d'arêtes reliant les sommets Si et Sj. La matrice M est symétrique (ai,j = aj,i) et que ses éléments diagonaux sont 0 ou 1 suivant que ai,i admet ou non une boucle.

La matrice dépend de l'ordonnancement choisi pour les sommets. Dans le cas ci-contre, en identifiant A à S1, B à S2, ..., D à S4, les ai,i sont nuls et :

Matrice associée à un graphe orienté :    

Dans ce cas, l'élément ai,j placé en i-ème ligne et j-ème colonne est égal au nombre d'arêtes reliant Si à Sj. La matrice M n'est généralement pas symétrique (une symétrie caractériserait des arcs doubles entre tout couple de sommets) et ne contient alors que des 0 ou des 1.

Là encore, la matrice dépend bien entendu de l'ordonnancement choisi pour les sommets. Dans le cas ci-contre, en identifiant A à S1, B à S2, ..., E à S5, les ai,i sont nuls sauf a2,2 = 1 (correspondant à la boucle en B); on a par exemple a1,2 = 0 (pas d'arc de A vers B),  mais a2,1 = 1 (arc de B vers A). On vérifiera que :

On remarquera, sachant qu'un graphe est orienté ou non, que la matrice d'un graphe caractérise ce graphe.


Représenter le graphe orienté défini par la matrice suivante :

         

Propriété 6 :         

Dans un graphe orienté de matrice M, l'élément ai,j (i-ème ligne, j-ème colonne)de la matrice Mn (puissance n-ème de M) est égal au nombre de chemins de longueur n reliant le sommet i au sommet j.


Dans le cas précédent, sans faire référence au graphe, donner le nombre de chemins de longueur 3 non triviaux (n'utilisant aucune boucle) reliant i/  A à C    ii/  B à D   iii/ C à C (circuits d'origine C). 

Graphe étiqueté (étiquettes), graphe pondéré (poids), graphe probabilisé (probabiliste) :    

Un graphe étiqueté est un graphe dont les arêtes ont reçu des attributs qualitatifs ou quantitatifs. Dans ce dernier cas, on parle aussi de poids et de graphe pondéré.

  à gauche, un graphe étiqueté à caractère qualitatif : les sommets sont des villes, les arêtes représentent des routes indiquées par leur nature et numéro (route nationale 73, route départementale 982, autoroute A9, etc.).

  à droite, un graphe étiqueté à caractère quantitatif : les étiquettes sont les vitesses maximales autorisées.

Flot, réseau, optimisation :

Matrice de transition (ou stochastique), chaîne de Markov, système ergodique :    

Un graphe peut servir à modéliser une situation probabiliste relative à un système (physique, économique, social) susceptible de passer au cours du temps par des états successifs (transitions) avec une certaine probabilité (par exemple, évolution d'une population, d'une épidémie, de la situation météorologique, de la nature chimique ou biologique d'un élément naturel, etc.). On parle de processus stochastique (du grec stokhastikos = divinatoire, aléatoire).

Les sommets du graphe représenteront les différents états possibles E1, E2, ..., Ek du système au cours du temps et les étiquettes sont les probabilités de passer d'un état à un autre : il s'agit donc d'un graphe orienté indiquant les probabilités sortantes.

On appelle matrice de transition du graphe (ou matrice stochastique), la matrice carrée dont les éléments pi,j (en ligne i, colonne j) sont les probabilités de passer de l'état Ei à l'état Ej, c'est à dire les probabilités conditionnelles pi,j = prob(Ej/Ei), probabilité de réalisation de Ej sachant Ei réalisé, également notées :

On suppose donc ici que les pi,j ne dépendent que des états possibles Ei et Ej définis au préalable et en aucune manière de l'évolution du système dans le temps : on parle alors de chaîne de Markov pour caractériser le modèle mathématique du système considéré.

Andreï A. Markov :

Considérons le cas élémentaire d'un système S pouvant prendre deux états E1 et E2 à différents instants successifs, l'état initial E0 étant apparu avec les probabilités po (état 1) et qo = 1 - po (état 2).

Le graphe correspondant est alors :

On peut dresser l'arbre des éventualités restreint aux dates initiale To et suivantes T1 et T2 :

La matrice de transition, indépendante des temps To + j (j = 1, 2, 3, ...) est alors ici, par définition :

Noter, et c'est bien normal, et cela sera vrai quelle que soit la dimension de la matrice, que la somme des probabilités de chaque ligne est égale à 1.

 
Vérifier que le carré de M est encore une matrice de transition, c'est à dire une matrice à termes positifs dont
la somme des éléments de chaque ligne est égale à 1. Ce cas se généralise : matrice de Markov

Les probabilités p1 et q1 d'obtenir respectivement les états E1 et E2 à l'issue de la transition 1 se calculent sur l'arbre par les produits  :

c'est à dire par le produit de la matrice  ligne (po,qo) par la matrice de transition :

Les probabilités p2 et q2 d'obtenir respectivement les états E1 et E2 à l'issue de la transition 2 se calculeraient sur l'arbre de la même manière avec p1 et q1 remplaçant po et qo. On en déduit matriciellement :

Notons plus généralement Pn la matrice ligne (pn  qn) fournissant les probabilités des états E1 et E2 à l'issue de la transition n avec Po correspondant à l'état initial :  Po = (po  qo). On a alors :

Ce résultat se généralise à un système soumis à un nombre quelconque k d'états transitoires. Voici un exemple avec k = 3, extrait d'un sujet de baccalauréat français, série ES :

   Graphe probabiliste et matrice de transition               Sujet complet : Bac ES, 2006, Centres étrangers
 

Notion de système ergodique :       

On peut se demander si la suite des matrices lignes admet une limite lorsque n devient infini (le nombre d'états s'avérant infini dénombrable). Si tel est le cas, cela signifie que chaque élément ai,j(n) de la matrice Mn admet une limite finie et si l'on note A la matrice obtenue à la limite, la matrice ligne Pn des états du système converge vers un état permanent P vérifiant P = PoAn.

Un cas particulier important est celui où les lignes de A sont identiques :  le système limite P est alors indépendant de Po. En effet, en dimension 2 comme ci-dessus, on aurait alors un résultat de la forme :

On dit alors que le système est ergodique.

Notion générale d'ergodicité :                           Exemple simple de système ergodique en génétique

Flot, réseau de transport, optimisation, flot maximum :    

On appelle réseau un graphe pondéré orienté possédant un nombre fini d'arcs et deux sommets E (entrée) et S (sortie) tels que E (resp. S) n'admet aucun arc entrant (resp. sortant). Chaque étiquette d'un arc est appelée capacité (maximale) ou de l'arc. Lorsqu'il s'agit de modéliser des capacités de transport comme maritime, fluvial, aérien, routier, énergétique (électricité, gaz, pétrole), etc., on parle de réseau de transport.

Soit plus précisément un réseau d'entrée E, de sortie S. Les capacités ci,j sont les étiquettes des arcs orientés reliant les ports de départ et d'arrivée. On appelle flot (ou flux) et on note ici fi,j la fraction de ci,j effectivement utilisée sur l'arc AiAj.

Si R et S sont des aéroports de départ et d'arrivée, on ne peut, par jour, ni faire décoller ni accueillir autant d'avions que souhaité. Par conséquent, les capacités au départ (E) et à l'arrivée (S) sont limitées. En notant e1, e2, ..., en et s1, s2, ..., sm ces capacités, on sera à la recherche de flots fi,j tels que le flot total :

soit maximum, sous les contraintes :

Dans les années 1960, de nombreux mathématiciens élaborent, dans le cadre de la recherche opérationnelle, étroitement liée à la théorie des graphes, des algorithmes d'optimisation :

Concernant ces algorithmes et leur programmation, on pourra consulter l'article Le plus court chemin, sur le site Interstices de l'INRIA/CNRS.

Algorithme de Dijkstra (au programme de la classe Terminale ES) :

Pour en savoir plus :

© Serge Mehl - www.chronomath.com