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
103 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
il y a cinq mois
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 il y a cinq mois et a été effectuée par AD.
Re: Équivalence graphes simples et orientés
il y a cinq mois
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 il y a cinq mois 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: 139 636, Messages: 1 361 233, Utilisateurs: 25 256.
Notre dernier utilisateur inscrit Excellent.


Ce forum
Discussions: 774, Messages: 6 217.

 

 
©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