Bonjour,
peut-on appliquer le théorème d'Euler dans le cas d'un graphe orienté en prenant pour degré de chaque sommet le nombre d'arêtes qui partent et arrivent à ce sommet ?
Merci !
C.
graphe orienté
-
Cédric
-
SoS-Math(31)
- Messages : 1360
- Enregistré le : lun. 12 oct. 2015 10:33
Re: graphe orienté
Bonjour Cédric,
Voici une vidéo qui t'expliquera le cas du graphe orienté :https://www.youtube.com/watch?v=1UzCnQOCMeY
Voici une vidéo qui t'expliquera le cas du graphe orienté :https://www.youtube.com/watch?v=1UzCnQOCMeY
-
Cédric
Re: graphe orienté
Bonjour,
merci pour votre réponse mais dans notre cours et le livre, contrairement à la vidéo, dans le cas d'un graphe orienté, le degré d'un sommet se calcule en ajoutant les arêtes qui arrivent au sommet et celles qui partent du sommet.
Est-ce que cela change quelque chose à l'application du théorème d'Euler :
"un graphe connexe admet une chaîne eulérienne non fermée si et seulement si deux sommets exactement ont un degré impair.
Un graphe connexe admet un cycle eulérien si et seulement si tous les sommets sont de degré pairs." ?
Merci.
C.
merci pour votre réponse mais dans notre cours et le livre, contrairement à la vidéo, dans le cas d'un graphe orienté, le degré d'un sommet se calcule en ajoutant les arêtes qui arrivent au sommet et celles qui partent du sommet.
Est-ce que cela change quelque chose à l'application du théorème d'Euler :
"un graphe connexe admet une chaîne eulérienne non fermée si et seulement si deux sommets exactement ont un degré impair.
Un graphe connexe admet un cycle eulérien si et seulement si tous les sommets sont de degré pairs." ?
Merci.
C.
-
sos-math(21)
- Messages : 10401
- Enregistré le : lun. 30 août 2010 11:15
Re: graphe orienté
Bonjour,
le théorème d'Euler peut se transférer aux cas de graphes orientés mais, on utilise dans ce cas la notion de connexité forte : un graphe orienté est fortement connexe lorsque pour tous sommets \(u\) et \(v\) de ce graphe, il existe un chemin de \(u\) à \(v\) (un chemin qui respecte les orientations des arêtes).
La version du théorème d'Euler est alors la suivante : Soit G un graphe orienté fortement connexe. Alors G est eulérien (il possède un cycle eulérien) si et seulement si pour tout sommet de G, le degré extérieur (nombre de flèches partant de ce sommet) est égal au degré intérieur (nombre de flèches arrivant au sommet).
Je te donne le lien vers la page wikipedia qui en parle : https://fr.wikipedia.org/wiki/Graphe_eul%C3%A9rien#Le_cas_orient%C3%A9
Bonne continuation
le théorème d'Euler peut se transférer aux cas de graphes orientés mais, on utilise dans ce cas la notion de connexité forte : un graphe orienté est fortement connexe lorsque pour tous sommets \(u\) et \(v\) de ce graphe, il existe un chemin de \(u\) à \(v\) (un chemin qui respecte les orientations des arêtes).
La version du théorème d'Euler est alors la suivante : Soit G un graphe orienté fortement connexe. Alors G est eulérien (il possède un cycle eulérien) si et seulement si pour tout sommet de G, le degré extérieur (nombre de flèches partant de ce sommet) est égal au degré intérieur (nombre de flèches arrivant au sommet).
Je te donne le lien vers la page wikipedia qui en parle : https://fr.wikipedia.org/wiki/Graphe_eul%C3%A9rien#Le_cas_orient%C3%A9
Bonne continuation