![\"K\u00f6nigsberg](\"https:\/\/www.mathweb.fr\/euclide\/wp-content\/uploads\/2020\/07\/Konigsberg_bridges.png\")
Ce probl\u00e8me consistait \u00e0 \u00ab\u00a0trouver une promenade \u00e0 partir d’un point donn\u00e9 qui fasse revenir \u00e0 ce point en passant une fois et une seule par chacun des sept ponts de la ville de K\u00f6nigsberg\u00a0\u00bb (source : https:\/\/fr.wikipedia.org\/wiki\/Th%C3%A9orie_des_graphes<\/a>).<\/p>\n\n\n\n Par la suite, toujours au XVIII\u00e8me si\u00e8cle, le math\u00e9maticien fran\u00e7ais Alexandre-Th\u00e9ophile Vandermonde se pencha sur le probl\u00e8me du cavalier devant visiter toutes les cases d’un \u00e9chiquier, probl\u00e8me r\u00e9soluble \u00e0 l’aide de la th\u00e9orie des graphes.<\/p>\n\n\n\n Un graphe<\/em> est un couple \\(\\mathcal{G} = ( V ; E )\\), o\u00f9 V<\/em> est un ensemble fini d’\u00e9l\u00e9ments, appel\u00e9s les sommets<\/em> du graphe (\u00ab\u00a0V<\/em>\u00a0\u00bb comme vertex<\/em>, autrement dit sommets<\/em>) et E<\/em> l’ensemble des connexions entre les sommets, que l’on nomme aussi les ar\u00eates<\/em> du graphe (\u00ab\u00a0E<\/em>\u00a0\u00bb comme edges<\/em>, dans le sens de ar\u00eates<\/em>).<\/p>\n\n\n\n Par exemple, $$\\mathcal{G} = ( \\{ A; B;C\\} ; \\{(A,B);(A,C);(B,C) \\} )$$ peut d\u00e9signer le graphe ayant trois sommets : A<\/em>, B<\/em> et C<\/em>, o\u00f9 A<\/em> et B<\/em>, A<\/em> et C<\/em> ainsi que B<\/em> et C<\/em> sont reli\u00e9s.<\/p>\n\n\n\n Les graphes servent \u00e0 repr\u00e9senter des situations diverses. Cela peut \u00eatre des:<\/p>\n\n\n\n Vous l’aurez peut-\u00eatre compris, dans certaines situations, deux sommets peuvent \u00eatre reli\u00e9s par une ar\u00eate avec ou sans orientation. Le simple fait de donner le couple \\(\\mathcal{G} = ( V ; E )\\) peut donc \u00eatre ambigu\u00eb, d’o\u00f9 la n\u00e9cessit\u00e9 d’introduire une repr\u00e9sentation graphique.<\/p>\n\n\n\n On nomme donc repr\u00e9sentation sagittale<\/em> la repr\u00e9sentation graphique d’un graphe; quand les ar\u00eates doivent avoir une orientation, on parlera de graphes orient\u00e9s<\/em>. Dans ce cas, on parlera plut\u00f4t d’arcs<\/em> et non d’ar\u00eates.<\/p>\n\n\n\n Mais il arrive aussi que l’on doive attribuer \u00e0 certaines arr\u00eates une pond\u00e9ration (un nombre). Par exemple, une probabilit\u00e9 (quand il s’agit de passer d’un \u00e9tat \u00e0 un autre), une distance ou encore un temps (quand les ar\u00eates repr\u00e9sentent une connexion entre deux lieux g\u00e9ographiques par exemple). On parle alors de graphes pond\u00e9r\u00e9s<\/em> ou de graphes probabilistes<\/em>.<\/p>\n\n\n\n Les pond\u00e9rations, les nombres qu’il y a sur chaque arc, peuvent repr\u00e9senter des:<\/p>\n\n\n\n Quel que soit le type de graphe, qu’il soit orient\u00e9 ou pas, pond\u00e9r\u00e9 ou non, il admet toujours une repr\u00e9sentation matricielle<\/em>.<\/p>\n\n\n\n Une matrice <\/em>est un tableau de nombres, repr\u00e9sent\u00e9 entre parenth\u00e8ses et sans trait de d\u00e9limitation. Quand une matrice repr\u00e9sente une graphe, chaque ligne et colonne repr\u00e9sente un sommet. La matrice est alors appel\u00e9e matrice d’adjacence <\/em>du graphe.<\/p>\n\n\n\n Par exemple, le graphe suivant:<\/p>\n\n\n\n admet pour matrice d’adjacence:<\/p>\n\n\n\n Quand deux sommets i<\/em> et j<\/em> sont reli\u00e9s par une ar\u00eates, on met un \u00ab\u00a01\u00a0\u00bb \u00e0 l’intersection de la ligne i<\/em> et de la colonne j<\/em>. Dans le cas contraire, on met un \u00ab\u00a00\u00a0\u00bb.<\/p>\n\n\n\n Remarquez que quand le graphe est non orient\u00e9, la matrice est sym\u00e9trique (par rapport \u00e0 la diagonale principale, celle qui part du haut \u00e0 gauche et qui va en bas \u00e0 droite, diagonale qui ne comporte que des \u00ab\u00a00\u00a0\u00bb).<\/p>\n\n\n\n La matrice du graphe suivant:<\/p>\n\n\n\n est:<\/p>\n\n\n\n Ici, le sens (l’orientation des arcs) \u00e0 une importance; il est donc normal que la matrice ne soit plus sym\u00e9trique par rapport \u00e0 la diagonale principale.<\/p>\n\n\n\n Quand il s’agit de graphes pond\u00e9r\u00e9s, on ne met plus uniquement de \u00ab\u00a00\u00a0\u00bb et de \u00ab\u00a01\u00a0\u00bb, mais on y met les pond\u00e9rations. Le graphe suivant:<\/p>\n\n\n\n admet alors pour matrice d’adjacence:<\/p>\n\n\n\n Pour le graphe suivant:<\/p>\n\n\n\n sa matrice d’adjacence est:<\/p>\n\n\n\n Ici, la somme des coefficients de chaque ligne doit valoir \u00ab\u00a01\u00a0\u00bb (somme des probabilit\u00e9s \u00ab\u00a0partantes\u00a0\u00bb d’un sommet).<\/p>\n\n\n\n Un labyrinthe peut \u00eatre vu comme un plateau d\u00e9compos\u00e9 en cases avec quelques traits de s\u00e9paration. Dans ce cas, le labyrinthe peut \u00eatre repr\u00e9sent\u00e9 par un graphe o\u00f9 chaque sommet repr\u00e9sente une case du \u00ab\u00a0tableau\u00a0\u00bb et o\u00f9 chaque ar\u00eate repr\u00e9sente le fait que l’on peut passer d’une case \u00e0 l’autre car il n’y a pas de mur qui l’en emp\u00eache.<\/p>\n\n\n\n C’est d’ailleurs ainsi que j’ai programm\u00e9 mon logiciel pour construire des labyrinthe (voir cette page<\/a>).<\/p>\n\n\n\n Supposons que la matrice suivante repr\u00e9sente des changements d’\u00e9tats:<\/p>\n\n\n\n On peut par exemple imaginer que A, B et C sont respectivement les \u00e9tats:<\/p>\n\n\n\n d’un individu. Supposons alors cet cet individu soit initialement fatigu\u00e9 (\u00e9tat A). On nomme alors:$$E_0=\\begin{pmatrix}1 &0&0\\end{pmatrix}$$ la repr\u00e9sentation matricielle de cet \u00e9tat initial. <\/p>\n\n\n\n Supposons maintenant qu’une observation de l’\u00e9tat soit faite toute les heures. Alors, si \\(M\\) est la matrice d’adjacence du graphe, l’\u00e9tat probabiliste au bout d’une heure est donn\u00e9 par:$$E_1 = E_0 \\times M = \\begin{pmatrix}0,4 & 0,1 & 0,5 \\end{pmatrix}.$$Une heure apr\u00e8s, on se retrouve avec un \u00e9tat repr\u00e9sent\u00e9 par:$$E_2 = E_1 \\times M = E_0 \\times M^2 = \\begin{pmatrix}0,23 & 0,26 & 0,51\\end{pmatrix}.$$Ainsi, si l’on veut savoir l’\u00e9tat \u00e0 tr\u00e8s long terme, on calcule:$$E_\\infty = E_0 \\times M^\\infty \\approx \\begin{pmatrix}0,3 & 0,26 & 0,44\\end{pmatrix}.$$Cet \u00e9tat nous donne les probabilit\u00e9s d’\u00eatre dans les \u00e9tats A<\/em>, B<\/em> et C<\/em>. Ici, \u00e0 long terme, on a par exemple 3 chances sur 10 d’\u00eatre dans l’\u00e9tat A<\/em>.<\/p>\n\n\n\n Quand le graphe est pond\u00e9r\u00e9 et que les pond\u00e9rations repr\u00e9sentent non plus des probabilit\u00e9s mais des nombres (comme des distances ou du temps), la matrice d’adjacence peut nous permettre de trouver le plus court chemin pour relier deux sommets, c’est-\u00e0-dire le chemin dont la somme des pond\u00e9rations est minimal. Un algorithme connu est celui de Dijkstra<\/em>. C’est d’ailleurs cet algorithme qui est utilis\u00e9 par les routeurs pour trouver le chemin le plus rapide, donc qui n\u00e9cessite le moins de temps de transmission.<\/p>\n\n\n\n Vous comprendrez donc que les matrices d’adjacence permettent de voir de fa\u00e7on abstraite des graphes et donc de les impl\u00e9menter dans un programme informatique.<\/p>\n\n\n\n Les graphes peuvent \u00eatre impl\u00e9ment\u00e9s en Python de plusieurs fa\u00e7on. J’en ai choisi deux.<\/p>\n\n\n\n Une approche na\u00efve serait de consid\u00e9rer un graphe comme un dictionnaire, o\u00f9 les cl\u00e9s sont les sommets et les valeurs, les sommets reli\u00e9s aux cl\u00e9s. Cela donnerait par exemple:<\/p>\n\n\n\n qui repr\u00e9sente le graphe:<\/p>\n\n\n\n Pour les graphes pond\u00e9r\u00e9s, on peut imaginer quelque chose qui ressemble \u00e0 \u00e7a:<\/p>\n\n\n\n qui repr\u00e9sente le graphe:<\/p>\n\n\n\n Ce genre d’impl\u00e9mentation est nomm\u00e9e impl\u00e9mentation par liste d’adjacence<\/em> de graphes en Python.<\/p>\n\n\n\n Une autre fa\u00e7on d’impl\u00e9menter des graphes en Python est d’utiliser leur matrice d’adjacence. Ainsi, pour le premier graphe, on aura:<\/p>\n\n\n\n L’inconv\u00e9nient d’une telle impl\u00e9mentation r\u00e9side dans l’espace m\u00e9moire d\u00e9di\u00e9 au graphe. En effet, pour un graphe \u00e0 n<\/em> sommets, il faut une matrice avec n<\/em>\u00b2 nombres\u2026 et la plupart du temps, il y a beaucoup de \u00ab\u00a00\u00a0\u00bb (on parle de matrices creuses<\/em>), ce qui est ballot non ?<\/p>\n\n\n\n Dans ce cas, l’impl\u00e9mentation par liste d’adjacence est bien mieux car n\u00e9cessite moins d’espace m\u00e9moire.<\/p>\n\n\n\n Un graphe n’est autre qu’une repr\u00e9sentation d’une situation; c’est donc un objet abstrait\u2026 Et en informatique, il existe un paradigme de programmation permettant d’impl\u00e9menter de telles notions : la Programmation Orient\u00e9e Objet<\/em> (POO pour les intimes). Ce paradigme colle parfaitement \u00e0 l’impl\u00e9mentation des graphes, m\u00eame si c’est un peu plus compliqu\u00e9 que l’approche na\u00efve.<\/p>\n\n\n\n Selon ce paradigme, un objet est repr\u00e9sent\u00e9 par une classe<\/em>, contenant id\u00e9alement un constructeur<\/em> et des m\u00e9thodes<\/em>.<\/p>\n\n\n\n C’est la \u00ab\u00a0fonction interne\u00a0\u00bb \u00e0 la classe, \u00e0 l’objet, qui d\u00e9finit pour cet objet, et lui seulement, d’\u00e9ventuels param\u00e8tres.<\/p>\n\n\n\n Prenons un exemple de graphe non orient\u00e9 et non pond\u00e9r\u00e9 (pour faire simple). On peut alors imaginer que l’on d\u00e9clare un graphe (le premier par exemple) sous la forme:<\/p>\n\n\n\n Dans ce cas, on peut imaginer un constructeur de la mani\u00e8re suivante:<\/p>\n\n\n\n On a ici d\u00e9finit un constructeur qui construit une liste des n\u0153uds du graphe et une liste contenant toutes les ar\u00eates.<\/p>\n\n\n\n \u00c0 ce constructeur, on peut ajouter \u00e0 notre classe une m\u00e9thode permettant d’avoir la matrice d’adjacence:<\/p>\n\n\n\n La fa\u00e7on d’impl\u00e9menter un graphe n’est pas unique : elle d\u00e9pend de notre fa\u00e7on de voir les choses mais aussi de ce que l’on veut en faire. Aussi, la classe que je viens de vous montrer n’est pas unique. D’ailleurs, dans le livre de Terminale NSI<\/a> que j’ai co-\u00e9crit, j’utilise d’autres mani\u00e8res.<\/p>\n\n\n\nMais qu’est-ce qu’un graphe ?<\/h3>\n\n\n\n
\u00c0 quoi \u00e7a peut servir ?<\/h3>\n\n\n\n
Repr\u00e9sentation sagittale<\/h3>\n\n\n\n
![\"graphe](\"https:\/\/www.mathweb.fr\/euclide\/wp-content\/uploads\/2020\/07\/graphe01.png\")
![\"graphe](\"https:\/\/www.mathweb.fr\/euclide\/wp-content\/uploads\/2020\/07\/graphe02.png\")
![\"graphe](\"https:\/\/www.mathweb.fr\/euclide\/wp-content\/uploads\/2020\/07\/graphe03.png\")
![\"graphe](\"https:\/\/www.mathweb.fr\/euclide\/wp-content\/uploads\/2020\/07\/graphe04.png\")
o\u00f9, par exemple, la probabilit\u00e9 de passer de l’\u00e9tat \u00ab\u00a0A\u00a0\u00bb
\u00e0 l’\u00e9tat \u00ab\u00a0C\u00a0\u00bb est \u00e9gale \u00e0 0,5<\/figcaption><\/figure><\/div>\n\n\n\nMatrice d’un graphe<\/h3>\n\n\n\n
<\/figure><\/div>\n\n\n\n![\"matrice](\"https:\/\/www.mathweb.fr\/euclide\/wp-content\/uploads\/2020\/07\/matrice-graphe01.png\")
<\/figure><\/div>\n\n\n\n<\/figure><\/div>\n\n\n\n![\"matrice](\"https:\/\/www.mathweb.fr\/euclide\/wp-content\/uploads\/2020\/07\/matrice-graphe02.png\")
<\/figure><\/div>\n\n\n\n![\"\"](\"https:\/\/www.mathweb.fr\/euclide\/wp-content\/uploads\/2020\/07\/graphe03-1.png\")
<\/figure><\/div>\n\n\n\n![\"matrice](\"https:\/\/www.mathweb.fr\/euclide\/wp-content\/uploads\/2020\/07\/matrice-graphe03.png\")
<\/figure><\/div>\n\n\n\n<\/figure><\/div>\n\n\n\n![\"matrice](\"https:\/\/www.mathweb.fr\/euclide\/wp-content\/uploads\/2020\/07\/matrice-graphe04.png\")
<\/figure><\/div>\n\n\n\nDeux exemples d’application de graphes<\/h3>\n\n\n\n
Labyrinthes<\/h4>\n\n\n\n
![\"labyrinthe](\"https:\/\/www.mathweb.fr\/euclide\/wp-content\/uploads\/2020\/07\/labyrinthe-graphe.png\")
Changements d’\u00e9tats<\/h4>\n\n\n\n
<\/figure><\/div>\n\n\n\nImpl\u00e9mentation de graphes en Python<\/h2>\n\n\n\n
Approche na\u00efve (mais simple)<\/h3>\n\n\n\n
G = { \n\t'A' : ('B' , 'C') , \n\t'B' : ('A' , 'C'),\n\t'C' : ('A' , 'B')\n}<\/pre>\n\n\n\n<\/figure><\/div>\n\n\n\nG = { \n\t'A' : ( {'B':4} , {'C':7} ) , \n\t'B' : ( {'A':4} , {'C':2} ),\n\t'C' : ( {'A':4} , {'B':2} )\n}<\/pre>\n\n\n\n<\/figure><\/div>\n\n\n\nG = [\n\t\t[ 0 , 1 , 1 ] ,\n\t\t[ 1 , 0 , 1 ] ,\n\t\t[ 1 , 1 , 0 ]\n\t]<\/pre>\n\n\n\n
Des graphes en Python sont des objets<\/h3>\n\n\n\n
Le constructeur<\/h4>\n\n\n\n
G = Graphe( ('A','B') , ('A','C') , ('B','C') )<\/pre>\n\n\n\nclass Graphe:\n def __init__(self,*args):\n self.edges = [ e for e in args ]\n self.nodes = []\n for e in self.edges:\n if e[0] not in self.nodes:\n self.nodes += [ e[0] ]\n if e[1] not in self.nodes:\n self.nodes += [ e[1] ]\n \nG = Graphe( ('A','B') , ('A','C') , ('B','C') )\nprint( 'Les noeuds de G sont : {}'.format(G.nodes) )\nprint( 'Les ar\u00eates de G sont : {}'.format(G.edges) )<\/pre>\n\n\n\nM\u00e9thodes de la classe<\/h4>\n\n\n\n
class Graphe:\n def __init__(self,*args):\n self.edges = [ e for e in args ]\n self.nodes = []\n for e in self.edges:\n if e[0] not in self.nodes:\n self.nodes += [ e[0] ]\n if e[1] not in self.nodes:\n self.nodes += [ e[1] ]\n \n def mat(self):\n self.mat = [[ 0 for j in range(len(self.nodes))] for i in range(len(self.nodes))] \n for i in self.edges:\n self.mat[ self.nodes.index(i[0]) ][ self.nodes.index(i[1]) ] = 1\n self.mat[ self.nodes.index(i[1]) ][ self.nodes.index(i[0]) ] = 1\n \n return self.mat\n \nG = Graphe( ('A','B') , ('A','C') , ('B','C') )\nprint( 'Les noeuds de G sont : {}'.format(G.nodes) )\nprint( 'Les ar\u00eates de G sont : {}'.format(G.edges) )\nprint( 'La matrice d\\'adjacence de G est : {}'.format(G.mat()) )<\/pre>\n\n\n\n
![\"\"](\"https:\/\/www.mathweb.fr\/euclide\/wp-content\/uploads\/2020\/06\/Interros-des-Lycees-Numerique-Sciences-Informatiques-Terminale.jpg\")
<\/a><\/figure><\/div>\n\n\n\n