MATHS EXPERTES : Question graphes théorème d'Euler

[ANTHONYP]

Bonjour, j'ai un exercice sur le théorème d'Euler et je bloque, le but est de le démontrer dans le cas du cycle eulérien :
Considérons un graphe connexe G ; pour un sommet s, nous noterons s(o) le nombre d'arête dont s est l'origine et s(e) le nombre d'arête dont s est l'extrémité.
1. Exprimer le degré d'un sommet s en fonction de s(e) et s(o)
2. Supposons qu'un cycle eulérien existe, justifier que pour tout sommet s, on a s(e) = s(o). En déduire que le degré de s est nécéssairement pair.

Pour la première question, j'ai trouve d(s) = (s(o)+s(e))/2 mais je ne suis pas sûr. Merci.

[Ben314]

Je comprend pas grand chose.
Déjà, la notation où la variable est et la fonction me laisse un peu perplexe vu que je suis pas vraiment habitué à noter l'image de 5 par la fonction sinus, mais bon, les notations, c'est jamais que des notations.

Ensuite, si tu différencie les arêtes d'origine s de celle d'extrémité s, ça signifie que tu as un graphe orienté (sinon c'est totalement couillon) et dans ce cas, la définition la plus courante du "degré" d'un sommet, c'est que c'est la somme du degré sortant et du degré entrant.
Donc, par définition, le degré, c'est (avec tes notations).

Sauf que, le léger problème, c'est que ce que je connais des cycles eulériens, en particulier le théorème d'Euler, ben ça concerne les graphes non orientés . . .
Bref, ton énoncé il dit quoi concernant le graphe : orienté ou pas ?

EDIT : En fait, s'il n'y avait pas la première question, je pourrait comprendre : on part d'un graphe non orienté et on suppose qu'il possède un cycle Eulérien, c'est à dire un chemin passant une fois et une seule par chaque arrête. Donc en parcourant le cycle, ça permet d'orienter toutes les arrêtes et on obtient trivialement que les degrés des sommets doivent êtres pairs vu que le cycle est arrivé au sommet autant de fois qu'il en est parti.

[ANTHONYP]

Enfait l'énoncé c'est ça :

Théorème et conclusion :
Théorème d'Euler. Un graphe connexe :
- possède ub cycle eulérien si tous ses sommets sont de degré pair,
- possède une chaîne eulérienne si exactement deux de ses sommets sont de degré impair.
Nous allons démontrer ce théorème dans le cas du cycle : considérons un graphe connexe G ; pour un sommet s, nous noterons sO le nombre d'arête dont s est l'origine et sE le nombre d'arête dont S est l'extrémité.
1. Exprimer le degré d'un sommet s en fonction de sE et sO
2. Supposons qu'un cycle eulérien existe, justifier que pour tout sommet s, on a sE = sO.
En déduire que le degré de s est nécessairement pair.
3. On admet la propriété suivante : "Si tous les degrés des sommets d'un graphe sont pairs, alors tout sommet a un cycle". Supposons que tous les degrés de G soient pairs et qu'il n'existe pas de cycle eulérien, soit alors C un cycle de longueur maximale.
a) Soit G' le graphe G auquel on a enlevé toutes les arêtes de C. Montrer que tous les sommets de G sont de degré pair.
b) Montrer qu'il existe un sommet s de C de degré non nul dans G'.
c) En déduire que s admet un cycle dans G', puis construire un cycle plus long que C.
d) Conclure sur l'existence d'un cycle eulérien.

Je ne comprends pas pourquoi la question 1. est posée alors qu'on ne sait pas si on parle de graphes orientés ou non, car deg(s) = sO + sE ne fonctionne que pour des graphes orientés.

[lyceen95]

Avant d'arriver à la question 1, on nous parle d'arêtes qui ont une origine. Donc d'arêtes orientées. Donc d'un graphe orienté.
Distinguer sO et sE n'a pas de sens pour un graphe non orienté.

[ANTHONYP]

Donc l'exercice est mal fait ? C'est tiré de mon manuel de MATHS EXPERTES et il y a beaucoup d'erreurs dessus donc cela ne m'étonnerait pas.

[Ben314]

Dans ce cas, part sur ce que j'ai mis dans mon précédent message :

I) On part d'un graphe (non orienté) et on suppose qu'il possède un cycle Eulérien, c'est à dire un chemin passant une fois et une seule par chaque arrête. On considère que ce chemin est parcouru dans un certain sens.
1) Que peut on dire du nombre de fois où le chemin arrive à une arête donnés par rapport au nombre de fois où il part de cette même arête ?
2) Que peut-on en déduire concernant le degré du sommet en question ?
3) Montrer que, si aucun sommet n'est isolé (i.e. de degré 0), le graphe est forcément connexe.

II) Réciproquement, on part d'un graphe (non orienté) connexe et on suppose que tout les sommets sont de degré pair. Partant d'un sommet quelconque on parcours une arêtes de vers un certain somme puis une arrête différente de à , etc (en ne reprenant jamais une arête déjà utilisée).
1) Pourquoi le processus est-il forcé de s'arrêter ?
2) Montrer qu'à la fin, lorsque l'on est bloqué, c'est qu'on est forcément revenu à .
3) On suppose que le circuit ainsi construit ne passe pas par toutes les arrêtes.
3)a) En utilisant la connexité du graphe, montrer qu'il y a au moins un des sommets parcourus sur lequel toutes les arêtes n'ont pas été utilisées.
3)b) En déduire que l'on peut construire un autre circuit partant de (et revenant à ) ne passant par aucune des arrêtes déjà utilisées.
3)c) Conclure.

Dans le cas des chemins Eulérien, même démarche pour la première partie et, pour la réciproque,, on peut simplement rajoute une arrête "fictive" pour rendre les degrés des sommets pairs.