ENCORE UN GRAPHE
Accueil Remonter

 

 

 C’est en 1968 que la conjecture de P. J. Heawood a enfin été résolue. Autrement dit ce cher Heawood, avait trouvé dés la fin du XIXème siècle, une technique permettant de dire si un graphe est planaire dans un espace à deux dimension, dans un tore, ou encore une autre figure à deux dimensions. En fait il aura même fallu attendre 1969, pour une démonstration complète, par : T. Youngs et G. Ringel. Notons au passage que la dites démonstration tien dans un petit livre, et donc je vous laisse vous y pencher dessus si le coeur vous en dit, pour ma part, non merci.

C'est grâce à cette conjecture, que nous pourrons dire s'il est possible de relier 5 maisons par un chemin, sur un tore, sans les croiser.

  1. Tout d'abord appelons notre graphe K. Comme il a 5 sommets (5 maisons), appelons le K5, partant de là, un graphe a n sommets, est appelé Kn.

  2. Le graphe K5, n'est pas planaire sur une surface de genre 0, c'est à dire une surface non percée par un trou. On dira par exemple que le tore est une surface de genre 1, car il a un trou.

  3. On appellera genre d'un graphe, le genre minimum sur lequel le graphe aura une bonne représentation géométrique, c'est à dire que les arêtes ne se croisent pas. (pour nous, se sont les routes)

  4. Voilà enfin ce que nous dit Heawood : le genre de Kn est égal au plus petit entier immédiatement supérieur à: ((n-3)(n-4))/12

    Voyons ce que ça donne, avec K5 : ((5-3)(5-4))/12 = 1/6 soit : 0,1666666666...

    et l'entier immédiatement supérieur est 1, donc on peut tracer K5 dans un tore! Formidable non? Il ne reste plus qu'à dessiner, mais bon, là je vous laisse travailler un peu, alors je vous donne un tore, munissez vous d'un feutre fin et au boulot. Vous pouvez directement le faire sur l'écran, comme ça à chaque fois que vous repasserez par ici, vous aurez votre graphe au bon endroit, et la vous allez en épater plus d'un(e).

     

 
v>