Équivalence graphes simples et orientés

Informellement tu peux "effacer les flèches" sur le dessin d'un graphe orienté. Si les arêtes d'un graphe orienté sont un ensemble $A$ de couples de sommets $(a, b)$, tu peux écrire la fonction $f$ qui à un graphe $G=(S, A)$ associe $(S, \{ \{a, b\}\ |\ (a, b)\in A\})$ (je considère que les arêtes d'un graphe non orienté sont des ensembles à un ou deux éléments). $f(G)$ est le "graphe non orienté sous-jacent à $G$" : tous les théorèmes valables sur $f(G)$ ont une interprétation sur $G$. Note d'ailleurs que $f$ n'est pas injective en général, c'est-à-dire que deux graphes non orientés qui ont la même image par $f$ ont la "même interprétation" quand on les voit non orientés (= ils sont dans la même classe d'équivalence de la relation "avoir la même image par $f$"). Exemple : les graphes a -> b et b -> a s'envoient sur a -- b.

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)\}$).