Théorème d'Euler et lemme de sperner

[invitecef3c426]

Bonjour,


J'aimerais savoir si le théorème d'Euler pour les graphes planaires peut etre étendu aux graphes non planaires car j'ai cherché mais je n'ai pas trouvé, j'ai vu qu'elle s'étendait aux graphes non connexes, mais après je ne sais pas.

Egalement je voulais savoir si quelqu'un connait une démonstration simple (sans introduire la notion de simplexe) du lemme de sperner, personnellement je n'ai pas compris celle de wikipédia, j'essaie d'en rédiger une avec mes propres mots mais c'est compliqué.

merci, au revoir.
-----

[invitecef3c426]

Finalement je viens de trouver une preuve assez simple pour le lemme de sperner à l aide des graphes duals, cependant j'ai toujours besoin d'aide pour le theorème d'euler.

[invite179e6258]

bonjour,

qu'appelles-tu théorème d'Euler? celui qui donne une cns pour qu'il existe un parcours eulérien dans un graphe? ou bien le fameux s-a+f=2 ?

[invitecef3c426]

j'essaye de généraliser le S-A+F=2 aux graphes non planaires

[A voir en vidéo sur Futura]

[invite179e6258]

ça a été fait. Pour un graphe quelconque tu peux définir les faces comme les cycles minimaux. Tu verras que le théorème ne se généralise pas (tu peux obtenir toutes sortes de valeurs pour s-a+f). Par contre si tu te restreins aux graphes plongés sur une surface donnée, tu as bien une relation s-a+f=cste (il faut que les faces soient simplement connexes)