théorie des graphes:théorème d'Euler
Bonjour
Y aurait-il une démonstration ou un raisonnement simple permettant de démontrer le théorème d'Euler en théorie des graphes ?
"dans un graphe connexe , il existe une chaine eulérienne ssi le nombre de sommets de degré impair est 0 ou 2
dans un graphe connexe, il existe un cycle eulérien ssi tous les sommets sont pairs".
autre question plus orientée concours, pensez-vous qu'à l'oral du capes un jury est en droit d'attendre la démo de ce théorème dans le cadre de loral 1 ? Sachant que cette preuve est admise en terminale eco ?
Merci
Y aurait-il une démonstration ou un raisonnement simple permettant de démontrer le théorème d'Euler en théorie des graphes ?
"dans un graphe connexe , il existe une chaine eulérienne ssi le nombre de sommets de degré impair est 0 ou 2
dans un graphe connexe, il existe un cycle eulérien ssi tous les sommets sont pairs".
autre question plus orientée concours, pensez-vous qu'à l'oral du capes un jury est en droit d'attendre la démo de ce théorème dans le cadre de loral 1 ? Sachant que cette preuve est admise en terminale eco ?
Merci
Réponses
-
pensez-vous qu'à l'oral du capes un jury est en droit d'attendre la démo de ce théorème dans le cadre de loral 1 ?
La notion de "droit" et de concours... Si tu fais une jolie preuve, je ne vois pas pourquoi ça ne te rapporterait pas de points???
Tu pars d'un point de degré impair et va à un point de degré pair en effaçant l'arête que tu viens de parcourir.
Si le graphe restant est connexe c'est fini (formulation récurrence exercice, t'as pris le graphe contre-exemple minimum)
Il te reste les cas chiants (mais sans difficulté particulière, en pensant que t'a aussi le droit de buter d'un coup l'éventuelle arête qui joint les 2 impairs)
Idem pour "tout le monde pair"
Réciproque plus uniforme: quand un chemin passe par s, il yentre et en sort (donc 2 arêtes à chaque fois)Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.2K Toutes les catégories
- 9 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 53 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 63 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 313 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 773 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres
In this Discussion
Qui est en ligne 27
+17 Invités