graphe complet et simple
graphe complet et simple
Bonjour,
Je me situe dans le cas de graphes non orientés.
Peut-on affirmer qu'un graphe complet est forcément simple ?
Merci beaucoup !
En effet, j'ai comme définition d'un graphe simple , un graphe qui a au plus une arête qui relie 2 sommets et s'il n'y a pas de boucle.
J'ai comme définition de l'adjacence : 2 sommets reliés par une arête sont dits adjacents. Mais est-ce que cela sous-entend exactement UNE ?
Et j'ai comme définition de complet : un graphe est complet si tous ses sommets sont deux à deux adjacents. Les boucles sont-elles exclues ?
Tous les exemples de graphes complets de mon livre sont simples. Voilà pourquoi je me pose ces questions.
Merci !
C.
Je me situe dans le cas de graphes non orientés.
Peut-on affirmer qu'un graphe complet est forcément simple ?
Merci beaucoup !
En effet, j'ai comme définition d'un graphe simple , un graphe qui a au plus une arête qui relie 2 sommets et s'il n'y a pas de boucle.
J'ai comme définition de l'adjacence : 2 sommets reliés par une arête sont dits adjacents. Mais est-ce que cela sous-entend exactement UNE ?
Et j'ai comme définition de complet : un graphe est complet si tous ses sommets sont deux à deux adjacents. Les boucles sont-elles exclues ?
Tous les exemples de graphes complets de mon livre sont simples. Voilà pourquoi je me pose ces questions.
Merci !
C.
-
- Messages : 10398
- Enregistré le : lun. 30 août 2010 11:15
Re: graphe complet et simple
Bonjour,
je viens de vérifier dans les manuels dont je dispose sur les graphes et la définition de graphe complet s'applique à un graphe simple (voir aussi wikipedia : https://fr.wikipedia.org/wiki/Graphe_complet) :
Bonne continuation
je viens de vérifier dans les manuels dont je dispose sur les graphes et la définition de graphe complet s'applique à un graphe simple (voir aussi wikipedia : https://fr.wikipedia.org/wiki/Graphe_complet) :
Cette définition sous-entend que l'adjacence est définie par une unique arête dans le cas des graphes non orientés. Les propriétés afférentes au graphe complet d'ordre \(n\) \(K_n\), notamment son nombre total d'arêtes \(\dfrac{n(n-1)}{2}\) viennent confirmer cette définition d'adjacence.En théorie des graphes, un graphe complet est un graphe simple dont tous les sommets sont adjacents deux à deux, c'est-à-dire que tout couple de sommets disjoints est relié par une arête. Si le graphe est orienté, on dit qu'il est complet si chaque paire de sommets est reliée par exactement deux arcs (un dans chaque sens).
Bonne continuation
Re: graphe complet et simple
Bonsoir,
merci beaucoup pour vos précisions !
Puis-je vous poser une dernière question à ce sujet ?
Je connais le théorème d'Euler dans le cas de graphes CONNEXES NON orientés, à savoir :
G admet un cycle eulérien si et seulement si tous les sommets de G sont de degré pair.
G admet une chaîne eulérienne NON fermée si et seulement si le nombre de sommets de degré impair de G est exactement 2.
Ce théorème connaît-il une extension pour les graphes orientés (en parlant de degré entrant et de degré sortant) ?
Comment est définie la connexité pour les graphes orientés ?
Merci !
C.
merci beaucoup pour vos précisions !
Puis-je vous poser une dernière question à ce sujet ?
Je connais le théorème d'Euler dans le cas de graphes CONNEXES NON orientés, à savoir :
G admet un cycle eulérien si et seulement si tous les sommets de G sont de degré pair.
G admet une chaîne eulérienne NON fermée si et seulement si le nombre de sommets de degré impair de G est exactement 2.
Ce théorème connaît-il une extension pour les graphes orientés (en parlant de degré entrant et de degré sortant) ?
Comment est définie la connexité pour les graphes orientés ?
Merci !
C.
-
- Messages : 10398
- Enregistré le : lun. 30 août 2010 11:15
Re: graphe complet et simple
Bonjour,
pour les graphes orientés on a la proposition suivante :
Soit G un graphe fortement connexe (c'est-à-dire que pour tous sommets \(u\) et \(v\) du graphe, il existe un chemin de \(u\) à \(v\) et un chemin de \(v\) à \(u\)). G admet un cycle eulérien si et seulement si chaque sommet a le même degré entrant et sortant.
Bonne continuation
pour les graphes orientés on a la proposition suivante :
Soit G un graphe fortement connexe (c'est-à-dire que pour tous sommets \(u\) et \(v\) du graphe, il existe un chemin de \(u\) à \(v\) et un chemin de \(v\) à \(u\)). G admet un cycle eulérien si et seulement si chaque sommet a le même degré entrant et sortant.
Bonne continuation
Re: graphe complet et simple
Bonsoir,
Merci beaucoup d'avoir apporté des réponses aussi claires et précises à mes questions !
C.
Merci beaucoup d'avoir apporté des réponses aussi claires et précises à mes questions !
C.
-
- Messages : 10398
- Enregistré le : lun. 30 août 2010 11:15
Re: graphe complet et simple
Bonjour,
pour conclure ce message, je cite une source qui te permet de vérifier la validité de mon message : https://www.lamfa.u-picardie.fr/fdurand ... xpose2.pdf (page 32)
Bonne continuation
pour conclure ce message, je cite une source qui te permet de vérifier la validité de mon message : https://www.lamfa.u-picardie.fr/fdurand ... xpose2.pdf (page 32)
Bonne continuation