Le forum SOS-MATH interrompra son service de modération des messages tous les dimanches de 14h00 à minuit.
Bien entendu, la consultation du forum reste toujours possible.

graphe orienté

Retrouver tous les sujets résolus.

graphe orienté

Messagepar Cédric le Mer 16 Oct 2019 17:19

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.
Cédric
 

Re: graphe orienté

Messagepar SoS-Math(31) le Mer 16 Oct 2019 18:46

Bonjour Cédric,
Voici une vidéo qui t'expliquera le cas du graphe orienté :https://www.youtube.com/watch?v=1UzCnQOCMeY
SoS-Math(31)
 
Messages: 1173
Inscription: Lun 12 Oct 2015 10:33

Re: graphe orienté

Messagepar Cédric le Jeu 17 Oct 2019 07:03

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.
Cédric
 

Re: graphe orienté

Messagepar sos-math(21) le Ven 18 Oct 2019 11:43

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
sos-math(21)
 
Messages: 7477
Inscription: Lun 30 Aoû 2010 11:15


Retourner vers Forum terminale