GRAPHES

 GENERALITES

GRAPHES PLANAIRES

DISTANCES

CONNEXITE

ARBRES ET ARBORESCENCES

STABILITE ET ABSORPTION

COLORATION

CYCLES ET COCYCLES

LEXIQUE

 

 

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.

 
Königsberg

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 "piège" 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.

 

 

 

K_3,3

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