formule d'Euler

Zaoul
Zaoul
dans Combinatoire et Graphes
Bonjour
Soit $G=(V,E)$ un graphe simple. La formule d'Euler dit que \quad $\displaystyle \sum_{v \in V} d(v)=2|E|.$
Je comprends bien le principe de la preuve qui consiste à compter deux fois les arêtes. Je n'arrive cependant pas à exhiber une preuve très (trop ?) rigoureuse qui ne contient pas de "on voit bien que". En effet, il doit être possible d'introduire une bijection ou une relation d'équivalence pour montrer que deux cardinaux sont égaux. Comment diable faire cela ?
Merci

[Edit: La case $\LaTeX$. Greg]

Réponses

  • Bu
    Bu
    Il suffit de compter de deux manières différentes les couples $(v,e)$ formés d'un sommet $v$ et d'une arête $e$ d'ayant $v$ pour extrémité.
    Ce principe du "double compte" est souvent utilisé en combinatoire (par exemple, pour démontrer la formule de Burnside).
  • Zaoul
    Zaoul
    Merci. Je vais regarder.
  • francois51
    francois51
    En même temps je ne vois pas ce qu'il y a de non rigoureux dans ce que tu disais, une preuve ça peut être quelque chose de simple, même sans calcul.
  • Bu
    Bu
    La simplicité est importante, mais encore faut-il qu'on voit clairement le point clé de l'argument. Où est l'argument dans "compter deux fois les arêtes" ? Par contre, je pense qu'on voit l'argument dans "compter de deux manières différentes les adjacences de sommets et d'arêtes". L'ensemble dont on compte le cardinal est alors clairement défini, et le compte du cardinal de cet ensemble peut difficilement être qualifié de "calcul".
Connectez-vous ou Inscrivez-vous pour répondre.

Bonjour!

Pour participer au forum, cliquer sur l'un des boutons :

Connexion S'inscrire

Catégories

In this Discussion

Qui est en ligne 13

Lirone93Milasjayberaoul.S +9 Invités