Bonjour à tous,
Voilà je cherche à démontrer la formule d'Euler concernant les graphes planaires connexes pour justifier l'utilisation du théorème des 4 couleurs sur la carte des régions de France (hors Corse).
J'ai lu différents articles et cours sur les bases de la théorie des graphes pour avoir une idée assez précise.
Donc si j'ai bien compris les démonstrations que j'ai lu (ce qui me semble pas tout à fait correct parce qu'il y a un détail qui me fait douter), on peut utiliser un raisonnement par récurrence avec comme hypothèse de départ soit a le nombre d'arêtes, n le sombre de sommets : a = n - 1.
On commence par l'initialisation pour n = 1, il n'y a effectivement aucune arête, jusque là tout va bien.
Ensuite on passe à l'hérédité et c'est là que je doute un peu, donc imaginons que j'ajoute un sommet, cela ajoute automatiquement une arête vu que le graphe est connexe, mais voilà mon premier souci c'est qu'ici à l'ajout d'une arête, une nouvelle face est créée et le nombre de sommets ne varie pas.
Ce qui revient à écrire a + 1 = n - 1 + f et on retrouve bien la formule d'Euler qui dit n + f = a + 2.
Mais n'aurai-je pas oublié quelques détails ? Parce que ça me parait un peu succinct comparé à la taille des démonstrations que j'ai pu voir.
Merci à vous.
Sperca
PS : Et bonne rentrée 2008
-----