t

[cours-maths-dis.git] / graphes / GraphesOrientes.tex

\section{Définitions}

\subsection{Digraphe (graphe orienté), sommet, arc}

En donnant un sens aux arêtes d'un graphe, on obtient un digraphe, ou graphe orienté.


\begin{Rem}
De l'anglais directed graph.
\end{Rem}

\begin{Def}[Digraphe, sommets, arcs]
Un \emph{digraphe}\index{digraphe}\index{graphe!orienté} fini $G = (V, E)$ est défini par :
\begin{itemize}
\item l'ensemble fini $V = \{v_1, v_2, ..., v_n\}$ ($|V| = n$) dont les éléments sont appelés \emph{sommets} \index{sommets},
\item et par l'ensemble fini $E = \{e_1, e_2, ..., e_m\}$ ($|E| = m$) dont les éléments sont appelés \index{arcs}\emph{arcs}.
\end{itemize}
Un arc $e$ de l'ensemble $E$ est défini par une paire ordonnée de sommets. Lorsque $e = (u, v)$, on dira que l'arc $e$ va de $u$ à $v$. On dit aussi que $u$ est l'extrémité initiale et $v$ l'extrémité finale de $e$.
\end{Def}


\begin{Ex}
Un exemple de digraphe :\\
\begin{center}
\includegraphics[scale=0.7]{graphes/digraphe111}
\end{center}
\end{Ex}



\begin{Exo}
Construire un graphe orienté dont les sommets sont les entiers compris entre 1 et 12 et dont les arcs représentent la relation \og être diviseur de \fg{}.
\end{Exo}

\begin{Exo}
 Quel est le nombre maximal d'arêtes dans un graphe orienté d'ordre $n$ qui ne possède pas d'arêtes parallèles ?
\end{Exo}


\begin{Ex}
Le graphe d'une relation binaire peut être assimilé à un graphe orienté.
\end{Ex}

\begin{Rem}
Les graphes orientés peuvent être représentés graphiquement, comme dans le cas non-orienté. On place alors des flèches au lieu de simples segments.
\end{Rem}

\subsection{Degré d'un sommet d'un digraphe}

Soit $v$ un sommet d'un graphe orienté.

\begin{Def}[Degré extérieur]
Le \emph{degré extérieur}\index{degré!extérieur} du sommet $v$ est le nombre d'arcs ayant $v$ comme extrémité initiale.
\end{Def}

\begin{Notation}
On le note $d_+(v)$.
\end{Notation}

\begin{Def}[Degré intérieur]
Le \emph{degré intérieur}\index{degré!intérieur} du sommet $v$ est le nombre d'arcs ayant $v$ comme extrémité finale.
\end{Def}

\begin{Notation}
On le note $d_-(v)$.
\end{Notation}


\begin{Th}
On a : $$d(v) = d_+(v) + d_-(v)$$.
\end{Th}

\begin{Exo}
Soit $G$ un graphe orienté quelconque. Démontrez que la somme des degrés entrants de tous les sommets est égal à la somme de tous les degrés sortants.
\end{Exo}

\noindent\textit{\underline{Réponse :}} Chaque arête compte une fois dans la somme des degrés entrants et une fois dans la somme des degrés sortants...
% 
% \begin{Exo}
% Trouvez les degrés extérieurs et intérieurs de chacun des sommets du graphe ci-dessous :
% \begin{center}
% \includegraphics[scale=0.7]{digraphe1.eps}
% \end{center}
% \end{Exo}



\begin{Exo}
Soit X un ensemble de lapins, et G un graphe orienté ayant X pour ensemble de sommets. On dit que G est un «graphe de parenté» si les arcs de G codent la relation «être l'enfant de...». Quelles conditions doit nécessairement vérifier G pour pouvoir être un graphe de parenté? 
\end{Exo}

\subsection{Chemins et circuits}

\subsubsection{Chemin}
\begin{Def}[Chemin]
Un \emph{chemin}\index{chemin} conduisant du sommet $a$ au sommet $b$ est une suite de la forme ($v_0,e_1,v_1,e_2,v_2, ..., e_k,v_k$) où les $v_i$ sont des sommets ($v_0=a$ et $v_k=b$) et les $e_i$ sont des arcs tels que $e_i$ va de $v_{i-1}$ à $v_i$.
\end{Def}

\begin{Ex}
Sur le digraphe ci-dessous, on peut voir par exemple le chemin ($v_3,e_3,v_4,e_4,v_5$).

\begin{center}
\includegraphics[scale=0.7]{graphes/Digraphe1.eps}
\end{center}
\end{Ex}

\begin{Rem}
Par convention, tout chemin comporte au moins un arc.
\end{Rem}

\subsubsection{Distance}

\begin{Def}[Distance]
On appelle \emph{distance}\index{distance} entre deux sommets d'un digraphe la longueur du plus petit chemin les reliant.

S'il n'existe pas de chemin entre les sommets $x$ et $y$, on pose $d(x,y) = +\infty$.
\end{Def}

\begin{Ex}
Par exemple, sur le digraphe ci-dessus (exemple précédent), $d(v_1,v_5)=2$, $d(v_1,v_6)=1$, $d(v_6,v_1)=+\infty$.
\end{Ex}



\begin{Exo}
Donnez un algorithme permettant de calculer la distance entre deux sommets x et y d'un digraphe connexe.
\end{Exo}


\subsubsection{Circuit}
\begin{Def}[Circuit]
Un \emph{circuit}\index{circuit} est un chemin avec $u_0=u_k$.
\end{Def}

\begin{Ex}
Le digraphe ci-dessus ne contient pas de circuit.
\end{Ex}

\begin{Rem}
Les notions de longueur, de chemins et de circuits sont analogues à celles des chaînes et des cycles pour le cas non orienté.
\end{Rem}


\section{Digraphe fortement connexe}

\subsection{Définitions}

\subsubsection{Connexité forte}

\begin{Def}[Digraphe fortement connexe]
Un digraphe est \emph{fortement connexe}\index{digraphe!fortement connexe}, si toute paire ordonnée ($a$, $b$) de sommets distincts du graphe est reliée par au moins un chemin.
\end{Def}



\begin{Rem}
En d'autres termes, tout sommet est atteignable depuis tous les autres sommets par au moins un chemin.
\end{Rem}



\subsubsection{Composantes connexes}

\begin{Def}[Composante fortement connexe]
On appelle \emph{composante fortement connexe}\index{composante fortement connexe} tout sous-graphe induit maximal fortement connexe (maximal signifie qu'il n'y a pas de sous-graphe induit connexe plus grand contenant les sommets de la composante).
\end{Def}

\begin{Exo}
Les graphes ci-dessous sont-il fortement connexes? Si non, donnez leurs composantes fortement connexes.
\begin{center}
\includegraphics[scale=0.7]{graphes/digraphe2.eps}
\includegraphics[scale=0.7]{graphes/digraphe3.eps}
\end{center}
\end{Exo}


\begin{Exo}
Proposez un algorithme qui détermine si un graphe est fortement connexe ou non.
\end{Exo}
\textit{Indication :} utilisez un système de marquage des sommets.


\subsection{Circuits eulériens}


\begin{Th}
Dans le cas des graphes orientés, il y a équivalence entre :
\begin{itemize}
 \item posséder un circuit eulérien,
 \item être fortement connexe, tel que $d_+(s) = d_-(s)$ pour tout sommet $s$.
\end{itemize}
\end{Th}

\section{Matrice et listes d'adjacences}


\subsection{Matrices d'incidence}

\begin{Def}[Matrice d'incidence entrante et sortante]
On suppose que les arêtes et les sommets ont été numérotés.

On appelle \emph{matrice d'incidence sortante $J^+$}\index{matrice d'incidence!sortante} la matrice dont l'élément $J^+(s,\varepsilon)$ vaut
\begin{itemize}
\item 1 si le sommet $s$ est le début de l'arête ${\varepsilon}$,
\item 0 sinon.
\end{itemize}

On appelle de même \emph{matrice d'incidence entrante $J^-$}\index{matrice d'incidence!entrante} la matrice dont l'élément $(s,\varepsilon )$ vaut :
\begin{itemize}
\item 1 si le sommet $s$ est la fin de l'arête $\varepsilon$,
\item 0 sinon.
\end{itemize}
\end{Def}


\begin{Def}
On suppose à nouveau que les arêtes et les sommets du graphe orienté considéré ont été numérotées, et on appelle alors \emph{matrice d'incidence J} de ce graphe la matrice dont l'élément $(s,\varepsilon)$ vaut :
 \begin{itemize}
  \item 2 si $s$ est une extrémité de $\varepsilon$, quand $\varepsilon$ est une boucle,
 \item 1 si $s$ est une extrémité de $\varepsilon$, quand $\varepsilon$ n'est pas une boucle,
 \item 0 sinon.
 \end{itemize}
\end{Def}

\begin{Rem}
$J$ est la matrice d'incidence du graphe non orienté sous-jacent, obtenu en remplaçant les arcs (flèches) par des arêtes.
\end{Rem}


\begin{Exo}
Reprendre les graphes orientés dessinés dans ce chapitre, et trouver à chaque fois $J^+$, $J^-$ et $J$.
\end{Exo}

\subsubsection{Résultats}

On peut relier $d^+(s)$ (resp. $d^-(s)$) au nombre de 1 apparaissant dans $J^+$ (resp. $J^-$), comme suit.

\begin{Th}
Soient $(s_1, \hdots, s_n)$ les sommets d'un graphe orienté. Alors
\begin{enumerate}
 \item $\left( \begin{array}{c}
                d^+(s_1) \\
                \vdots \\
                d^+(s_n) \\
               \end{array} \right) = J^+ \left( \begin{array}{c}
                1 \\
                \vdots \\
                1 \\
               \end{array} \right)
$ et $\left( \begin{array}{c}
                d^-(s_1) \\
                \vdots \\
                d^-(s_n) \\
               \end{array} \right) = J^- \left( \begin{array}{c}
                1 \\
                \vdots \\
                1 \\
               \end{array} \right)
$
\item $J^{+}J^{-t} = \left( \begin{array}{ccc} d^+(s_1) & & 0 \\ & \ddots & \\ 0 & & d^+(s_n) \end{array}
 \right)$
\item $J^{-}J^{+t} = \left( \begin{array}{ccc} d^-(s_1) & & 0 \\ & \ddots & \\ 0 & & d^-(s_n) \end{array}
 \right)$
\end{enumerate}

\end{Th}

\begin{Exo}
Vérifier ces résultats avec les matrices d'incidences calculées dans l'exercice précédent.
\end{Exo}


\subsection{Matrice d'adjacence}

\subsubsection{Définition}
\begin{Def}[Matrice d'adjacence]
On peut représenter un digraphe par une \emph{matrice d'adjacence}\index{matrice!d'adjacence} :
\begin{itemize}
\item Les lignes et les colonnes représentent les sommets du graphe.
\item Un 1 à la position ($i$,$j$) signifie qu'un arc part de $i$ pour rejoindre $j$.
\end{itemize}
\end{Def}




\subsubsection{Exemple}

Voici un digraphe et sa matrice d'adjacence :

\begin{center}
\includegraphics[scale=0.7]{graphes/digraphe123.eps}
\end{center}

$$M = \left(\begin{array}{cccccc}
0 & 1 & 0 & 1 & 0 & 1 \\
0 & 0 & 0 & 1 & 1 & 0 \\
0 & 0 & 0 & 1 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 & 0 & 0 \\
\end{array}\right)
$$



\begin{Exo}
Décrivez le digraphe G ci-contre par une matrice d'adjacences.
\begin{center}
\includegraphics[scale=0.7]{graphes/digraphe4.eps}
\end{center}
\end{Exo}


\begin{Rem}
Se donner un graphe orienté revient à se donner sa matrice d'adjacence.
\end{Rem}

\subsubsection{Propriétés}

\begin{Th}
La matrice d'adjacence à plusieurs caractéristiques :
\begin{itemize}
\item Elle est carrée : il y a autant de lignes que de colonnes.
\item Il n'y a que des zéros sur la diagonale. Un 1 sur la diagonale indiquerait une boucle.
\item Contrairement au cas non orienté, elle n'est pas symétrique.
\end{itemize}
\end{Th}



\begin{Th}[Nombre d'arcs de longueur k]
$A^k(s,t)$, élément à la position $(s,t)$ de la puissance k\textsuperscript{ième} de A, est aussi le nombre d'arcs de longueur $k$ qui mènent de $s$ à $t$.
\end{Th}


\begin{Th}
 Soient $(s_1, \hdots, s_n)$ les sommets d'un graphe orienté. Alors
$$\left( \begin{array}{c} d^+(s_1)\\ \vdots \\ d^+(s_n) \end{array} \right) = A \left(\begin{array}{c}
                1 \\
                \vdots \\
                1 \\
               \end{array} \right) \textrm{ et } \left( \begin{array}{c} d^-(s_1)\\ \vdots \\ d^-(s_n) \end{array} \right) = A^t \left( \begin{array}{c}
                1 \\
                \vdots \\
                1 \\
               \end{array} \right) 
$$ 
\end{Th}





\begin{Exo}
Vérifier les propriétés ci-dessus sur la matrice d'adjacence calculée dans l'exercice précédent. On déterminera les chemins de longueur 2.
\end{Exo}



\begin{Th}[Lien entre les matrices d'adjacence]
Soit A la matrice d'adjacence d'un graphe orienté, et B la matrice d'adjacence du graphe non orienté qui lui est associé. Alors
$$\boxed{B = A+A^t}$$
\end{Th}


\begin{Exo}
Vérifier la dernière propriété sur le digraphe ci-dessous
\begin{center}
\includegraphics[scale=0.7]{graphes/digraphe4.eps}
\end{center}
\end{Exo}

\subsection{Lien entre matrices d'adjacences et d'incidences}


Les remarques précedentes permettent de conclure que se donner ($J^+,J^-$) ou $A$, \og c'est pareil \fg{}. Plus précisément, on a
$$\boxed{J^{+}J^{-t}  = A}$$



\begin{Exo}
On pose $$A=\left( \begin{array}{cccc} 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ \end{array}\right)$$
\begin{enumerate}
\item Dessinez le graphe orienté ayant $A$ pour matrice d'adjacence.
\item Déterminez ses matrices d'incidences.
\item Vérifiez, sur cet exemple, les formules précédentes.
\end{enumerate}
\end{Exo}


\begin{Exo}
A partir du graphe orienté $G$, on fabrique un graphe orienté $H$ en retournant le sens de toutes les flèches.
\begin{enumerate}
\item Comment sont liées les matrices d'incidence de $G$ et de $H$ ?
\item Comment sont liées leurs matrices d'adjacence ?
\end{enumerate}
\end{Exo}

\noindent\textit{\underline{Réponse :}} La matrice $J^+$ de $G$ est la matrice $J^-$ de $H$, et réciproquement. Leurs matrices d'adjacence sont transposées l'une de l'autre.



\begin{Th}
Soient $s_1, s_2, \hdots, s_n$ les sommets d'un graphe orienté. Alors
$$\left( \begin{array}{c} d(s_1) \\ \vdots \\ d(s_n) \end{array} \right) = J \left( \begin{array}{c}
                1 \\
                \vdots \\
                1 \\
               \end{array} \right)$$
\end{Th}

\begin{Th}[relation entre $J, J^+$ et $J^-$]
On note $J^+$ et $J^-$ les matrices d'incidences d'un graphe orienté, et J la matrice d'incidence du graphe non orienté qui lui est associé. Alors
$$\boxed{J = J^+ + J^-}$$
\end{Th}


\begin{Exo}
Vérifier ces propriété sur le digraphe ci-dessous
\begin{center}
\includegraphics[scale=0.7]{graphes/digraphe4.eps}
\end{center}
\end{Exo}


\subsection{Listes d'adjacence}


On peut encore représenter un digraphe à l'aide de listes d'adjacences : en donnant pour chacun de ses sommets la liste des sommets qu'on peut atteindre directement en suivant un arc (dans le sens de la flèche).


\begin{Ex}
Voici les listes d'adjacences du digraphe G:
\begin{center}
\includegraphics[scale=0.7]{graphes/digraphe11.eps}
\end{center}
\begin{tabular}{ccl}
1 & : & 2, 4, 6\\
2 & : & 4, 5\\
3 & : & 4\\
4 & : & 5\\
5 & : & -\\
6 & : & 2\\
\end{tabular}
\end{Ex}


\begin{Exo}
Décrivez le digraphe $G$ de l'exercice précédent par des listes d'adjacences.
\end{Exo}



\section{Digraphes sans circuits}

\subsection{Théorème}

\begin{Th}
Le digraphe $G = (V, E)$ est sans circuit si et seulement si on peut attribuer un nombre $r(v)$, appelé le \emph{rang}\index{rand!d'un sommet} de $v$, à chaque sommet $v$ de manière que pour tout arc $(u, v)$ de $G$ on ait $r(u) < r(v)$.
\end{Th}


\begin{Pre}
Si $G$ comporte un circuit $C$, il n'est pas possible de trouver de tels nombres $r(i)$ car, autrement, considérant $r(j) = max \{r(i) | i \in C\}$ et l'arc $(j, k) \in C$ on aurait $r(j) \leqslant r(k)$ en contradiction avec la définition de $r( )$.


Réciproquement, si $G$ n'a pas de circuits, il existe au moins un sommet sans prédécesseurs dans $G$ (sans cela, en remontant successivement d'un sommet à un prédécesseur, on finirait par fermer un circuit). Ainsi, on peut attribuer séquentiellement des valeurs $r( )$ aux sommets du graphe à l'aide de l'algorithme qui suit, ce qui conclura la démonstration.
\end{Pre}



\subsection{Algorithme de calcul du rang}

L'algorithme suivant permet de calculer $r(v)$ pour tout sommet v du digraphe. Il permet donc de savoir si un digraphe possède ou non un circuit.

Au début,
\begin{itemize}
\item r = 0, 
\item X est l'ensemble des sommets du digraphe.
\item R est l’ensemble des sommets de X sans prédécesseurs dans X.
\end{itemize}

Tant que X n’est pas vide, faire
\begin{itemize}
\item r(v) := r pour tout sommet v de R,
\item Enlever de X les sommets contenus dans R,
\item Recalculer R comme ci-dessus,
\item Incrémenter r.
\end{itemize}

\subsection{Exercice}

\begin{Exo}
Attribuez un rang aux sommets du digraphe ci-dessous en utilisant l'algorithme de calcul du rang :
\begin{center}
\includegraphics[scale=0.7]{graphes/rang.eps}
\end{center}
\end{Exo}






\gsaut
\centerline{\x{Fin du Chapitre}}