Pensez à lire la Charte avant de poster !

$\newcommand{\K}{\mathbf K}$


Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
134 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 

Équivalence graphes simples et orientés

Envoyé par jma 
jma
Équivalence graphes simples et orientés
l’an passé
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.



Edité 1 fois. La dernière correction date de l’an passé et a été effectuée par AD.
Re: Équivalence graphes simples et orientés
l’an passé
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)\}$).



Edité 3 fois. La dernière correction date de l’an passé et a été effectuée par Athanagor.
Seuls les utilisateurs enregistrés peuvent poster des messages dans ce forum.

Cliquer ici pour vous connecter

Liste des forums - Statistiques du forum

Total
Discussions: 144 519, Messages: 1 435 844, Utilisateurs: 26 911.
Notre dernier utilisateur inscrit Tohcip.


Ce forum
Discussions: 826, Messages: 6 849.

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page