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 à R2. On ne confondra pas un graphe plan avec un graphe planaire.

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

Sommets adjacents, arêtes incidentes, 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 propositions (A,B)∈U et (B,A) ∈U est vraie.

     

 

 


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

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

On appelle chemin une chaîne dont les sens de parcours successifs ne présentent pas d'opposition.

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

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 (/) :

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, graphe simple, multigraphe, chaîne fermée, élémentaire ou 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 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.

         

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.

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 (donc constituée d'arêtes distinctes).

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

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.

Chaîne eulérienne, cycle eulérien, circuit eulérien, graphe eulérien :

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.

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.

 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.

  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 Cs (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/Cs 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 Cf (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 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).

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


C'était trop facile ! Vérifier que le graphe ci-dessous 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


Le graphe complet ci-dessous, dit K5, est-il 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.

Kuratowski et reconnaissance d'un 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/  Lorsque 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 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 :

  
Chemin hamiltonien sur un polyèdre et graphe planaire

Dual d'un graphe planaire :

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 :

    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) : » 

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

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)

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

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

    

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

        

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.


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 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 = Po × An.

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

Graphe adjoint :    

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


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.

Graphes infinis :    

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


   Pour en savoir plus :

  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


© Serge Mehl - www.chronomath.com