# data[].attributes.attachment_link.readable_text
On peut jouer

Graphes non orientés
Pour chacun de ces graphes non orientés, on peut

placer des pions (prédateurs, gendarmes ou chiens) pour un des joueurs et un pion (proie, voleur ou tangue) pour l'autre joueur, et le premier essaye de bloquer l'autre en bougeant un seul de ses pions à la fois. Ces jeux sont très anciens ;

analyser le jeu ci-dessus en cherchant où placer les chiens et le tangue pour équilibrer le jeu ;

jouer au jeu de Col : Chaque joueur à son tour colorie un sommet encore blanc du graphe, en évitant de colorier de la même couleur deux sommets adjacents du graphe ;

jouer au jeu de Snort : Comme ci-dessus mais cette fois-ci il ne faut pas colorier deux sommets adjacents dans des couleurs différentes ;

colorier les sommets du graphe sans jamais que deux sommets adjacents soient de même couleur, et en minimisant le nombre total de couleurs utilisées (son nombre chromatique) ;

inscrire dans chaque sommet le degré de celui-ci (optionnellement, reproduire les sommets et leurs degrés sans donner les arêtes, puis demander à un autre joueur de reconstituer le graphe) ;

inscrire dans chaque sommet la distance au sommet du graphe qui est le plus éloigné de celui-ci ;

parcourir le graphe, sommet après sommet, avec un seul pion, sans jamais passer par un sommet déjà visité ;

jouer à des jeux de semaille, les graines étant semées en suivant un chemin du graphe (chaque graine doit être semée dans un sommet adjacent à la graine précédente) ;

jouer (à un seul joueur) à sliding tokens, une généralisation de rush hour (casse-tête) à un graphe quelconque, où on place des pions sur des sommets non adjacents et chaque mouvement consiste à déplacer un pion vers un sommet adjacent à sa position actuelle mais adjacent à aucun autre sommet occupé. Le but du jeu est de mener un pion (rouge) à un sommet d'arrivée, quitte à bouger tous les autres pions (bleus) pour lui libérer le passage.

L'histoire se joue entre trois personnages, que nous allons nommer, respectivement, la grande sœur, le petit frère et le tonton. Le tonton est animateur IREM et il lui arrive parfois d'occuper les enfants à des jeux sur les graphes orientés (voir plus bas). La grande sœur fait partie des plus acharnés parmi les joueurs de Nim et dès l'âge de 7 ans elle a régulièrement créé ses propres graphes orientés. L'un de ces graphes (dessiné un peu avant le huitième anniversaire de la grande sœur) comporte 6 sommets :

Le tonton n'a toutefois pas été satisfait par ce graphe, en effet il y a une arête allant directement du départ à l'arrivée, ce qui, selon le tonton, " diminue considérablement l'intérêt du jeu ". Et oui, ils sont parfois exigeants, les tontons ! Ceci dit, le tonton a alors imaginé deux variantes du graphe, l'une obtenue en enlevant l'arête en question, l'autre en enlevant l'orientation du graphe. Voici les résultats obtenus :

version orientée

version non orientée

graphe à 6 sommets

Par la suite, à l'occasion d' un jour de pluie, les trois personnages, privés d'école, ont passé plusieurs heures à tester les graphes non orientés ci-dessus, en cherchant notamment comment colorier ces graphes, (et une fois le petit frère lassé) comment gagner au jeu de Col sur ces mêmes graphes. Mais surtout la grande sœur et le tonton se sont longuement posés, graphe après graphe, la question du nombre minimum de chiens à placer sur les graphes pour que ceux-ci aient une chance de bloquer le tangue (voir ci-dessous pour des précisions sur ce vocabulaire). La question s'est évidemment posée aussi sur le graphe non orienté de cette histoire : Comme il y a un sommet de degré 2, il y a des chances que 2 chiens suffisent pour bloquer le tangue. Ni la grande sœur ni le tonton n'ont alors eu le temps de chercher si dans ce cas les deux chiens bénéficient d'une stratégie gagnante.

L'épisode suivant de cette histoire est la semaine des maths où le graphe a eu un grand succès, notamment auprès des plus jeunes, probablement parce qu'il n'a que 6 sommets. Ce sont surtout les activités de coloriage qui y ont été menées. Et pendant ce temps, le petit frère n'a cessé de manifester son envie de jouer sur les graphes comme sa grande sœur. C'est peu après son quatrième anniversaire que le tonton a accédé à sa requête en lui présentant les graphes non orientés, l'un après l'autre, pour lui demander sur lequel il préférait jouer. Étant depuis peu élève en moyenne section, il a choisi le graphe qui est à la fois le plus simple et le plus gros, à savoir celui de notre histoire.

Il a choisi que l'un des joueurs dispose du pion orange et l'autre joueur, des deux pions cyan, lesquels peuvent alors bloquer le pion orange :

Est-ce que, pour n'importe quelle position de départ des 3 pions, celui qui a les pions cyan va nécessairement gagner le jeu ? Ou est-ce qu'au contraire le pion orange peut obtenir une partie nulle en obligeant les pions cyan à répéter le même mouvement ?

Quoiqu'il en soit, si, à l'âge de 4 ans, il est difficile d'inventer seul ce genre de jeu (des conseils du tonton et l'émulation de la grande sœur ont été utiles) à cause de problèmes de vision des zones du graphe (lignes), le plaisir de la création de jeu et celui de la manipulation des pions sont bel et bien présents à cet âge !

fer à cheval

madelinette

chiens et tang

2 parkings

chaque joueur a 2 pions et il ne reste qu'un sommet vide où on puisse bouger un pion

chaque joueur a 3 pions et il ne reste qu'un sommet vide où on puisse bouger un pion

le jeu du lièvre et du chien est un classique

chaque joueur a 3 pions mais au lieu de bloquer l'adversaire on peut mener ses pions aux sommets diamétralement opposés

le jeu d'Ovide

fanorona-dimy

le premier qui a réussi à aligner ses trois pions a gagné

le but du jeu est de prendre tous les pions de l'adversaire, par approche ou par éloignement

Ces graphes ont été dessinés une fois pour toutes, et même si on veut les colorier il est possible de le faire de façon réversible, en posant des jetons de couleur sur les sommets du graphe. D'autres jeux, plus " papier-crayon ", sont basés sur la construction (ou, dans un cas, la destruction) du graphe, arête par arête. Par exemple bridg-it où on construit des ponts. En fait ce jeu est un cas particulier du switching game de Shannon, la construction d'un pont bleu ayant pour effet de couper la route aux elfes rouges.

Le jeu de Sprouts est un jeu " papier-crayons " (un crayon par joueur) qui se joue sur une feuille initialement blanche. Enfin presque puisqu'elle contient n points (ci-dessous n=0). Ce sont n sommets (actuellement de degré 0) d'un futur graphe que le jeu consiste à construire. Alors chaque joueur à son tour va

ajouter une arête

soit reliant un sommet à lui-même (son degré augmente alors de 2 unités)

soit reliant deux sommets distincts (leur degré augmente alors d'une unité chacun)

ajouter sur la nouvelle arête un sommet (de degré 2).

Mais aucun sommet ne doit jamais avoir un degré supérieur à 3 et aucune arête ne doit jamais croiser une autre arête (ni elle-même). Le premier joueur qui ne peut plus tracer d'arête sans violer une de ces règles, est le perdant du jeu.

Voici une feuille permettant de jouer à Sprouts avec n=3 sans avoir à tracer les 3 points avant le jeu :

Le logiciel Nirina974 possède notamment un lien vers les graphes non orientés. La page s'ouvre avec un graphe prédéfini dont on n'aperçoit pas forcément qu'il est planaire :

Pour modifier le graphe, on peut

cliquer quelque part sur le graphe (ou à côté ; mais ailleurs que sur un sommet) ce qui fait apparaître un nouveau sommet (automatiquement nommé par le nombre de sommets créés) ;

Appuyer sur le bouton Control, puis, sans relâcher celui-ci, cliquer sur une arête (ce qui permet ensuite de la supprimer avec le bouton Suppr)

Effectuer un Control-clic du même genre que ci-dessus mais sur un sommet, ce qui permet ensuite de le supprimer par Suppr ou de changer sa couleur par p (comme " plus ") ou m (comme " moins ")

Appuyer sur le bouton Control, puis, sans le lâcher, cliquer sur un sommet, et sans lacher le bouton gauche de la souris, glisser celle-ci de manière à bouger le sommet :

Ci-dessus c'est le sommet 1 qui est en cours de déplacement, en continuant à le tirer par Control-cliquer-glisser vers le bas de la page, on finit par avoir cette version du graphe :

Pour créer un sommet, on clique donc sur la partie vide de la feuille de travail :

Comme il y a déjà 6 sommets sur le graphe, nommés, dans l'ordre, 0, 1, 2, 3, 4 et 5 (le sommet sélectionné, en marron), le sommet nouvellement créé s'appelle 6. Pour continuer la construction du graphe, il est temps de rajouter une arête entre, disons, les sommets 1 et 6. Pour cela, on part de l'un de ces sommets (le 1 ici) puis, en cliquant dessus et en glissant la souris, sans lâcher le bouton gauche, il apparaît une arête provisoire qui est reliée, d'un côté, au sommet, de l'autre côté, à la souris :

Si on lâche le bouton gauche de la souris alors que celle-ci n'est pas au-dessus d'un sommet, aucune arête n'est créée, et il faut tout recommencer à l'étape précédente. Mais si on lâche le bouton gauche de la souris alors qu'elle est au-dessus du sommet 6, une nouvelle arête est créée, et elle relie les sommets 1 et 6 :

Cette arête est sélectionnée comme si on avait Control-cliqué dessus, ce qui se voit au fait qu'elle est dessinée en pointillés. En sélectionnant le sommet 5 (en cliquant dessus) on voit que l'arête, maintenant désélectionnée, est de même nature que les autres arêtes :

Une fois le graphe créé, on peut cliquer sur le bouton Col en haut à droite, pour passer en mode jeu :

Comme le jeu consiste à colorier des sommets, ils sont devenus blancs :

Un message dit que c'est au tour du joueur " Bleu " de jouer. En effet, les deux joueurs portent en guise de pseudonyme, les noms des couleurs qu'ils utilisent pour remplir les sommets de leurs choix. Comment ? En cliquant sur un sommet

actuellement blanc

non adjacent à un sommet déjà colorié dans la même couleur (ici, le bleu) auparavant.

Bleu décide de colorier le sommet 6 :

Le message dit alors que c'est à Rouge de jouer. Rouge décide de colorier le sommet 1 :

C'est donc à Bleu de jouer. Mais Bleu ne peut colorier ni le sommet 1 ni le sommet 6 qui sont déjà coloriés ; il décide de colorier le sommet 0 :

Le message dit que c'est à Rouge de jouer. Les sommets 0,1 et 6 étant déjà coloriés, il ne reste plus que 4 choix ; en réalité 2 car les sommets 2 et 5 étant adjacents à un sommet rouge ne peuvent plus être coloriés en rouge. Seuls les sommets 3 et 4 respectent la double contrainte de n'être ni déjà coloriés, ni adjacents à un sommet rouge. Rouge choisit de colorier le sommet 4 :

C'est donc à Bleu de colorier en bleu un des sommets 2 et 3 (le sommet 5, adjacent à un sommet bleu, est injouable). Il choisit le sommet 3 :

Le texte dit que c'est à Rouge de jouer, mais il ne reste que les sommets 2 et 5 qui sont chacun adjacent à un sommet rouge : Rouge est censé jouer mais ne peut pas jouer. Que se passe-t-il alors ? Rouge a perdu !

Pour rejouer à Col (ou jouer à Snort) il est nécessaire de revenir en mode édition, en cliquant à nouveau sur le bouton Col.

Une fois en mode édition, on peut démarrer une partie de Snort en cliquant sur le bouton Snort :

Comme le jeu consiste à colorier des sommets, ceux-ci sont tous blancs au début du jeu. L'un des joueurs s'appelle Bleu et colorie (d'un clic) les sommets en bleu, l'autre joueur, appelé Rouge, colorie les sommets en rouge. Comme l'indique le texte, c'est à Bleu de commencer le jeu. Bleu va donc cliquer sur un des sommets du graphe pour le colorier en bleu. Il choisit le sommet 0 (en exergue ci-dessous) :

C'est là que Bleu clique, ce qui a pour effet

de colorier le sommet 0 en bleu

de changer le nom du joueur en haut :

Bleu passe alors la tablette à Rouge qui peut cliquer sur n'importe quel sommet

pas encore colorié (le sommet 0 est déjà colorié en bleu donc plus coloriable)

non adjacent à un sommet bleu : Les sommets 1, 4 et 5 doivent servir de zones-tampon entre les territoires bleu et rouge.

Rouge choisit alors le sommet 2 :

Le texte indique que Rouge doit repasser la tablette à Bleu qui ne peut maintenant plus colorier que l'un des sommets 4 et 6 (tous les autres sommets sont rouges ou adjacents à au moins un sommet rouge). Il choisit le sommet 4 :

C'est maintenant au tour de Rouge de choisir quel sommet il va colorier. Il colorie le sommet 6 :

C'est à nouveau au joueur Bleu de jouer, mais s'il joue le 1, que se passe-t-il ?

Rien ! Bon sang mais c'est bien sûr : Le sommet 1 est adjacent au sommet 2 qui est rouge, et Bleu ne peut donc pas le jouer. Ce serait contraire à la règle du jeu de Snort. De fait, quoique fasse Bleu, il ne se passera rien, Bleu ne peut plus jouer alors que pourtant c'est à son tour de jouer : Bleu a perdu le jeu.

Voici une présentation des activités menées durant la semaine des maths 2018 :

article au format pdf

source en LaTeX

article version courte

Graphes orientés

Les graphes orientés sur lesquels on joue à Nim sont particuliers :

L'un des sommets, appelé départ, a un degré entrant nul (on ne peut y mener le pion) ;

Il y a au moins une arrivée qui est un sommet de degré sortant nul (une fois que le pion y est, il ne peut plus bouger).

Pour jouer à Nim sur un graphe orienté muni d'un départ et au moins une arrivée,

On place le pion (commun aux deux joueurs) sur le départ ;

Chaque joueur à son tour déplace le pion

depuis le sommet où il se trouve

vers un sommet adjacent libre

en suivant le sens de la flèche.

Le premier qui ne peut plus bouger le pion, parce que celui-ci est à l'arrivée , perd le jeu de Nim.

La simplicité du graphe ci-dessus permet d'analyser le jeu à la recherche d'une stratégie gagnante et de découvrir cette notion. Un graphe similaire est ici et un autre, plus complexe mais esthétiquement intéressant, est ici.

jeu de la soustraction

jeu " soustrais un carré "

nim sur triangle

nim sur rectangle

En allant sur la page des graphes orientés on voit un graphe déjà commencé :

Les sommets numéros 0 et 2 sont plus gros que les autres, parce que ce sont le départ et une arrivée du graphe. Ensuite, dès qu'on clique quelque part sur le graphe, il naît à l'endroit du clic, un nouveau sommet :

Par contre si on ne lâche pas le bouton de la souris après avoir cliqué sur un sommet existant, il se crée une arête qui suit, tant que son bouton gauche reste enfoncé, la souris :

Cette arête disparaît si on lâche le bouton gauche de la souris en dehors d'un sommet, sinon le sommet ainsi sélectionné se voit relié au sommet d'où est parti ce mouvement de cliquer-glisser :

On voit que le sommet 3 est devenu une arrivée, il est donc dessiné plus gros et cerclé de rouge. L'arête qui vient d'être créée est en pointillés pour signifier qu'elle a été sélectionnée. Pour sélectionner une autre arête, il ne faut pas cliquer dessus ! En effet on a vu que cela créerait un nouveau sommet. En fait pour sélectionner un sommet ou une arête, il faut appuyer sur le bouton Control (ou la pomme) et, sans lâcher ce bouton, cliquer sur l'objet que l'on veut sélectionner. Sélectionner un sommet sert, le plus souvent, à le supprimer (avec la touche suppr) puisque, comme on l'a vu, chaque fois que l'on clique par erreur sur un objet, on voit naître un nouveau sommet.

Si on veut jouer à Nim sur le graphe orienté créé dans le tutoriel ci-dessus, il suffit de cliquer sur le bouton jouer :

Le clic sur une arête ne va maintenant plus provoquer l'apparition de sommets supplémentaires mais sélectionner l'arête, ce qui peut faire bouger le pion. Le pion est visible en noir sur le sommet de départ et au-dessus du graphe, on peut lire le nom du joueur qui doit cliquer sur l'arête de son choix :

S'il clique sur l'arête en pointillés (celle qui était sélectionnée à l'étape de construction du graphe) cela n'aura aucun effet, car le pion n'est pas au départ de cette arête. Mais si A clique sur l'arête visée ci-dessus, on voit que non seulement le pion a bougé, mais aussi que c'est à B de jouer le coup suivant :

Quoiqu'il joue, il gagne puisque le pion ira à une arrivée. Pour recommencer à jouer, il faut momentanément revenir au mode création :

Après cela, un nouveau clic sur jouer remettra le pion au départ, et ce sera à nouveau au joueur A de jouer.

Pour jouer à un jeu de type Nim, il faut un graphe orienté acyclique, en anglais DAG (" Directed Acyclic Graph "), d'où le nom de Doug donné au jeu ci-dessous (" beat Doug on a DAG ") :

Pour jouer à Doug, on place plusieurs pions (ou plutôt des jetons, superposables) sur des positions initiales qui ne sont pas nécessairement des départs. Chaque joueur bouge un des jetons en suivant une flèche, et plusieurs jetons peuvent cohabiter pacifiquement sur un même sommet. Lorsque les 4 jetons sont sur les sommets verts (arrivées, ou " puits " dans le langage des réseaux de flot, ou trou noir chez Fraenkel) le jeu est terminé. Celui qui devait bouger un des jetons a alors perdu la partie. Pour connaître la stratégie gagnante, la notion de nimber s'avère nécessaire, parce qu'il y a plusieurs jetons. Une fois maîtrisée, cette notion permet de " battre Doug " sur n'importe quel DAG, en particulier ceux présentés ci-dessus.

Si le graphe comporte un ou plusieurs cycles, il devient un Cyclic Graph et Fraenkel fait alors appel à Craig :

Dans le graphe cyclique ci-dessus (" Craig ") il n'y a qu'un seul trou noir, le jeu se termine donc lorsque les 4 jetons sont dans ce trou noir. S'il se termine ! En effet s'il ne reste qu'un jeton encore déplaçable sur le graphe, et que ce jeton est tout en bas à droite, il peut accomplir une ronde sans fin autour de ce sommet (le fameux cycle du graphe) et le jeu est déclaré partie nulle ou ko (go). Malgré cela, il y a une stratégie gagnante pour le premier joueur.

Il en est de même pour ce plus grand Craig, avec 5 corps célestes (les jetons) gravitant autour de 3 " puits gravitationnels " :

La recherche d'une stratégie gagnante est encore (beaucoup) plus difficile si les jetons interagissent ; la variante proposée par Conway est que lorsque deux jetons sont sur un même sommet, ils disparaissent du jeu (la collision les détruit). C'est le cas sur ce graphe à 17 jetons initiaux, inspiré par Shoemaker-Levy 9 :

On remarque qu'il y a 8 " puits gravitationnels ", qui peuvent servir de pièges à jetons : Une fois qu'un jetonest dedans, il ne peut plus échapper à l'attaque d'un pion-kamikaze qui viendrait l'annihiler. Voici les questions posées par Aviezri Fraenkel à propos de ce jeu :

Existe-t-il une stratégie gagnante à ce jeu ?

Si oui, en existe-t-il une pour laquelle il survivrait plus d'un jeton à la fin de la partie, chacun coincé dans un piège gravitationnel ?

Si oui, est-il possible que le jeton rouge survive à ce jeu ?

Cela a donné à Aviezri Fraenkel l'idée d'explorer une variante, où, comme aux échecs, si un pion va sur un sommet déjà occupé, c'est l'ancien occupant qui disparaît du jeu (il a été " pris ") mais pas l'attaquant. Ce jeu, appelé arrows parce que le graphe est partiellement orienté, a été commercialisé par Aviezri Fraenkel et Frank Eggleton en 1976, avec des billes de verre et de métal dans un plateau similaire à celui du solitaire :

Dans la version papier, il y a 7 sommets bleus où placer les jetons bleus au début du jeu, et 7 sommets rouge où placer les jetons rouges :

Chaque joueur à son tour déplace un des jetons de sa couleur, depuis le sommet où il se trouve, jusqu'à un sommet adjacent

en suivant la flèche s'il y en a une

dans le sens de son choix sinon

et si le sommet d'arrivée est déjà occupé par un jeton de la couleur adverse, celui-ci est retiré du jeu. Attention : On ne peut pas amener un jeton vers un sommet déjà occupé par un jeton de la même couleur (comme aux échecs !). Le but du jeu est de prendre tous les jetons de l'adversaire.

On peut aussi jouer, sur les graphes orientés, à des jeux de semaille :

et une autre généralisation des graphes orientés est les réseaux de Petri, sur lesquels on peut jouer comme ci-dessus, chaque joueur effectuant une transition du réseau de Petri jusqu'à ce que ce ne soit plus possible.

article sur Petri

source en LaTeX

Jeux sur réseaux de Petri

comme dans ce jeu créé par une descendante de champions de fanorona

Si tout cela vous paraît compliqué, sachez qu'une beta-testeuse de 8 ans y est arrivé sans grande difficulté malgré le fait que la souris était en fait un trackpad et que sa main est un peu petite par rapport à la distance entre le bouton Control et le trackpad.

Critique formulée par Nirina : Si on supprime le sommet numéro 6 et qu'ensuite on crée un nouveau sommet, celui-ci ne sera pas baptisé 6. Ce n'est pas grave mais il suffit d'éviter de supprimer un sommet si on pense en avoir besoin plus tard, si on tient comme Nirina à avoir des sommets numérotés par les entiers consécutifs.

représentant à l'époque la planète Jupiter alors que les autres jetons représentent les fragments de la comète, en imaginant que la collision avec ne serait-ce qu'un seul fragment détruise la planète et que cela menace l'avenir de tout le système solaire, le jeu a été titré " le système solaire survivra-t-il ? "

# data[].attributes.attachment_link.title
La théorie des graphes par le jeu, dès l'école primaire

# data[].attributes.attachment_link.description
On peut jouer Graphes non orientés Pour chacun de ces graphes non orientés, on peut placer des pions (prédateurs, gendarmes ou chiens) pour un des joueurs et un pion (proie, voleur ou tangue) pour l'autre joueur, et le premier essaye de bloquer l'autre en bougeant un seul de ses pions à la fois.

# data[].attributes.attachment_link.title
Mots croisés sur les termes de la théorie des graphes

# data[].attributes.attachment_link.readable_text
On peut commander une version papier de "Introduction à la théorie des graphes" sur le site www.crm-editions.ch au prix de 7 CHF l'exemplaire. Offre réservée aux écoles. Le cahier de solutions des exercices est uniquement disponible en version numérique.

# data[].attributes.attachment_link.description
On peut commander une version papier de "Introduction à la théorie des graphes" sur le site www.crm-editions.ch au prix de 7 CHF l'exemplaire. Offre réservée aux écoles. Le cahier de solutions des exercices est uniquement disponible en version numérique.

# data[].attributes.attachment_link.readable_text
Ce site est dédié à la Théorie des Graphes qui est une branche de la Mathématique discrète des plus fécondes et, en particulier, en France, avec Claude BERGE Les Graphes ont commencé dans le Magasin des "curiosités" Mathématiques mais sont largement utilisés dans la pratique, par exemple, des Sciences Humaines.

On fait généralement remonter la naissance de la Théorie des Graphes au célèbre problème des ponts de Königsberg (aujourd'hui Kaliningrad) qui passionnait la bourgeoisie prussienne du XVIIIème siècle : La Ville de Königsberg, sur la Pregel, était pourvue de 7 ponts et la question était de savoir si l'on pouvait imaginer une promenade dans la ville qui emprunterait chacun des 7 ponts une fois et une seule pour revenir à son point de départ.

Un Graphe, au départ, c'est simple : des sommets et des arcs, des points et des flèches ou des traits qui les relient. Quand ce sont des flèches, on a affaire à des graphes orientés; si ce sont des traits, le graphe n'est pas orienté. Certains problèmes font intervenir l'orientation, d'autres non.

Par exemple, le problème archi-connu consistant à savoir si on peut tracer ce dessin en un trait de crayon (c'est à dire sans le lever) sans repasser deux fois sur le même trait, c'est de la Théorie des Graphes.

Un autre classique de cour d'école qui consiste à demander de relier 3 maisons à 3 sources différentes d'énergie (eau, gaz et électricité) sans que les canalisations se croisent sur la feuille de papier, c'est aussi de la Théorie des Graphes.

Le fameux résultat qui dit qu'on peut colorier une carte géographique avec 4 couleurs de sorte que 2 pays limitrophes ne soient pas de même couleur, connue depuis 1852 sous le nom de "conjecture des 4 couleurs" parce que non démontrée, prouvée en 1976 à l'aide de l'ordinateur et 1000 heures de calcul, ce qui soulève le problème épistémologique de la vérificabilité de la preuve, c'est encore de la Théorie des Graphes.

Le célèbre "Jeu de Marienbad" qui revient comme un leitmotiv dans le magnifique film d'Alain Resnais scénarisé par Alain Robbe-Grillet : "L'Année dernière à Marienbad", c'est toujours de la Théorie des Graphes.

La Théorie des Graphes reste un des rares domaines de la Mathématique moderne où la recherche peut commencer sans arrière-plan théorique trop fourni, sans bagage pré-requis, bref, une zone de fraîcheur dans un monde de brutes. Marc BEVERAGGI

# data[].attributes.attachment_link.description
Ce site est dédié à la Théorie des Graphes qui est une branche de la Mathématique discrète des plus fécondes et, en particulier, en France, avec Claude BERGE Les Graphes ont commencé dans le Magasin des "curiosités" Mathématiques mais sont largement utilisés dans la pratique, par exemple, des Sciences Humaines.

# data[].attributes.attachment_link.readable_text
Everyone

Untangle is a simple and addictive puzzle game.
Your goal is to untangle the lines to advance to the next level. Be fast and effective to obtain the best score !

Untangle features :
★ 276 puzzles
★ Multiplayer mode : are you the best untangler in the world ? check it in our addictive multiplayer duel mode with worldwide ranking
★ Easy to play : single button game
★ 4 levels of difficulty : from short and easy to long and hard games
★ Random levels generator for infinite single player gameplay
★ Keep track of your best score and time with public leaderboards
★ All levels are solvable

Additional Information

12 rue de Sinzig am Rhein F-57330 Hettange-Grande

# data[].attributes.attachment_link.description
Untangle is a simple and addictive puzzle game. Your goal is to untangle the lines to advance to the next level. Be fast and effective to obtain the best score ! Untangle features : ★ 276 puzzles ★ Multiplayer mode : are you the best untangler in the world ?

# data[].attributes.attachment_link.readable_text
Simple rule: complete the grid accordingly with colors and discover the picture that hides beneath. Sounds easy? Not really! Each level is a real brain-teaser in which you will have to use logic and ingeniosity to complete larger paints.
If you like to challenge your mind with Sudoku and Logigrams then this addictive game is definitely for you!

Include:
1000+ grids
Large weekly paint every... Tuesday! (contains 9 grids)
Cloud save and cross platform support
Many cats to customize and share with your friends
A weekly updated customization shop

SUPPORT & FEEDBACK
Please contact support@tuesdayquest.com for any issue or feedback, we'd love to hear from you!

Follow @TuesdayQuest on Twitter for the latest development updates, news & tips: http://twitter.com/TuesdayQuest

You can also reach us on Facebook: http://facebook.com/tuesdayquest

Want to know more, get tips and latest news on Hungry Cat Picross? Follow us ==> https://www.facebook.com/HungryCatPicross
Any question? First check our FAQ here: https://docs.google.com/document/d/1dLD7ftr4GYzkfztt3s4qBh7FlYR2i7SkjfgpGcnHh2Q/edit?usp=sharing

What's new?

More content, more frequently
We can now add directly to your application new paints without having to go through the whole update process. Meaning, sometimes when coming back to the game you'll see new content to play with whereas you haven't updated the app. This feature will improve our ability to add new levels more often because it will reduce our development time. Cool meoooow ?

Customize your app
If you regularly play to Hungry Cat Picross, we thought you might want to set the game at your own tastes... now you can change the cat and many other accessories, you can even change the whole game colorset to fit your mood. Your cat will appear in the weekly leaderboards.

Cloud Save and Tuesday Leaderboards
Now you can log in any accounts (Facebook, Google Play or Twitter) or even create a Tuesday Quest one. Once connected, your progress is stored on servers and can be played from any devices. Being logged makes you eligible to the Tuesday Paint Leaderboard too, which is updated every week.
Creating an account is facultative! And yes, you still don't need an internet connection to play!

To celebrate all those brand new features, we've added a new type of paint type: Frescoes.

And there's more!
- Undo function
- Color blind support
- No more ad banners
- Catch Coin gameplay
- Weekly shop
- Cat interaction
- Statistics
- Tuesday Grids description

# data[].attributes.attachment_link.title
Hungry Cat Picross Purrfect Edition - Apps on Google Play

# data[].attributes.attachment_link.description
Simple rule: complete the grid accordingly with colors and discover the picture that hides beneath. Sounds easy? Not really! Each level is a real brain-teaser in which you will have to use logic and ingeniosity to complete larger paints. If you like to challenge your mind with Sudoku and Logigrams then this addictive game is definitely for you!

# data[].attributes.attachment_link.readable_text
Flow Free® is a simple yet addictive puzzle game.

Connect matching colors with pipe to create a Flow®. Pair all colors, and cover the entire board to solve each puzzle in Flow Free. But watch out, pipes will break if they cross or overlap!

Free play through hundreds of levels, or race against the clock in Time Trial mode. Flow Free gameplay ranges from simple and relaxed, to challenging and frenetic, and everywhere in between. How you play is up to you. So, give Flow Free a try, and experience "mind like water"!

Flow Free features:

★ Over 2,500 free puzzles
★ Free Play and Time Trial modes
★ Clean, colorful graphics
★ Fun sound effects

Special thanks to Noodlecake Studios, creators of Super Stickman Golf, for their work on Flow Free!

Enjoy.

# data[].attributes.attachment_link.description
Flow Free® is a simple yet addictive puzzle game. Connect matching colors with pipe to create a Flow®. Pair all colors, and cover the entire board to solve each puzzle in Flow Free. But watch out, pipes will break if they cross or overlap!

# data[].attributes.attachment_link.readable_text
Everyone

You can start but You never be able to stop. You will fall in love with Connect'Em

Connect'Em is a puzzle game in which you will have to strategically connect blobs together. Each blob only has a set number of connections available. So you will to make sure they all connect to each other the right way. Beware the game is very addictive :) For those of you who enjoy math workouts, make sure you take part in this daily mental ritual.

3 game modes are available
- Challenge mode with 4000 levels !
- Arcade mode to play freely. The Easy mode in Arcade is great to learn about the game but also to get kids to learn about numbers
- Time Attack where you will strive to beat your best all time record

We will add more levels in next updates.

Additional Information

22 rue de la voie des Bans Argenteuil, 95100 France

# data[].attributes.attachment_link.description
You can start but You never be able to stop. You will fall in love with Connect'Em Connect'Em is a puzzle game in which you will have to strategically connect blobs together. Each blob only has a set number of connections available. So you will to make sure they all connect to each other the right way.

# data[].attributes.attachment_link.readable_text
Tout public

Ajouter à la liste de souhaits

Untangle est un jeu de réflexion simple et captivant.
Votre objectif est de démêler les lignes pour progresser au niveau suivant. Soyez le plus rapide et le plus efficace pour obtenir le meilleur score !

Contenu d'Untangle :
★ 276 casses-tête
★ Mode multijoueur
★ Générateur de niveaux aléatoires pour des parties à l'infini
★ Simple à jouer : aides visuelles pour vous guider
★ 4 niveaux de difficulté : du niveau court et simple au niveau long et complexe
★ Suivez vos meilleurs scores et temps avec les classements publics
★ Tous les niveaux ont une solution

Informations supplémentaires

Classification du contenu

12 rue de Sinzig am Rhein F-57330 Hettange-Grande

# data[].attributes.attachment_link.description
Untangle est un jeu de réflexion simple et captivant. Votre objectif est de démêler les lignes pour progresser au niveau suivant. Soyez le plus rapide et le plus efficace pour obtenir le meilleur score !

# data[].attributes.attachment_link.readable_text
Everyone

You can start but You never be able to stop. You will fall in love with Connect'Em

Connect'Em is a puzzle game in which you will have to strategically connect blobs together. Each blob only has a set number of connections available. So you will to make sure they all connect to each other the right way. Beware the game is very addictive :) For those of you who enjoy math workouts, make sure you take part in this daily mental ritual.

3 game modes are available
- Challenge mode with 4000 levels !
- Arcade mode to play freely. The Easy mode in Arcade is great to learn about the game but also to get kids to learn about numbers
- Time Attack where you will strive to beat your best all time record

We will add more levels in next updates.

Additional Information

22 rue de la voie des Bans Argenteuil, 95100 France

# data[].attributes.attachment_link.description
You can start but You never be able to stop. You will fall in love with Connect'Em Connect'Em is a puzzle game in which you will have to strategically connect blobs together. Each blob only has a set number of connections available. So you will to make sure they all connect to each other the right way.

# data[].attributes.attachment_link.readable_text
Everyone

Contains Ads

Offers in-app purchases

Brain training mind game with amazing puzzle.
This free game helps you to improve your concentration.
One touch Drawing is a simple yet very addictive puzzle.
The rule is very simple.
Draw given figures with only one stroke.
The only problem is "You cannot draw twice the same line".
There are hundreds of handcrafted levels with funny tricks.
All levels are free!
New lines and points like below will make it difficult.
1. Line that must be passed twice.
2. One directional line.
3. Warp point.
4. Direction trigger.
5. Way trigger.
6. Warp Maker. (Very challenging)

Loading...

What's New

Bug fix and performance improvement.

Additional Information

1415, 1244 Seongnam-daero, Sujeong-gu, Seongnam-si, Gyeonggi-do 13311

# data[].attributes.attachment_link.description
Brain training mind game with amazing puzzle. This free game helps you to improve your concentration. One touch Drawing is a simple yet very addictive puzzle. The rule is very simple. Draw given figures with only one stroke. The only problem is "You cannot draw twice the same line".

# data[].attributes.attachment_link.readable_text
Connect to communicate! Transmission is a mind-bending puzzle game where you create communication networks and reveal their strengths.

- 70 levels with 146 stars to collect
- 7 unlockable worlds
- Easy to learn, tough to master
- In-game trophies
- Google play achievements
- Over 8 hours of gameplay
- Multi-path world map
- Features music by David Kanaga

By connecting transmitters and receivers, you will send information around increasingly complex networks. As you progress, you will discover six networks that have transformed the way we communicate, each with its own unique gadgets and gizmos. Featuring a vibrant soundtrack by David Kanaga, stylish graphics and hours of fun, challenging gameplay.

# data[].attributes.attachment_link.description
Connect to communicate! Transmission is a mind-bending puzzle game where you create communication networks and reveal their strengths. - 70 levels with 146 stars to collect - 7 unlockable worlds - Easy to learn, tough to master - In-game trophies - Google play achievements - Over 8 hours of gameplay - Multi-path world map - Features music by David Kanaga By connecting transmitters and receivers, you will send information around increasingly complex networks.

# data[].attributes.attachment_link.readable_text
Everyone

Contains Ads

Offers in-app purchases

Hexio is a relaxing, mind-bending, minimalist puzzle game that offers over 60 meticulously designed levels to immerse yourself into. A beautiful piano soundtrack accompanies you in your delightful experience.

Features:

- 96 hand-crafted puzzles
- All levels are free and accessible from the start
- Option to purchase hints to help you find the solution to some levels
- Game progress is saved automatically

Don't hesitate to contact us if you find any issue with the game or if you simply want to send us your feedback, it is greatly appreciated.

What's New

- Fixed issue with sign in causing the app to crash
- General fixes and improvements

# data[].attributes.attachment_link.description
Hexio is a relaxing, mind-bending, minimalist puzzle game that offers over 60 meticulously designed levels to immerse yourself into. A beautiful piano soundtrack accompanies you in your delightful experience.

# data[].attributes.attachment_link.readable_text
Pour colorier. Glen Scott/Flickr, CC BY-NC-ND

Après de brillantes études, vous avez été recruté au ministère des Affaires étrangères. Un jour le ministre vous convoque pour vous annoncer la bonne nouvelle : ça y est, il a enfin réussi à convaincre ses homologues de 100 pays à envoyer des ambassadeurs à Paris dans une semaine pour un congrès sur la paix et les échanges culturels. Maintenant c'est à vous d'organiser tout ça. Ce colloque lui tient vraiment à cœur. Il faut que ça soit une réussite, il en va de l'honneur du pays !

Après d'âpres négociations, 30 thèmes ont été retenus. Cet évènement se déroulera sur une seule journée et sera organisé sous forme de réunions d'une heure chacune, dont les noms de code sont R1... R30. Les participants à chaque réunion sont fixés, vous avez la liste. Le ministère a loué un espace avec 30 salles suffisamment grandes pour accueillir tous les participants.

Le ministre s'exclame : " Grâce aux 30 salles de réunions, tout cela va pouvoir se boucler en une seule heure. Ça donnera ensuite aux délégations l'occasion de se rencontrer de manière informelle pour discuter. Excellent, tout ça ! " Visiblement le " patron " n'a pas tout en tête. Vous lui glissez : " M. le ministre, cela ne va pas pouvoir se faire exactement comme vous dites. Par exemple, il est prévu que le diplomate canadien assiste à trois réunions. Il n'est donc pas possible de mettre les 30 réunions toutes en même temps sinon il ne pourra assister qu'à une seule. " Après un instant de réflexion, le ministre vous dit : " En effet... Je vous confie la mission d'établir le planning. " Avant que vous n'ayez pu émettre un son, il a déjà tourné les talons, préoccupé par les déclarations qu'il devra faire devant la presse. L'organisation n'est pas son problème ; c'est le vôtre.

Vous vous mettez à l'œuvre immédiatement. Vous prenez une feuille de papier : vous y dessinez 30 ronds, chacun représentant une réunion. Ensuite, vous tracez un trait entre deux réunions Ri et Rj si elles ont un ou plusieurs participants en commun et ne peuvent donc pas avoir lieu en même temps (sinon ces personnes inscrites à Ri et à Rj ne pourront pas suivre les deux, ce qui peut provoquer une crise). Ce que vous obtenez est un graphe. Les réunions sont les éléments ou sommets du graphe. Un trait éventuel entre deux sommets est une arête.

Read more: La vie secrète des graphes

Pour commencer à tâter le terrain, examinons deux cas extrêmes.

Graphe sans arête : les réunions peuvent être organisées toutes en même temps (chaque participant n'assiste qu'à une réunion). En une seule heure, tout est terminé.

Graphe complet : entre chaque paire de sommets, il y a une arête. Dans ce cas il faut prévoir 30 réunions successives car aucune ne peut avoir lieu en même temps qu'une autre. Durée totale : 30 heures !

En regardant votre dessin, vous constatez que vous n'êtes ni dans un cas ni dans l'autre. Les choses ne vont pas être simples...

Coloration de graphes

Ce que vous avez à faire s'appelle de la coloration de graphe. Une coloration de G est la donnée d'une couleur (ou un entier qui représente la couleur) à chaque sommet de telle manière que si deux sommets sont reliés par une arête (on dit qu'ils sont voisins) alors ils ne doivent pas avoir la même couleur.

Auteur, Author provided

Observons les trois graphes ; celui non coloré le plus à gauche ; à sa droite une coloration utilisant 4 couleurs ; enfin une coloration qui n'utilise que 3 couleurs. Posons le problème suivant : étant donné un graphe G quelconque, construire une coloration de G utilisant le nombre minimum de couleurs, dite coloration optimale.

Notez que les couleurs utilisées n'ont pas d'importance, seul compte le nombre total de couleurs utilisées.

Sur l'exemple de la figure 1, la coloration la plus à droite est optimale (impossible de colorier ce graphe avec moins de 3 couleurs) et permet de faire les 7 réunions en seulement 3 heures (une couleur = un créneau d'une heure). Notez qu'il peut y avoir plusieurs colorations optimales. Par exemple le sommet 6 pourrait être colorié en jaune (au lieu de bleu).

Mais au fait, comment a-t-on trouvé cette solution ? Vous avez consulté un livre sur les graphes et vous vous êtes rendu compte que votre problème fait partie de la liste des problèmes algorithmiques les plus difficiles (il est lié à ce que l'on appelle la question " P=NP ? "). En faisant quelques estimations, vous vous apercevez qu'avec une méthode exacte il vous faudra largement plus d'une semaine pour calculer une coloration optimale, même en utilisant l'ordinateur le plus puissant du ministère. Vous le sentez bien : tout cela ne va pas plaire au ministre si vous lui donnez le planning de l'évènement... après l'événement lui même.

Comment faire alors ? Il n'y a pas de méthode totalement satisfaisante pour résoudre ce type de problèmes. Soit vous voulez une réponse exacte et dans ce cas vous allez devoir calculer très, très, très longtemps, soit vous voulez " rapidement " une réponse et dans ce cas vous risquez d'avoir une réponse de qualité médiocre. Il faut souvent faire des compromis entre temps de calcul et qualité du résultat.

Une approche simple et gloutonne

Allons-y pour un travail à la pelle. Un algorithme très simple à mettre en œuvre est à votre disposition. Voici comment il marche sur un exemple de la figure ci-dessous.

Auteur, Author provided

Considérons une liste des sommets de ce graphe. Pour faire simple, prenons la liste a, b, c, d, e, f, g. Définissons maintenant une liste de couleurs numérotées : 1 est rouge ; 2 est bleu ; 3 est vert ; 4 est jaune ; 5 est orange. Précisons que seul compte le numéro de la couleur, pas la teinte en elle-même. Le cœur de l'algorithme consiste à prendre chaque sommet, dans l'ordre de la liste (a, puis b puis c, etc.) et à le colorier avec une couleur de la liste avec la règle suivante : ce sommet reçoit la plus petite couleur non encore attribuée à ses voisins déjà coloriés. Pour illustrer, nous avons représenté le graphe en mettant les sommets de gauche à droite, dans l'ordre a, b, c, d, e, f, g.

Le sommet a, le premier de la liste, n'a aucun voisin déjà colorié. On lui donne donc la plus petite couleur de la liste : rouge. On passe au suivant, le sommet b, qui a maintenant un voisin déjà colorié (le sommet a). La plus petite couleur possible pour lui est alors bleu. Au tour de c qui n'a qu'un voisin déjà colorié : (a en rouge). Il prend alors lui aussi la couleur bleu. Le prochain sommet de la liste, d n'a qu'un voisin déjà colorié, b qui est en bleu. D'après la règle il prend alors la couleur la plus petite compatible avec cette contrainte, qui est rouge. Le sommet e a deux voisins coloriés, un en bleu, l'autre en rouge, il est donc obligé de prendre la 3 e couleur, vert. Le sommet f a un voisin bleu et un vert. Il peut donc prendre la couleur rouge. A la fin, g doit obligatoirement prendre la 4 e couleur de la liste, le jaune. Vous êtes un peu perdus ? Regardez donc la vidéo ci-dessous.

En appliquant cette méthode avec cette liste, quatre couleurs sont utilisées (le planning correspondant tient sur quatre heures en tout). La coloration du même graphe, la plus à droite n'utilise que trois couleurs (donnant un planning de trois heures seulement), ce qui montre bien, que, hélas, cette méthode ne retourne pas toujours une coloration optimale.

Il vous vient alors une idée : " Et si j'essayais toutes les listes ? " Pour chaque liste vous coloriez suivant la méthode précédente et vous gardez en mémoire celle qui a utilisé le moins de couleurs. Mais avec 30 sommets vous avez 265252859812191058636308480000000 listes à tester en tout (30 choix pour le 1 er de la liste puis 29 pour le 2 e, puis 28 pour le 3 e, etc, ce qui donne en tout 30*29*28*... *2*1 listes). Même en en testant 10 000 000 000 par seconde avec un ordinateur puissant, il vous faudra environ 841 111 300 774 324 ans pour tout faire.

Le découragement vous gagne. Que va dire le ministre si vous lui apportez le planning dans 841 111 300 774 324 ans ? Il faut que vous trouviez une solution ! Il est impossible de tester toutes les listes mais rien ne vous empêche d'en essayer au hasard quelques milliers avec votre ordinateur. C'est ce que vous faites. Par chance, cette méthode vous donne une coloration utilisant 8 couleurs. En la reprenant à la main, en " bricolant ", vous arrivez à réduire à 6 couleurs. Vous êtes sauvé ! L'événement durera 6 heures en tout. C'est acceptable. Fier de vous, vous portez le planning, fruit de vos longs efforts, au ministre.

En jetant un œil distrait à votre travail, il vous annonce qu'en fin de compte l'ambassadeur d'Italie ira assister à la réunion 7 à laquelle il n'était pas initialement prévu et que l'ambassadeur japonais n'ira pas à la réunion 14 pour laquelle il s'était inscrit. Malheur ! ça risque de tout changer !

Allez, vous vous êtes fait des frayeurs pour rien. Le fait que le Japonais n'aille pas à la réunion 14 n'est pas grave. Le planning peut être conservé tel quel (on libère une contrainte) mais l'Italien induit une nouvelle contrainte. Il devait assister initialement aux réunions 4,8 et 11. Il doit maintenant, en plus, assister à la réunion 7. Dans votre planning, les réunions 4, 8 et 11 n'ont pas lieu au même moment (au moins à cause de l'Italien). Mais la 7 pourrait avoir lieu en même temps que la 4, la 8 ou la 11. Vous regardez votre planning. Ouf ! Ce n'est pas le cas.

Observons sur un petit exemple ce qui peut se passer en cas de modifications des contraintes. Sur le graphe de la figure ci-dessous, le graphe le plus à gauche peut être colorié avec 2 couleurs. En ajoutant une arête entre a et d il est toujours possible de le colorier avec 2 couleurs. Par contre, en ajoutant une arête entre a et c, le " triangle " a,b,c créé nécessite l'utilisation d'une 3 e couleur.

Auteur, Author provided

Happy end...

L'événement a eu beaucoup de succès. Le ministre est ravi et vous accorde quelques jours de congés au soleil, histoire de reprendre des couleurs, loin de celles des graphes !

# data[].attributes.attachment_link.title
Comment élaborer un planning ? Avec des crayons de couleur, de la patience et... des mathématiques

# data[].attributes.attachment_link.description
Après de brillantes études, vous avez été recruté au ministère des Affaires étrangères. Un jour le ministre vous convoque pour vous annoncer la bonne nouvelle : ça y est, il a enfin réussi à convaincre ses homologues de 100 pays à envoyer des ambassadeurs à Paris dans une semaine pour un congrès sur la paix et les échanges culturels.

# data[].attributes.attachment_link.readable_text
Reading time: ~10 min Reveal all steps

Every day we are surrounded by countless connections and networks: roads and rail tracks, phone lines, the internet, electronic circuits and even molecular bonds. There are even Can you think of any other examples? social networks between friends and families.

In mathematics, all these examples can be represented as graphs (not to be confused with the graph of a function).

Graph theory is the study of graphs and their properties. It is one of the most exciting and visual areas of mathematics, and has countless important applications.

We can draw the layout of simple graphs using circles and lines. The position of the vertices and the length of the edges is irrelevant - we only care about how they are connected to each other. The edges can even cross each other, and don't have to be straight.

We can create new graphs from an existing graph by removing some of the vertices and edges. Here you can see a few more examples of graphs, with coloured edges and vertices indicating a possible subgraph:

We say that the The order of a graph is the number of vertices it has. degree of a vertex is the number of edges which meet at that vertex.

Graphs that consist of a single loop of vertices are called All cycles have the same number of edges and vertices more edges than vertices fewer edges than vertices.

Equipped with these new definitions, let's explore some of the fascinating properties and applications of graphs.

To reveal more content, you have to complete all the activities and exercises above.
Are you stuck? Skip to the next step or reveal all steps

The Bridges of Königsberg

# data[].attributes.attachment_link.description
Reading time: ~10 min Reveal all steps Every day we are surrounded by countless connections and networks: roads and rail tracks, phone lines, the internet, electronic circuits and even molecular bonds. There are even Can you think of any other examples? social networks between friends and families.

# data[].attributes.attachment_link.description
Découvrez les graphes et les algorithmes de graphes grâce à de courtes vidéos à base d'exemples et d'illustrations. Videos de vulgarisation, pour débutants. Pour aller plus loin ou pour découvrir d'autres thèmes, je vous invite à lire mon livre, "À la découverte des graphes et des algorithmes de graphes" (voir le lien ci-dessous).

# data[].attributes.attachment_link.title
#3. Les graphes (5 min. pour comprendre)

# data[].attributes.attachment_link.title
#2. Algorithme de Dijkstra (5 min. pour comprendre)

# data[].attributes.attachment_link.title
Le théorème des 4 couleurs — Science étonnante #4

# data[].attributes.attachment_link.description
On peut toujours colorier n'importe quelle carte géographique en utilisant seulement 4 couleurs. Si vous n'y croyez pas, cherchez donc un contre-exemple ! Facebook : https://www.facebook.com/sciencetonnante Twitter : https://www.twitter.com/dlouapre Abonnez vous à la chaîne : https://www.youtube.com/user/ScienceE... Le blog de Science étonnante : http://sciencetonnante.wordpress.com

# data[].attributes.attachment_link.title
Deux (deux ?) minutes pour... le théorème des 4 couleurs

# data[].attributes.attachment_link.title
Option Informatique | Ecole Alsacienne | 2015-2016

# data[].attributes.attachment_link.readable_text
Les graphes sont des objets mathématiques essentiels des mathématiques du XXI e siècle, une structure de donnée fondamentale pour appréhender le réel et accessibles de manière très élémentaire. Nous décrivons ici des activités dont l'objectif principal est de rendre ces objets plus familiers.

Depuis plusieurs années maintenant, des jeux sont proposés par l' IREM de La Réunion, dont certains portent sur des graphes.

Temps de lecture 30 minutes

Ces activités, adaptables à la classe du primaire (sur une séance ou deux), sont source d'images, dessinées ou coloriées de manière réfléchie par des enfants, les plaçant en tant que scientifiques suivant des règles logiques plutôt que dessinateurs. Cet article propose des exemples comme :

- la création de graphes orientés dans le cadre de jeux de type Nim ;

- le coloriage de graphes planaires pour le jeu de Col ;

- le coloriage de graphes planaires pour le jeu de Snort ;

- le calcul de degrés des sommets (activité arithmétique) pour les besoins de l'analyse des jeux.

Sans rentrer dans les détails, cet article décrit également quelques outils techniques, pour l'enseignant, comme des logiciels utiles pour dessiner des graphes, supports d'activités de coloriage ludique et réfléchi.

Nous terminons sur des scénarios possibles d'utilisation en classe, de la fin de cycle 1 au cycle 3.

La notion de graphe est la base de nombreuses notions mathématiques fondamentales (relations, mathématiques discrètes, topologie), formalisant les notions de voisinage, d'ordre, de connexité : deux sommets sont voisins s'ils sont reliés par une arête d'un graphe non orienté, un sommet précède un autre s'ils sont reliés par une arête orientée, la composition d'arêtes en chemins permet de connecter ses sommets. Dans un réseau social par exemple, les sommets représentent les personnes, et deux sommets sont adjacents si les personnes représentées par ces sommets, sont amies. Les réseaux électriques, internet, fluviaux, aériens, routiers, ferroviaires, etc. étant modélisés par des graphes, cette notion se prête remarquablement à l'abstraction. Et Édouard Lucas qui dès la fin du XIX e siècle créait et analysait des jeux sur ce qu'il appelait réseaux, avait même utilisé des graphes pour modéliser les rondes des enfants de l'école maternelle !

Les enfants dès la grande section s'approprient rapidement le vocabulaire qui remplace ou précise celui des dessins habituels, de ronds et de traits afin de formaliser les règles qu'on introduit quand il y en a besoin :

les objets dessinés en rond s'appellent les sommets du graphe ;

les traits entre les sommets s'appellent les arêtes du graphe ;

lorsqu'une arête joint deux sommets, on dit que ces sommets sont adjacents ;

le nombre d'arêtes se rencontrant en un sommet s'appelle le degré du sommet ;

le plus petit nombre de couleurs dont on a besoin pour colorier un graphe en respectant la règle du jeu s'appelle le nombre chromatique du graphe.

On peut très bien rentrer dans les activités sans introduire le vocabulaire mais changer de mots permet de changer de regard sur l'objet, qui d'un dessin devient un graphe. L'objectif principal de ces jeux est de rendre plus familière cette structure de données si fondamentale aux mathématiques contemporaines et d'en explorer quelques propriétés de base émergeant de ces jeux, faisant travailler la logique élémentaire. Parmi les compétences développées on peut citer la vision dans le plan, la reconnaissance des formes (lignes, cercles, flèches), le raisonnement hypothético-déductif, le comptage, la planification, le repérage dans l'espace, la perception des aires et des couleurs, la pensée algorithmique et l'abstraction. L'étendue des concepts qu'on peut modéliser à l'aide des graphes est très large, le langage par exemple est éclairé par la notion de réseau sémantique.

Énumérer les éléments d'un graphe, le nombre de sommets ou d'arêtes, le degré des sommets, est une activité en soi intéressante, en particulier si le sommet n'est pas planaire ( polyèdre par exemple), l'enfant devant développer une stratégie d'énumération, dont on peut graduer la difficulté en autorisant ou pas à marquer les sommets/arêtes déjà énuméré(e)s, à manipuler ou pas l'objet. Ces activités d'énumération peuvent ou non accompagner, préparer ou réinvestir les activités de jeu décrites ici.

Col et Snort
L'intérêt porté par les enfants à la coloration de graphes (en jouant à Nim, voir plus bas) a mené à une expérimentation sur des jeux de coloriages de graphes, les jeux de Col et Snort avec des règles différant légèrement selon le jeu choisi parmi ces deux. Dans les deux cas, chaque joueur (traditionnellement appelés " Bleu " et " Rouge ") colorie un sommet actuellement blanc dans sa propre couleur, mais :

dans Col, il ne faut pas que deux sommets adjacents soient de la même couleur ;

dans Snort, il ne faut pas au contraire que deux sommets adjacents soient de couleurs différentes.

Pour jouer à Col ou Snort, il faut un graphe non orienté et non encore colorié. Chaque joueur a son propre crayon de couleur et le mot " adjacent " a été expliqué brièvement aux élèves avant de jouer.

Règle de Col

Le joueur qui a le crayon bleu commence. Il colorie en bleu un des sommets de son choix. Ensuite c'est au tour du joueur ayant le crayon rouge de jouer, il colorie un des sommets restants en rouge. Puis le joueur aux crayons bleus colorie un des sommets restants en bleu, et ainsi de suite. Mais il ne faut jamais colorier un sommet dans la même couleur qu'un des sommets voisins (auxquels il est adjacent).

Le premier qui ne peut plus jouer (parce que tous les sommets blancs sont adjacents à un sommet de sa couleur, et que c'est à son tour de jouer) a perdu le jeu.

Règle de Snort

Le joueur qui a le crayon bleu commence. Il colorie en bleu un des sommets de son choix. Ensuite c'est au tour du joueur ayant le crayon rouge de jouer, il colorie un des sommets restants en rouge. Puis le joueur aux crayons bleus colorie un des sommets restants en bleu, et ainsi de suite. Mais il ne faut jamais qu'un sommet rouge et un sommet bleu soient adjacents.

Le premier qui ne peut plus jouer (parce que tous les sommets blancs sont adjacents à un sommet de la couleur de son adversaire, et que c'est à son tour de jouer) a perdu le jeu.

Le nom de Col est à la fois une allusion au nom de son créateur (Colin Vout) et au fait qu'il s'agit d'un jeu de coloriage. Le nom de Snort est également une double allusion :

au nom de son créateur Simon Norton ;

à un habillage agricole. Dans la version initiale deux éleveurs se partageaient un ranch en plaçant des vaches et des taureaux, tout en préservant la chasteté nécessaire. Or les ruminants commençaient par se renifler (to snort) s'ils étaient trop proches les uns des autres ...

Les plus jeunes joueurs s'étant affrontés dans ces jeux (de coloriage, pas de reniflage) étaient en Moyenne Section. Par exemple la photo qui ouvre cet article montre une partie de Col entre élèves de Grande Section (on constate d'ailleurs avec quel soin ils colorient). De belles réalisations sont visibles dans cet article.

Les plus jeunes joueurs ont parfois tendance à se tromper, en coloriant par erreur un sommet qui leur était interdit (adjacent à un sommet de sa propre couleur dans Col, à un sommet de la couleur adverse dans Snort). Dans ce cas, les enfants conviennent spontanément que celui qui a commis l'erreur est perdant du jeu (" tu as triché donc j'ai gagné ").

Saurez-vous deviner

quel est le joueur qui a joué en premier ?

qui a gagné le jeu ?

Quant à l'âge du capitaine plus jeune joueur (les rouges), c'est 6 ans, comme on peut le deviner à sa calligraphie.
Comment puis-je faire jouer mes élèves à Col ?

La première étape est de dessiner (soi-même, à l'aide des logiciels ci-dessus, ou par les élèves) un ou plusieurs graphes planaires. On peut aussi simplement télécharger ceux qui sont dans le bloc " ressources " tout en bas de cet article.

Ensuite il faut en faire tirer environ autant d'exemplaires que l'on a d'élèves à faire jouer.

Enfin, pour ce qui est du matériel, il faut un crayon de couleur par joueur.

Il faut prévoir plusieurs parties pour que les enfants ne se trompent plus dans le coloriage et pour partager les graphes coloriés obtenus ; en effet il arrive souvent que des joueurs veuillent garder le résultat, dont ils apprécient la beauté, et deux joueurs doivent parfois choisir lequel des deux pourra garder le jeu.
Les énigmes de Col et Snort
Les questions posées ci-dessus (qui a joué en premier ? Qui a perdu le jeu ?) sont des exercices intéressants à mener. Par exemple on peut récupérer des parties terminées par des élèves d'une autre classe (ou les scanner pour les vidéoprojeter) puis les soumettre aux élèves en groupe et leur poser ce genre de questions, les amenant ainsi à verbaliser leur raisonnement. De toute manière, dès la fin du jeu, une question assez naturelle est " J'ai perdu mais aurais-je pu gagner ? " et tenter d'y répondre peut mener à un travail de recherche avec analyse des différents cas, initiant ainsi les élèves à la recherche scientifique.

Il est à noter à ce propos que les jeux de Col et Snort sont liés à des problèmes ouverts, notamment de recherche de stratégie gagnante (on n'en connaît pas à l'heure actuelle).
Théorème des quatre couleurs
Il faut quelques minutes pour familiariser un élève de cycle 2 ou 3 au vocabulaire sommet-arête-adjacence-degré-nombre chromatique et le fait que ce soient uniquement les sommets d'un graphe qu'on colorie (plutôt que les régions sur une carte) permet de mener l'activité assez rapidement (typiquement moins d'une demi-heure avec un groupe d'une dizaine d'élèves) pour apprendre à colorier :

les sommets (et non les faces du graphe) sans trop déborder, en Petite Section ;

en respectant la consigne de ne pas colorier de la même couleur deux sommets adjacents, en Grande Section ;

en minimisant le nombre de couleurs (atteindre le nombre chromatique du graphe) dès le CP.

Par exemple, lors de la semaine des maths, il a été demandé à des élèves de 4e, de dessiner à la craie, puis colorier, un graphe de nombre chromatique 3, puis 4, puis 5, en quelques minutes. L'impression qu'ils ne pouvaient pas réussir avec 5 couleurs est vite apparue, même s'il n'était pas question de leur demander de prouver le théorème des quatre couleurs ! Dans le contexte présent, le théorème peut s'énoncer ainsi :

Pour colorier n'importe quel graphe planaire (sans croisement des arềtes) de manière que jamais deux sommets adjacents ne soient de la même couleur, quatre crayons suffisent.

Jeux de Nim
Le jeu de type Nim sur un graphe orienté nécessite de particulariser deux sommets, le " départ " où on pose en premier le pion et l'" arrivée " coloriée ; ensuite chaque joueur à son tour déplace le pion depuis le sommet où il se trouve jusqu'à un sommet adjacent, en suivant le sens de la flèche. Celui qui mène le pion à une arrivée gagne le jeu.

La pratique de cette activité a mené à deux constatations :

la plupart des enfants ont du mal à voir et concevoir les graphes non planaires et les graphes qu'ils créent sont en général planaires (voir exemple ci-dessous), un sommet est naturellement le lieu où deux traits se rencontrent sur le papier ;

si le graphe orienté comporte un cycle, on court le risque que la partie dure un temps infini et les cycles sont rapidement évités par les jeunes créateurs de graphes.

Ces constatations ne sont pas des problèmes en soi, il est naturel de jouer sur des graphes planaires et de bannir les cycles, et s'en tenir là, ces notions abstraites ne sont pas des visées de cette activité mais peuvent apparaître comme questionnements. On peut attendre le collège pour aborder l'existence de graphes non planaires par exemple en jouant à Planarity.
Dessiner un graphe comme un jeu
Créer un graphe est si ludique qu'il arrive parfois un miracle : le simple dessin d'un graphe orienté, pour peu qu'on le contraigne à quelques propriétés, est en lui-même considéré comme un jeu. Dans le cadre d'un atelier IREM, a ainsi été développé un outil en ligne très simple d'aide à la création de graphes : ce logiciel décrit dans la suite et que vous pouvez utiliser pour construire vous-même de jolis graphes à imprimer pour votre classe.

Voici un graphe orienté créé pour jouer avec un unique pion dessus :

Dessiner de manière agréable et sans ambiguïté ce graphe n'est pas forcément évident. Deux petits logiciels, l'un interactif en ligne, l'autre textuel en Python, permettent de fabriquer une image numérique (au format SVG) qu'on peut ensuite utiliser, après impression puis éventuelle plastification, pour jouer plusieurs fois sur le même graphe.

Sur ce graphe précis, trouver une stratégie gagnante n'est pas très difficile. Mais un algorithme existe pour en trouver sur n'importe quel graphe, en coloriant le graphe ; on colorie en vert les sommets où on veut mener le pion, car ils sont gagnants :

si au moins une arête issue d'un sommet va vers un sommet déjà colorié en vert, je colorie ce sommet en rouge (le feu est rouge car je ne veux pas y aller, en effet je perdrais le jeu en laissant mon adversaire aller vers la case verte) ;

à l'inverse, si aucune arête issue d'un sommet ne va vers un sommet vert, je colorie ce sommet en vert : le feu est vert pour moi, puisque pour mon adversaire il n'y a que des feux rouges.

L'algorithme décrit ainsi est récursif, notion peu accessible à de jeunes enfants, mais le départ du coloriage est facile à verbaliser : L'arrivée (ou les arrivées) ne menant à aucun sommet vert (puisqu'elle ne mène à aucun sommet), est coloriée en vert. C'est le point de départ du coloriage.

Colorié par sa créatrice, le graphe montre l'existence d'une stratégie gagnante pour celui qui joue en premier (depuis le départ) :

# data[].attributes.attachment_link.description
Les graphes sont des objets mathématiques essentiels des mathématiques du XXI e siècle, une structure de donnée fondamentale pour appréhender le réel et accessibles de manière très élémentaire. Nous décrivons ici des activités dont l'objectif principal est de rendre ces objets plus familiers.

# data[].attributes.attachment_link.readable_text
Imaginez une pile de journaux identiques que vous faites sauter avec des pétards pour en faire une pluie de fragments de texte aléatoire. Comment feriez-vous, à partir de ces milliers de morceaux de papier, pour reconstruire un exemplaire complet du journal ? La même question se pose lorsque l'on désire reconstruire le génome d'un organisme à partir des milliards de courtes séquences générées par un séquenceur haut débit. Si vous pensez qu'il suffit de tester toutes les combinaisons en comparant les fragments deux à deux, sachez que même avec un ordinateur très puissant, cela prendrait beaucoup de temps. Nous allons donc voir dans ce billet, comment les programmes d'assemblages classiques fonctionnent et comment un gars du nom de Euler, en s'amusant à compter les ponts de la ville de Königsberg, nous permet aujourd'hui de faire de l'assemblage de génomes de façon efficace.

Les sont l'ensemble des mots de k lettres que l'on peut lire dans une séquence. Par exemple, la séquence suivante TAATGCCATGGGATGT peut se décomposer (avec des pétards ou non) en 14 mots de 3 lettres appelés 3-mers :

TAATGCCATGGGATGT
TAA
 AAT
  ATG
   TGC
    GCC
     CCA
      CAT
       ATG
        TGG
         GGG
          GGA
           GAT
            ATG
             TGT

Ce que nous allons tenter dans la suite de ce billet, c'est de reconstruire la séquence d'origine à partir de ces 14 mots de 3 lettres rangés dans un ordre arbitraire :

AAT,ATG,ATG,ATG,CAT,CCA,GAT,GCC,GGA,GGG,TAA,TGC,TGG,TGT

Attention, notez bien dans cette liste que le mot ATG est présent 3 fois. Il s'agit de l'abondance du k-mer qu'il faut prendre en compte en raisonnant bien avec 3 mots ATG et non un seul.

À partir de cette liste de 3-mers, nous allons construire un graphe orienté. C'est-à-dire un ensemble de nœuds reliés par des flèches. Pour cela, deux méthodes s'offrent à nous.

Les k-mers sont des nœuds

Si nous représentons chaque k-mer par un nœud, alors deux nœuds consécutifs dans la séquence partagent le même suffixe et préfixe. Par exemple le k-mer T GC précède le k-mer GC C car le suffixe du premier (-GC) correspond au préfixe du second (GC-). Cette relation se représente avec deux nœuds et une flèche :

Nous pouvons alors construire un graphe en reliant tous nos k-mers via leurs suffixes/préfixes et obtenir la figure suivante :

Pour reconstruire la séquence d'origine, il suffit de trouver un chemin passant par tous les nœuds une fois et une seule. On appelle ce chemin un parcours Hamiltonien. Essayez de le trouver par vous même avant de regarder l'animation ci-dessous :

Cette méthode est simple, mais il y a un hic. La recherche du parcours Hamiltonien dans un graphe est un problème mathématique dit NP-complet. Pour faire simple, il n'existe pas d'algorithme informatique rapide pour trouver ce chemin. Le temps de calcul augmente exponentiellement avec la taille du graphe. Par exemple, pour un graphe plus complexe, tel que celui utilisé pour reconstruire la séquence d'un génome, il vous faudra toujours énormément de temps de calcul, même avec les plus super des super calculateurs. Il nous faut une meilleure méthode...

Les k-mers sont des flèches

Nous allons cette fois construire un graphe en représentant les k-mers par des flèches. Les nœuds contiendront le préfixe et le suffixe du k-mer. Par exemple si une flèches représente le k-mer TGC alors les deux nœuds autour de la flèche sont TG et GC.

Nous pouvons alors construire le graphe suivant :

Cette fois, au lieu de chercher un chemin passant par tous les nœuds une seule fois, nous allons chercher un chemin passant par toutes les flèches une fois et une seule. En le recherchant, vous verrez tout de suite qu'un tel parcours n'existe pas dans ce dernier graphe. Par exemple, on ne peut pas traverser tous les chemins AT-> TG sans être bloqué. Pour remédier à ce problème, nous allons fusionner tous les nœuds identiques. Visualisez par exemple les 3 nœuds violets AT et imaginez-les se rapprocher pour former un seul nœud sans jamais toucher aux flèches. Vous obtenez alors un unique nœud AT relié par 3 flèches au nœud TG. Faites la même chose pour les autres nœuds identiques et vous obtiendrez le fameux graphe de de Bruijn.

Vous pouvez maintenant chercher le chemin passant par toutes les flèches une fois et une seule. C'est ce qu'on appelle un parcours Eulérien. Essayer de le trouver par vous même, ce n'est pas très difficile.

Contrairement au parcours Hamiltonien, le parcours Eulérien, si il existe, peut être trouvé rapidement par un algorithme informatique. La complexité de cet algorithme est dite " en O(n) ". C'est à dire que le temps de calcul est proportionnel à la taille du graphe. Voyons maintenant la théorie mathématique derrière ce parcours que l'on doit à Leonhard Euler et à la ville de Königsberg en Pologne.

Le théorème de Euler

En 1873, un mathématicien du nom de Leonhard Euler s'est posé la question de savoir si il existait une promenade dans la ville de Königsberg passant par tous les ponts une fois et une seule. C'est le problème des 7 ponts de Königsberg qui peut être modélisé sous la forme d'un graphe :

Euler démontre qu'un parcours Eulérien (passant par toutes les arêtes une fois et une seule) existe dans un graphe si et seulement chaque nœud est relié à un nombre pair d'arêtes. En effet, si l'on doit entrer dans un nœud par 1 arête, il faut forcément ressortir par 1 autre arête. Dans le cas des ponts de Königsberg, un tel chemin n'existe pas, car le nombre d'arêtes par nœud est respectivement de 5,3,3,3 (voir image ci-dessus). Dans un graphe orienté comme le notre, c'est à dire lorsque les arrêtes sont des flèches, un chemin Eulérien existe si le nombre de flèches à l'entrée d'un nœud est le même qu'à la sortie.

Avons-nous un chemin eulérien dans notre graphe de de Bruijn ?

Pour que les conditions du théorème de Euler s'appliquent à notre graphe de de Bruijn, nous devons tricher en ajoutant une flèche entre le dernier nœud TA et le premier nœud GT et former ainsi un cycle. Vous constaterez alors, que pour chaque nœud, il y a autant de flèches d'entrée que de flèches de sortie. Nous pouvons alors conclure, sans même le connaître, qu'un chemin Eulérien existe.

L'algorithme de Euler

Il existe une algorithme rapide pour pouvoir trouver le chemin Eulérien. Pour le comprendre (c'est très simple, je vous rassure), regardez juste cette courte vidéo sur la chaîne YouTube " à la découverte des graphes ". Personnellement, je trouve que c'est la meilleure chaîne de vulgarisation sur la théorie des graphes. A garder en favoris.

Nous avons vu deux méthodes pour reconstruire une séquence à partir de ses k-mers. Nous pouvons soit chercher un parcours Hamiltonien dans un graphe de k-mer ou alors chercher un parcours Eulérien dans un graphe de de Bruijn. Cette dernière méthode est préférée, car il existe un algorithme efficace. Dans ce billet, je me suis grandement inspiré du livre Bioinformatics Algorithms que je vous conseille fortement. C'est le même exemple détaillé sur plus de 20 pages. Sinon, dans la réalité, la reconstruction d'un génome est plus complexe et fait intervenir d'autres notions comme les contigs, les scaffolds, les bulles, la correction d'erreurs de séquençage ou encore le gap filling. Je ne suis absolument pas spécialiste de ce domaine, mais j'avais juste envie de vous partager ce que j'avais compris. Pour plus de précisions, voir avec@Natir, c'est un expert de l'assemblage. Enfin, tout les notions vues dans ce billet concernent l'assemblage d'un génome à partir de courtes séquences d'ADN ou short reads. Cette méthode est aujourd'hui devancée par les séquenceurs de 3e génération capable de séquencer des longs fragments d'ADN rendant toutes les notions abordées dans ce billet... complètement obsolètes !

Références

Remerciements

Merci à @Natir pour m'avoir fait comprendre que je ne comprend toujours rien !

Ce site est versionné sur GitHub. Vous pouvez corriger des erreurs en vous rendant à cette adresse

# data[].attributes.attachment_link.description
Imaginez une pile de journaux identiques que vous faites sauter avec des pétards pour en faire une pluie de fragments de texte aléatoire. Comment feriez-vous, à partir de ces milliers de morceaux de papier, pour reconstruire un exemplaire complet du journal ?

# data[].attributes.attachment_link.readable_text
Mathématiques du jonglage par V. Pantaloni.

Version imprimable en pdf.
16 pages, soit 4 feuilles recto-verso en format livret. Évidemment, il n'y aura pas les GIF animés.
Tapé en LaTeX.

Introduction :

Je vais présenter ici un panorama des résultats mathématiques sur le jonglage que l'on trouve un peu éparpillés sur le net et assez rarement en français.

À l'été 2013, 20 ans après avoir appris à jongler avec trois balles je me suis remis au jonglage en me lançant le défi de réussir jongler à cinq balles c'est à dire de réussir cette magnifique " cascade " :

Grâce à YouTube j'ai pu suivre des tutoriels qui m'ont bien aidé, et en parcourant différents sites web sur le jonglage j'ai rapidement découvert et essayé de comprendre un système de notation des figures appelé siteswap (mot à mot : échange de site). Par exemple pour apprendre la cascade à cinq balles ci-contre on recommande de commencer par maîtriser le jonglage normal à quatre balles puis les figures ci-dessous : le 55550 (à gauche) et le 552 (à droite)

siteswap 55550

siteswap 552

Outre l'immense plaisir de réussir à jongler avec cinq balles à la fin de l'été, j'ai découvert différents aspects des mathématiques du jonglage que j'ai enseignés à des élèves dans le cadre de la DNL (maths en anglais) ou lors d'un projet trans-diciplinaire sur le cirque en seconde ou encore lors de conférences pour la semaine des mathématiques, et en 2017 Colin Wright - un des co-inventeurs du siteswap - m'a demandé de traduire sa conférence jonglée pour la Nuit des maths à Blois.
Je vais présenter ici les différents aspects mathématiques du jonglage qui m'ont passionnés en essayant autant que possible d'éviter trop de formalisme. Tous les gif animés de robots qui jonglent ont été pris sur juggle.wikia.com et ont été créés avec Juggling Lab. Toutes les autres figures ont été créées personnellement avec Inkscape, Gimp ou GeoGebra.

Théorème de Shannon.

Si on essaye de passer du jonglage à trois balles au jonglage à 4 puis 5 balles (et plus si affinité) on se rend vite compte qu'il va falloir lancer les balles plus haut.

Cascade à 3 balles

Cascade à 7 balles

Pour comprendre pourquoi et même déterminer à quelle hauteur lancer les balles pour réussir à réaliser un jonglage régulier avec B balles (B entier supérieur à 1), il y a le théorème de Shannon. Du même Claude Shannon que la théorie de l'information. Ce grand mathématicien a démontré le premier théorème sur le jonglage et même fabriqué des machines qui jonglent ( video)

Théorème de Shannon. On a pour un jonglage régulier (i.e. chaque main fait le même lancer à chaque fois) avec B balles l'égalité de rapports suivants :

(f+d) / (e+d)=B / H
où les lettres f, d, e, et H désignent :

f : le temps qu'une balle passe en l'air

d : le temps qu'une balle passe dans la main

e : le temps qu'une main reste vide

H : le nombre de mains utilisées pour jongler

Preuve Je vais donner une démonstration de ce théorème dans le cas H=2 (deux mains) et B=3 (trois balles). Le principe se généralise bien. Il faut imaginer qu'on déroule verticalement dans le temps ce mouvement des balles vues du dessus.

On observe ce motif de tresse (On peut d'ailleurs effectivement obtenir une vraie tresse si on jongle avec des cordes accrochées aux balles). Si on représente cette tresse schématiquement comme ci-dessous sur une période (entre les pointillés) on peut y lire les différents temps utilisés par Shannon.

On compte le temps d'une période de deux manières : d'une part pour une balle (ici la bleue à droite) et d'autre part pour une main (la gauche). On obtient :

Et donc en divisant de part et d'autre par 2(e+d) :

Ce qui est bien le résultat annoncé pour le cas H=2 et B=3. □

En partant de la relation de Shannon :

(f+d) / (e+d)=B / H
On peut exprimer le temps de vol f en fonction des autres variables en multipliant par e+d :
f = (e+d)B/H -d
Cette dernière relation montre que f est une fonction affine croissante du nombre de balles B. Autrement dit, plus on veut jongler avec un nombre important de balles, plus il faut augmenter leur temps de vol f. Comment augmenter f ? En lançant les balles plus haut bien sûr. Pour savoir plus précisément à quelle hauteur, on doit utiliser la loi de la chute des corps.
Hauteur des lancers pour jongler B balles.

Étant uniquement soumis à l'accélération de la pesanteur g (environ 10 m/s² sur Terre), la chute des corps nous dit que chaque balle met un temps t pour tomber d'une hauteur h reliés par la relation :

h=gt²/2
Comme une balle met autant de temps pour monter à la hauteur h, on a f=2t et donc :
h=g(f/2)²/2
Soit pour g=10, après simplification :
h=1,25 f²
En combinant ce résultat avec le résultat obtenu grace au théorème de Shannon : f = (e+d)B/H -d on a donc :
h = 1,25[(e+d)B/H -d]²
Pour deux mains (H=2) et en fixant les valeurs en secondes de e et d à un quart de seconde (e=d=0,25) on obtient la relation : h = 1,25[B/4 -1/4]² ce qui se réarrange en :
h ≈ 0,08(B-1)²
On peut ainsi obtenir un tableau de valeur et une courbe pour la hauteur h en mètres à laquelle il faut lancer chacune des B balles avec lesquelles on veut jongler.

B

1

2

3

4

5

6

7

8

9

10

h

0

0.1

0.3

0.7

1.3

2

3

4

5

6.5

La hauteur évolue comme le carré du nombre de balles, on comprend pourquoi une balle de plus augmente considérablement la difficulté. Ces hauteurs sont approximatives, en particulier pour éviter d'avoir à lancer trop haut, on peut jouer sur e et d : en diminuant e+d, c'est à dire en étant plus rapide avec les mains, on pourra faire baisser la hauteur nécessaire. Les hauteurs pour 8, 9, 10 balles peuvent sembler exagérées, mais je vous laisse regarder cette vidéo de Bruce Sarafian avec différents records pour 8, 9, 10, 11 et même 12 balles ou celle-ci d'Alex Baron pour un flash avec 13 balles pour apprécier la hauteur des lancers et la vitesse des mains.

Siteswap.

On pourra visiter les liens suivants :

Voici le principe, on reprend le schéma de la tresse, où on représente le temps qui s'écoule vers le bas, les points de part et d'autres représentent les mains qui vont lancer les balles alternativement à un rythme régulier, schématisé par le point rouge sur cette animation. L'intervalle de temps entre deux mouvements de main, donc entre deux positions du point rouge est pris comme unité de tempo. Cela représente un temps. A partir de là on peut définir les différents lancers par le nombre de temps qu'il faudra à la balle pour retomber.

La balle est lancée directement dans la main opposée, rapidement (1 temps)

La balle est lancée dans la même main pas très haut (en pratique, même on ne la lance pas, elle reste dans la main)

La balle est lancée dans la main opposée mais plus haut puisqu'il lui faut 3 temps pour retomber. Dans le même temps on doit pouvoir faire trois lancers 1 : G->D->G->D. C'est le lancer utilisé pour jongler la cascade à 3 balles.

La balle est lancée verticalement pour retomber dans la même main

Lancer croisé haut (pour la cascade à 5 balles)

Ainsi de suite, les lancers impairs sont croisés et les pairs sont verticaux et retombent dans la même main. On peut alors désigner une figure de jonglage par la succession de ces nombres entiers. On donne juste le code sur une période si le mouvement est cyclique.

Les jonglages réguliers correspondent aux siteswaps de période 1. La cascade à 3 balles est simplement : 3. Plus généralement le jonglage régulier à n balles se code par : n. Ci-dessous les tresses régulières pour les jonglages réguliers à 3, 4 et 5 balles. On observe que le jonglage régulier à 4 balles ne croise pas : tout se passe comme si on jonglait avec deux balles dans chaque main.

Tresses régulières

4

Groupe des tresses mathématiques

Il existe une théorie mathématique sur les tresses ( braid theory en anglais) qui est liée à la théorie des noeuds. On peut voir des similarités avec les tresses de jonglage mais il y a des différences notables. Pour les tresses mathématiques il est important de savoir quel brin passe au dessus de quel autre brin ce qui est sans intérêt pour nous, et la notion de temps qui est fondamentale en jonglage n'existe pas dans la théorie des tresses. Des tresses qui sont mathématiquement isomorphes peuvent correspondre à des jonglages différents.

Questions et résultats mathématiques sur le siteswap

Les questions mathématiques que je me suis posées et auxquelles je vais répondre sont :

Toute succession de nombres correspond-elle à un siteswap jonglable ? (On verra que non)

Y a-t-il une condition sur la séquence de nombres pour qu'un siteswap soit jonglable ?

Si un siteswap jonglable est donné, comment savoir combien il nécessite de balles ?

Comment déterminer tous les siteswap jonglables ?
Tout siteswap n'est pas jonglable. La réponse à la première question est donc négative. Par exemple le siteswap 12 ne peut pas être jonglé comme le montre le diagramme ci-contre car deux balles arriveraient simultanément dans la même main. Pour répondre aux deux questions suivantes, on va utiliser un résultat important : le théorème de la moyenne.

Théorème de la moyenne

Site swap
Il est temps d'expliquer l'origine du mot " siteswap ". Dans le diagramme en échelle on a le point (site) de départ et d'arrivée de chaque balle. Si on considère deux balles lancées successivement, on peut en gardant les mêmes points de départ intervertir leur point d'arrivée sans perturber le reste de la séquence. On a échangé ( to swap en anglais) les sites d'arrivée. Qu'est-ce que cela change à la paire de nombres considérée ?
Regardons d'abord un exemple : 51.

Par rapport au temps zéro, on prévoit l'arrivée de la première balle dans 5 temps et de la deuxième dans deux temps (puisqu'elle sera lancé un temps après la première). Si on fait l'échange des arrivées (en pointillés), la première balle lancée arrivera dans deux temps (on lance donc un 2) et la deuxième arrivera dans cinq temps il faudra donc lancer un 5-1=4.
Ainsi 51->24. On peut remarquer que si on refait l'échange des arrivées à partir de 24 on retombe sur 51. Plus généralement :
Si on échange les arrivées pour un siteswap ab où a et b sont deux en

# data[].attributes.attachment_link.description
Mathématiques du jonglage par V. Pantaloni. Version imprimable en pdf. 16 pages, soit 4 feuilles recto-verso en format livret. Évidemment, il n'y aura pas les GIF animés.Tapé en LaTeX. Je vais présenter ici un panorama des résultats mathématiques sur le jonglage que l'on trouve un peu éparpillés sur le net et assez rarement en français.

# data[].attributes.wish_content.attachment_props.text
Le réseau des voies romaines en carte de métro avec les "hubs" antiques

# data[].attributes.wish_content.attachment_props.original_text
Le réseau des voies romaines en carte de métro avec les "hubs" antiques https://t.co/Fv9qvgKJAB

# data[].attributes.attachment_link.metadata.attachment_props_source.data.text
Le réseau des voies romaines en carte de métro avec les "hubs" antiques https://t.co/Fv9qvgKJAB

# data[].attributes.attachment_link.metadata.attachment_props.original_text
Le réseau des voies romaines en carte de métro avec les "hubs" antiques https://t.co/Fv9qvgKJAB

# data[].attributes.attachment_link.metadata.attachment_props.text
Le réseau des voies romaines en carte de métro avec les "hubs" antiques

# data[].attributes.attachment_link.readable_text
I used to believe mathematics was discovered, not invented. Mathematics was the elegant language the universe was written in! Yeeeeeah. That changed when I first learnt about matrices, coz sure, they're useful, but oh my god are they ugly like a carnival freakshow. Who would wanna write a universe in this crap?!

Several years later, I was coding a videogame, when I bumped into matrices again. These matrices were transformation matrices, which affected the size, position, and rotation of my game's images. Now, when I changed a matrix, I could actually see what the matrix did. I could actually see what a matrix was! It was intuitive. Kind of charming. A majestic creature, finally freed from its n x m rectangular cage.

So, I made this little matrix toy. Hopefully this helps someone else figure out matrices, or maybe everyone else except me already found matrices intuitive. At the very least, I made this as a tribute to you, 2D matrix...

...you beautiful, beautiful bastard.

A bunch of peeps, including me, are making things that help others learn by doing. We call 'em Explorable Explanations. We're a loose & informal "movement", and if you'd like to play with more interactive edu-things, check out ExplorableExplanations.com!

This was a side project, just to get something out while I'm working on my bigger project, I'd Like To Be A Machine. Coming soon-ish. It's an Explorable Explanation on neurons & anxiety - hopefully it helps people on a deeper level. It also features a baby dinosaur. If you'd like to keep up with my work, here's my Twitter. And if you'd like to support me making free/open-source ed-stuff, you're awesome, and here's my Patreon!

Oh! Right, almost forgot to say, this thing is open source. Public domain, specifically. In fact, all my work is public domain, so teachers can use it freely in their classrooms, and others can dissect and build upon this. You can fork this project's repo on Github.

Welp, that's all I got for today. Thanks for reading!

# data[].attributes.attachment_link.description
I used to believe mathematics was discovered, not invented. Mathematics was the elegant language the universe was written in! Yeeeeeah. That changed when I first learnt about matrices, coz sure, they're useful, but oh my god are they ugly like a carnival freakshow. Who would wanna write a universe in this crap?!

# data[].attributes.attachment_link.readable_text
Markov chains, named after Andrey Markov, are mathematical systems that hop from one "state" (a situation or set of values) to another. For example, if you made a Markov chain model of a baby's behavior, you might include "playing," "eating", "sleeping," and "crying" as states, which together with other behaviors could form a 'state space': a list of all possible states. In addition, on top of the state space, a Markov chain tells you the probabilitiy of hopping, or "transitioning," from one state to any other state---e.g., the chance that a baby currently playing will fall asleep in the next five minutes without crying first.

A simple, two-state Markov chain is shown below.

With two states (A and B) in our state space, there are 4 possible transitions (not 2, because a state can transition back into itself). If we're at 'A' we could transition to 'B' or stay at 'A'. If we're at 'B' we could transition to 'A' or stay at 'B'. In this two state diagram, the probability of transitioning from any state to any other state is 0.5.

Of course, real modelers don't always draw out Markov chain diagrams. Instead they use a "transition matrix" to tally the transition probabilities. Every state in the state space is included once as a row and again as a column, and each cell in the matrix tells you the probability of transitioning from its row's state to its column's state. So, in the matrix, the cells do the same job that the arrows do in the diagram.

If the state space adds one state, we add one row and one column, adding one cell to every existing column and row. This means the number of cells grows quadratically as we add states to our Markov chain. Thus, a transition matrix comes in handy pretty quickly, unless you want to draw a jungle gym Markov chain diagram.

One use of Markov chains is to include real-world phenomena in computer simulations. For example, we might want to check how frequently a new dam will overflow, which depends on the number of rainy days in a row. To build this model, we start out with the following pattern of rainy (R) and sunny (S) days:

One way to simulate this weather would be to just say "Half of the days are rainy. Therefore, every day in our simulation will have a fifty percent chance of rain." This rule would generate the following sequence in simulation:

Did you notice how the above sequence doesn't look quite like the original? The second sequence seems to jump around, while the first one (the real data) seems to have a "stickyness". In the real data, if it's sunny (S) one day, then the next day is also much more likely to be sunny.

We can minic this "stickyness" with a two-state Markov chain. When the Markov chain is in state "R", it has a 0.9 probability of staying put and a 0.1 chance of leaving for the "S" state. Likewise, "S" state has 0.9 probability of staying put and a 0.1 chance of transitioning to the "R" state.

In the hands of metereologists, ecologists, computer scientists, financial engineers and other people who need to model big phenomena, Markov chains can get to be quite large and powerful. For example, the algorithm Google uses to determine the order of search results, called PageRank, is a type of Markov chain.

Above, we've included a Markov chain "playground", where you can make your own Markov chains by messing around with a transition matrix. Here's a few to work from as an example: ex1, ex2, ex3 or generate one randomly. The transition matrix text will turn red if the provided matrix isn't a valid transition matrix. The rows of the transition matrix must total to 1. There also has to be the same number of rows as columns.

You can also access a fullscreen version at setosa.io/markov

# data[].attributes.attachment_link.description
Markov chains, named after Andrey Markov, are mathematical systems that hop from one "state" (a situation or set of values) to another. For example, if you made a Markov chain model of a baby's behavior, you might include "playing," "eating", "sleeping," and "crying" as states, which together with other behaviors could form a 'state space': a list of all possible states.

# data[].attributes.attachment_link.readable_text
J'ai récemment découvert un remarquable petit livret de coloriage réalisé par un mathématicien américain à destination des enfants de 7 ans...
Il permet d'expliquer par le coloriage et le dessin les nombres chromatiques et les circuits Euleriens.

Joel David Hamkins, un brillant mathématicien et philosophe de New York, tient un blog ou il parle de divers sujets s'adressant généralement à des plus grands, mais à notamment publié cet article, ainsi que le leaflet en version anglaise.

Il m'a aimablement autorisé à le traduire dans la langue de Molière (merci à lui !),
voici donc la version française qui vous permettra, au choix, d'occuper vos enfants pendant un trajet en train, un journée pluvieuse, ou de les convertir à la beauté de la chose mathématique par le jeu !

Attention ! Danger d'addiction mathématique !

# data[].attributes.attachment_link.title
Coloriages de graphes et nombres chromatiques ! - Toysfab

# data[].attributes.attachment_link.description
J'ai récemment découvert un remarquable petit livret de coloriage réalisé par un mathématicien américain à destination des enfants de 7 ans... Il permet d'expliquer par le coloriage et le dessin les nombres chromatiques et les circuits Euleriens. Joel David Hamkins, un brillant mathématicien et philosophe de New York, tient un blog ou il parle de ...

# data[].attributes.attachment_link.readable_text
Je vous avais déjà partagé (ici) un remarquable petit livret de coloriage réalisé par le grand mathématicien américain JD Hamkins, à destination des enfants de 7 ans, qui permettait d'expliquer par le coloriage et le dessin les nombres chromatiques et les circuits Euleriens. Ce fut un grand succès, tant auprès de mes gamins que de ceux d'autres parents*

Voici donc un deuxième livret (PDF à imprimer) qui le prolonge sur la théorie des graphes , destiné aux enfants de 8 ans, qu'il m'a aimablement autorisé à traduire dans la langue de Molière (merci à lui !) Pour l'article original, en américain donc, .

De quoi occuper vos enfants pendant un trajet en train, un journée pluvieuse, et les convertir à la beauté de la chose mathématique par le jeu ! Attention ! Danger d'addiction mathématique !

Joel David Hamkins, brillant mathématicien et philosophe de New York, tient ou il parle de divers sujets s'adressant généralement à des plus grands, mais publie également des articles destinés aux enfants....

* je tiens à préciser que tous ces enfants ne sont ni les uns ni les autres particulièrement des surdoués en math, juste des gamins curieux auxquels il ne faut surtout pas dire qu'il s'agit de maths avant qu'ils aient fini de remplir les feuilles 🙂
Ils découvriront ainsi qu'ils sont doués en math, tout simplement !

# data[].attributes.attachment_link.title
La théorie des graphes pour enfants ! - Toysfab

# data[].attributes.attachment_link.description
Je vous avais déjà partagé (ici) un remarquable petit livret de coloriage réalisé par le grand mathématicien américain JD Hamkins, à destination des enfants de 7 ans, qui permettait d'expliquer par le coloriage et le dessin les nombres chromatiques et les circuits Euleriens.

# data[].attributes.attachment_link.readable_text
Résumé : Ce document a pour vocation de présenter, d'expliquer et de jouer avec les graphes et les algorithmes. Ces notions sont centrales en informatique et sont très importantes pour un grand nombre d'applications concernant les réseaux de télécommunication (réseau sans fil, réseau optique, réseau du Web), les réseaux électriques, les réseaux routiers, en biologie (structurale) et pour résoudre un grand nombre de problèmes en général. L'objectif est de présenter des problèmes de graphes et des algorithmes sous la forme la plus simple et la plus ludique possible. Toutes les activités expliquées dans ce document peuvent se décliner dans trois espaces : l'espace d'une feuille de papier, l'espace d'un plateau de jeu et l'espace grandeur nature (par exemple avec des cerceaux et des lattes en plastique).

# data[].attributes.attachment_link.keywords[]
jeux  ; graphes  ;  algorithmes  ;  vulgarisation

# data[].attributes.attachment_link.title
Graphes et Algorithmes - Jeux grandeur nature

# data[].attributes.attachment_link.description
Ce document a pour vocation de présenter, d'expliquer et de jouer avec les graphes et les algorithmes. Ces notions sont centrales en informatique et sont très importantes pour un grand nombre d'applications concernant les réseaux de télécommunication (réseau sans fil, réseau optique, réseau du Web), les réseaux électriques, les réseaux routiers, en biologie (structurale) et pour résoudre un grand nombre de problèmes en général.

# data[].attributes.attachment_link.title
GALEJADE - Graphes et ALgorithmes : Ensemble de Jeux À Destination des Ecoliers... (mais pas que)

# data[].attributes.attachment_link.description
GALEJADE a pour vocation de familiariser élèves, professeurs et grand public avec les graphes et les algorithmes. Ces notions sont centrales en informatique et sont cruciales pour un grand nombre d'applications dans des domaines aussi divers que les réseaux, la biologie ou les sciences sociales.

# data[].attributes.attachment_link.readable_text
Licence CC BY-NC-SA
Lecture zen

Dans ce chapitre vous verrons la définition d'un graphe, ainsi que ses différentes caractéristiques remarquables.
Nous donnerons un premier aperçu des problèmes pouvant être identifiés comme des problèmes de graphe. Puis nous étudierons les deux principaux moyens de le stocker en mémoire.

Le graphe

Un graphe est un ensemble de points, dont certaines paires sont directement reliées par un (ou plusieurs) lien(s).

Wikipédia

Ces points sont nommés nœuds ou sommets. Ces liens sont nommés arêtes.

Notez bien que ces fameux points n'ont pas de position absolue dans le plan, ni de position relative les uns aux autres. De la même façon, les arêtes ne sont pas forcées d'être droites (bien que conventionnellement on les représente comme tel par soucis de lisibilité) : elles peuvent se croiser, être courbées ou faire des détours, etc... Ainsi un graphe n'est pas une figure, bien que l'on puisse représenter un graphe par une figure. Les graphes ne se cantonnent donc pas à des considérations d'ordre purement géométrique, bien au contraire !

En effet, un graphe sert avant tout à manipuler des concepts, et à établir un lien entre ces concepts. N'importe quel problème comportant des objets avec des relations entre ces objets peut être modélisé par un graphe.
Il apparaît donc que les graphes sont des outils très puissants et largement répandus qui se prêtent bien à la résolution de nombreux problèmes.

En voici quelques uns.

Une carte, un labyrinthe, un lieu... et la recherche de chemins

Il s'agit d'un cas très classique, notamment dans le domaine du jeu vidéo. Chaque nœud représente une position (ici une case libre) et chaque arête correspond à un chemin entre deux positions (ici deux cases libres adjacentes).
Il est courant de chercher le chemin le plus court entre deux positions : les IA s'en servent pour déplacer les créatures aussi vite que possible dans le monde virtuel. En remplaçant les nœuds par des adresses et les arêtes par des routes, on obtient le graphe utilisé par les GPS ou Google Map par exemple.
On utilise couramment le terme anglais pathfinding pour désigner la recherche de chemins dans un graphe.

Des relations entre individus

Cet outil est très utilisé en sciences sociales pour représenter des individus et leurs différents liens. On en fait usage dans le milieu de la recherche, mais aussi dans les réseaux sociaux. L'objectif va être de pouvoir identifier les communautés formées, les centres d'intérêt communs... Une exploitation intelligente de ces données est indispensable pour suggérer à l'utilisateur les choses qu'il est susceptible d'aimer, les personnes qu'il connaît peut-être, et avant tout (et surtout) pour créer des publicités ciblées adaptées à chacun.

Une anecdote à ce sujet : en moyenne seules 8 personnes vous séparent de n'importe quelle autre personne à la surface de la Terre. Si vous prenez la connaissance de la connaissance etc... d'une de vos connaissances, en moyenne 8 personnes permettront de vous connecter avec n'importe quel français, américain, indien ou japonais. Et il est rare de dépasser 11 ou 12. Il s'agit là du diamètre moyen du graphe social de l'humanité.

L'ordonnancement de tâches : le tri topologique

Les problèmes d'ordonnancement de tâches sont toujours un sujet de recherche active aujourd'hui. On peut représenter chacune des tâches à effectuer par un nœud, et les dépendances entre chacune des tâches par les arêtes. Ainsi, l'ordre dans lequel on enfile chaussettes et pantalon importe peu, mais il faut que les deux soient mis avant de lacer ses chaussures. De la même façon, on peut installer les câblages électrique et téléphonique dans l'ordre de notre choix, mais il faut que les murs soient construits avant !
On résout ce problème avec un tri topologique.

Minimiser l'usage de ressources avec les arbres couvrants minimaux

En parlant de câblage, vous souhaitez que toutes vos prises soient reliées au secteur, non ? Cela est simple ! Mais le fil électrique coûte cher au mètre et vous souhaitez minimiser le prix de votre installation.
Ainsi, vous associerez un nœud à chaque prise, et une arête à chaque fil qu'il est possible (mais pas nécessaire) d'installer. A vous de choisir l'ensemble de câbles les plus courts pour relier toutes les prises !
Cela correspond à la recherche de l'arbre couvrant minimal.

Ici l'ensemble de fils les plus courts est colorié en rouge.

Tromper votre ennui en géographie en coloriant des cartes

Vous vous ennuyez à mourir en géographie. Comme vous êtes un individu froid et austère, mais aussi efficace, économe et démuni, vous souhaitez colorier cette triste carte en utilisant un minimum de couleurs, et en faisant en sorte que deux pays limitrophes ne soient jamais de la même couleur.
Il s'agit du problème de coloration de graphe. Pour une carte en 2D ne cherchez plus : la réponse est 4, mais ce n'est pas le cas de tout les graphes... en effet, dans un carte, chaque pays est un nœud, et les arêtes correspondent au frontières communes.

Poster du courrier

Vous êtes le facteur d'un petit village, vous distribuez le courrier à vélo, à la seule force de vos jambes. Vous devez passer devant toutes les maisons du village, ce qui implique de traverser toutes les rues. Mais soucieux de préserver vos forces et de renouveler continuellement votre découverte des paysages, vous ne voulez pas traverser deux fois la même rue. Ici chaque nœud est un carrefour, et chaque arête une rue. Vous êtes en train de chercher un circuit Eulérien !

Il doit son nom à Leonhard Euler, qui chercha à savoir s'il était possible de franchir les 7 ponts de Königsberg sans jamais repasser deux fois sur le même (et en ne traversant le fleuve que grâce aux ponts, bien entendu).

...et tout le reste !

Pensez à Youtube qui suggère des vidéos proches de celle que vous regardez (d'aucun prétendent qu'on finira toujours par aboutir à des vidéos de chats), pensez à wikipédia qui propose des articles connexes (nous reviendrons sur ce terme), pensez au cerveau humain, à ses milliards de neurones et à ses centaines de milliards de connexions entre eux ! Les graphes sont partout.

Apprenez à reconnaître un problème de graphe lorsque vous en voyez un, c'est déjà la moitié du travail. Il ne vous reste alors plus qu'à trouver l'algorithme qui répond à votre problème !

Quelques conventions et notations...

Maintenant que nous avons une idée de ce qu'est un graphe, tâchons d'employer un vocabulaire précis pour traiter de chacune de ses caractéristiques. Certains algorithmes ne fonctionnent que sur des graphes possédant certaines particularités.

Pouvoir décrire en quelques mots les caractéristiques principales d'un graphe est donc indispensable, et vous devez toujours avoir le réflexe de le faire sitôt le graphe identifié. Cela vous guidera vers le choix de l'algorithme approprié.

Fixons d'ores et déjà quelques notations, par soucis de clarté. Ces notations sont conventionnellement utilisées dans la plupart des cours ou articles parlant de graphes.

L'ensemble des nœuds du graphe est désigné par $N$. L'ensemble des arêtes est désigné par $A$. Le graphe $G$ est simplement défini comme $G = (N,A)$. Ainsi, la représentation du graphe importe peu : les deux graphes ci-dessous sont isomorphes (ici, on peut traduire grossièrement ce terme barbare par équivalents).

Graphe simple ou multigraphe

Une boucle est une arête qui relie un nœud à lui même.
Un lien double caractérise l'existence de plusieurs arêtes entre deux nœuds donnés.
Un graphe possédant l'une ou l'autre de ces caractéristiques est dit multigraphe. Un graphe ne possédant aucune des deux est dit graphe simple.
Nous travaillerons exclusivement sur des graphes simples par soucis de simplicité : ils couvrent la plupart des utilisations, et sont plus simples à traiter que les multigraphes dans le cas général.

Connexité

Un graphe est dit connexe lorsqu'il existe un chemin entre toute paire de nœuds. Une composante connexe d'un graphe est un sous-graphe connexe de ce graphe. Un sous-graphe est un sous-ensemble de nœuds du graphe, avec une partie de leurs arêtes associées. Ainsi, sur le dessin ci-dessous, vous ne voyez qu'un seul et unique graphe, comportant 3 composantes connexes.

Graphes orientés et non-orientés

Voici une autre caractéristique fondamentale d'un graphe. Dans un graphe orienté les arêtes sont à sens unique. On les représente donc avec une flèche sur les dessins. D'ailleurs, le terme employé n'est plus arête, mais arc. Cette distinction est importante, car nombre d'algorithmes ne fonctionnent tout simplement pas sur des graphes orientés. Notez bien que cela n'empêche en rien que deux nœuds puissent être reliés dans les deux sens : il suffit d'utiliser deux arcs, chacun dans un sens (cela ne rompt pas la condition de graphe simple).

Graphes pondérés

Dans un graphe pondéré les arêtes (ou les arcs) sont, ben, pondérés, quoi. Autrement dit, on associe une valeur à chaque arête. Elles peuvent très bien être négatives.
Cela peut-être une distance : lorsque que l'on cherche un plus court chemin entre deux nœuds, il va de soit que la somme des pondérations des arêtes doit être aussi petit que possible.
Mais ça peut aussi être un réel dans $[0;1]$ pour désigner des probabilités dans les chaînes de Markov par exemple. Cela peut aussi être un score, un prix, etc. N'importe quelle quantité qui peut vous passer par la tête !

Graphes cycliques

Un graphe cyclique comporte au moins un cycle. Un cycle est un chemin qui permet de relier un nœud à lui même, sans jamais passer deux fois par la même arête. Un graphe comportant cette propriété peut-être orienté ou non orienté (indifféremment).
La détection de cycles est d'ailleurs un problème récurrent en informatique, notamment lorsqu'on s'intéresse aux dépendances d'un fichier ou d'un programme : A requiert B, B requiert C, et C requiert A est un cas de dépendances cyclique habituel.

Les graphes ne possédant pas de cycles dont dit acycliques. Il existe un sous-ensemble remarquable de graphes acycliques : les DAG (pour Directed Acyclic Graph); ce sont des graphes acycliques orientés. Les algorithmes dynamiques (nous verrons ça plus tard) ne peuvent travailler que sur des DAG.

Densité d'un graphe et degré d'un nœud

La densité d'un graphe correspond au rapport du nombre d'arêtes sur le nombre total d'arêtes possibles. C'est donc un réel compris entre $0$ et $1$. Cette caractéristique influe sur le choix de sa représentation.
Une densité de $0$ correspond à un graphe sans arêtes où tout les sommets sont isolés.
Une densité de 1 correspond à un graphe complet : chaque nœud est relié à chaque autre nœud.

Dans un graphe simple orienté de $N$ nœuds, chaque nœud ne peut être relié qu'à ses $N-1$ voisins au maximum, soit un total de $N(N-1)=N^2-N$ arcs.
Et $\frac{N^2-N}{2}$ arêtes dans le cas d'un graphe non orienté.

Le degré d'un nœud correspond au nombre d'arêtes reliées à ce nœud. Dans le cas d'un graphe orienté, le degré entrant d'un nœud est le nombre d'arcs qui aboutissent à ce nœud, et le degré sortant le nombre d'arcs qui partent de ce nœud.

De façon générale, lorsque le nombre d'arêtes d'un graphe est de l'ordre de $N$, le graphe est dit creux. Le degré moyen de ses nœuds est une constante. A l'inverse, lorsque le nombre d'arêtes est de l'ordre de $N^2$, le graphe est dit dense : le degré moyen de ses nœuds est de l'ordre de $N$.

Arbre

Un graphe est un arbre s'il vérifie les propriétés suivantes : il est acyclique, non orienté, et connexe. De cela il découle qu'il n'existe qu'un et un seul chemin entre deux nœuds donnés (c'est vraiment très pratique, je vous l'assure !).

Attardons sur quelques évidences. Un arbre possède une seule et unique racine. Il relié à d'autres nœuds - ses fils - par des branches (le terme arête demeure correct toutefois). Tout les nœuds peuvent posséder 0, 1 ou plusieurs fils. En revanche, ils possèdent tous un seul et unique père, à l'exception de la racine qui n'en a pas. Les feuilles sont caractérisées par l'absence de fils.

Un dessin pour mieux comprendre tout ce fouillis :

Comme vous pouvez le voir, les nœuds correspondent à des embranchements. Si on part d'un nœud et qu'on descend de fils en fils, on aboutira nécessairement à une feuille. Et si on remonte de père en pères, on aboutit à la racine (et dire qu'il y a encore des gens qui doutent du créationnisme !).

Si le graphe n'est pas connexe mais qu'il possède les propriétés cités ci-dessus, alors chacun des sous-graphes connexes est un arbre, et l'ensemble forme une forêt (ben oui, un ensemble d'arbres c'est une forêt).

Graphe biparti

Un graphe est biparti s'il est possibles de former deux partitions (comprendre, de le couper en deux morceaux distincts) de ses sommets de façon à ce que chaque arête passe d'une partition à l'autre, sans que jamais une arête ne relie deux nœuds dans la même partition.

Une fois encore, un joli dessin vaut tout les discours du monde.

J'imagine que l'intérêt doit vous paraître limité pour le moment. Mais les graphes bipartis servent dans plein de situations, et à pleins de choses différentes, comme représenter une relation binaire par exemple.

Remarquez qu'un arbre est forcément un graphe biparti. En effet, les nœuds à profondeur paire sont "pris en sandwich" entre des nœuds à profondeur impaire (son père et ses fils), et vice-versa. Ainsi deux nœuds à une profondeur de même parité ne seront jamais reliés par une arête, on peut donc former une partition contenant les nœuds de même parité.

Généralités

Maintenant, cher lecteur, nous avons une idée bien plus précise de ce qu'est un graphe. Mais il n'est pas destiné à rester un outil purement théorique ! Il faut pouvoir résoudre des problèmes avec, et donc implémenter des algorithmes qui travaillent dessus.

Nous devons donc trouver une structure de données adaptée pour le stocker, qui soit économe en mémoire, et qui permette aux algorithmes de l'exploiter rapidement.

Chaque nœud est stocké dans un tableau, une liste, ou n'importe quelle autre structure de données plus complexe (aucune contrainte particulière à ce propos, à vous de choisir la plus adaptée). Il est composé de propriétés, comme par exemple une position, une lettre, une valeur ou n'importe quelle entité plus complexe, qui dépend du problème (au cas par cas).

La difficulté consiste donc à lister intelligemment les arêtes entre les nœuds.
On résout ce problème avec une liste d'adjacence ou une matrice d'adjacence. La quasi totalité des implémentations d'un graphe sont des variantes de ces deux structures de données.

Attention ! La liste et la matrice ne sont pas seulement des structures de données, elles sont aussi une représentation du graphe.
La matrice et la liste contiennent suffisamment d'informations pour définir le graphe, au même titre que la représentation géométrique à base de sommets et d'arêtes.
Mais contrairement à cette dernière, qui est plus intuitive et plus adaptés aux êtres humains, la matrice et la liste peuvent être aisément implémentées sous forme de structure de données et utilisées par un programme.

La liste d'adjacence

La liste d'adjacence est le moyen le plus répandu pour stocker un graphe en mémoire : elle correspond à la représentation intuitive que l'on s'en fait. La liste d'adjacence d'un nœud est la liste de ses voisins (ou la liste des arêtes qui le relie à ses voisins).

Fin de la théorie.

Passons à la pratique : vous pouvez avoir, selon ce que vous propose votre langage, plusieurs moyens de stocker la liste des voisins.

1) Des indices et un tableau

C'est la façon la plus naturelle, et la plus triviale. Vous mettez tout vos nœuds dans un tableau, et la liste d'adjacence de chaque nœud contient l'indice de ses voisins. En raison de sa simplicité et de son expressivité, c'est l'implémentation qui sera utilisée dans la suite du tutoriel.

Voici un moyen d'itérer sur tout les voisins du nœud indexé par courant.

Le facteur constant d'accès à chaque voisin est très faible, ce qui vous permet de vous "promener" très rapidement dans le graphe. Vous pouvez généralement obtenir de très bonnes performances de cette façon.

Le seul inconvénient de cette méthode est de devoir disposer de l'intégralité du graphe dans la mémoire. Problématique si vos ressources en mémoire sont limitées, ou si pire, le graphe est de taille infinie !
Cela impose également que vous connaissiez dès le début l'ensemble du graphe, ce qui n'est pas toujours le cas : il en résulte une représentation figée qui interdit toute modification de certaines données (nombre de nœuds... ), et se limite à leur simple exploitation (ce qui demeure suffisant pour la plupart des algorithmes, en particulier tout ceux que nous étudierons).

2) Des hash et une table de hashage

Il s'agit de la version adaptée de l'implémentation précédente, pour palier à son principal défaut. Tout les nœuds que vous connaissez déjà sont stockés dans une table de hachage, et la liste d'adjacence de chaque nœud contient le hash de ses voisins. C'est généralement l'implémentation idéale pour un graphe dans lequel les arêtes entre chaque nœud sont définies par des règles précises, et non pas de manière purement arbitraire.

Prenons l'exemple du jeu d'échecs : en associant à un nœud à chaque position, on constate que les arêtes correspondent à chaque coup légal qui mène à une position légale elle aussi (le milieu des jeux de stratégie semble très policé). Ainsi, pour chaque nœud, on peut facilement lister ses voisins.

Il n'est pas possible de stocker autant de nœuds que de configurations du plateau : il en existe de l'ordre de $10^{50}$ !
Mais ce n'est pas un problème : jouer une partie revient à se promener dans ce graphe (c'est d'ailleurs un arbre), et il n'est en rien nécessaire d'énumérer tout les nœuds pour cela.

Le principal défaut de cette implémentation est le calcul des hashs : cela se fait en $O(1)$ en temps mais avec un facteur constant très important.

3) Des pointeurs

Cette implémentation est à réserver aux langages qui supportent ce concept (langages bas-niveaux essentiellement).

La liste d'adjacence contient des pointeurs vers chaque nœud voisin. Chaque nœud est alloué dynamiquement. Cela permet une représentation très souple du graphe : ajout et suppression de nœuds, et d'arêtes. Pour reprendre un précédent exemple : sur des réseaux sociaux des comptes peuvent être supprimés ou ajoutés, et on peut "aimer" ou "ne plus aimer" certaines choses, etc...

Cependant, la construction du graphe et son exploitation n'est pas facile : cette implémentation sujette aux bugs est à réserver aux cas dans lesquels elle est absolument nécessaire.

Conclusion

Voici quelques caractéristiques remarquables de la liste d'adjacence :

Complexité en mémoire : $O(N+A)$

Complexité en temps pour itérer sur tout les voisins d'un nœud : $O(d)$ avec $d$ le degré sortant du nœud

Ajout d'arête : $O(1)$

Retrait d'arête : $O(d)$ car il faut la retrouver avant de la supprimer

Tester si deux nœuds sont voisins : $O(d)$ car il faut itérer naïvement sur toutes les arêtes de l'un des deux nœuds

Variante :

Plutôt que d'utiliser une liste, vous pouvez utiliser un arbre binaire de recherche équilibré :

Ajouts et retraits d'arêtes en $O(\log{d})$

Tester si deux nœuds sont voisins en $O(\log{d})$
En effet les opérations pour retrouver les arêtes sont plus rapides, mais en contre-partie leur ajout est plus long. Cette optimisation n'est raisonnablement valable que lorsque le degré des nœuds devient important (en particulier, en dessous de 8 les gains sont souvent invisibles, mais des tests s'imposent en toutes circonstances, ne faites pas de cette indication une généralité !).

N'oubliez pas que la construction du graphe au préalable nécessite un ajout des arêtes une à une, soit ici une construction du graphe en $O(N)$ contre $O(N\log{N})$.

Choisissez l'implémentation la plus adaptée à votre problème, faites un compromis, ou inventez en d'autres...

La matrice d'adjacence

La matrice d'adjacence est un tableau en deux dimensions. Chacune des dimensions est indexée par les nœuds du graphe (typiquement de $0$ à $N-1$).
A l'intersection de chaque ligne et colonne on trouve un nombre : il vaut 1 si une arête relie les deux nœuds indexés par les coordonnées de la case, et 0 sinon.

On observe plusieurs choses intéressantes.

Les boucles reliant un nœud à lui même sont sur la diagonale de la matrice.

Cette matrice est symétrique par rapport à sa diagonale dans un graphe non-orienté (puisque si A est relié à B, alors B est relié à A).

Si le graphe ne comporte aucune arête, alors c'est la matrice nulle.

Si le graphe est creux, alors la matrice le sera aussi.

Pour $N$ nœuds, cette matrice est de taille $N\times N$. Soit une complexité de $O(N^2)$ en mémoire. Si votre langage le permet, vous pouvez stocker chacun des booléens sur un bit; il en résulte une consommation en mémoire de $\frac{N^2}{8}$ octets exactement, ce qui est très compact (incompressible dans le cas général).

Vous pouvez itérer sur tout les voisins d'un nœud en $O(N)$

En outre, à tout moment vous pouvez déterminer si deux nœuds sont voisins (c'est à dire reliés par une arête) en $O(1)$

Pour finir les ajouts et retraits d'arêtes se font en $O(1)$

Si cette représentation est couteuse pour un graphe creux (on lui préférera la liste d'adjacence), elle devient très rentable pour un graphe dense.
La densité est souvent le critère décisif du choix entre la matrice ou la liste.

Si le graphe est pondéré, vous pouvez remplacer les booléens par des nombres correspondant à la pondération de chaque arête. Et vous fixez une valeur spéciale pour signifier l'absence d'arête ($-1$, $0$ ou $\infty$ par exemple, selon les cas).

Les matrices d'adjacence sont particulièrement usitées lors de démonstrations sur un graphe, car la matrice est un outil mathématique bien connu.

Conclusion

Un petit tableau récapitulatif fera l'affaire.

Opérations

Liste d'adjacence

Matrice d'adjacence

Retirer une arête

$O(d)$ avec $d$ le degré du nœud

$O(1)$

Ajouter une arête

$O(1)$

$O(1)$

Itérer sur les voisins d'un nœud

$O(d)$ avec $d$ le degré du nœud

$O(N)$

Tester si deux nœuds sont voisins

$O(d)$ avec $d$ le degré du nœud

$O(1)$

Complexité mémoire

$O(N+A)$

$O(N^2)$

Autres représentations

Il existe bien d'autres représentations d'un graphe.

Citons particulièrement la matrice d'incidence.
C'est une matrice de dimensions $N\times A$ qui indique quels liens arrivent sur quels sommets.
A l'intersection d'une ligne correspondant à nœud et d'une colonne correspondant à une arête on trouve un nombre.
Il vaut $0$ si cette arête n'est pas reliée à ce nœud.
En revanche, si ce nœud est une extrémité de l'arête, ce coefficient diffère selon si le graphe considéré est orienté ou non.
Pour un graphe non orienté, cette valeur vaudra alors $1$ dans le cas général, et $2$ si cette arête réalise une boucle sur ce nœud (car ce nœud est deux fois l'extrémité de cette arête). Ainsi la somme des coefficients sur une colonne vaudra toujours 2.
Pour un graphe orienté ce coefficient vaut $-1$ si l'arc sort du nœud considéré, et $1$ lorsque l'arc entre dans le nœud.

La raison pour laquelle je ne vous l'ai pas proposée en structure de données est simple : ses performances sont en tout point inférieures à celles de la liste ou de la matrice d'adjacence, quelque soit l'opération considérée. La consommation en mémoire, du $O(N\times A)$, soit un $O(N^3)$ en pire des cas, est aberrante si le graphe est dense.

Alors, pourquoi cette représentation a été inventé, me direz-vous ?
Eh bien il se trouve que les graphes sont des objets mathématiques comme les autres, et leurs différentes représentations ont nécessairement des liens entres elles. Des relations relient la matrice d'incidence avec la matrice Laplacienne, la matrice d'adjacence, la matrice des degrés ou encore le line graph.
Cela sert dans des calculs, et occasionnellement dans certains algorithmes.

Il y a cependant trop de choses à dire sur chacun de ces sujets pour que je m'y risque ici. Les curieux pourront approfondir leurs recherches.

# data[].attributes.attachment_link.title
Graphes et représentation de graphe - À la découverte des algorithmes de graphe * Tutoriels * Zeste de Savoir

# data[].attributes.attachment_link.description
Licence CC BY-NC-SA Lecture zen Dans ce chapitre vous verrons la définition d'un graphe, ainsi que ses différentes caractéristiques remarquables. Nous donnerons un premier aperçu des problèmes pouvant être identifiés comme des problèmes de graphe. Puis nous étudierons les deux principaux moyens de le stocker en mémoire.

# data[].attributes.attachment_link.readable_text
Licence CC BY-NC-SA
Lecture zen

C'est bon ? Vous avez un graphe joli tout plein ? Il attend sagement dans la RAM que vous vous occupiez de lui ?

Vous êtes ici pour pouvoir - enfin ! - programmer vos premiers algorithmes de graphe.

Vous allez apprendre à explorer la bébête, avec le DFS, le BFS et l'exhaustif. Et avec la foultitude d'exemples que je vous donnerai, je vous promets que vous ne tarderez pas à découvrir le nombre incroyable de problèmes que ces simples algorithmes résolvent.

Préparez vous à plonger profondément dans l'univers des graphes.

Les pyramides

Aaaah l'Egypte ! Le soleil, le sable, le Nil ! Le Sphinx et son nez ! Les pyramides, leurs labyrinthes, et leurs... euh... labyrinthes.

Fidèle à la tradition familiale vous êtes devenu un pilleur de tombeaux. Vous n'êtes pas sans ignorer que la chambre funéraire recèle maints trésors, que vous avez hâte de vous approprier afin d'ouvrir le magasin de guimauve dont vous rêvez depuis votre enfance.

Sauf qu'aujourd'hui vous êtes tombé sur une pyramide très particulière, avec de nombreux carrefours... mais certains mènent à des pièges abominables, tellement abominables que je n'ose pas les décrire ici !

Vous disposez d'une carte du labyrinthe (remettant ainsi en cause l'utilité de ce dernier). Soucieux de ne pas prendre de risques superflus, vous confiez à votre ordinateur la dure tâche de trouver un itinéraire fiable.

Voici le plan :

Exercice : trouvez le graphe associé à ce problème. Trouvez ses caractéristiques principales. Trouvez quelle question on se pose sur ce graphe. Puis choisissez la structure de données qui vous semble la plus appropriée à la résolution du problème !

Commençons par le graphe.

Il apparaît clairement que chaque couloir est une arête.
Par conséquent les nœuds seront des intersections.

Certains nœuds sont particuliers.
Les entrées du labyrinthe : c'est de l'une d'entre elles que commence le chemin.
La chambre funéraire : c'est l'aboutissement d'un chemin (s'il existe).

Les salles piégées posent problème : elles existent mais nous ne pouvons pas les traverser. Deux solutions.

soit on ajoute ces nœuds particuliers au graphe, en précisant bien qu'ils sont piégés pour que l'algorithme les ignore (compliqué et désagréable à implémenter, plein de cas particuliers à gérer).

soit on les ignore purement et simplement lors de la construction du graphe, comme s'ils n'en faisaient pas parti (plus simple, plus propre).

Nous choisirons donc la seconde solution.
Et retenez de cela qu'il ne faut pas s'encombrer de superflu (un sérieux coup de pied dans les fesses de la société de consommation, pas vrai ?), la simplicité, l'expressivité et la concision sont les mots d'ordre du développeur. Cela vous évitera de tristes après-midis de débogage.

Labyrinthe simplifié

Passons aux caractéristiques du graphe.

Ce graphe est non orienté : vous pouvez traverser un couloir dans les deux sens, et même sur les mains si ça vous plaît.

Ce graphe est cyclique, car certains itinéraires tournent en rond (ah les fourbes !).

Ce graphe n'est pas pondéré. Certains objecteront qu'on peut associer à chaque couloir sa longueur, le coefficient de dureté du sol, l'âge de sa construction ou que sais-je encore. C'est vrai. Sauf qu'on s'en fout. On est pas ici pour trouver le chemin le plus respectueux pour vos pieds, donc ne nous encombrons pas de ces broutilles. Pas de superflu.

Ce graphe n'est pas connexe : vous ne pouvez pas accéder à n'importe quel endroit depuis n'importe quel autre endroit. On dénombre 2 composantes connexes d'ailleurs.

Ce graphe est creux : on a seulement 17 arêtes pour 18 nœuds (après suppression des nœuds piégés et des couloirs qui leur sont associés).

On choisira donc la liste d'adjacence pour stocker ce graphe !

Pour finir voici la question que l'on se pose.

Existe-t-il un chemin entre une entrée et la chambre funéraire ?
Autrement dit, la chambre funéraire est-elle connexe à au moins une entrée ?
Quel est ce chemin (ou l'un de ces chemins) ?

Le parcours en profondeur

Le DFS est la méthode la plus simple pour parcourir un graphe. Elle fonctionne sur tout type de graphe, cyclique ou non,orienté ou non, etc.

En langage naturel ça donne : je pars d'un endroit que je ne connais pas, je me dirige vers d'autres endroits que je ne connais pas, et quand je suis bloqué je fais demi-tour jusqu'à retrouver un chemin que je n'ai pas encore parcouru. Assez instinctif pas vrai ?

C'est la méthode que l'on utilise lorsqu'on est perdu, ou lorsqu'on visite un bâtiment : on essaie plusieurs chemins, et lorsqu'on est coincés on fait demi-tour jusqu'à la précédente intersection.

Voici sa description sous forme d'algorithme :

1) Je cherche un nœud non visité.

2) Pour visiter ce nœud, je marque le nœud comme visité.

3) Je prends l'un de ses voisins :

si le voisin a déjà été visité je l'ignore et je cherche un autre voisin

si le voisin n'a pas encore été visité, je le visite

si tout les voisins ont été visité, je reviens au nœud précédent, et je ré-applique le 3)

4) Je reprend le 1) tant qu'il reste des nœuds non visités

Vous avez remarqué ? Une boucle (de 4 à 1) englobe la totalité de l'algorithme. Cette condition d'arrêt ( tant qu'il reste des nœuds non visités) nous assure que l'entièreté du graphe sera exploré.
Il n'y a pas que ça : pour visiter un nœud, il faut aussi visiter l'un de ses voisins non visité. Un concept qui se renvoie à lui même pour se définir, ça ne vous fait penser à rien ? Mais si, la récursivité bien sûr !

Passons au pseudo-code.

Remarquez une chose : la fonction explorer fera autant d'appels à DFS qu'il existe de composantes connexes distinctes, dans un graphe non orienté. Le DFS est donc un bon moyen de retrouver les composantes connexes d'un graphe non orienté.
Si nous ne marquions pas les nœuds comme étant visités, nous nous mettrions à tourner en rond, dans le cas d'un graphe cyclique. Cela entraînerait donc des appels récursifs infinis, et notre programme ne se terminerait jamais ! Pour cette raison, le DFS est l'algorithme le plus adapté à la détection de cycles.

Vous comprenez maintenant l'origine du nom DFS : l'algorithme descend en profondeur dans le graphe, avant de faire demi-tour.
Sur le graphe ci-dessous l'ordre d'exploration pourra donc être : A - B - D - F - E - C - G

Voyons le problème sous un autre angle, et dessinons les arêtes empruntées par le DFS :

Arbre

Cela ne vous fait penser à rien ? C'est un arbre !
En effet, ce graphe ne comporte pas de cycles (puis que le DFS ne doit pas boucler).
Et on s'aperçoit que le DFS, de nature récursive, se prête bien au parcours de cette structure de données récursive : pour explorer un arbre, on explore sa racine puis les sous-arbres qui le composent.

Jetons un petit coup d'œil à la complexité en temps de cet algorithme.
On remarque que chaque nœud ne sera traité qu'une seule fois, et on a tôt fait de conclure (à tort) qu'il est en $O(N)$.
Sauf que... pour chaque nœud, on itère sur tout ses voisins (qu'un appel récursif soit fait dessus ou non).
D'où une complexité en temps de $O(N+A)$. On voit donc ici que le nombre de nœuds est fonction - de façon assez évidente - de la vitesse d'exécution, mais que la densité du graphe a elle aussi un rôle très important.
La complexité en mémoire dépend du nombre d'appels récursifs (qui font grossir la pile), et il peut y en avoir autant que de nœuds dans le graphe. La complexité en mémoire est donc $O(N)$. Le pire des cas correspond à un graphe sous la forme d'une liste de nœuds chaînés les uns à la suite des autres, là où la profondeur d'appel est maximale.

Le DFS tel que je vous l'ai présenté ici est assez "nu" mais il va sans dire qu'avec quelques modifications il est en mesure de résoudre un grand nombre de problèmes (ici déterminer si deux nœuds sont sur la même composante connexe). Nous verrons cela dans les chapitres suivants.

Que le DFS soit de nature récursive est autant un avantage qu'un inconvénient. Un avantage car beaucoup plus simple à lire, à écrire et à déboguer (lorsqu'on est à l'aise avec la récursivité). Mais un inconvénient car chaque appel récursif fait grossir la pile d'appel, qui possède une taille limitée dépendant de votre langage, de votre OS et de votre compilateur/interpréteur (souvent 1000 mais n'en faites pas une généralité). Si votre graphe est trop gros vous pourriez rencontrer d'importants problèmes de mémoire. La solution consiste à ré-implémenter le DFS en itératif en simulant la pile d'appel grâce à une pile LIFO.

Luke, je suis ton père

Normalement, vous disposez d'assez d'informations pour résoudre le problème à présent. Il suffit de modifier un peu la fonction DFS.
Ne regardez pas la solution avant d'avoir bien cherché !

Bon, récapitulons : si ce chemin existe, après l'avoir parcouru, il faut savoir le retrouver.
Remarquons deux choses : ce chemin, quel qu'il soit, reste le même quelque soit le sens dans le quel on l'emprunte; en outre, chaque nœud n'est visité qu'une et une seule fois, donc il n'existe qu'un seul moyen de parvenir à lui dans le DFS.
C'est directement en lien avec l'observation de tout à l'heure : le DFS explore un arbre, donc chaque nœud n'a qu'un seul père.
Il suffit donc de remonter dans l'arbre, depuis la chambre funéraire jusqu'à la racine (c'est à dire le premier appel à la fonction DFS sur cette composante connexe).
Et pour cela rien de plus simple : il faut que chaque nœud retienne qui est son père.

Si ce chemin existe il sera trouvé. Sinon, la fonction trouverChemin renverra la liste singleton [NUL] pour signifier l'absence de chemin.
Ci-dessous, un exemple de solution (pas forcément la plus courte).

Labyrinthe résolu

Et voilà ! Vous avez trouvé votre chemin. Mais n'oubliez pas : il y a une différence entre connaître le chemin et arpenter le chemin.

Big Buzz

Vous venez d'achever l'œuvre de votre vie : une vidéo si stupide qu'elle va rencontrer un succès incroyable.
Elle va faire le buzz, vous le savez : quiconque la voit ne pourra pas s'empêcher de la partager juste après. Personne n'y échappera, subjugué par tant de bêtise humaine.
Vous voulez suivre la progression de votre création sur le net, et en particulier vous souhaitez savoir combien de personnes en tout ont visionné votre vidéo au bout d'un certain nombre d'heures.

Vous êtes ami avec un employé de la NSA, ce qui vous permet d'obtenir une carte très détaillée de votre réseau social préféré, où vous voyez les liens entre chaque individu. Sitôt qu'un individu voit la vidéo, il la partage. Tous ses contacts la voient très exactement une heure après, puis la partagent immédiatement à leur tour, etc.

Vous êtes le point d'émission de la vidéo à l'heure 0, qui ira vers vos amis, puis les amis de vos amis... A partir du réseau social, vous souhaitez obtenir la liste triée des gens l'ayant vue, en fonction de l'heure.

Quel est le graphe ?

Bon là c'est assez explicite, un nœud pour chaque individu, et une arête pour chaque relation entre deux individus.
Ce graphe est :
1. cyclique
2. non orienté (l'amitié marche dans les deux sens normalement, mais si vous préférez un système avec des followers ce sera un graphe orienté)
3. non pondéré
4. pas forcément connexe car il est possible de trouver des communautés ou individus parfaitement isolés
5. creux (sauf quand tout le monde connait tout le monde, mais c'est rare).

On va donc, une fois de plus, utiliser une liste d'adjacence.
On veut obtenir la liste des nœuds en fonction de leur distance à un nœud particulier, le vôtre.

Le parcours en largeur

Le BFS est l'algorithme qui permet de parcourir tout les nœuds en fonction de leur distance à l'origine. Il explore les cartes par cercles concentriques de plus en plus grands. Il fonctionne sur tout type de graphe, cyclique ou non, orienté ou non, etc.

Le BFS procède de la façon suivante : il prend le premier nœud (distance 0), puis traite tout les nœuds qui sont à une distance de 1, puis tout les nœuds à une distance de 2, puis tout les nœuds à une distance de 3... et ainsi de suite.
On remarque très vite que les nœuds à une distance 1 de l'origine sont ses voisins, à une distance de 2 ce sont les voisins de ses voisins, à une distance 3 les voisins des voisins de ses voisins... de manière générale, un nœud à distance $n$ est : soit relié à des nœuds de distance $n-1$, soit des nœuds de distance $n$, soit des nœuds de distance $n+1$. Certainement pas plus : sinon il existerait un moyen plus rapide de rejoindre le nœud suivant; certainement pas moins, sinon le nœud courant aurait pu être atteint plus rapidement.
Si nous disposons de tout les nœuds à distance $n$, nous avons accès à tout les nœuds de distance $n+1$.
Dès le début on a accès au nœud de distance 0, donc en appliquant itérativement ce procédé on aura accès à tout les nœuds en fonction de leur distance à l'origine (s'ils sont connexes à elle).

Si vous ignorez ce qu'est une file FIFO, il n'est pas trop tard !

Voici l'algorithme :

1) Je prend le premier nœud de la file d'attente des nœuds à traiter.

2) Pour visiter ce nœud je le marque comme visité.

3) Je prend chacun de ses voisins non visités et je les ajoute à la fin de la file d'attente des nœuds à visiter

4) Je reprends le 1) tant qu'il reste des nœuds à traiter dans la file d'attente

Voici le pseudo code correspondant :

Cet algorithme fonctionne, je vous le promet !
Il commence par enfiler l'origine à distance 0, puis tout les nœuds 1, puis pour chaque nœud à distance 1 il va enfiler d'autres nœuds à la distance 2 (à la suite des nœuds à distance 1 donc), puis il défilera les nœuds à distance 2 pour enfiler des nœuds à distance 3 à leur suite.
Ainsi les nœuds ne sont jamais mélangés : ils sont présents dans la file par "paquets" consécutifs qui correspondent à leur distance à l'origine.

Sur un arbre, il explore les nœuds en fonction de leur hauteur (distance à la racine) contrairement au DFS qui va effectuer toutes les descentes possibles de la racine à une feuille. Ainsi, l'ordre d'exploration des nœuds du graphe ci-dessous pourra être : A - B - C - E - D - F - G. Comme vous pouvez le constater, tout les nœuds frères sont parcourus les uns à la suite des autres, la racine étant l'origine du BFS.

Et que se passera-t-il si d'aventure nous remplacions la file par une pile ? On retrouve la version itérative du DFS présentée à la section précédente !
Il apparaît donc qu'il y a un lien important entre algorithme et structure de données. L'écriture sous forme itérative ou récursive dépend essentiellement de facteurs comme la lisibilité, la manière de laquelle l'algorithme s'explique le mieux, et enfin les performances.

Tout comme pour le DFS, la complexité en temps est en $O(N+A)$. Une fois encore la densité du graphe influe beaucoup sur les performances de l'algorithme.
La file peut contenir autant de nœuds que le graphe en possède, d'où une complexité en mémoire de $O(N)$. Le pire des cas concerne un graphe de diamètre très faible : la file est encombrée par la présence des nombreux nœuds à distance égale de l'origine.

Le BFS peut servir à détecter les composantes connexes d'un graphe (tout comme le DFS), si plusieurs appels à la fonction BFS() sont réalisés avec des origines différentes. Mais le BFS a un avantage sur le DFS lors de la recherche de composantes connexes : il trouve le plus court chemin entre ces deux nœuds (s'il existe) dans le cas d'un graphe non pondéré.
Dans le cas d'un graphe implicite de taille infini (ou de très très grande taille) le DFS risque de s'engager dans une mauvaise voie dans le début et de s'y enfoncer trop profondément, voir à l'infini ! Impossible de déterminer en un temps raisonnable (ou un temps fini) un chemin entre deux nœuds connexes, alors que le BFS va explorer plusieurs chemins possibles à la fois, ce qui lui donne l'assurance de trouver un jour ce chemin. Pour cette raison les graphes implicites de grande taille sont souvent parcouru par un BFS plutôt qu'un DFS.
Mais le BFS peut aussi servir à marquer les nœuds en fonction de leur distance à l'origine. C'est ce que nous allons voir tout de suite !

Le prix du succès

Une petite modification suffit à la résolution du problème.

Ci-dessous, vous pouvez voir l'effet de cet algorithme sur un graphe simple. Les nœuds sont marqués en fonction de leur ordre de visite par le BFS : le nœud n°1 correspond donc à l'origine. Les nœuds en cours de visite (c'est à dire présents dans la file) sont coloriés en bleu. Les nœuds déjà visités et extraits de la file sont coloriés en vert. Ici, tout les nœuds à distance 2 ou moins ont été explorés. Les nœuds à distance 3 sont en cours d'exploration. Le seul nœud à distance 4 n'a pas encore été traité.

Et voilà. Vous pouvez également indiquer le nombre total de gens ayant vu la vidéo à chaque heure, je vous laisse le coder vous même, ce n'est pas très difficile.

Connaissez-vous Uno$^{TM}$ ?

Comme nous l'explique si bien Wikipédia, c'est un jeu de carte américain créé en 1971 par Merle Robbins. Il est pourvu de pleins de règles subtiles et de cartes agressives pour faire rager les petits comme les grands.

Aujourd'hui, je ne vous propose pas de programmer ce célèbre jeu. A la place je vous propose plutôt de résoudre ce petit problème.

Dans Uno, chaque joueur possède un certain nombre de cartes en main, qui peuvent être de 4 couleurs : bleues, vertes, rouges ou jaunes.
Elles sont numérotées de 0 à 9.
Il existe également certaines cartes spéciales ("Joker", "Inversion", "Super Joker"...) mais nous ne y intéresserons pas ici, par soucis de simplicité.

Le jeu comporte un talon. On ne peut poser une carte sur le sommet de ce talon que si la carte au sommet du talon est :

De même couleur que la carte qu'on joue

De même valeur faciale que la carte qu'on joue

Un petit exemple :

poser un 7 rouge sur un 9 rouge est autorisé

poser un 4 vert sur un 4 bleu est autorisé

poser un 2 jaune sur un 2 jaune est autorisé

poser un 6 bleu sur un 3 vert est interdit

Il est ainsi possible d'empiler ces cartes de diverses façons en suivant ces règles, pour obtenir un talon plus ou moins haut.

Comme vous n'avez rien de mieux à faire, vous voulez savoir, à partir d'un ensemble de cartes donné, quels sont tout les talons qu'il est possible de réaliser avec. Les cartes qui ne pourront pas être ajoutées au talon seront éventuellement laissées sur le côté.
Vous pouvez empiler les cartes de votre choix dans n'importe quel ordre, tant que vous respectez les règles.

Exercice : vous commencez à le connaître par cœur normalement.
Quel est le graphe ? Quels sont ses caractéristiques ? Quelle question se pose-t-on sur lui ?

Correction :

Rappelez-vous : un graphe représente des objets et des relations entre ces objets.
Ici chaque objet, chaque nœud, est donc une carte. Les arêtes sont définies par une valeur faciale ou une couleur commune. C'est donc un bon exemple de graphe dans lequel les arêtes peuvent être déduites du nœud à partir de certaines règles de construction simples.

Ce graphe est cyclique. Certes, on ne peut pas utiliser une même carte plus d'une fois, mais il y a plus d'une manière de poser une carte, qui aboutira à d'autres situations où il serait ensuite théoriquement valide de poser cette carte si elle n'avait pas déjà été jouée.

Ce graphe est non orienté. L'ordre dans lequel sont empilés les cartes n'a pas d'importance, puisque les règles ne s'intéressent qu'à la relation d'adjacence de deux cartes, indépendamment de leur ordre.

Ce graphe est non pondéré (sapristi, un de plus !).

Une fois encore, ce graphe n'est pas nécessairement connexe. Il est parfois possible de former deux groupes de cartes n'ayant aucune couleur ou aucun numéro en commun.

Ce graphe est dense, selon moi. En effet il n'y a pas de caractérisation formelle entre un graphe dense et un graphe qui ne l'est pas, c'est laissé à l'appréciation de chacun. Laissez moi vous expliquer ma démarche.
En supposant que l'on ait beaucoup de cartes, disons $N$, et qu'elles soient toutes tirées au hasard : en moyenne nous aurons $\frac{N}{4}$ cartes de chaque couleur (car il y a 4 couleurs).
Toutes les cartes de même couleur seront au moins reliées entre elles. Donc, en moyenne, chaque carte sera reliées à au moins $\frac{N}{4}$ autres cartes.
Chaque carte est aussi reliée à un $\frac{1}{10}$ (car 10 chiffres) des cartes des 3 autres couleurs, soit $\frac{3\times N}{40}$ autres cartes en moyenne.
Cela fait une moyenne de $0,325\times N$ arêtes par nœud. Le degré de chaque nœud n'est pas constant : il dépend de $N$.
Ce qui porte le total à environ $0,162\times N^2$ arêtes, car c'est un graphe non orienté (il ne faut pas compter deux fois chaque arête).
Le nombre d'arêtes du graphe est fonction de $N^2$. On peut donc qualifier ce graphe de dense.
Et il est suffisamment dense pour rendre la matrice d'adjacence plus intéressante que la liste.

Voici le graphe associé à un ensemble de 20 cartes (5 de chaque couleur).

En théorie chaque carte devrait être reliée à elle même. Mais comme on ne peut pas utiliser deux fois la même carte (ce qui n'empêche pas celle-ci d'être présente en plusieurs exemplaires dans le jeu de départ), on sait d'avance que ces arêtes (qu'on nomme boucle) ne nous serviront pas. Autant les supprimer maintenant.

On souhaite connaître quels sont tout les talons possibles. Un talon est caractérisé par un ensemble de cartes dans un certain ordre. Et les contraintes d'adjacence de deux cartes sont celles des arêtes du graphe !
Par conséquent, chaque talon peut être représenté par un chemin du graphe : l'ordre de visite des nœuds et la taille du chemin suffit à définir le talon.
Pour générer tout les talons possibles, il faut donc générer tout les chemins du graphe !

L'exhaustif

Exhaustif : qui inclut tous les éléments possibles d'une liste, qui traite totalement un sujet.

Wiktionnaire

Nous cherchons une liste de tout les talons possibles, sans en oublier aucun. Il nous faut donc une liste exhaustive des talons possibles.
Cela nécessite un algorithme capable d'effectuer une énumération exhaustive de tout les chemins du graphe. D'où le nom "exhaustif".
Il faut trouver une méthode systématique pour dénombrer les chemins du graphe.

Comment procéderions-nous "à la main" ?

Par exemple, nous pourrions prendre une carte et l'ajouter au talon. Puis prendre une autre carte et l'ajouter au talon (en respectant les règles). Puis continuer à ajouter des cartes qu'il est possible d'en ajouter, sans réutiliser deux fois la même (évidemment).
Et lorsqu'on est bloqué ? Une retire une carte au sommet du talon et on met une autre à la place, et c'est reparti !
On continue d'ajouter des cartes jusqu'à ce qu'on soit forcé d'en retirer une au sommet pour la remplacer par une autre qui n'a pas déjà été posée à cette hauteur et avec ce talon spécifique en dessous.
Ainsi, à la fin, tout les talons auront été construits.

Vous avez remarqué ? Un talon est une pile, donc nous aurons sûrement affaire à une pile dans cet algorithme !

En voici le pseudo-code :

Sans grande surprise, ici, la pile est la pile d'appel. Mais une fois encore, cet algorithme peut être passé sous forme itérative si le besoin s'en fait sentir.

Cette fonction ressemble beaucoup à celle du DFS, à deux exceptions près.
Premièrement, elle retourne quelque chose : la liste des chemins.
Secondement, et c'est là le point le plus important : l'état d'un nœud n'est pas définitivement fixé. A l'entrée de la fonction le nœud est marqué comme "utilisé"; en revanche, à la sortie de la fonction, il est de nouveau marqué comme "inutilisé".
Ainsi, la fonction exhaustif va pouvoir traiter plusieurs fois le même nœud, ce qui est somme-toute logique puisque qu'un même nœud peut faire parti de plusieurs chemins distincts. L'importance de marquer un nœud comme utilisé durant son utilisation (comme les toilettes publiques à verrou coloré) est la même que celle du DFS : empêcher les appels récursifs infinis en bouclant dans un cycle.

Sur le graphe ci-dessous, après un appel sur le nœud A, l'ordre d'exploration des nœuds pourrait être : A - B - D - F - E - C - G - E - F - B - D.

Cela générerait les chemins suivants :

A

A - B

A - B - D

A - B - F

A - B - F - E

A - C

A - C - G

A - E

A - E - F

A - E - F - B

A - E - F - B - D

Et cela juste avec le nœud A comme origine ! Je vous épargne les autres.

Comme vous pouvez le constater le nombre de chemins différents augmente très vite et atteint un nombre important, même sur un graphe de petite taille.

Ce qui nous amène tout de suite à une question épineuse : quelle est la complexité en temps et en mémoire de l'algorithme ?

Commençons par la complexité en temps.
Quel est le pire des cas ?
Le pire des cas serait un jeu de carte où toutes les cartes sont reliées entre elles (typiquement : toutes de même couleur), ce qui revient à travailler sur un graphe complet.
Ainsi, je dispose de $N$ choix pour le premier élément du talon. Puis de $N-1$ pour le second. Puis de $N-2$ pour le troisième, et ainsi de suite. Le nombre de talons possible est donc égal à $N \times (N-1) \times (N-2) \times ... \times 2 \times 1 = N!$
En fait, toutes les permutations de cartes sont possibles (puisque toutes les cartes peuvent être adjacentes). Et le nombre de permutations de $N$ éléments est bien égal à $N!$.
Cet algorithme est donc en $O(N!)$ en temps.
La fonction factorielle croit asymptotiquement plus vite que la fonction exponentielle. Pour cette raison, même sur des instances de petite taille, certains problèmes sont insolubles en un temps raisonnable.

Pour vous faire une idée, 20! = 2 432 902 008 176 640 000. Donc si le graphe ci-dessus était complet, il faudrait plusieurs dizaines de milliers d'années de calcul. Heureusement il ne l'est pas ! De mon côté j'ai trouvé 437 672 443 chemins différents (vous pouvez vérifier si l'envie vous en prend).

Quant à la complexité en mémoire, elle est nécessairement $O(N!)$ elle aussi, puisqu'il s'agit là du nombre de solutions.
Cependant, si vous n'aviez qu'à dénombrer les solutions (sans les produire), vous auriez alors un algorithme en $O(N)$, car la profondeur de récursion peut atteindre N nœuds.

La recherche exhaustive, bien que donnant des résultat exacts de par son exhaustivité, ne peut pas être utilisée en pratique pour tout les problèmes, à cause de sa lenteur.
Pour cette raison, de nombreux problèmes sont résolus avec des algorithmes donnant une réponse approchée (ou exacte mais dont on ne peut pas prouver qu'elle est exacte) qui ont une durée d'exécution plus courte. Ces algorithmes sont des sujets de recherche encore actifs qui mériteraient un tutoriel entier à eux seuls, donc nous n'en parlerons pas plus ici.

# data[].attributes.attachment_link.title
Parcourir un graphe - À la découverte des algorithmes de graphe * Tutoriels * Zeste de Savoir

# data[].attributes.attachment_link.description
Licence CC BY-NC-SA Lecture zen C'est bon ? Vous avez un graphe joli tout plein ? Il attend sagement dans la RAM que vous vous occupiez de lui ? Vous êtes ici pour pouvoir - enfin ! - programmer vos premiers algorithmes de graphe.

# data[].attributes.attachment_link.readable_text
Created 26 May 2014, updated Aug 2014, Feb 2016, Jun 2016, Jun 2020

In games we often want to find paths from one location to another. We're not only trying to find the shortest distance; we also want to take into account travel time. Move the blob (start point) and cross (end point) to see the shortest path.

To find this path we can use a graph search algorithm, which works when the map is represented as a graph. A* is a popular choice for graph search. Breadth First Search is the simplest of the graph search algorithms, so let's start there, and we'll work our way up to A*.

The first thing to do when studying an algorithm is to understand the data. What is the input? What is the output?

Input: Graph search algorithms, including A*, take a "graph" as input. A graph is a set of locations ("nodes") and the connections ("edges") between them. Here's the graph I gave to A*:

Sprites by StarRaven - see footer for link

A* doesn't see anything else. It only sees the graph. It doesn't know whether something is indoors or outdoors, or if it's a room or a doorway, or how big an area is. It only sees the graph! It doesn't know the difference between this map and this other one.

Output: The path found by A* is made of graph nodes and edges. The edges are abstract mathematical concepts. A* will tell you to move from one location to another but it won't tell you how. Remember that it doesn't know anything about rooms or doors; all it sees is the graph. You'll have to decide whether a graph edge returned by A* means moving from tile to tile or walking in a straight line or opening a door or swimming or running along a curved path.

Tradeoffs: For any given game map, there are many different ways of making a pathfinding graph to give to A*. The above map makes most doorways into nodes; what if we made doorways into edges? What if we used a pathfinding grid?

The pathfinding graph doesn't have to be the same as what your game map uses. A grid game map can use a non-grid pathfinding graph, or vice versa. A* runs fastest with the fewest graph nodes; grids are often easier to work with but result in lots of nodes. This page covers the A* algorithm but not graph design; see my other page[1] for more about graphs. For the explanations on the rest of the page, I'm going to use grids because it's easier to visualize the concepts.

There are lots of algorithms that run on graphs. I'm going to cover these:

Breadth First Search explores equally in all directions. This is an incredibly useful algorithm, not only for regular path finding, but also for procedural map generation, flow field pathfinding, distance maps, and other types of map analysis.

Dijkstra's Algorithm (also called Uniform Cost Search) lets us prioritize which paths to explore. Instead of exploring all possible paths equally, it favors lower cost paths. We can assign lower costs to encourage moving on roads, higher costs to avoid forests, higher costs to discourage going near enemies, and more. When movement costs vary, we use this instead of Breadth First Search.

A* is a modification of Dijkstra's Algorithm that is optimized for a single destination. Dijkstra's Algorithm can find paths to all locations; A* finds paths to one location, or the closest of several locations. It prioritizes paths that seem to be leading closer to a goal.

I'll start with the simplest, Breadth First Search, and add one feature at a time to turn it into A*.

The key idea for all of these algorithms is that we keep track of an expanding ring called the frontier. On a grid, this process is sometimes called "flood fill", but the same technique also works for non-grids. Start the animation to see how the frontier expands →→

How do we implement this? Repeat these steps until the frontier is empty:

Pick and remove a location from the frontier. →

Expand it by looking at its neighbors . Skip walls. Any unreached neighbors we add to both the frontier and the reached set → .

Let's see this up close. The tile are numbered in the order we visit them. Step through to see the expansion process:

It's only ten lines of (Python) code:

frontier = Queue()
frontier.put(start )
reached = set()
reached.add(start)

while not frontier.empty():
   current = frontier.get()
   for next in graph.neighbors(current):
      if next not in reached:
         frontier.put(next)
         reached.add(next)

This loop is the essence of the graph search algorithms on this page, including A*. But how do we find the shortest path? The loop doesn't actually construct the paths; it only tells us how to visit everything on the map. That's because Breadth First Search can be used for a lot more than just finding paths; in this article I show how it's used for tower defense, but it can also be used for distance maps, procedural map generation, and lots of other things. Here though we want to use it for finding paths, so let's modify the loop to keep track of where we came from for every location that's been reached, and rename the reached set to a came_from table (the keys of the table are the reached set):

frontier = Queue()
frontier.put(start )
came_from = dict()came_from[start] = None while not frontier.empty(): current = frontier.get() for next in graph.neighbors(current): if next not incame_from: frontier.put(next)came_from[next] = current

Now came_from for each location points to the place where we came from. These are like "breadcrumbs". They're enough to reconstruct the entire path. Move the cross to see how following the arrows gives you a reverse path back to the start position.

The code to reconstruct paths is simple: follow the arrows backwards from the goal to the start. A path is a sequence of edges, but often it's easier to store the nodes:

current = goal
path = []
while current != start:
   path.append(current)
   current = came_from[current]
path.append(start) # optional
path.reverse() # optional

That's the simplest pathfinding algorithm. It works not only on grids as shown here but on any sort of graph structure. In a dungeon, graph locations could be rooms and graph edges the doorways between them. In a platformer, graph locations could be locations and graph edges the possible actions such as move left, move right, jump up, jump down. In general, think of the graph as states and actions that change state. I have more written about map representation here[2]. In the rest of the article I'll continue using examples with grids, and explore why you might use variants of breadth first search.

We've found paths from one location to all other locations. Often we don't need all the paths; we only need a path from one location to one other location. We can stop expanding the frontier as soon as we've found our goal. Drag the around see how the frontier stops expanding as soon as it reaches the goal.

Without early exit

With early exit

The code is straightforward:

frontier = Queue()
frontier.put(start )
came_from = dict()
came_from[start] = None

while not frontier.empty():
   current = frontier.get()

if current == goal: break  for next in graph.neighbors(current): if next not in came_from: frontier.put(next) came_from[next] = current

There are lots of cool things you can do with early exit conditions.

So far we've made step have the same "cost". In some pathfinding scenarios there are different costs for different types of movement. For example in Civilization, moving through plains or desert might cost 1 move-point but moving through forest or hills might cost 5 move-points. In the map at the top of the page, walking through water cost 10 times as much as walking through grass. Another example is diagonal movement on a grid that costs more than axial movement. We'd like the pathfinder to take these costs into account. Let's compare the number of steps from the start with the distance from the start:

For this we want Dijkstra's Algorithm (or Uniform Cost Search). How does it differ from Breadth First Search? We need to track movement costs, so let's add a new variable, cost_so_far, to keep track of the total movement cost from the start location. We want to take the movement costs into account when deciding how to evaluate locations; let's turn our queue into a priority queue. Less obviously, we may end up visiting a location multiple times, with different costs, so we need to alter the logic a little bit. Instead of adding a location to the frontier if the location has never been reached, we'll add it if the new path to the location is better than the best previous path.

frontier =PriorityQueue() frontier.put(start, 0) came_from = dict() cost_so_far = dict() came_from[start] = None cost_so_far[start] = 0 while not frontier.empty(): current = frontier.get() if current == goal: break for next in graph.neighbors(current):new_cost = cost_so_far[current] + graph.cost(current, next)if next not in cost_so_far or new_cost < cost_so_far[next]: cost_so_far[next] =new_costpriority = new_cost frontier.put(next, priority) came_from[next] = current

Using a priority queue instead of a regular queue changes the way the frontier expands. Contour lines are one way to see this. Start the animation to see how the frontier expands more slowly through the forests, finding the shortest path around the central forest instead of through it:

Breadth First Search

Dijkstra's Algorithm

Movement costs other than 1 allow us to explore more interesting graphs, not only grids. In the map at the top of the page, movement costs were based on the distance from room to room. Movement costs can also be used to avoid or prefer areas based on proximity to enemies or allies.

Implementation notes: We want this priority queue to return the lowest value first. On the implementation page I show PriorityQueue in Python using heapq to return the lowest value first and also in C++ using std::priority_queue configured to return the lowest value first. Also, the version of Dijkstra's Algorithm and A* I present on this page differs from what's in algorithms textbooks. It's much closer to what's called Uniform Cost Search. I describe the differences on the implementation page.

With Breadth First Search and Dijkstra's Algorithm, the frontier expands in all directions. This is a reasonable choice if you're trying to find a path to all locations or to many locations. However, a common case is to find a path to only one location. Let's make the frontier expand towards the goal more than it expands in other directions. First, we'll define a heuristic function that tells us how close we are to the goal:

def heuristic(a, b):
   # Manhattan distance on a square grid
   return abs(a.x - b.x) + abs(a.y - b.y)

In Dijkstra's Algorithm we used the actual distance from the start for the priority queue ordering. Here instead, in Greedy Best First Search, we'll use the estimated distance to the goal for the priority queue ordering. The location closest to the goal will be explored first. The code uses the priority queue from Dijkstra's Algorithm but without cost_so_far:

frontier = PriorityQueue()
frontier.put(start, 0)
came_from = dict()
came_from[start] = None

while not frontier.empty():
   current = frontier.get()

   if current == goal:
      break

   for next in graph.neighbors(current):
      if next not in came_from:
priority = heuristic(goal, next) frontier.put(next, priority) came_from[next] = current

Let's see how well it works:

Dijkstra's Algorithm

Greedy Best-First Search

Wow!! Amazing, right? But what happens in a more complex map?

Dijkstra's Algorithm

Greedy Best-First Search

Those paths aren't the shortest. So this algorithm runs faster when there aren't a lot of obstacles, but the paths aren't as good. Can we fix this? Yes!

Dijkstra's Algorithm works well to find the shortest path, but it wastes time exploring in directions that aren't promising. Greedy Best First Search explores in promising directions but it may not find the shortest path. The A* algorithm uses both the actual distance from the start and the estimated distance to the goal.

The code is very similar to Dijkstra's Algorithm:

frontier = PriorityQueue()
frontier.put(start, 0)
came_from = dict()
cost_so_far = dict()
came_from[start] = None
cost_so_far[start] = 0

while not frontier.empty():
   current = frontier.get()

   if current == goal:
      break

   for next in graph.neighbors(current):
      new_cost = cost_so_far[current] + graph.cost(current, next)
      if next not in cost_so_far or new_cost < cost_so_far[next]:
         cost_so_far[next] = new_cost
         priority = new_cost + heuristic(goal, next) frontier.put(next, priority) came_from[next] = current

Compare the algorithms: Dijkstra's Algorithm calculates the distance from the start point. Greedy Best-First Search estimates the distance to the goal point. A* is using the sum of those two distances.

Dijkstra's Algorithm

Greedy Best-First

A* Search

Try opening a hole in the wall in various places. You'll find that when Greedy Best-First Search finds the right answer, A* finds it too, exploring the same area. When Greedy Best-First Search finds the wrong answer (longer path), A* finds the right answer, like Dijkstra's Algorithm does, but still explores less than Dijkstra's Algorithm does.

A* is the best of both worlds. As long as the heuristic does not overestimate distances, A* finds an optimal path, like Dijkstra's Algorithm does. A* uses the heuristic to reorder the nodes so that it's more likely that the goal node will be encountered sooner.

And ... that's it! That's the A* algorithm.

Are you ready to implement this? Consider using an existing library. If you're implementing it yourself, I have companion guide that shows step by step how to implement graphs, queues, and pathfinding algorithms in Python, C++, and C#.

Which algorithm should you use for finding paths on a game map?

If you want to find paths from or to all all locations, use Breadth First Search or Dijkstra's Algorithm. Use Breadth First Search if movement costs are all the same; use Dijkstra's Algorithm if movement costs vary.

If you want to find paths to one location, or the closest of several goals, use Greedy Best First Search or A*. Prefer A* in most cases. When you're tempted to use Greedy Best First Search, consider using A* with an "inadmissible" heuristic[3].

What about optimal paths? Breadth First Search and Dijkstra's Algorithm are guaranteed to find the shortest path given the input graph. Greedy Best First Search is not. A* is guaranteed to find the shortest path if the heuristic is never larger than the true distance. As the heuristic becomes smaller, A* turns into Dijkstra's Algorithm. As the heuristic becomes larger, A* turns into Greedy Best First Search.

What about performance? The best thing to do is to eliminate unnecessary locations in your graph. If using a grid, see this. Reducing the size of the graph helps all the graph search algorithms. After that, use the simplest algorithm you can; simpler queues run faster. Greedy Best First Search typically runs faster than Dijkstra's Algorithm but doesn't produce optimal paths. A* is a good choice for most pathfinding needs.

What about non-maps? I show maps here because I think it's easier to understand how the algorithms work by using a map. However, these graph search algorithms can be used on any sort of graph, not only game maps, and I've tried to present the algorithm code in a way that's independent of 2d grids. Movement costs on the maps become arbitrary weights on graph edges. The heuristics don't translate as easily to arbitrary maps; you have to design a heuristic for each type of graph. For planar maps, distances are a good choice, so that's what I've used here.

I have lots more written about pathfinding here[4]. Keep in mind that graph search is only one part of what you will need. A* doesn't itself handle things like cooperative movement, moving obstacles, map changes, evaluation of dangerous areas, formations, turn radius, object sizes, animation, path smoothing, or lots of other topics.

# data[].attributes.attachment_link.description
Created 26 May 2014, updated Aug 2014, Feb 2016, Jun 2016, Jun 2020 In games we often want to find paths from one location to another. We're not only trying to find the shortest distance; we also want to take into account travel time.

# data[].attributes.attachment_link.readable_text
How to represent a graph in Python ?

Dedicated class

Some libraries use a class to represent graphs. For example the very complete Python library NetworkX provides a class for direction graphs ( DiGraph) and for undirected graphs ( Graph). Each class has methods to add nodes ( add_node), and edges (respectively arcs) ( add_edge), as well as a method to iterate over all neighbors of a vertex ( neighbor), for a directed graph to iterate over the endpoints of incoming or outgoing arcs ( predecessors and successors).

The iGraph library also provides a class to represent graphs and is particular useful to visualize them and to read and write graphs to files in various formats.

Dictionary

The Python Algorithms and Datastructures library by David Epstein made the choice of using simply a dictionary to represent graphs. The keys are nodes, and could be for example strings, and the values are adjacency lists. Consider the following example graph.

A dictionary adjacency list representation of this graph would like follows.

This graph representation leads to quite elegant code. Looping over all nodes in the graph is done by for v in G and looping over all neighbors simply by for u in G[v]. Edge weights need to be stored in a separate structure such that weight[v][u] is the weight of the edge (v,u). Such a structure would simply be a dictionary of dictionaries.

Lists

However in the tryalgo library we choose to work with integer identifiers. One of the reason is efficiency and the other one is that the resulting code could be easier translated into C++. So the vertices of a graph with n nodes will be numbered from 0 to n-1. With such a numbering the graph above could have the following identifiers.

The advantage of this representation is that we can use a list instead of a dictionary and gain some access time. Even if accesses to a dictionary are in linear time in the worst case (which almost never happens), the practical access time is constant. But this constant is bigger than the access to an element of a Python list. Vertex labels have to be stored in a separate table, associating the vertex identifier to its label.

The above graph would be represented in Python as follows.

Again, edge weights are stored in a separate data structure, with the same syntax as for the dictionary, such that weight[u][v] is the weight of the edge (u,v). This time the edge weights can be represented as lists of lists, as you represent a 2-dimensional array in Python. If the graph is sparse one could as well use a lists of dictionaries to store edge weights.

Mapping vertex names to identifiers

However in many applications we would like to name vertices by strings or tuples, rather than identifiers. An example is given in the next section. For this purpose we propose to use a class Graph that permits to maintaining the mapping between vertex names and vertex identifiers.

The method add_node(name) adds a new vertex to the graph with a given name, and returns the corresponding identifier. It is assumed that the graph does not have another vertex with the same name.

The method add_edge(name_u, name_v, weight_uv=None) adds a new edge to the graph, where endpoints are identified by names. The optimal edge weight is then attached to the edge. Internally an undirected graph is represented as a directed graph, where every edge (u,v) generates the two arcs (u,v) and (v,u). A similar method add_arc permits to add only a single arc.

The graph class has also a method __len__ which returns the number of vertices and an element access operator, which returns the adjacency list for a given vertex identifier. These two methods/operators permit to use the graph class in exactly the same manner as a list-list representation of graphs, as described in the previous section. As a result one can pass an object of the class Graph as parameter to all graph algorithms implementations of the tryalgo library.

Here is the implementation of the class.

Example

To illustrated the above graph class, we refer to a problem posted in the BattleDev March'2018 competition. You are given a n by n grid representing a maze. A cell can either be empty, contain a door, a wall, a person or a duck. Ducks and persons can walk in this maze, by successive steps. A step leads to to a vertically or horizontally neighboring cell, provided it does not contain a wall or a locked door. Initially all doors are unlocked. The goal is to find out if it possible to lock some doors so that no person can get in touch with a duck. And if it is possible we want to know the minimal number of doors we need to lock.

Clearly this is a min s-t-cut problem, it is a just a matter of finding the right graph. For this purpose we have 2 vertices for every grid cell (i,j), namely a vertex (IN,i,j) and a vertex (OUT,i,j). If (i',j') is adjacent to (i,j), then there is an arc from (OUT,i,j) to (IN,i',j') of infinite capacity. In addition there is an arc from (IN,i,j) to (OUT,i,j) with capacity 0 if the cell is a wall, capacity 1 if the cell is a door and capacity infinite otherwise.

In this graph there are two more vertices, a source s that is connected to every vertex (IN,i,j) for cells containing a person, and a target vertex t that is connected from every vertex (OUT,i,j) for cells containing a duck. If the maximum s-t-flow in this graph has infinite value then persons cannot be separated from ducks. Otherwise the value of the flow is the answer. The infinite capacity can be represented by the number of cells in the grid.

In the graph on the right, the arcs of capacity 0 are not depicted, the black arcs have infinite capacity, and the red arc has unit capacity.

This is how the graph could be build using our class.

# data[].attributes.attachment_link.description
How to represent a graph in Python ? Some libraries use a class to represent graphs. For example the very complete Python library NetworkX provides a class for direction graphs ( DiGraph) and for undirected graphs ( Graph).

# data[].attributes.attachment_link.readable_text
Voici un cinquième billet concernant l'analyse de réseau et QGIS (billet 1, billet 2, billet 3, billet 4), car une certaine demande semble apparemment exister. En effet, lorsque que l'on consulte les statistiques du...

# data[].attributes.attachment_link.description
Voici un cinquième billet concernant l'analyse de réseau et QGIS (billet 1, billet 2, billet 3, billet 4), car une certaine demande semble apparemment exister. En effet, lorsque que l'on consulte les statistiques du...

# data[].attributes.attachment_link.authors[].name
Tiago de Paula Peixoto <tiago@skewed.de>

# data[].attributes.attachment_link.title
graph-tool: Efficent network analysis with python

# data[].attributes.attachment_link.description
graph-tool: Efficent network analysis with python

# data[].attributes.attachment_link.description
Graph drawer is a tool for drawing Mathematical graphs. You define the graph by number of vertices and by edges between them.

# data[].attributes.attachment_link.description
This game is provided free of charge, but if you would like to make a donation it would be greatly appreciated. Just click on the Paypal button above. Even a small donation would go a long way. Thank you!

# data[].attributes.attachment_link.readable_text
In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices, nodes, or points which are connected by edges, arcs, or lines.

D3 Graph Theory is a project aimed at anyone who wants to learn graph theory. It provides quick and interactive introduction to the subject. The visuals used in the project makes it an effective learning tool.

And yes, it is an open-source project. Check the code at GitHub.

# data[].attributes.attachment_link.title
D3 Graph Theory - Interactive Graph Theory Tutorials

# data[].attributes.attachment_link.description
In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices, nodes, or points which are connected by edges, arcs, or lines. D3 Graph Theory is a project aimed at anyone who wants to learn graph theory.

# data[].attributes.attachment_link.readable_text
L'objectif d'une cartographie directe des valeurs des flux qui se sont produits entre des couples (i,j) de lieux d'origine (i) et de destination (j) est de représenter la quantité en mouvement ou, à défaut,...

# data[].attributes.attachment_link.description
L'objectif d'une cartographie directe des valeurs des flux qui se sont produits entre des couples (i,j) de lieux d'origine (i) et de destination (j) est de représenter la quantité en mouvement ou, à défaut,...

# data[].attributes.attachment_link.readable_text
Ce chapitre traite principalement des Graphes.

1. T.D. : Travaux Dirigés sur les Graphes

Point d'Histoire : L'algorithme de Dijkstra porte le nom de son inventeur, l'informaticien néerlandais Edsger Dijkstra (1930-2002), et a été publié en 1959. Ce algorithme sert à résoudre le problème du plus court chemin. Il permet, de déterminer un plus court chemin pour se rendre d'un point à un autre connaissant le réseau routier d'une région. Plus précisément, il calcule des plus courts chemins à partir d'une source dans un graphe orienté pondéré par des réels positifs.

TD n°3 : les Graphes au Bac, partie 2 .
Un bilan du chapitre. De nombreux exercices du bac ES/L proposés en intégralité avec des corrections détaillées.
Les exercices portent sur les Graphes pondérés, les matrices et l'algorithme de Dijkstra.

2. Les Cours sur les Graphes

Point Histoire : C'est le génial mathématicien suisse Leonhard Euler (1707-1783) qui donna la solution du problème des sept ponts de Königsberg en caractérisant les graphes que l'on appelle aujourd'hui " eulériens " en référence à l'illustre mathématicien. Il propose un théorème répondant au problème, sans preuve, en 1736. Un siècle plus tard, le mathématicien allemand Carl Hierholzer (1840-1871) expose une démonstration, juste avant sa mort prématurée en 1871, à un collègue qui la publie à titre posthume en 1873. La solution d'Euler au problème du pont de Königsberg est considérée comme le premier théorème de la théorie des graphes et la première preuve vraie dans la théorie des réseaux , sujet désormais considéré généralement comme une branche de la combinatoire.

3. Devoirs

4. Compléments

Le Bac

Recommander l'article :

Articles Connexes

# data[].attributes.attachment_link.description
Ce chapitre traite principalement des Graphes. Point d'Histoire : L'algorithme de Dijkstra porte le nom de son inventeur, l'informaticien néerlandais Edsger Dijkstra (1930-2002), et a été publié en 1959. Ce algorithme sert à résoudre le problème du plus court chemin.

# data[].attributes.attachment_link.readable_text
Le but principal de cette série d'exercices est de servir de source d'inspiration.
Bon nombre de ces exercices peuvent être à l'origine de toute une famille d'exercices que l'enseignant n'aura aucun mal à " générer ".
Des solutions sont proposées en téléchargement (voir à la fin de cette page).

1. NOTIONS DE BASE

1-1 Modélisation (ex 1 à 11)
1-2 Degré des sommets (ex 12 à 20)
1-3 Graphes eulériens (ex 21 à 25)

2. PROBLÈMES DE COLORATION (ex 26 à 30)

3. PROBLÈMES DE CHEMINS (ex 31 à 37)

4. PROBLÈMES D'ORDONNANCEMENT (ex 38 - 39)

5. PROBLÈMES D'AUTOMATES

5-1 automates simples (ex 40 à 43)

5-2 automates avec actions (ex 44 à 47)

6. PROBLÈMES DIVERS

6-1 Arbres, arbres couvrants (ex 48 à 51)

6-2 Graphes hamiltoniens (ex 52 à 55)

7. BIBLIOGRAPHIE

Ce cahier d'exercice est disponible sous trois formes : énoncés seuls, solutions seules, énoncés + solutions.

Télécharger les énoncés (format RTF zippé ; 36 Ko)
Télécharger les énoncés (format PDF ; 51 Ko)
Télécharger les solutions (format RTF zippé ; 148 Ko)
Télécharger les solutions (format PDF ; 152 Ko)
Télécharger le document complet (format RTF zippé : 178 Ko)
Télécharger le document complet (format PDF : 197 Ko)

# data[].attributes.attachment_link.description
Le but principal de cette série d'exercices est de servir de source d'inspiration. Bon nombre de ces exercices peuvent être à l'origine de toute une famille d'exercices que l'enseignant n'aura aucun mal à " générer ". Des solutions sont proposées en téléchargement (voir à la fin de cette page). 1.

# data[].attributes.attachment_link.description
Ce document, portant sur les fondements de la théorie des graphes, constitue une approche théorique à l'usage des enseignants. Il n'est pas destiné à être directement exploité avec les élèves, certaines notions présentées dépassant largement le cadre du programme de mathématiques de la classe terminale de la série ES.

# data[].attributes.attachment_link.readable_text
ChronoMath , une chronologie des MATHMATIQUES l'usage des professeurs de mathmatiques, des tudiants et des lves des lyces & collges

Vocabulaire et notions lmentaires de la thorie des graphes
Pour rechercher une dfinition, taper Ctrl F puis son nom

Initie par Euler, avec le clbre problme des 7 ponts de Knigsberg, les applications de la thorie des graphes et de la recherche oprationnelle sont aujourd'hui immenses tant au plan civil que militaire : aide la dcision, stratgie, optimisation (plus court chemin, GPS, cot minimal), rseaux de transports : chemins de fer, mtropolitain, lignes ariennes, lectricit, gaz, oloducs (transport de l'nergie), Internet (rseau de l'information), ports et aroports, ordonnancement des tches, etc.

La thorie des graphes n'est pas une branche indpendante des mathmatiques, elle se rattache la programmation linaire, la programmation convexe (o le concept plus gnral de fonction convexe remplace les fonctions linaires et affines), la topologie, le calcul des probabilits. Depuis l'anne 2002, une initiation la thorie des graphes est donne en classe Terminale ES dans son enseignement de spcialit.

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 Erds, sont galement considrs comme les leaders du dveloppement de la thorie des graphes et de ses applications au 20 sicle.

➔ Dans toute la suite, il s'agira de . On ne confondra pas un graphes plans, mais tout ce qui suit peut s'appliquer des graphes dfinis sur une sphre que l'on peut, par projection strographique, identifier R graphe plan avec un graphe planaire. 2

Abstraitement, un graphe est la donne d'un certain nombre de points du plan, appels nuds ou sommets , certains tant relis par des segments de droites ou de courbes (simples) appels artes, la disposition des sommets et la forme choisie pour les artes 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 artes, 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 artes 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'arte DC coupe l'arte 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 ncessairement une tare, cependant cela peut entraner des situations illicites : ci-dessous, l'arte DC possde deux points doubles : c'est illgal !

G raphe orient ou non, arc d'un graphe, :

Si deux sommets conscutifs A et B sont relis par une arte, 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 artes sont alors flches dans le sens de parcours autoris et on parle d' arcs pouvant s'interprter comme un couple (A,B) distinguer de (B,A). "nommer une arte, un arc, une chane.

Graphe symtrique, graphe antisymtrique, graphe d'une relation binaire :

Ci-dessous, graphe 2, on peut parler de l'arte (A,B) mais pas de (B,A). Lorsque (A,B)∈U entrane (B,A)∈U, le graphe est dit symtrique . Un graphe non orient s'interprte comme un graphe symtrique.

Lorsque (A,B) ∉U entrane (B,A) ∈U, le graphe est dit antisymtrique .

Dans un graphe dfini comme tant orient, on doit faire apparatre les sens de parcours sur chaque arte. Sauf indication contraire, un graphe sera considr comme non orient et les artes peuvent tre parcourues dans les deux sens. Ce type de graphe peut se prsenter dans des problmes lmentaires de type combinatoire. La plupart des applications de la thorie graphes, (problmes d'optimisation, communications, trafics ariens, ...) conduisent des graphes orients.

Artes 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'arte AC, d'origine A, d'extrmit 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 ambigit l'instar du graphe 2c ci-dessus. Ce qui s'avre d'ailleurs indispensable par exemple dans le cas concret d'un trajet aller-retour sur deux routes diffrentes. Il peut aussi s'agir de dbits aller-retour dans un pipe-line, etc.

➔ Dans le dnombrement des artes d'un graphe conduisant des conclusions sur la nature et les proprits du graphe, le sens de parcours n'interviendra pas, sauf mention contraire explicite. Les deux arcs AC et CA reprsentes ci-dessus droite sont comptabiliss comme une arte unique. Cependant, on peut galement concevoir deux arcs distincts reliant deux sommets :

C'est le cas du problme des ponts de Knigsberg, problme 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, p eut-on se promener, en revenant son point de dpart,
en passant une seule fois par tous les ponts ?

Vrifier que le graphe de la situation se rsume 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 prsence de sens uniques...).

Rponse ce problme, graphe eulrien : "

Sommets adjacents, artes incidentes, graphe complet, degr d'un sommet, chane, longueur, chemin :

Deux sommets d'un graphe sont dits adjacents s'il existe une arte (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'artes auxquelles il est reli (on parle d' artes incidentes ce sommet).
Proprit 1: Dans un graphe non orient, la somme des degrs des sommets est gale au double du nombre d'artes du graphe.
Une chane de longueur n est une suite ordonne finie (liste) de n + 1 sommets adjacents (n est donc le nombre d'artes de la chane).

On appelle chemin une chane dont les sens de parcours successifs ne prsentent pas d'opposition.

Nommer une arte, une chane, un arc :
Pour dcrire une chane, comme ci-dessus, le chemin ACDEB, on convient de respecter l'ordre du cheminement. Il est d'usage de donner un nom aux artes (pratique dans un problme concret o une arte s'apparente par exemple une voie de communication, un flux, etc.) distinguant (A,B)∈U et (B,A)∈U tout comme en thorie des ensembles o l'on distingue le couple d'lments (A,B) ≠ (B,A) tenant compte de l'ordre et la paire d'lments {A,B} = {B,A} n'en tenant pas compte. "nommer au moyen des faces

Ci-contre, l'arte 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 artes permet de nommer facilement une chane tenant compte de l'ordre de cheminement et en sparant les noms des artes par des slashs (/) :

On appelle distance entre deux sommets distincts la longueur de la plus courte chane qui les relie. La plus grande distance entre deux sommets est le diamtre du graphe.

Dans des problmes d'tats transitoires (et/ou probabilistes) d'un systme, deux sommets adjacents peuvent reprsenter deux tats possibles du systme des instants diffrents. On peut envisager un tat stationnaire pour signifier que le systme conserve le mme tat : il "boucle".

♦ Afin de reprsenter cette situation sur un graphe, on utilise un arc circulaire dont l'origine et l'extrmit ont le mme sommet : une boucle est un arte incidente deux fois un mme sommet. C'est le cas au sommet B du graphe 5 ci-dessus. On nommerait indiffremment (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 arte. Dans le cas contraire, on parle de multigraphe .

♦ Une chane est dite ferme si son origine concide avec son extrmit.

♦ Une chane est dite lmentaire (resp. simple ) si aucun de ses sommets (resp. arcs) n'apparat plus d'une fois.

♦ On appelle cycle une chane ferme et simple (donc constitue d'artes distinctes).

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

♦ On appelle arbre un graphe orient ne possdant aucun cycle. Un graphe possdant plusieurs arbres disjoints (graphe non connexe) prend le nom de forts . Cette dfinition d'un arbre est celui connu des lves de 1res et terminales, relatif au calcul des probabilits, et permettant d'obtenir une reprsentation logique du problme rencontr. "graphe pondr.

Bayes et probabilits conditionnelles : "

♦ On appelle circuit un cycle dont les sens de parcours successifs ne prsentent 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 reprsentation de la rflexivit :

des artes d'un graphe conduisant des conclusions sur la nature et les proprits du graphe, le sens de parcours n'interviendra pas, sauf mention contraire explicite comme dans le cas des ! Rappelons encore ici que dans le dnombrement 7 ponts. Une boucle n'est ni une arte ni un arc.

Ainsi baptis en l'honneur de Euler, une chane eulrienne se rattache au contre-exemple clbre de la situation des 7 ponts de Knigsberg (1735) : il s'agit d'une chane contenant une fois et une seule toutes les artes du graphe (ou les arcs dans le cas orient). Si la chane est un cycle (resp. circuit), on parlera de cycle eulrien (resp. circuit eulrien ). Euler tablit alors ce rsultat nonc ici en ces termes :
Proprit 2 :
Un graphe connexe admet une chane eulrienne (resp. un cycle eulrien) si et seulement si
le nombre de sommets dedegr impair est 0 ou 2 (resp. tous ses sommets sont de degr pair).

On parle de graphe eulrien pour exprimer un graphe admettant au moins un cycle eulrien.

∗ ∗ ∗
En utilisant la proprit P2, vrifier que l'on doit rpondre par la ngative au problme 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 reoit 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 chane est un cycle (resp. circuit), on parlera de cycle (resp. circuit) hamiltonien (l'origine et l'extrmit sont alors considrs comme un seul sommet).

Pos en 1859, le problme est de trouver des conditions afin qu'un graphe orient contienne un chemin hamiltonien. Par exemple :
Thorme de Koenig-Redei :
Tout graphe complet admet un chemin hamiltonien.

(ou (), il en vint s'intresser la thorie des graphes qui deviendra l'objet principal de ses travaux. On lui doit en particulier i Dnes Knig Koenig, 1884-1944) : mathmaticien 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 clbre problme des 4 couleurs Cayley" Source : Thorie des graphes finis et infinis ( Theorie der endlichen und unendlichen Graphen, 1936). . Wikipedia.hu

i Laszlo Rdei (1900-1980) : mathmaticien hongrois qui tudia Debrecen et complta ses tudes Gttingen avant d'obtenir un poste l'universit de Szeged (1941). Il s'intressa principalement aux structures algbriques ( semi-groupes) et la thorie des corps de nombres. Source : Wikipedia.hu.

∗ ∗ ∗ Chemin hamiltonien sur un polydre

Un graphe est dit connexe (ou simplement connexe ) si deux sommets quelconques et distincts du graphe admettent au moins une chane 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 artes 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'artes.

C omposantes connexes :

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

A C s B ⇔ (A = B) ou (il existe une chane entre A et B)

est une relation d'quivalence (rflexive, symtrique et transitive). Les lments 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 mme 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 possde 3 composantes simplement connexes : H = {H} (classe rduite 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}

G raphes 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 dplaant D, on obtient une reprsentation planaire (obtenue ci-dessous). On pouvait aussi tirer l'arc BD en passant "sous la boucle situe en C.

Graphe planaire :

on qualifie de planaire un graphe pouvant tre reprsent dans le plan par changement de position des sommets ou tirement/rtractation des artes (on parle plus prcisment, comme en topologie, d' homomorphisme) de sorte que :

les sommets apparaissent distincts;

les artes sont des courbes simples (pas de point double ou multiple);

les artes ne se rencontrent qu'en leurs extrmits.

! rappelons ici encore que deux arcs orients, comme AD et DA constituent une mme arte ! !

On comprend ici, tout comme en thorie des nuds, qu'un graphe peut avoir de multiples reprsentations : deux graphes apparemment distincts peuvent tre quivalents, en ce sens qu'ils sont solutions d'un mme problme.
Thorme de Fary (1948) :
Les artes d'un graphe qui peuvent tre en arcs, en zig-zags, en lignes brises, etc. ( courbes de Jordan). En utilisant les moyens sophistiqus de la topologie diffrentielle, le mathmaticien hongrois Istvan Fary a prouv le rsultat suivant ( " preuve en rf. 15) :
Tout graphe planaire admet une reprsentation telle que toutes ses artes soient rectilignes (segments de droites).
, mathmaticien hongrois, 1922-1984. Professeur l'universit de Californie (Berkeley), il fut un spcialiste en i Istvan Fary gomtrie algbrique et topologie algbrique. Par l, il s'illustra galement en thorie des nuds. On trouvera sur le site Numdam ( " rf. 13b) quelques publications en franais de ce mathmaticien.

" Jones Milnor

♦ Face d'un graphe :

Tout comme pour un polydre, on appelle face d'un graphe G tout cycle de G de longueur au moins gale 3 ne contenant en son intrieur aucun sommet et aucune arte. Par convention, le contour extrieur d'un graphe connexe planaire est considr comme une face, dite face extrieure ou face infinie (au sens de non limite).

Le graphe ci-dessous possde 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 extrieure.

Nommer une arte au moyen des faces :

On peut donner un nom aux faces d'un graphe permettant une nouvelle faon de caractriser une arte 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 extrieure du graphe 7. L'arte a = AD est adjacente Φ et F4 : on peut noter, sans ambigut : a = {Φ,F4}. On utilise les accolades car {Φ,F4} = {F4,Φ}.

Vrifier que le graphe ci-dessous, d'aspect "cubique", est planaire :

Si votre navigateur accepte les applets Java :
V rifier par dplacement des sommets que le graphe ci-dessus est planaire Figure CabriJava.class : Utiliser Microsoft Internet Explorer en activant Java

C'tait trop facile ! Vrifier que le graphe ci-dessous est planaire. ☼

Si votre navigateur accepte les applets Java :
Vrifier par dplacement des sommets que le graphe ci-dessus est planaire Figure CabriJava.class : Utiliser Microsoft Internet Explorer en activant Java

Le graphe complet ci-dessous, dit K5, est-il planaire ? ☼

Si votre navigateur accepte les applets Java :
Vrifier par dplacement des sommets que le graphe ci-dessus est planaire Figure CabriJava.class : Utiliser Microsoft Internet Explorer en activant Java

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 concrtement 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'exprience montre que l'on arrive tracer 8 arcs non scants mais jamais 9 comme il le faudrait...

On pourra prouver que K3,3 est non planaire de faon tout fait similaire celle donne pour K5 , en notant que dans ce cas, un graphe planaire candidat devra possder au moins 4 artes. En effet si une face ne possde que 3 artes, 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 : "
c composantes simplement connexes,s sommets, f faces et
2/
celle pour les polydres convexes : a artes, alors :

Formule d'Euler pour les graphes :

1/

s - a + f =c + 1

o S, F et A dsignent respectivement le nombre de sommets, de faces et d'artes.

Chemin hamiltonien sur un polydre et graphe planaire

Dual d'un graphe planaire :

s - a + f = 2

le nombre f tient ici compte de la ! face extrieure (galement dite infinie) sinon, la formule s'crit s - a + f = 1. On pourra s'exercer vrifier la formule en considrant les nombreux graphes de cette "page".

La formule d'Euler pour les polydres s'applique au cas des graphes planaires :

Le graphe ci-dessus prsente 6 sommets, 5 faces et 9 artes et : 6 + 5 - 9 = 2.

Selon . un polydre rgulier (P) de F faces et S sommets, il s'agit alors d'associer, avec le Euler, il y a entre le nombre s s de sommets, le nombre mme nombre d'artes, un polydre rgulier de s faces et f sommets, appel dual de (P). Si d'un sommet part a artes, chaque face du dual possdera a cts. f de faces et le nombre a d'artes, la relation - a + f = 2

A la manire du dual d'un polydre, on construit le dual G* d'un graphe planaire G de la faon suivante :

Les sommets de G* sont les faces de G identifies un point intrieur celles-ci qualifi de "centre".

Les artes s'obtiennent en joignant les "centres" des faces de G ayant une arte commune (faces adjacentes).

Proprit 3 :

➔ On remarquera que, de par sa dfinition et construction, le dual d'un graphe planaire est planaire.
Proprit 4 :
Cellules de Vorono et triangulation de Delaunay (Boris Delone) : "

Le graphe7 ci-contre n'est pas complet. Le sous-graphe G' constitu des 3 sommets A, F et D est complet : il va donc dj nous falloir 3 couleurs. Le degr de E est 4 : c'est le degr maximum. On choisit alors tout d'abord une couleur pour E, ici vert . Le sous-graphe A,B,C,D,E tant en toile autour de E, il suffit de choisir 2 autres couleurs pour le colorier : on choisit le et le jaune . En coloriant en vert bleu , le sommet F, on constate que le nombre chromatique de notre graphe7 est gal 3.

Proprit 5 (trs utile dans la pratique):

Reprenons le graphe7 ci-dessus : on a k = 4 (degr de E). Le nombre chromatique est donc au plus 5. Le sous-graphe G' constitu de A, D et F est complet. Le nombre chromatique de G est donc compris entre 3 et 5. On affecte d'abord une couleur au sommet de plus haut degr : E est colori en vert. On doit maintenant utiliser au moins 2 autres couleurs qui serviront colorier le graphe G". On voit alors qu'elles suffisent.

Le nombre chromatique de tout graphe planaire est au plus gal 5, et si on admet
lethorme des 4 couleurs, ce nombre se rduit 4
Une application du nombre chromatique (planning)
Thorme :

Matrice associe 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 :

Ce concept remonte la clbre conjecture de Guthrie (1852) relatif au coloriage des cartes gographiques la Socit Mathmatique de Londres et rappel en 1872 par Cayley : il suffirait de quatre couleurs pour que, quelle que soit la configuration gopolitique, deux pays ayant une frontire commune soient de couleurs diffrentes. Une carte s'identifie ici un graphe G = (X,U) non orient dont les diverses frontires communes des pays constituent les artes.

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

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 dsignant le plus haut degr des sommets.

Reprsenter le graphe orient dfini par la matrice suivante :

☼
Proprit 6 :

Dans le cas prcdent, sans faire rfrence 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).☼
tiquet est un graphe dont les artes ont reu des attributspondr .

gauche, un graphe tiquet caractre qualitatif : les sommets sont des villes, les artes reprsentent des routes indiques par leur nature et numro (route nationale 73, route dpartementale 982, autoroute A9, etc.).

droite, un graphe tiquet caractre quantitatif : les tiquettes sont les vitesses maximales autorises.

qualitatifs ouquantitatifs . Dans ce dernier cas, on parle aussi depoids et de gra

Graphe tiquet (tiquettes), graphe pondr (poids), graphe probabilis (probabiliste) :

La matrice dpend de l'ordonnancement choisi pour les sommets.

Dans le cas ci-dessous, en identifiant A S 1, B S 2, ..., D S 4, les a i,i sont nuls et :

Dans ce cas, l'lment a i,j plac en i-me ligne et j-me colonne est gal au nombre d'artes reliant Si Sj. La matrice M n'est gnralement pas symtrique (une symtrie caractriserait des arcs doubles entre tout couple de sommets) et ne contient alors que des 0 ou des 1.
On remarquera, sachant qu'un graphe est orient ou non, que la matrice d'un graphe caractrise ce graphe.

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

Flot, rseau, optimisation : "

Un graphe peut servir modliser une situation probabiliste relative un systme (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 pidmie, de la situation mtorologique, de la nature chimique ou biologique d'un lment naturel, etc.). On parle de stokhastikos = divinatoire, alatoire). processus stochastique (du grec

Les sommets du graphe reprsenteront du systme au cours du temps et les tiquettes sont les diffrents tats possibles E 1, E 2, ..., E k les probabilits de passer d'un tat un autre : il s'agit donc d'un graphe orient indiquant les probabilits sortantes.

On appelle , c'est dire les probabilits conditionnelles p matrice de transition du graphe (ou matrice stochastique ), la matrice carre dont les lments p i,j (en ligne i, colonne j) sont les probabilits de passer de l'tat E i l'tat E i,j = prob(E j j/E i), probabilit de ralisation de E j sachant E i ralis, galement notes :

➔ On suppose donc ici que les p dfinis au pralable et en aucune manire de l'volution du systme dans le temps : on parle alors de i,j ne dpendent que des tats possibles E i et E j chane de Markov pour caractriser le modle mathmatique du systme considr.
Notion de systme ergodique :
"Andre A. Markov

Considrons le cas lmentaire d'un systme S pouvant prendre deux tats E 1 et E 2 diffrents instants successifs, l'tat initial E0 tant apparu avec les probabilits p o (tat 1) et q o = 1 - p o (tat 2).

Le graphe correspondant est alors :

On peut dresser l'arbre des ventualits restreint aux dates initiale T o et suivantes T 1 et T 2 :

La matrice de transition, indpendante des temps To + j (j = 1, 2, 3, ...) est alors ici, par dfinition :

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

Vrifier que le carr de M est encore une matrice de transition, c'est dire une matrice termes positifs dont ∗ ∗ ∗

la somme des lments de chaque ligne est gale 1. Ce cas se gnralise : "matrice de Markov

Les probabilits p 1 et q 1 d'obtenir respectivement les tats E 1 et E 2 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 :

Ce rsultat se gnralise un systme soumis un nombre quelconque k d'tats transitoires.

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

On peut se demander si la suite des matrices lignes admet une limite lorsque n devient infini (le nombre d'tats s'avrant infini dnombrable). Si tel est le cas, cela signifie que chaque lment a des tats du systme converge vers un tat i,j(n) de la matrice M n admet une limite finie et si l'on note A la matrice obtenue la limite, la matrice ligne P n permanent P vrifiant P = P o × A n.

Un cas particulier important est celui o les lignes de A sont identiques : le systme limite P est alors indpendant de P o. En effet, en dimension 2 comme ci-dessus, on aurait alors un rsultat de la forme :

On dit alors que le systme est ergodique .

Notion gnrale d'ergodicit : " ∗ ∗ ∗ Exemple simple de systme ergodique en gntique

On appelle rseau un graphe pondr orient possdant un nombre fini d'arcs et deux sommets E (entre) et S (sortie) tels que E (resp. S) n'admet aucun arc entrant (resp. sortant). Chaque tiquette d'un arc est appele capacit (maximale) ou de l'arc. Lorsqu'il s'agit de modliser des capacits de transport comme maritime, fluvial, arien, routier, nergtique (lectricit, gaz, ptrole), etc., on parle de rseau de transport .

Soit plus prcisment un rseau d'entre E, de sortie S. Les sont les tiquettes des arcs orients reliant les effectivement utilise sur l'arc A capacits c i,j ports de dpart et d'arrive. On appelle flot (ou flux) et on note ici f i,j la fraction de c iA j. i,j

➔ Pour en savoir plus :

Exemple : si une ligne arienne ne peut tolrer simultanment, par scurit, que ci,j = 4 avions, le flot un instant donn peut tre fi,j = 3 ≤ ci,j.

Si R et S sont des aroports de dpart et d'arrive, on ne peut, par jour, ni faire dcoller ni accueillir autant d'avions que souhait. Par consquent, les capacits au dpart (E) et l'arrive (S) sont limites. En notant e 1, e 2, ..., e n et s 1, s 2, ..., s m ces capacits, on sera la recherche de flots f i,j tels que le flot total :

soit maximum, sous les contraintes :

Dans les annes 1960, de nombreux mathmaticiens laborent, dans le cadre de la recherche oprationnelle, troitement lie la thorie des graphes, des algorithmes d'optimisation :

Algorithme de Ford & Fulkerson, de Bellmann-Kalaba, de Dijkstra
Concernant ces algorithmes et leur programmation, on pourra consulter la rf. 5.

l'article L e plus court chemin, sur le site Interstices de l'INRIA/CNRS.

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

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

Chaque arte de G est assimil un sommet de G* : il y a autant de sommets de G* que d'artes de G.

Deux sommets de G* sont adjacents s'ils proviennent d'artes de G ayant un sommet en commun.

Un graphe G, gauche et son adjoint G*, droite
Les graphes adjoints se rencontrent dans les problmes d'optimisation de rseaux de communication.

Niveau lmentaire : Tout manuel de Terminale ES.

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

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, tlchargez-le ici.

Introduction la thorie des graphes, par ric Sigward (univ. Paris-sud), prpa au CAPES :
https://www.math.u-psud.fr/~thomine/fr/archives/Enseignement1718/CAPES/PolycopieSigward.pdf

Thorie des graphes l'intention des enseignants, par Graldine Morin, INPT Toulouse :
http://morin.perso.enseeiht.fr/DocumentsPDF/Graphes/polyEnseignants.pdf

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

Sur le site Apprendre en ligne, un cours trs complet de Didier Mller (Suisse) : http://www.apprendre-en-ligne.net/graphes/index.html.

Introduction la thorie des graphes :http://www.labri.fr/perso/courcell/Conferences/GraphesX.pdf

Des points et des flches... la thorie des graphes, A. Kaufmann, d. Dunod Science-poche - 1968

Programmes jeux, rseaux, transport , C. Berge , A. Ghouila-Houri, Ed. Dunod, Paris - 1962.

Algbre moderne et thorie des graphes, B. Roy, Ed. Dunod, Paris - 1969.

Thorie des graphes et applications avec exercices et problmes , par J.-C. Fournier, d. Herms - 2006

La Thorie des graphes par Aim Sache - Que sais-je n1554 -P.U.F. Paris - 1974

Quelque publications de Istvan Fary numrises sur Numdam : http://www.numdam.org/search/Istvan Fary-a

Graphes planaires, dont le thorme de Fary, par Thophile trunck (ENS Lyon) :
http://perso.ens-lyon.fr/eric.thierry/Graphes2009/theophile-trunck.pdf

© Serge Mehl - www.chronomath.com

# data[].attributes.attachment_link.description
ChronoMath , une chronologie des MATHMATIQUES l'usage des professeurs de mathmatiques, des tudiants et des lves des lyces & collges Vocabulaire et notions lmentaires de la thorie des graphes Pour rechercher une dfinition, taper Ctrl F puis son nom Initie par Euler, avec le clbre problme des 7 ponts de