graphe complet et simple

[Cédric]

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.

[sos-math(21)]

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) :

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).

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.
Bonne continuation

[Cédric]

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.

[sos-math(21)]

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

[Cédric]

Bonsoir,
Merci beaucoup d'avoir apporté des réponses aussi claires et précises à mes questions !
C.

[sos-math(21)]

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