Définitions
Définition
Un
graphe orienté \( \G\) est la donnée de :
- \( (i)\)
- Un ensemble fini et non vide noté \( \Som(\G)\) appelé les sommets du graphe \( \G\) .
- \( (ii)\)
- Un ensemble noté \( \Arc(\G)\) appelé les Arcs du graphe \( \G\) dont les éléments sont des couples de \( \Som(\G)\) .
Par exemple \( \Som(\G)=\left\{a,b,c,d,e,f\right\}\) et \( \Arc(\G)=\left\{(a,b), (a,c), (b,b), (c,d), (d,a), (d,e), (d,f), (e,a), (f,a)\right\}\) définissent un graphe orienté.
Définition
Un
graphe non orienté \( \G\) est la donnée de :
- \( (i)\)
- Un ensemble fini et non vide noté \( \Som(\G)\) appelé les sommets du graphe \( \G\) .
- \( (ii)\)
- Un ensemble noté \( \Ar(\G)\) appelé les arêtes du graphe \( \G\) dont les éléments sont des ensembles formés de deux éléments de \( \Som(\G)\) .
Par exemple, \( \Som(\G)=\{a,b,c,d,e,f\}\) et \( \Ar(\G)=\left\{
\{a,c\},\{a,d\},\{a,e\},\{a,f\},\{b,c\},\{b,e\},\{c,f\}
\right\}\) définissent un graphe non orienté.
On prendra garde à ne pas confondre les notations et à ne pas mélanger avec les notions de graphe orienté et non orienté.
Un arc est un couple.
Une arête est un ensemble.
Alors que, dans le cas orienté, il y a une différence entre les arcs \( (a,b)\) et \( (b,a)\) il n'y a, dans le cas non orienté, aucune différence entre les arêtes \( \{a,b\}\) et \( \{b,a\}\) .
De même, alors que \( (a,a)\) a un sens dans le cas orienté, il n'y a aucun sens à parler de l'arête \( \{a,a\}\) . En particulier, dans le cas non orienté, aucun sommet ne boucle sur lui-même.
Remarque
Dans la suite on parlera simplement de graphe pour ne pas avoir a distinguer les graphes orientés des graphes non orientés.
Définition
Soient \( \G\) et \( \G'\) deux graphes. On dira que \( \G'\) est un
sous-graphe de \( \G\) , noté \( \G'\subseteq\G\) si
- \( (i)\)
- \( \Som(\G')\subseteq\Som(\G)\)
- \( (ii)\) Cas non orienté :
- \( \Ar(\G')\subseteq\Ar(\G)\)
- \( (ii)\) Cas orienté :
- \( \Arc(\G')\subseteq\Arc(\G)\)
Définition
Soient \( \G\) un graphe et \( P\subset\Som(\G)\) . On définit \( \G'\) le
graphe engendré par \( P\) par
- \( (i)\)
- \( \Som(\G')=P\) ,
- \( (ii)\) Cas non orienté :
- \( \Ar(\G')=\left\{\{x,y\}\in\Ar(\G)\Big|(x,y)\in \Som(\G')^2\right\}\)
- \( (ii)\) Cas orienté :
- \( \Arc(\G')=\left\{(x,y)\in \Arc(\G)\Big|(x,y)\in\Som(\G')^2\right\}\)