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       » Pour rechercher une notion relative aux graphes, taper Ctrl F puis son nom.

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.

 ➔   Dans toute la suite, il s'agira de graphes plans, mais tout ce qui suit peut s'appliquer à des graphes définis sur une sphère que l'on peut, par projection stéréographique, identifier à R². On ne confondra pas un graphe plan avec un graphe planaire.

Abstraitement, un graphe est la donnée d'un certain nombre de points du plan, appelés nœuds ou 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).

 ➔  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 !

Graphe orienté ou non, arc d'un graphe, :   

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).   » nommer une arête, un arc, une chaîne.

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

Ci-dessous, 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 la théorie graphes, (problèmes d'optimisation, communications, trafics aériens, ...) 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é à l'instar du graphe 2c ci-dessus. 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 illustré ci-dessus. 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...).

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

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 propositions (A,B)∈U et (B,A) ∈U est vraie.

• Les graphes 1, 3 et 4  ne sont pas complets. Les graphes 2 et 4a sont complets.

Le degré d'un sommet est le nombre d'arêtes auxquelles il est relié (on parle d'arêtes incidentes à ce sommet).

• Dans le graphe 1, A est de degré 2, B et C sont de degré 1. Dans le graphe 2, tous les sommets sont de degré 2. Dans le graphe 4, E est de degré 4.

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).

• BAC est une chaîne du graphe1 de longueur 2, d'origine B, d'extrémité C. Mais BCA n'est pas une chaîne.

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.

Nommer une arête, une chaîne, un arc :   

Pour décrire une chaîne, comme ci-dessus, le chemin ACDEB, on convient de respecter l'ordre du cheminement. Il est d'usage de 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.) distinguant (A,B)∈U et (B,A)∈U tout comme en théorie des ensembles où l'on distingue le couple d'éléments (A,B) ≠ (B,A) tenant compte de l'ordre et la paire d'éléments {A,B} = {B,A} n'en tenant pas compte.  » nommer au moyen des faces

• Ci-contre, l'arête b s'identifie à (A,B) mais (B,A) ∉ U.

• (A,D)∈U et (D,A)∈U : en écrivant  α = {A,D} on signifie ce double sens de parcours.

• On a β = (A,B)

Donner un nom aux arêtes permet de nommer facilement une chaîne tenant compte de l'ordre de cheminement et en séparant les noms des arêtes par des slashs (/) :

• La chaîne AEDCB du graphe 6 s'écrit a/e/d/c/b.

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.

• Dans le graphe 5, la distance entre A et E est 2. Le diamètre est 4.  

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 dont l'origine et l'extrémité ont le même sommet : une boucle est un arête incidente deux fois à un même sommet. C'est le cas au sommet B du graphe 5 ci-dessus. On nommerait indifféremment (B,B) ou {B,B} une telle boucle.

• 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 :

♦ Un graphe est dit simple lorsqu'il n'admet aucune boucle et qu'entre deux quelconques de ses sommets il existe au plus une arête. Dans le cas contraire, on parle de multigraphe.

• le graphe 5 est un multigraphe. Il en est de même de celui des ponts de Königsberg.

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

• ADCBA est une chaîne fermée du graphe 4.  

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

• Dans le cas du graphe 4, BECDEA est une chaîne simple non élémentaire.

♦ On appelle cycle une chaîne fermée et simple (donc constituée d'arêtes distinctes).

•  La chaîne a/e/d/c/b/a du graphe 6 est un cycle.

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

• C'est par exemple le cas du cycle e/a/d/c/b/a du graphe 6.

♦ 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é.

Thomas 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 en chaque sommet 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.

Ainsi baptisé en l'honneur de Euler, une chaîne eulérienne 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 eulérien (resp. circuit eulérien). Euler établit alors ce résultat énoncé ici en ces termes :

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).

On parle de graphe eulérien pour exprimer un graphe admettant au moins un cycle eulérien.

∗∗∗
En utilisant la propriété P2, vérifier que l'on doit répondre par la négative au problème des 7 ponts.
Les secteurs A et C sont de degré 3 (correspondant à l'incidence de 3 ponts chacun), l'île B est de degré 5 (elle reçoit 5 ponts) et D de degré 3.

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.

 i   Dénes König (ou Koenig, 1884-1944) : mathématicien hongrois issu de l'université de Budapest. Il 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 vint à 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). Source : Wikipedia.hu.

 i  Laszlo Rédei (1900-1980) : mathématicien hongrois qui étudia à Debrecen et compléta ses études à Göttingen avant d'obtenir un poste à l'université de Szeged (1941). Il s'intéressa principalement aux structures algébriques (semi-groupes) et à la théorie des corps de nombres. Source : Wikipedia.hu.

• Dans ce graphe complet d'ordre 4 ci-dessous, le chemin BACD est hamiltonien : tous les sommets ont été rencontrés en parcourant 4 arêtes (sur 6). CDBAC est un circuit hamiltonien.

• Dans ce graphe, non complet d'ordre 5 ci-dessous, le chemin ADEBC est hamiltonien : tous les sommets ont été rencontrés en parcourant 4 arêtes (sur 8).

∗∗∗  Chemin hamiltonien sur un polyèdre

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 C_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/C_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 C_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.

• Le graphe ci-dessous possède 3 composantes simplement connexes : H = {H} (classe réduite à H), E = {E,J} et A = {A,B,C,D,F}. Hormis E = {E,J} et B = {B,C,F}, ses composantes fortement connexes sont triviales :  H = {H},  D = {D},  A = {A}

 

Graphes planaires, face d'un graphe :

L'arc BD de ce 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 (obtenue ci-dessous). On pouvait aussi étirer l'arc BD en passant "sous la boucle située en C.

Graphe planaire :  

on qualifie de planaire un graphe pouvant être représenté dans le plan par changement de position des sommets ou étirement/rétractation des arêtes (on parle plus précisément, comme en topologie, d'homéomorphisme) de sorte que :

1. les sommets apparaissent distincts;

2. les arêtes sont des courbes simples (pas de point double ou multiple);

3. les arêtes ne se rencontrent qu'en leurs extrémités.

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

On comprend ici, tout comme en théorie des nœuds, qu'un graphe peut avoir de multiples représentations : deux graphes apparemment distincts peuvent être équivalents, en ce sens qu'ils sont solutions d'un même problème.

Théorème de Fary (1948) :      

Les arêtes d'un graphe qui peuvent être en arcs, en zig-zags, en lignes brisées, etc. (courbes de Jordan). En utilisant les moyens sophistiqués de la topologie différentielle, le mathématicien hongrois Istvan Fary a prouvé le résultat suivant (» preuve en réf. 15) :

Tout graphe planaire admet une représentation telle que toutes ses arêtes soient rectilignes (segments de droites).

 i  Istvan Fary, mathématicien hongrois, 1922-1984. Professeur à l'université de Californie (Berkeley), il fut un spécialiste en géométrie algébrique et topologie algébrique. Par là, il s'illustra également en théorie des nœuds. On trouvera sur le site Numdam (» réf. 13b) quelques publications en français de ce mathématicien.

» Jones Milnor 

♦ Face d'un graphe :     

Tout comme pour un polyèdre, 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 (au sens de non limitée).

• Le graphe ci-dessous possède 4 faces finies : ADE, EDF, EFA et ABCF. ADF n'en est pas une. Ce graphe connexe contient donc 5 faces si on lui adjoint sa face extérieure.

Nommer une arête au moyen des faces :    

On peut donner un nom aux faces d'un graphe permettant une nouvelle façon de caractériser une arête lorsque celle-ci n'est pas une boucle. Elle est alors adjacente à 2 faces. Ci-dessus, par exemple, on a appelé F4 la face ADE et Φ la face extérieure du graphe 7. L'arête a = AD est adjacente à Φ et F4 : on peut noter, sans ambiguïté : a = {Φ,F4}. On utilise les accolades car {Φ,F4} = {F4,Φ}.

∗∗∗
Vérifier que le graphe ci-dessous, d'aspect "cubique", est planaire :

Si votre navigateur accepte les applets Java (» extension CheerpJ) :
Vérifier par déplacement des sommets que le graphe ci-dessus est planaire

Si votre navigateur accepte les applets Java (» extension CheerpJ) :
Vérifier par déplacement des sommets que le graphe ci-dessus est 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...

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.

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

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

2/  Lorsque c = 1, on a la formule de Euler pour les graphes, semblable à celle pour les polyèdres convexes :

 !  le nombre f tient ici compte de la face extérieure (également dite 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".

La formule d'Euler pour les polyèdres s'applique au cas des graphes planaires :

• Le graphe ci-dessus présente 6 sommets, 5 faces et 9 arêtes et : 6 + 5 - 9 = 2.

Selon Euler, il y a entre le nombre s de sommets, le nombre f de faces et le nombre a d'arêtes, la relation s - a + f = 2. À un polyèdre régulier (P) de F faces et S sommets, il s'agit alors d'associer, avec le même nombre d'arêtes, un polyèdre régulier de s faces et f sommets, appelé dual de (P). Si d'un sommet part a arêtes, chaque face du dual possédera a côtés.

A la manière du dual d'un polyèdre, on construit le dual G* d'un graphe planaire G de la façon suivante :

• Les sommets de G* sont les faces de G identifiées à un point intérieur à celles-ci qualifié de "centre".
• Les arêtes s'obtiennent en joignant les "centres" des faces de G ayant une arête commune (faces adjacentes).

 ➔   On remarquera que, de par sa définition et construction, le dual d'un graphe planaire est planaire.

Cellules de Voronoï  et triangulation de Delaunay (Boris Delone) : » 

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 :

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 d'au plus 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 planaire 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.

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

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'.

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

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

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

La matrice dépend de l'ordonnancement choisi pour les sommets.

• Dans le cas ci-dessous, en identifiant A à S₁, B à S₂, ..., D à S₄, les a_i,i sont nuls et :

Dans ce cas, l'élément a_i,j placé en i-ème ligne et j-ème colonne est égal au nombre d'arêtes reliant S_i à S_j. 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 à S₁, B à S₂, ..., E à S₅, les a_i,i sont nuls sauf a_2,2 = 1 (correspondant à la boucle en B); on a par exemple a_1,2 = 0 (pas d'arc de A vers B),  mais a_2,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.

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

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é.

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 E₁, E₂, ..., E_k 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 p_i,j (en ligne i, colonne j) sont les probabilités de passer de l'état E_i à l'état E_j, c'est à dire les probabilités conditionnelles p_i,j = prob(E_j/E_i), probabilité de réalisation de E_j sachant E_i réalisé, également notées :

 ➔  On suppose donc ici que les p_i,j ne dépendent que des états possibles E_i et E_j 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 E₁ et E₂ à différents instants successifs, l'état initial E0 étant apparu avec les probabilités p_o (état 1) et q_o = 1 - p_o (état 2).

• p_1,1 = prob(E₁/E₁) est la probabilité que S étant à l'état 1, il conserve cet état.

• p_2,1 = prob(E₂/E₁) est la probabilité que S étant à l'état 1, il passe à l'état 2.

• p_1,2 = prob(E₁/E₂) est la probabilité que S étant à l'état 2 , il passe à l'état 1.

• p_2,2 = prob(E₂/E₂) est la probabilité que S étant à l'état 2, il conserve cet état.

Le graphe correspondant est alors :

On peut dresser l'arbre des éventualités restreint aux dates initiale T_o et suivantes T₁ et T₂ :

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 p₁ et q₁ d'obtenir respectivement les états E₁ et E₂ à l'issue de la transition 1 se calculent sur l'arbre par les produits  :

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

Les probabilités p₂ et q₂ d'obtenir respectivement les états E₁ et E₂ à l'issue de la transition 2 se calculeraient sur l'arbre de la même manière avec p₁ et q₁ remplaçant p_o et q_o. On en déduit matriciellement :

Notons plus généralement P_n la matrice ligne (p_n  q_n) fournissant les probabilités des états E₁ et E₂ à l'issue de la transition n avec P_o correspondant à l'état initial :  P_o = (p_o  q_o). On a alors :

Ce résultat se généralise à un système soumis à un nombre quelconque k d'états transitoires.

∗∗∗
Graphe probabiliste et matrice de transition (k = 3, Bac ES 2006 Centres étrangers)
Sur le site panamaths : Graphe probabiliste et matrice de transition (k = 2, Bac ES 2006 Pondichéry)
Voir aussi : Graphe probabiliste et matrice de transition (k = 2, Bac ES 2012 Amérique du nord)

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 a_i,j(n) de la matrice Mⁿ admet une limite finie et si l'on note A la matrice obtenue à la limite, la matrice ligne P_n des états du système converge vers un état permanent P vérifiant P = P_o × Aⁿ.

Un cas particulier important est celui où les lignes de A sont identiques :  le système limite P est alors indépendant de P_o. 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

On appelle réseau un graphe pondéré orienté composé d'un nombre fini d'arcs et de deux sommets E (entrée) et S (sortie), E (resp. S) n'admettant 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 c_i,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 f_i,j la fraction de c_i,j effectivement utilisée sur l'arc A_iA_j.

• Exemple : si une ligne aérienne ne peut tolérer simultanément, par sécurité, que c_i,j = 4 avions,  le flot à un instant donné peut être f_i,j = 3 ≤ c_i,j.

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 e₁, e₂, ..., e_n et s₁, s₂, ..., s_m ces capacités, on sera à la recherche de flots f_i,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 comme celui de Dijkstra :

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

 ➔  Concernant d'autres méthodes (Ford & Fulkerson, Bellmann-Kalaba), on pourra consulter en particulier la réf.5, l'article Le plus court chemin, sur le site Interstices de l'INRIA/CNRS (ref.6) et l'incontournable Programmes, jeux et réseaux de transport (ref.10) de Claude Berge et Alain Ghouila-Houri (jeune mathématicien français, 1939-1966, polytechnicien, docteur ès Sciences, décédé prématurément à 27 ans).  

On appelle graphe adjoint (noté ici G*) d'un graphe non orienté G le graphe ainsi obtenu :

• Chaque arête de G est assimilé à un sommet de G* : il y a autant de sommets de G* que d'arêtes de G.
• Deux sommets de G* sont adjacents s'ils proviennent d'arêtes de G ayant un sommet en commun.

Un graphe G, à gauche et son adjoint G*, à droite

Les graphes adjoints se rencontrent dans les problèmes d'optimisation de réseaux de communication.

Pour le besoin de certaines applications, en chimie par exemple dans l'étude des polymères, il est envisagé des graphes dont le nombre de sommets est illimité. Par exemple :

- Graphe carré -

ou encore :

- Graphe hexagonal (nid-d'abeilles) -

1. Niveau élémentaire : Tout manuel de Terminale ES.

2. Graphes pour la Terminale ES (Groupe IREM Luminy, octobre 2002) :
   a) http://www.irem.univ-mrs.fr/IMG/pdf/graphes_1_.pdf, ou bien :
   b) https://www.math.u-psud.fr/~thomine/fr/archives/Enseignement1718/CAPES/PolycopieArnoux.pdf

3. Accompagnement des programmes Ter ES : http://media.education.gouv.fr/file/Programmes/16/8/graphes_109168.pdf
   Si la page a (encore) changé d'adresse, téléchargez-le ici.

4. Introduction à la théorie des graphes, par Éric Sigward (univ. Paris-sud), prépa au CAPES :
   https://www.math.u-psud.fr/~thomine/fr/archives/Enseignement1718/CAPES/PolycopieSigward.pdf

5. Théorie des graphes à l'intention des enseignants, par Géraldine Morin, INPT Toulouse :
   http://morin.perso.enseeiht.fr/DocumentsPDF/Graphes/polyEnseignants.pdf

6. Algorithmes de Ford & Fulkerson, de Bellmann-Kalaba, et de Dijkstra : Le plus court chemin, sur le site Interstices de l'INRIA/CNRS.

7. Sur le site Apprendre en ligne, un cours très complet de Didier Müller (Suisse) : http://www.apprendre-en-ligne.net/graphes/index.html.

8. Introduction à la théorie des graphes : http://www.labri.fr/perso/courcell/Conferences/GraphesX.pdf

9. Des points et des flèches... la théorie des graphes, A. Kaufmann, Éd. Dunod Science-poche - 1968

10. Programmes jeux, réseaux, transport, C. Berge , A. Ghouila-Houri, Ed. Dunod, Paris - 1962.

11. Algèbre moderne et théorie des graphes, B. Roy, Ed. Dunod, Paris - 1969.

12. Théorie des graphes et applications avec exercices et problèmes, par J.-C. Fournier, Éd. Hermès - 2006

13. La Théorie des graphes par Aimé Sache - Que sais-je n°1554 -P.U.F. Paris - 1974

14. Quelque publications de Istvan Fary numérisées sur Numdam : http://www.numdam.org/search/Istvan Fary-a

15. Graphes planaires, dont le théorème de Fary, par Théophile trunck (ENS Lyon) :
    http://perso.ens-lyon.fr/eric.thierry/Graphes2009/theophile-trunck.pdf