Bonjour,
est-il normal qu'il n'existe pas de graphe connexe avec 1 seul sommet de degré impair ?
Existe-il un graphe avec 1 seul sommet de degré impair ?
Merci !
C.
graphes
-
sos-math(21)
- Messages : 10401
- Enregistré le : lun. 30 août 2010 11:15
Re: graphes
Bonjour,
il y a une propriété importante valable pour tous les graphes non orientés :
En conséquence, ce qui est important de retenir, c'est la somme des degrés d'un graphe est toujours un nombre pair ce qui interdit l'existence d'un unique sommet de degré impair puisque la somme de plusieurs nombres pairs et d'un seul nombre impair est un nombre impair.
Plus généralement, on obtient que le nombre de sommets de degré impair est pair : il peut donc y en avoir 0, 2, 4,...
Cette propriété s'applique au cas général et don aussi au cas d'un graphe connexe.
J'espère que cela répond à ta question
Bonne continuation
il y a une propriété importante valable pour tous les graphes non orientés :
En effet, déterminer le degré d'un sommet revient à compter le nombre d'arêtes dont il est l'une des extrémités. Lorsqu'on fait la somme des degrés des sommets d'un graphe, le comptage revient donc à compter exactement deux fois chaque arête.Propriété : la somme des degrés des sommets d'un graphe (non orienté) est égale au double du nombre d'arêtes (lemme des poignées de main)
En conséquence, ce qui est important de retenir, c'est la somme des degrés d'un graphe est toujours un nombre pair ce qui interdit l'existence d'un unique sommet de degré impair puisque la somme de plusieurs nombres pairs et d'un seul nombre impair est un nombre impair.
Plus généralement, on obtient que le nombre de sommets de degré impair est pair : il peut donc y en avoir 0, 2, 4,...
Cette propriété s'applique au cas général et don aussi au cas d'un graphe connexe.
J'espère que cela répond à ta question
Bonne continuation
-
Cédric
Re: graphes
Merci infiniment,
voilà pourquoi le théorème d'Euler peut aussi s'écrire :
G admet une chaîne eulérienne si et seulement si G admet au plus 2 sommets de degré impair.
Je comprends mieux.
Bonne soirée !!!
C.
voilà pourquoi le théorème d'Euler peut aussi s'écrire :
G admet une chaîne eulérienne si et seulement si G admet au plus 2 sommets de degré impair.
Je comprends mieux.
Bonne soirée !!!
C.
-
sos-math(21)
- Messages : 10401
- Enregistré le : lun. 30 août 2010 11:15
Re: graphes
Bonjour,
oui c'est cela, il faut tout de même la condition que le graphe soit connexe :
La version que tu cites est un simple corollaire (une conséquence) :
Bonne continuation
oui c'est cela, il faut tout de même la condition que le graphe soit connexe :
cette condition est indispensable pour construire la démonstration : (G avec sommets de degré pair ) \(\Rightarrow\) (G possède un cycle eulérien). Cette démonstration s'appuie sur un raisonnement par récurrence en utilisant les degrés des sommets qui sont tous supérieurs à deux.théorème d'Euler : Un graphe connexe possède un cycle eulérien si et seulement si tous ses sommets sont de degré pair.
La version que tu cites est un simple corollaire (une conséquence) :
Si tu veux en savoir plus, je te joins un cours dispensé à des lycéens pour les olympiades de maths : les démonstrations y figurent.Corollaire du théorème d'Euler : Un graphe connexe possède un chemin eulérien si et seulement si le nombre de ses sommets de degré impair est 0 ou 2.
De plus, si le graphe possède exactement deux sommets de degré impair alors toutchemin eulérien commence en un de ces sommets et se termine à l'autre.
graphes-cours.pdf- (376.64 Kio) Téléchargé 157 fois
-
Cédric
Re: graphes
Bonjour,
merci pour cet éclairage supplémentaire qui me fait bien comprendre toutes les subtilités et les conditions indispensables de validité du théorème.
Avec toute ma gratitude,
C.
merci pour cet éclairage supplémentaire qui me fait bien comprendre toutes les subtilités et les conditions indispensables de validité du théorème.
Avec toute ma gratitude,
C.