4 - Relier d'un trait - Connections - 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)

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.




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 !

Thèmes : << 1 < 2 < 3 4 5 > 6 > 7 > 8 > 9 > 10 >>