16 avril 2007

 

Origine de la théorie des graphes


1) Le tracé de l'enveloppe: Un jeu bien connu consiste à demander de tracer la figure ci-dessus d'un seul trait (sans repasser deux fois au même endroit ) et sans lever le crayon.

L’unique moyen de réussir est de commencer par un sommet d’où partent un nombre impair de traits (en bas à droite ou en bas à gauche), pour arriver à l’autre sommet d’où partent un nombre impair de traits. En effet, pour un point de passage (pas le point de départ ni le point d’arrivée), il est nécessaire que de ce point partent un nombre pair de traits ( car à chaque fois que le tracé y arrive, il doit en repartir)

2) Les ponts de Königsberg : Le célèbre problème posé à Léonhard Euler.
Est-il possible de parcourir en boucle toute la ville de Königsberg (composée de 4 quartiers) en traversant chacun de ses sept ponts une fois et une seule ?



Pour résoudre ce problème , 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 le dessin ci- dessous existe-t-il un chemin passant une seule fois par chaque trait ?


Nous sommes donc ramené à un problème du type du n°1
La réponse d’Euler : Il n’y a de solution que si le nombre de points où aboutit un nombre impair de traits est égal à zéro ou à deux ! (par conséquent pas de solutions au problème des ponts de Königsberg)

Ce fut l’amorce de la théorie des graphes qui est restée sans applications pendant des décennies mais qui est incontournable aujourd'hui .

La théorie des graphes n'a jamais été aussi actuelle grâce au développement d'internet. Car l'ensemble de tous les sites internet du monde peut être vu comme un immense graphe dans lequel les noeuds seraient les sites eux-mêmes et les arêtes les liens hypertextes qui les relient entre eux.

La théorie des graphes est devenue une branche entière des mathématiques

Libellés :






<< Home

This page is powered by Blogger. Isn't yours?