Équivalence graphes simples et orientés
Bonjour
Au tout début du Que sais-je ? "La théorie des graphes" par Aimé Sache, je lis : "Bien entendu chaque graphe G={X,U} permet de définir un 1-graphe ou un graphe simple (ceux-ci sont en fait que des classes d'équivalence de graphes). De ce fait, tous les théorèmes obtenus pour les graphes simples sont encore valables pour les graphes G orientés...".
Je ne sais pas comment interpréter cette phrase.
Pour aller plus loin, est-ce que toute l'étude des graphes orientés est contenu dans l'étude des graphes simples ?
Merci pour vos réponses.
Cordialement.
Au tout début du Que sais-je ? "La théorie des graphes" par Aimé Sache, je lis : "Bien entendu chaque graphe G={X,U} permet de définir un 1-graphe ou un graphe simple (ceux-ci sont en fait que des classes d'équivalence de graphes). De ce fait, tous les théorèmes obtenus pour les graphes simples sont encore valables pour les graphes G orientés...".
Je ne sais pas comment interpréter cette phrase.
Pour aller plus loin, est-ce que toute l'étude des graphes orientés est contenu dans l'étude des graphes simples ?
Merci pour vos réponses.
Cordialement.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Une autre présentation, plus générale, des graphes c'est d'avoir un couple $G=(S, A)$, sans définir directement les éléments de $A$. Pour eux on définit des fonctions $or$ et $de$ tels que pour tout élément $a\in A$, on a $or(a)\in S$ et $de(a)\in S$ (origine et destination de l'arc $a$ respectivement). Les graphes simples (dans ma définition, mais elle doit être proche de ce que tu as !) sont ceux tels que $or(a)\neq de(a)$ (pas de boucle) et $\{or(a), de(a)\} = \{or(b), de(b)\} \implies a = b$ (deux arêtes de mêmes extrémités sont identiques). Les théorèmes sur les graphes simples non orientés sont ceux qui ne différencient pas $or$ et $de$ (ils ne considèrent que les ensembles $\{ or(a), de(a)\}$).