Graphes terminale ES

[bloublou91]

Bonjour à tous,
j'ai un DM a faire pendant les vacances et un exercice me pose problème:

1) Démontrer que si un graphe complet admet un cycle eulérien, alors l'ordre de ce graphe est impair.
2) quels sont les graphes complets qui admettent une chaîne eulérienne ?


merci d'avance de m'aider !

[SaintAmand]

Bonsoir,

j'ai un DM a faire pendant les vacances et un exercice me pose problème:

À peine les vacances viennent-elles de commencer que tu déclares forfait... En plus le problème est intéressant. C'est chouette la théorie des graphes non ?

1) Démontrer que si un graphe complet admet un cycle eulérien, alors l'ordre de ce graphe est impair.
2) quels sont les graphes complets qui admettent une chaîne eulérienne ?

Examine des graphes d'ordre 1, 2, 3, 4, ... C'est un bon moyen de comprendre ce qui se passe.

[bloublou91]

je pense avoir trouver la réponse à la 1 :

Si un graphe complet est d'ordre pair N, alors ses sommets sont de degré N-1, nombre impair. Or pour admettre un graphe eulérien, le degré de tous les sommets doit être pair donc si un graphe complet admet un cycle eulérien alors il est d'ordre impair.

voila !

et donc pour la 2) ....

[bloublou91]

ha j'ai aussi trouvé pour la 2 :

Dans un graphe complet, tous les sommets sont de même degré et pour admettre une chaine eulérienne, un graphe ne doit posséder que 2 sommets de degré impair ce qui est impossible dans un graphe complet. Or un cycle eulérien est une chaîne eulérienne fermée donc, d'après la question précédente, les graphes complets d'ordre impair sont les seuls à admettre une chaîne eulérienne qui est alors fermée.

[gigamesh]

ha j'ai aussi trouvé pour la 2 :

Dans un graphe complet, tous les sommets sont de même degré et pour admettre une chaine eulérienne, un graphe ne doit posséder que 2 sommets de degré impair ce qui est impossible dans un graphe complet. Or un cycle eulérien est une chaîne eulérienne fermée donc, d'après la question précédente, les graphes complets d'ordre impair sont les seuls à admettre une chaîne eulérienne qui est alors fermée.

M'ouais. Un point de vocabulaire quand même : quand une chaîne est fermée on parle de cycle ; par conséquent si on te demande une chaîne c'est qu'on souhaite que les extrémités soient distinctes ; ce qui fait que bien que tu dises des choses justes tu ne réponds pas à la question telle qu'elle est posée.

En creusant un peu, tu vas t'apercevoir qu'il y a un seul ordre pour lequel le graphe complet possède une chaîne eulérienne (c'est-à-dire, j'insiste, avec des extrémités distinctes).

[gigamesh]

un graphe ne doit posséder que 2 sommets de degré impair ce qui est impossible dans un graphe complet

Impossible ? Essaie encore !

[SaintAmand]

par conséquent si on te demande une chaîne c'est qu'on souhaite que les extrémités soient distinctes ;

Une chaine peut avoir des extrémités identiques.

[gigamesh]

Une chaine peut avoir des extrémités identiques.

Ouaip, ça s'appelle un cycle ; mais à mon avis on attend une réponse plus spécifique que celle qui a été proposée.

[bloublou91]

Impossible ? Essaie encore !

oui c'est impossible car dans un graphe complet tous les sommets sont relié entre eux et sont donc tous de même degrés ! donc il ne peut pas y avoir seulement 2 de degré impairs.

et pour le voc je pense que c'est bon paske dans un exercice on a déjà mis ca et c'etait bon !
merci bien sur !!