Répondre à la discussion
Affichage des résultats 1 à 2 sur 2

Théorie des graphes : démonstration de la formule d'Euler



  1. #1
    sperca

    Théorie des graphes : démonstration de la formule d'Euler

    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

    -----


  2. #2
    invite986312212
    Invité

    Re : Théorie des graphes : démonstration de la formule d'Euler

    bonjour,

    il y a des démonstrations de la formule d'Euler sans récurrence, mais si tu y tiens, je crois qu'il vaut mieux raisonner sur le nombre d'arêtes.

    pour ce qui est du théorème des quatre couleurs et de sa preuve, on en trouve un certain nombre d'expositions, certaines adoptant un point de vue strictement combinatoire, d'autres faisant une part à la topologie (la question est à la jonction des deux disciplines). Par exemple pour un combinatoricien, il est évident que le graphe dual d'un graphe planaire est planaire, ou que les faces d'un graphe planaire connexe sont simplement connexes, etc.

    l'exposé que je préfère est celui de Fritsch & Fritsch publié chez Springer.

Sur le même thème :

Discussions similaires

  1. Théorie des graphes
    Par NAGHAM dans le forum Mathématiques du supérieur
    Réponses: 0
    Dernier message: 01/01/2008, 13h18
  2. Théorie des graphes
    Par -Zweig- dans le forum Lectures scientifiques
    Réponses: 4
    Dernier message: 21/12/2007, 11h05
  3. Theorie des graphes
    Par BioBen dans le forum Mathématiques du supérieur
    Réponses: 1
    Dernier message: 29/11/2007, 18h25
  4. Théorie des graphes et graphes de liaisons
    Par Eogan dans le forum Mathématiques du supérieur
    Réponses: 2
    Dernier message: 08/12/2006, 22h59
  5. Théorie des graphes: un seul chemin
    Par Brumaire dans le forum Mathématiques du supérieur
    Réponses: 3
    Dernier message: 11/12/2004, 00h36