Passer d'un graphe normal à graphe triangulés

[allezlolo]

Bonsoir à tous,

j'essaye de décrypter les différentes lignes de la fausse preuve de Kempe sur la théorie des graphes et nottement le coloriage en 4 couleurs d'une carte géorgraphique. adresse : http://www.enseignement.polytechnique.fr/profs/informatique/Georges.Gonthier/pi2000/pro/gonthier/)


Je bloque hélas sur ce petit passage à 2 endroits (je pense avoir compris la suite) :


tout d'abord :

Code: Tout sélectionner

La transformation carte-graphe est en fait une dualité. En effet les ``routes'' d'un graphe planaire délimitent aussi des régions du plan, appelées faces du graphe, et le graphe de la carte des faces n'est autre que... le graphe des fontières de la carte d'origine !

Serait-il possible de m'expliquer cela un peu plus en détail avec exemple car j'ai vraiment du mal à comprendre ?

ainsi que ce passage :

Code: Tout sélectionner

On remarque que l'on peut se limiter au coloriage des graphes connexes triangulés, dont chaque face est délimitée par exactement trois routes (y compris la face infinie qui entoure le graphe tout entier). En effet, on peut obtenir un graphe triangulé GT à partir d'un graphe G quelconque en supprimant les routes parallèles, et en ajoutant n-3 routes diagonales en travers de chaque région n-gonale (n³ 4); alors, tout 4-coloriage de GT sera aussi un 4-coloriage de G.

Je ne coprends pas comment à partir de n'importe quel graphe, je peux obtenir un graphe triangulés et que le coloriage est équivalent, j'aimerai bien si possible aussi un exemple ?

Merci d'avance pour votre aide

[busard_des_roseaux]

Bonjour,

pour la dualité, intuitivement, les "intérieurs" deviennent des éléments,
des sommets d'un graphe dual,, que l'on relie par une arête (dans le dual) ssi ils ont une frontière commune dans le graphe initial.


si tu veux, les sommets d'un graphe peuvent réprésenter n'importe quel objet
physique, puisque les arêtes signifient simplement que deux objets sont en relation. On peut donc considérer comme sommet d'un nouveau graphe (le dual) les "intérieurs" des pays et dessiner une arête,dans le dual, si deux "intérieurs" ont une frontière commune.

enfin, l'idée naïve, c'est ptet de remonter le graphe plan sur une sphère,
via la fonction réciproque de la projection stéréographique,
en rajoutant un point à l', parce que sur une sphère,
tous les pays jouent le même rôle. le graphe dual est connexe
et doit avoir des chaines eulériennes