# Graphe Orienté

Cette section présente pour commencer la notion de graphe orienté en introduisant conjointement la notion de graphe et d'orientation.

## Définition de graphe orienté

 ![](http://www.geog.umontreal.ca/geotrans/fr/ch2fr/meth2fr/img/Image4.gif)

Le graphe $G$ peut se représenter de la façon suivante :

$G=(X,U)$

$X \\subseteq U \\times U$

Avec :

$X=\\{Sommets\\}=\\{1,2,3,4,5\\}$

$U=\\{Arcs\\}=\\{(1,2),(1,3),(2,2),(2,5),(4,2),(4,3),(4,5)\\}$

## Définition de successeur et prédécesseur

### Définition de successeur

Soit $\\mathcal{T}^{+}(S)$, l'ensemble des **successeurs** de $S$ (ie les sommets $Y$ tels que $(S,Y) \\in U$)

On a donc : $\\mathcal{T}^{+} & : & X & \\to & P \\\\$ où $P \\subseteq U$

En reprenant notre exemple, nous avons :

$\\mathcal{T}^{+}(1) & = & \\{2,3\\}$

$\\mathcal{T}^{+}(2) & = & \\{2,5\\}$

$\\mathcal{T}^{+}(3) & = & \\varnothing$

$\\mathcal{T}^{+}(4) & = & \\{3,2,5\\}$

$\\mathcal{T}^{+}(5) & = & \\varnothing$

### Définition de prédécesseur

Soit $\\mathcal{T}^{-}(S)$, l'ensemble des **prédecessuers** de $S$ (ie les sommets $Y$ tels que $(Y,S) \\in U$)

On a donc : $\\mathcal{T}^{-} & : & X & \\to & P \\\\$ où $P \\subseteq U$

En reprenant notre exemple, nous avons :

$\\mathcal{T}^{-}(1) & = & \\varnothing$

$\\mathcal{T}^{-}(2) & = & \\{2,1,4\\}$

$\\mathcal{T}^{-}(3) & = & \\{1,4\\}$

$\\mathcal{T}^{-}(4) & = & \\varnothing$

$\\mathcal{T}^{-}(5) & = & \\{2,4\\}$

## Définition de demi-degré intérieur et demi degré-extérieur

### Définition de demi-degré extérieur

Le **demi-degré extérieur** noté $d^{+}(S)$ d'un sommet $S$ est le nombre de successeurs du sommet $S$ : $d^{+}(S)=\\#\\mathcal{T}^{+}(S)$

Exemple :

$d^{+}(1)=\\#\\mathcal{T}^{+}(1) & = & \\#\\{2,3\\} = 2$

$d^{+}(2)=\\#\\mathcal{T}^{+}(2) & = & \\#\\{2,5\\} = 2 $

$d^{+}(3)=\\#\\mathcal{T}^{+}(3) & = & \\#\\varnothing = 0$

$d^{+}(4)=\\#\\mathcal{T}^{+}(4) & = & \\#\\{3,2,5\\} = 3 $

$d^{+}(5)=\\#\\mathcal{T}^{+}(5) & = & \\#\\varnothing = 0$

### Définition de demi-degré intérieur

Le **demi-degré intérieur** noté $d^{-}(S)$ d'un sommet $S$ est le nombre de prédécesseur du sommet $S$ : $d^{-}(S)=\\#\\mathcal{T}^{-}(S)$

Exemple :

$d^{-}(1)=\\#\\mathcal{T}^{-}(1) & = & \\#\\varnothing = 0$

$d^{-}(2)=\\#\\mathcal{T}^{-}(2) & = & \\#\\{2,1,4\\} = 3$

$d^{-}(3)=\\#\\mathcal{T}^{-}(3) & = & \\#\\{1,4\\} = 2$

$d^{-}(4)=\\#\\mathcal{T}^{-}(4) & = & \\#\\varnothing = 0$

$d^{-}(5)=\\#\\mathcal{T}^{-}(5) & = & \\#\\{2,4\\} = 2$

## Définition de chemin et de boucle

Un **chemin** est une suite d'arcs tel que l'extrémité terminale d'un arc coïncide avec l'extrémité initiale du suivant.

Dans notre exemple nous avons comme chemin : $((1,2),(2,2),(2,5))=((1,2,2,5))$ ou $((4,2),(2,5))=(4,2,5)$

Une boucle est un arc du type $(S,S)$ où $S \\in X$

## Définition de circuit

Prenons le nouveau graphe $G\_{2}$ suivant :

 ![](http://www.geog.umontreal.ca/geotrans/fr/ch2fr/meth2fr/img/Image9.gif)

$G\_{2}=(X\_{2},U\_{2})$

Avec :

$X\_{2}=\\{1,2,3,4,5,6\\}$

$U\_{2}=\\{(1,2),(2,4),(4,1),(2,3),(5,4),(3,6),(5,6)\\}$

Un **circuit** est un chemin dont le premier sommet coïncide avec le dernier et qui ne passe pas 2 fois par le même arc.

Il y a 2 circuits dans ce graphe qui sont :

$((1,2),(2,4),(4,1)) = (1,2,4,1)$

$((1,2),(2,5),(5,4),(4,1)) = (1,2,5,4,1)$

## Définition de chemin Hamiltonien

Un **chemin Hamiltonien** dans un graphe est un chemin qui passe une et une seule fois par chaque sommet du graphe

 ![](http://geekz.fr/IMG/png/09.png)

Le chemin (1,2,3,5,4,1) est un chemin Hamiltonien (Le sommet 1 étant inscrit en double pour montrer la jointure)

# Graphe Non Orienté

## Définition de graphe non orienté

Le graphe $G\_{3}$ peut se représenter de la façon suivante :

 ![](http://www.geog.umontreal.ca/geotrans/fr/ch2fr/meth2fr/img/Image14.gif)

$G\_{3}=(X\_{3},U\_{3})$

$U\_{3}$ représente cette fois ci des **arrêtes**, car il n'y a pas d'orientation.

$X\_{3}=\\{Sommets\\}=\\{1,2,3,4,5\\}$

$U\_{3}=\\{Arrêtes\\}=\\{\\{1,2\\},\\{1,3\\},\\{2,3\\},\\{3,4,\\},\\{4,5\\}\\}$

## Définition d'une chaîne

Une **chaîne** est une suite d'arrête telle que toute arrête a une extrémité commune avec l'arrête précédente (sauf la première) et l'autre avec l'arrête suivante (sauf la dernière).

## Définition d'adjacence

Un sommet $Y$ est **voisin ou adjoint** d'un sommet $S$ si $\\{Y,S\\} \\in U$

Exemple : $3$ a comme voisins $1,2$ et $4$

On note $\\mathcal{T}(S)$, l'ensemble des **voisins ou adjoints** de $S$

Dans notre exemple : $\\mathcal{T}(S) = \\{1,2,3\\}$

## Définition de degré

Le degré noté $d(S)$ d'un sommet $S$ est le nombre de voisins du sommet $S$ : $d(S)=\\#\\mathcal{T}(S)$

Exemple :

$d(1)=#\\mathcal{T}(1)=\\#\\{2,3\\}=2$

$d(2)=#\\mathcal{T}(2)=\\#\\{1,3\\}=2$

$d(3)=#\\mathcal{T}(3)=\\#\\{1,2,4\\}=3$

$d(4)=#\\mathcal{T}(4)=\\#\\{3,5\\}=2$

$d(5)=#\\mathcal{T}(5)=\\#\\{4\\}=1$

## Définition de cycle

Un cycle est une chaîne dont les 2 extrémités coîncident et qui ne passe pas 2 fois par la même arrête.

Exemple : $(1,2,3,1)$ est un cycle.

## Définition de chaîne Eulérienne

Une chaine eulérienne est une chaîne qui passe une et une seule fois par chaque arrête

 ![](http://www.anglaisfacile.com/cgi2/myexam/images/21624.jpg)

$(1,2,5,4,3,1)$ est une chaîne eulérienne.

#### Théorème d'Euler

*Un graphe [/divers/cours/theorie_des_graphes_et_optimisation_dans_les_graphes/connexite_forte_connexite_fermeture_transitive](/doc/1bce86c3-bb5a-4edb-8e68-97c1158e4f4d) admet une chaîne eulérienne ssi le nombre de sommets de degrés impairs est de 0 ou de 2.*

Pour un graphe connexe $G$, $\\exists$ chaîne eulérienne dans $G \\Leftrightarrow \\#\\{S \\in X, d(S)=1\[2\]\\} \\in \\{0,2\\}$

Il suffit donc de calculer le degré de tous les sommets et de dénombrer ceux qui sont impaires et de voir si le résultat est 0 ou 2.

Dans notre exemple :

$d(1)=2$

$d(2)=3$

$d(3)=3$

$d(4)=2$

$d(5)=2$

Le nombre de sommets de degrés impairs étant de $2$ (le sommet $2$ et le sommet $3$), il existe bien une chaîne eulérienne dans ce graphe.

# Sources

[http://www.geog.umontreal.ca/geotrans/fr/ch2fr/meth2fr/ch2m1fr.html](http://www.geog.umontreal.ca/geotrans/fr/ch2fr/meth2fr/ch2m1fr.html "http://www.geog.umontreal.ca/geotrans/fr/ch2fr/meth2fr/ch2m1fr.html")

[http://geekz.fr/Definitions-sur-les-graphes](http://geekz.fr/Definitions-sur-les-graphes "http://geekz.fr/Definitions-sur-les-graphes")

[http://www.mathematiquesfaciles.com/graphes-chaine-eulerienne-niveau-t-es_2_45326.htm](http://www.mathematiquesfaciles.com/graphes-chaine-eulerienne-niveau-t-es_2_45326.htm "http://www.mathematiquesfaciles.com/graphes-chaine-eulerienne-niveau-t-es_2_45326.htm")