4- Relier d'un trait

4.1- Des points et des traits

Königsberg, 1736 : est-il possible de parcourir la ville en traversant chacun de ses sept ponts une fois et une seule ?

Pour résoudre ce problème, à l’origine de la théorie des graphes, Euler retient l’information essentielle : il y a quatre quartiers séparés par l’eau du fleuve, soit quatre “points” à relier par 7 traits qui symbolisent les ponts.

Le problème devient : sur ce dessin existe-t-il un chemin passant une seule fois par chaque trait ? Ce fut l’amorce de la théorie des graphes.

La réponse d’Euler : combien y a-t-il de points où aboutit un nombre impair de traits ? Il n’y a de solution que si ce nombre est égal à zéro ou à deux ! Leonhard Euler (1707-1783)

Expérience sur table

Chemins dans un cube

Essayez de construire un cube de 3x3 ou un mur de 2x3, de telle sorte que la ligne rouge soit continue.
Essayez encore en utilisant le moins de circuits droits.

Que retenir ?

C’est Euler qui a donné naissance à la théorie des graphes avec des problèmes de ce type.
Ici, le problème est en plus de savoir s’il y a des solutions minimales.
Comment prouver qu’il n’y a pas de solution avec aucun circuit droit ?
Comment prouver que toute solution a au moins 2 circuits droits ?
Idée & Réalisation : Centre•Sciences

4.2- Quatre couleurs suffisent !

Combien de couleurs suffisent à colorier une carte, de telle façon que deux pays voisins soient de couleurs différentes ?

La théorie des graphes a permis de modéliser ce problème et de réduire le nombre de cas à étudier. Mais c’est grâce à l’ordinateur que l’on a pu analyser un grand nombre de situations.

La théorie des graphes est utilisée pour modéliser et étudier des situations très concrètes comme les réseaux de télécommunication, les circuits électroniques, les réseaux de distribution – eau, gaz, électricité, courriers…- et de nombreux problèmes de logistiques, transport, production.

Expérience sur table

Un jeu de coloriage

Deux joueurs : chacun, à son tour, place une couleur de son choix sur l’un des pays.
La règle : 2 pays voisins doivent être de couleurs différentes. Perd celui qui ne peut plus jouer.

Que retenir ?

Si vous jouez seul, avec la théorie des graphes nous savons que 4 couleurs suffisent.
Mais si vous jouez à deux, vous pouvez utiliser jusqu’à 6 couleurs pour gagner.
Il existe des algorithmes de coloriage avec 6 couleurs.
le problème n’a pas encore trouvé de solution pour 4 couleurs.
Idée & Réalisation : Jean Lefort (Strasbourg) & Centre•Sciences

4.3- Allo ?! M’entends-tu ?

Dans un réseau de communications locales, comment circule votre appel téléphonique ?
Il se propage de relais en relais jusqu’au commutateur le plus proche de votre correspondant qui est prévenu par une sonnerie.

Dans une ville, ces nœuds de réseaux sont placés au mieux en tenant compte de la topologie irrégulière des rues. Chaque nœud définit une zone de proximité d’appel sous forme d’un polygone qui est relié aux autres par voisinage.

Ces zones définissent un pavage de la ville, appelé mosaïque de Voronoï. Si on relie ces commutateurs entre eux de telle sorte qu’ils appartiennent à des zones voisines, on met en place un graphe qui représente les cables le long desquels l’appel va cheminer.

Graphes, probabilités, géométrie s’associent ici pour vous permettre de communiquer dans des conditions optimales !

Expérience sur table

Le Tour du Monde

Choisissez un globe et trouvez un chemin qui passe une seule fois par chacune des arêtes.

Que retenir ?

Un chemin eulérien passe une fois et une seule par chacun des sommets.
Un chemin hamiltonien passe une seule fois par chacune des arêtes.
Ce type de problème n’a pas encore trouvé de solution générale.
Hamilton a montré qu’il n’y a pas de solution pour les arêtes d’un dodécaèdre régulier (12 faces pentagonales).

Est-il possible de repasser avec un doigt sur ce dessin d'un “hypercube” en passant une fois et une seule par chaque sommet ?
Idée & Réalisation : Euler, Hamilton & Centre•Sciences – Illustration : JF Colonna