\chapter{Les graphes :\\structures relationnelles}

\begin{exointro}{Lycée Turgot, Paris}
On considère le graphe pondéré suivant:

\Par

\begin{figure}
\begin{center}
\includegraphics{129_04-graphe-crs-exointro}
\end{center}
\end{figure}

\Par

Implémenter ce graphe en Python, puis trouver le chemin le plus court de P à H.
\end{exointro}

\begin{problematique}
La gestion des réseaux, qu'ils soient routiers, électriques ou sociaux, est un enjeu majeur de l'informatique.

Comment représenter de telles structures ?
\end{problematique}

\newpage

\section{Notion de graphes}

\begin{defin}
Un \textit{graphe} $G=(V,E)$ est la donnée :
\begin{itemize}
\item d'un ensemble $V$ d'éléments, appelés \textit{sommets} (appelés aussi \textit{n\oe uds});
\item d'un ensemble $E$ dont les éléments sont des parties à un ou deux éléments de $V$, nommés \textit{arêtes} ou \textit{arcs}.
\end{itemize}
\end{defin}
\index{Graphes!Sommets}
\index{Graphes!N{\oe}uds}
\index{Graphes!Arcs}
\index{Graphes!Arêtes}

\begin{Remarque}
nous avons utilisé les lettres $V$ et $E$ pour respectivement \textit{Vertex} (\og sommet \fg)  et \textit{Edge} (\og fil \fg, sous-entendu : le fil reliant deux sommets).
\end{Remarque}

Un graphe est utilisé pour représenter le lien entre divers objets ou entités.


\begin{Exemple}
$V=\{A;B;C\}$ et $E=\big\{ (A,B) ; (A,C) ; (C) \big\}$.

Dans ce cas, $G=(V,E)$ est le graphe de sommets $A$, $B$ et $C$, où $A$ et $B$ sont reliés, $A$ et $C$ sont reliés et où $C$ est connecté à lui-même.
\end{Exemple}

\begin{defin}
La \textit{représentation sagittale} d'un graphe $G=(V,E)$ est un schéma où les\linebreak éléments de $V$ sont représentés par des disques et où les éléments de $E$ sont représentés par des traits (rectilignes ou courbés).
\end{defin}
\index{Graphes!Sagittale (représentation)}
\begin{Exemple}
une représentation sagittale du graphe défini dans l'exemple précédent est la suivante:
\Par
\begin{figure}
\begin{center}
\includegraphics{130_01-crs-graphe-repSag}
\figcaption{Représentation sagittale du graphe $G=(V,E)$\\avec $V=\{A;B;C\}$ et $E=\big\{ (A,B) ; (A,C) ; (C) \big\}$}
\end{center}
\end{figure}
\end{Exemple}

\enlargethispage*{2em}
Par la suite, par souci de simplification, on confondra le graphe et sa\linebreak représentation sagittale.

\begin{defins}[vocabulaire]
\begin{itemize}
\item L'\textit{ordre} d'un graphe est le nombre de ses sommets.
\item Un graphe est dit \textit{cyclique} s'il existe un chemin reliant n'importe quel sommet à lui-même.
\item Un graphe est dit \textit{connexe} si ses sommets peuvent être reliés deux à deux par une arête ou un arc.
\item Un \textit{chemin} est une suite de sommets reliés par une arête.
\end{itemize}
\end{defins}
\index{Graphes!Ordre}
\index{Graphes!graphe cyclique}
\index{Graphes!Graphes connexe}

\newpage

\section{Les différents types de graphes}

Il existe deux types de graphes : \textit{orientés} et \textit{non orientés}.

\subsection{Graphes non orientés}

\begin{defin}
Un graphe \textit{non orienté} est un graphe dont les \textit{arêtes} n'ont pas de sens.
\end{defin}


Cela signifie que si $G=(V,E)$ est un graphe avec $V=\{A;B;C\}$ alors les éléments $(A,B)$ et $(B,A)$ de $E$ sont identiques.


\begin{Exemple}
trois villes A, B et C sont reliées par un réseau routier:
\begin{itemize}
\item A et B sont reliées par une route;
\item A et C sont reliées par une route;
\item B et C sont reliées par une route.
\end{itemize}
On peut alors représenter ce réseau routier par le graphe suivant $G=(V,E)$ où:
\Par
\begin{center}
$V=\{A;B;C\}$ et $E=\big\{ (A,B) ; (A,C) ; (B,C) \big\}$
\end{center}
\Par
dont une représentation sagittale est:

\Par

\begin{figure}
\begin{center}
\includegraphics{131_01-crs-graphe-non-oriente}
\figcaption{Représentation sagittale d'un graphe non orienté}
\label{graphe-non-oriente}
\end{center}
\end{figure}

\Par

Ce graphe est d'ordre 3 (car il y a 3 sommets); il est de plus connexe et cyclique.
\end{Exemple}

\begin{Remarque}
la représentation sagittale d'un graphe n'est pas unique car on peut, par exemple, placer les sommets n'importe où.
\end{Remarque}

\enlargethispage*{\baselineskip}
\index{Graphes!Sommets adjacents}
\index{Graphes!Graphe simple}
\index{Graphes!Boucle}

\begin{defins}
Dans un graphe non orienté,
\begin{itemize}
\item deux sommets reliés par une arête sont dits \textit{adjacents};
\item une arête ne possédant qu'un élément est une \textit{boucle};
\item un graphe qui ne comporte pas de boucle est qualifié de \textit{simple}.
\end{itemize}
\end{defins}


\subsection{Graphes orientés}

\begin{defin}
Un graphe \textit{orienté} est un graphe dont les \textit{arcs} ont un sens.
\end{defin}

\vspace*{-5mm}
\begin{Remarque}
cela signifie que dans le graphe $G=(V,E)$ où $V=\{A;B;C\}$, les éléments $(A,B)$ et $(B,A)$ sont distincts.
\end{Remarque}

\vspace*{-3mm}
\begin{Exemple}
\mbox{imaginons un site internet composé de trois pages, nommées A, B et C.}
\begin{itemize}
\item Sur A sont présents des liens vers B et C.
\item Sur B figure un lien vers C.
\item Sur C figure un lien vers A.
\end{itemize}
On peut représenter ceci à l'aide d'un graphe où les sommets sont A, B et C et où les arcs représentent les liens.
\Par
\begin{figure}
\begin{center}
\includegraphics{132_01-crs-graphe-oriente}
\figcaption{Représentation sagittale d'un graphe orienté}
\label{ex:graphe-oriente}
\end{center}
\end{figure}
\end{Exemple}

\index{Graphes!Arêtes}
\index{Graphes!Arcs}

\begin{aretenir}
Un graphe non orienté a des \textit{arêtes}.

Dans un graphe orienté, les arêtes sont souvent appelées \textit{arcs}.
\end{aretenir}

\begin{defins}
Soit $G=(V,E)$ un graphe orienté. Si $(A,B)$ est un arc de $G$ alors:
\begin{itemize}
\item $A$ est appelé le \textit{prédécesseur} de $B$;
\item $B$ est appelé le \textit{successeur} de $A$.
\end{itemize}
\end{defins}

\vspace*{-3mm}
\begin{Remarque}
on dit aussi que pour un arc $(A,B)$, $A$ est son \textit{origine} et $B$ son\linebreak \textit{extrémité}.
\end{Remarque}

\enlargethispage*{5em}
\vspace*{-3mm}
\subsection{Graphes pondérés}
\vspace*{-3mm}
\begin{defins}
On dit d'un graphe qu'il est \textit{pondéré} (ou \textit{valué}) quand ses arêtes ou ses arcs sont couplés avec des nombres. Ces nombres sont appelés des \textit{poids}.
\end{defins}
\newpage

\begin{Exemple}[graphe pondéré]
imaginons le cas d'un livreur dont le parcours peut être représenté par le graphe suivant:

\Par\Par

\begin{figure}
\begin{center}
\includegraphics{133_04-graphe-crs-pondere}
\figcaption{Graphe du livreur}
\label{graphe-pondere}
\end{center}
\end{figure}

\Par\Par

Les nombres attribués à chaque arc représentent ici le temps (en minutes) qu'il met pour aller d'un sommet à un autre.
\end{Exemple}

\index{Graphes!Plus court chemin}
\vspace*{-3mm}
\begin{defin}[plus court chemin]
Dans le cas d'un graphe pondéré, on appelle \textit{plus court chemin} le chemin dont la somme des pondérations est minimale.
\end{defin}

\begin{Exemple}
dans l'exemple précédent, le plus court chemin de A à E est:

\Par

\begin{center}
A -- B -- F -- E
\end{center}

\Par

dont le poids total est : $1 + 8 + 7 = 16$.
\end{Exemple}

\enlargethispage*{5em}
\vspace*{-5mm}
\section{Matrices de représentation}
\vspace*{-3mm}
\subsection{Matrice d'adjacence (graphe non pondéré)}

\index{Graphes!Matrice d'adjacence}
\vspace*{-3mm}
\begin{defin}
Soit $G$ un graphe d'ordre $n$. On appelle \textit{matrice d'adjacence de $G$} la matrice carrée $M=(m_{ij})$ d'ordre $n$ telle que:
\begin{itemize}
\item si $G$ est non orienté, 
\[
m_{ij}=\begin{cases}
1 & \text{si les sommets $i$ et $j$ sont adjacents}\\
0 & \text{sinon}
\end{cases}
\]
\Break
\item si $G$ est orienté, 
\[
m_{ij}=\begin{cases}
1 & \text{si le sommet $i$ est l'origine d'un arc}\\
& \text{dont le sommet $j$ en est l'arrivée}\\
0 & \text{sinon}
\end{cases}
\]
\end{itemize}
\end{defin}

\begin{Exemple}
~\Par
\begin{center}
\includegraphics{131_01-crs-graphe-non-oriente}
\end{center}
\Par
Ce graphe admet pour matrice d'adjacence:
\[
\NiceMatrixOptions{code-for-first-row=\color{DB}\scriptstyle,code-for-last-col=\color{DB}\scriptstyle}
M = \begin{pNiceMatrix}[first-row,last-col=4]
A  & B & C\\
0 & 1  & 1 & A\\
1 & 0  & 1 & B\\
1 & 1  & 0 & C
\end{pNiceMatrix}
\]
En effet, 
\begin{itemize}
\item le sommet $A$ n'est pas relié à lui-même (donc il y a un \og 0 \fg{} à l'intersection de la 1\iere{} ligne et de la 1\iere{} colonne);
\item les sommets $A$ et $B$ sont reliés (donc il y a un \og 1 \fg{} à l'intersection de la 1\iere{} ligne et de la 2\ieme colonne, ainsi qu'à l'intersection de la 1\iere{} colonne et de la 2\ieme{} ligne;
\item etc.
\end{itemize}
\end{Exemple}

\begin{prop}
La matrice d'adjacence d'un graphe non orienté est nécessairement symétrique par rapport à sa diagonale principale (diagonale qui va du haut-gauche vers le bas-droit de la matrice).
\end{prop}

\enlargethispage*{5em}
\begin{Exemple}[graphe orienté]
~\Par
\begin{minipage}{0.45\linewidth}
\includegraphics{132_01-crs-graphe-oriente}
\end{minipage}
\hfill
\begin{minipage}{0.45\linewidth}
Ce graphe admet pour matrice\\
d'adjacence:
\[
\NiceMatrixOptions{code-for-first-row=\color{DB}\scriptstyle,code-for-last-col=\color{DB}\scriptstyle}
M = \begin{pNiceMatrix}[first-row,last-col=4]	
A  & B & C\\
0 & 1  & 1 & A\\
0 & 0  & 1 & B\\
1 & 0  & 0 & C
\end{pNiceMatrix}
\]
\end{minipage}
\Break
En effet,
\begin{itemize}
\item le sommet $A$ n'est pas relié à lui-même (d'où le \og 0 \fg{} à l'intersection de la 1\iere{} ligne et 1\iere{} colonne;
\item il y a un arc de $A$ vers $B$, d'où le \og 1 \fg{} à l'intersection de la 1\iere{} ligne et 2\ieme{} colonne mais pas d'arc de $B$ vers $A$, d'où le \og 0 \fg{} à l'intersection de la 2\ieme{} ligne et 1\iere{} colonne;
\item etc.
\end{itemize}
\end{Exemple}

%\begin{Remarque}La matrice d'adjacence n'est pas très adaptée aux graphes ayant peu d'arêtes ou d'arcs car dans ce cas, elle comporte beaucoup de zéros et de la mémoire est sollicitée pour rien lors de son implémentation en y mettant beaucoup de \og 0 \fg.\end{Remarque}

\subsection{Matrice de valuation (graphe pondéré)}
\enlargethispage*{\baselineskip}
\index{Graphes!Matrice de valuation}
\begin{defin}
La \textit{matrice de valuation} d'un graphe pondéré d'ordre $n$ est la matrice $(m_{i,j})$ telle que:
\begin{itemize}
\item $m_{i,j}$ est le poids de l'arête (ou arc) du sommet $i$ au sommet $j$;
\item $m_{i,j}=+\infty$ si aucune arête (ou arc) ne relie les sommets $i$ et $j$.
\end{itemize}
\end{defin}

\begin{Remarque}
en Python, par convention, on remplace « $+\infty$ » par « 0 » ou \linebreak « None ».
\end{Remarque}

\begin{Exemple}
reprenons le graphe de l'exemple du livreur (figure \ref{graphe-pondere} page \pageref{graphe-pondere}).

Sa matrice de valuation est:
\[
\NiceMatrixOptions{code-for-first-row=\color{DB}\scriptstyle,code-for-last-col=\color{DB}\scriptstyle}
M = \begin{pNiceMatrix}[first-row,last-col=7]
A  & B & C & D & E & F\\
0 & 1  & 17 & 0 & 0 & 0 & A\\
3 & 0  & 15 & 13 & 0 & 8 & B\\
19 & 14  & 0 & 15 & 11 & 0 & C\\
0 & 15 & 12 & 0 & 5 & 0 & D\\
0 & 0 & 9 & 7 & 0 & 6 & E\\
0 & 7 & 0 & 0 & 7 & 0 & F
\end{pNiceMatrix}
\]
\end{Exemple}

%\textit{Voir exercices \ref{exo:05-qcm1} à \ref{exo:05-maison} pages \pageref{exo:05-qcm1} et \pageref{exo:05-maison}.}

\section{Implémentation d'un graphe}

\subsection{Densité d'un graphe}

\begin{defin}
La densité d'un graphe est égale au rapport du nombre d'arêtes sur le nombre total d'arêtes possibles.

La densité est donc un nombre compris entre 0 et 1.
\end{defin}

\begin{Remarques}
\begin{itemize}
\item Une densité nulle correspond à un graphe sans arêtes : tous les sommets sont isolés.

\item Une densité égale à 1 correspond à un graphe complet: chaque sommet est relié à tous les sommets, y compris lui-même.
\end{itemize}
\end{Remarques} 

\begin{Exemple}
pour un graphe simple non orienté à $n$ sommets, chaque sommet ne peut être relié qu'à $n-1$ sommets au maximum (car le graphe est simple, donc il n'y a pas de boucle). Il y a donc $n(n-1)$ arêtes au maximum.

La densité du graphe est alors:
\[
d = \dfrac{2\times\text{nombre d'arêtes}}{n(n-1)}.
\]
En effet, si une arête est entre les sommets $A$ et $B$, alors on compte deux fois cette arête dans le calcul de la densité (une pour $A$, et une pour $B$) car le graphe est non orienté.
\end{Exemple}

\begin{defin}[graphe creux, graphe denses]
\begin{itemize}
\item Un graphe à $n$ sommets est \textit{creux} si son nombre d'arêtes \og est proche \fg{} de $n$.

\item Un graphe à $n$ sommets est \textit{dense} si son nombre d'arêtes \og est proche \fg{} de $n^2$.
\end{itemize}
\end{defin}

\begin{prop}
Un graphe est dense si sa densité est \og assez proche \fg{} de 1.

Un graphe est creux si sa densité est \og assez éloignée \fg{} de 1.
\end{prop}


\begin{Remarque}
la notion de \textit{graphe dense} n'est pas une notion précise. En effet,\linebreak \og assez proche \fg{} peut différer d'un individu à l'autre.

Aussi, dans la pratique, on pourra considérer qu'un graphe est dense si sa densité est au moins égale à 0,75 (tout en ayant à l'esprit que cette valeur est arbitraire).
\end{Remarque}

\begin{Exemple}
reprenons le graphe orienté \ref{graphe-pondere} de la page \pageref{graphe-pondere}. 

Le nombre d'arêtes est égal à 18 et le nombre maximal d'arêtes est :
\[
n(n-1)=6\times5=30.
\]
La densité de ce graphe est donc :
\[
d=\dfrac{18}{30}=0,6.
\]
On peut alors estimer que le graphe est creux.
\end{Exemple}

\newpage
\subsection{Graphes non pondérés}

\subsubsection{Graphes denses : par matrice d'adjacence}

Dans le cas des graphes denses, on attribue un booléen à chaque coefficient de la matrice.

\begin{algorithme}{}
Pour i variant de 0 à n-1:
\quad	Pour j variant de 0 à n-1:
\quad\quad	m[i][j] $\leftarrow$ 1 si i et j sont reliés, 0 sinon
\quad	Fin du Pour j
Fin du Pour i
\end{algorithme}

\Par

L'un des avantages de cette représentation est sa simplicité : étant donnés deux sommets de rangs $i$ et $j$, le booléen à la $i$-ième ligne et $j$-ième colonne représente l'existence ou l'absence d'une arrête les reliant.

\begin{Exemple}
si nous reprenons le graphe de la figure \ref{graphe-non-oriente} de la page \pageref{graphe-non-oriente}, dont la\linebreak matrice d'adjacence est $M=\begin{pmatrix}
0 & 1  & 1 \\
1 & 0  & 1 \\
1 & 1  & 0
\end{pmatrix}$ comme vu précédemment, nous\linebreak pouvons implémenter ce graphe en Python comme ci-dessous.
\end{Exemple}

\begin{minipage}{0.45\linewidth}
\begin{listing}{En Python}{05-01.py}
\end{listing}
\end{minipage}
\begin{minipage}{0.5\linewidth}
\begin{center}
\includegraphics{131_01-crs-graphe-non-oriente}
\end{center}
\end{minipage}


\Par

La complexité est ici en $O\big(|S|^2\big)$, où $|S|$ est le nombre de sommets du graphe. 

En effet, il y a deux boucles de $n$ itérations, donc $n \times n=n^2$ affectations pour les coefficients de la matrice, et $n^2$ affectations pour $i$ et $j$, soit en tout $2n^2$\linebreak affectations élémentaires.

Or, $n=|S|$; la complexité est donc bien en $O(n^2)$.

\subsubsection{Graphes creux : par liste d'adjacence}
\enlargethispage*{5em}

\index{Graphes!Liste (ensemble) d'adjacence}
\begin{defin}
Soit $G=(V,E)$ un graphe tel que $V=\{A_1;A_2;\ldots;A_n\}$.

L'\textit{ensemble d'adjacence} d'un sommet $A_k$, $1\leqslant k \leqslant n$, est l'ensemble des $A_p$ tels que $A_k$ et $A_p$ sont reliés par une arête (graphe non orienté) ou un arc (graphe orienté).
\end{defin} 

\newpage

Dans le cas des graphes creux, on utilise l'\textit{ensemble d'adjacence} pour l'implémentation.  L'idée consiste alors, pour chaque sommet du graphe, à construire cet ensemble.

\begin{algorithme}{}
G $\leftarrow$ liste vide
Pour k variant de 0 à n-1:
\quad L[k] est une liste vide
\quad Pour p variant de 0 à n-1:
\quad\quad Si $A_k$ est relié à $A_p$:
\quad\qquad On ajoute $A_p$ dans la liste L[k]
\quad\quad Fin du Si
\quad Fin du Pour p
\quad G $\leftarrow$ G + ($A_k$ , L[k])
Fin du Pour k
\end{algorithme}

\Par

La taille de la représentation est ici en $O(|S|+|A|)$, où $|S|$ et $|A|$ sont respectivement le nombre de sommets et le nombre d'arêtes du graphe.

\Par

En Python, on pourra par exemple utiliser un dictionnaire.

\begin{Exemple}
reprenons le graphe représenté sur la figure \ref{ex:graphe-oriente} page \pageref{ex:graphe-oriente} en y ajoutant un sommet D, origine d'aucun arc. Nous pouvons l'implémenter comme suit :
\Par
\begin{minipage}{0.45\linewidth}
\begin{listing}{En Python}{05-02.py}
\end{listing}
\end{minipage}
\begin{minipage}{0.5\linewidth}
\begin{center}
\includegraphics{132_01-crs-graphe-oriente}
\end{center}
\end{minipage}
\end{Exemple}

\begin{Remarque}il existe plusieurs manières d'implémenter le sommet D n'est pas unique. Nous aurions aussi pu écrire par exemple : 
\Par
\begin{center}
\texttt{'D' : [ ]}
\end{center}
\end{Remarque}

\subsubsection{À l'aide d'une classe}

Un graphe peut être implémenté à l'aide d'une classe. 

Voyons page suivante ce que cela peut donner en définissant par liste d'adjacence le graphe non orienté de la figure \ref{ex:parcours-largeur} page \pageref{ex:parcours-largeur}.
\newpage
\begin{listing}{Implémentation d'un graphe par une classe}{05-03.py}\end{listing}
\label{graphes-classe}

\Par

Ce programme affiche :

\Par

\begin{multicols}{2}
{\ttfamily
B : ['A', 'C']

A : ['B', 'D', 'E']

D : ['A', 'C', 'E']

E : ['A', 'D', 'F', 'G']

C : ['B', 'D']

F : ['E', 'G']

G : ['E', 'F', 'H']

H : ['G']
}
\end{multicols}

\Par

On peut ensuite utiliser cette classe afin d'y implémenter des parcours.

\Par\Par

\qrset{height=1.1cm,version=5}\rput(-1,0){
\psframebox{\qrcode{https://idl-live.prepamath.fr/ILTNSI/05-12.py}}}
%\vspace*{-10pt}
\textit{Téléchargez la classe complète.}
\label{graphe-classe-complete}


\subsection{Graphes pondérés}

\subsubsection{Par liste d'adjacence}

On peut implémenter un graphe pondéré à l'aide d'un dictionnaire dont les valeurs sont aussi des dictionnaires.

Ainsi, pour le graphe de la figure \ref{graphe-pondere} page \pageref{graphe-pondere}, une implémentation possible est celle présentée page suivante (on ne met ici que le début du dictionnaire).

\newpage

\begin{listing}{Implémentation d'un graphe pondéré en Python}{05-04.py}\end{listing}

\Par


Les clés du dictionnaire principal sont les sommets du graphe et les valeurs sont des dictionnaires où chaque clé représente un sommet connecté à la clé du dictionnaire principal et où chaque valeur est la pondération de l'arc.

\begin{Remarque}
un sommet qui n'est l'origine d'aucun arc peut être représenté par un dictionnaire vide par exemple.
\end{Remarque}

\Par

Implémenter un graphe pondéré peut alors se faire en créant une classe comme ceci:

\qrset{height=1.1cm,version=5}\rput(-1,-0.7){
\psframebox{\qrcode{https://idl-live.prepamath.fr/ILTNSI/05-05.py}}}
\vspace*{-10pt}
\begin{listing}{Implémentation d'un graphe pondéré par liste d'adjacence}{05-05.py}
\end{listing}

\Par\enlargethispage*{5em}

Cela donne en mode console :

\vspace*{-2mm}
\hrulefill{\ttfamily

\pychevrons G = GraphePond()

\pychevrons G.addArc('K','M',4)

\pychevrons G.addArc('K','E',1)

\pychevrons G.addArc('A','B',5)

\pychevrons G.Liste

\{'K': \{'M': 4, 'E': 1\}, 'A': \{'B': 5\}\}

}
\vspace*{-2mm}
\hrulefill
\newpage

\subsubsection{Par matrice d'adjacence}

Sur le même modèle que précédemment, on peut créer une classe qui définit un graphe quand on connaît sa matrice d'adjacence:

\qrset{height=1.1cm,version=5}\rput(-1,-0.7){
\psframebox{\qrcode{https://idl-live.prepamath.fr/ILTNSI/05-06.py}}}
\vspace*{-10pt}
\begin{listing}{Implémentation d'un graphe pondéré par matrice d'adjacence}{05-06.py}\end{listing}
\label{graphe-pondere-classe-matrice}

\Par

En mode console, on aura par exemple :

\Par

\hrulefill

{\ttfamily

\pychevrons G = GraphePondM()

\pychevrons G.add([0,1,2])

\pychevrons G.add([2,0,5])

\pychevrons G.add([5,3,0])

\pychevrons G.Liste

[[0, 1, 2], [2, 0, 5], [5, 3, 0]]
}

\hrulefill

\section{Algorithmique}

\subsection{Parcours d'un graphe}

Parcourir un graphe consiste à lister tous ses sommets une seule fois. Il peut y avoir deux raisons principales au parcours d'un graphe : lister simplement tous les sommets ou trouver un chemin pour relier un sommet à un autre.



\subsection{Parcours en largeur}
\index{Graphes!Parcours en largeur}
\enlargethispage*{5em}

L'idée est d'utiliser une file de la manière suivante :

\begin{questions}
\item on part d’un sommet et on initialise une file vide (file) qui contiendra les
sommets à visiter ;
\item on ajoute le premier sommet dans une liste \texttt{sortie} initialement vide ;
\item tant que \texttt{file} n’est pas vide, on défile \texttt{file} et pour chaque voisin du sommet défilé, s’il n’a pas été visité, on le marque comme visité et on l’ajoute à \texttt{sortie}.
\end{questions}

\begin{Exemple}
regardons par rapport au graphe suivant:

\Par\Par

\begin{figure}
\begin{center}
\includegraphics{142_04-crs-parcours-largeur}
\figcaption{Parcours en largeur d'un graphe}
\label{ex:parcours-largeur}
\end{center}
\end{figure}

\Par\Par

Nous souhaitons parcourir ce graphe en partant du sommet A.

\begin{itemize}
\item On défile alors A. Les sommets B, D et E sont les voisins de A; ils sont donc
enfilés en premier (peu importe l’ordre).
\item On défile B : parmi les voisins de B, seul C n’a pas été visité donc on l’ajoute à la file.
\item On défile D : parmi ses voisins, tous ont été visités donc on ne fait rien.
\item On défile E : parmi ses voisins, G et F n’ont pas été visités donc on les enfile.
\item On défile C : pas de voisins non visités.
\item On défile G : le sommet H n’a pas été visité donc on l’enfile.
\item On défile F : pas de voisins non visités.
\item On défile H : pas de voisins non visités.
\end{itemize} 
\end{Exemple}

\qrset{height=1.1cm,version=5}\rput(-1,-0.7){
\psframebox{\qrcode{https://idl-live.prepamath.fr/ILTNSI/05-07.py}}}
\vspace*{-10pt}
\begin{listing}{Parcours en largeur écrit en Python}{05-07-1.txt}\end{listing}

\newpage
\begin{listing}{}{05-07-2.txt}\end{listing}

\Par
Ce programme affiche :
\begin{center}
\texttt{['A', 'B', 'D', 'E', 'C', 'G', 'F', 'H']}
\end{center}

L’algorithme du parcours en largeur est le suivant :

\begin{algorithme}{Parcours en largeur d'un graphe}
F est une file vide
On enfile le premier sommet (S)
Marquer S comme visité
Tant que F n'est pas vide:
\quad S $\leftarrow$ tête de F
\quad Défiler F
\quad Pour chaque voisin (v) de S:
\quad\quad Si v n’est pas visité:
\quad\quad\quad Marquer v comme visité
\quad\quad\quad Enfiler v dans F
\quad Fin do Pour
Fin du Tant que
\end{algorithme}

\Par

Pour le cas de graphes implémentés par matrice d'adjacence, vous trouverez un exercice à ce sujet (exercice \ref{exo:implementation-graphe-matrice-adj} page \pageref{exo:implementation-graphe-matrice-adj}).

\Par

L'algorithme de parcours en largeur permet de dresser la liste des sommets d'un graphe par distance croissante au sommet d'origine. On peut ainsi s'en servir pour trouver un chemin de distance minimale entre deux sommets.

\subsection{Parcours en profondeur}

L'idée est d'utiliser une pile de la manière suivante :

\begin{questions}
\item on part d'un sommet que l'on empile;
\item si le sommet de la pile a des voisins qui ne sont pas dans la pile et qui ne sont pas déjà passés dans la pile, on choisit l'un des ces voisins et on l'empile. Dans le cas contraire, on dépile (on supprime l'élément du haut de la pile);
\item on revient au point 2 tant que la pile n'est pas vide.
\end{questions}

\newpage

\begin{Exemple}
le programme suivant est basé sur le même graphe que précédemment.
\end{Exemple}

\qrset{height=1.1cm,version=5}\rput(-1,-0.7){
\psframebox{\qrcode{https://idl-live.prepamath.fr/ILTNSI/05-08.py}}}
\vspace*{-10pt}
\begin{listing}{Parcours en profondeur écrit en Python}{05-08.py}\end{listing}

\Par

Il affiche: \texttt{['A', 'E', 'F', 'G', 'H', 'D', 'C', 'B']}


\subsection{Recherche d'un chemin}
\index{Graphes!Recherche d'un chemin}

On peut s'inspirer de l'un des parcours (en largeur ou en profondeur) pour élaborer un algorithme permettant de trouver un chemin d'un sommet à un autre dans un graphe.

\begin{algorithme}{Algorithme de recherche d'un chemin}
G est un graphe
start $\leftarrow$ sommet de départ
end $\leftarrow$ sommet d'arrivée
P est une pile
\vspace*{-3mm}
\Break
Empiler le couple (start,[start])
Tant que P n'est pas vide:
\quad (S,path) $\leftarrow$ tête de P
\quad list\verb+_+nodes $\leftarrow$ liste des sommets adjacents à S
\hspace*{30mm} qui ne sont pas dans path
\quad Pour i dans list\verb+_+nodes:
\qquad Si i = end:
\quad\qquad Afficher path + [i]
\qquad Sinon:
\quad\qquad Empiler (i,path+[i])
\qquad Fin du Si
\quad Fin du Pour
Fin du Tant que
\end{algorithme}

\Par

Le programme suivant donne par exemple tous les chemins qui mènent de A à H sans passer deux fois par le même sommet:
\enlargethispage*{5em}

\qrset{height=1.1cm,version=5}\rput(-1,-0.7){
\psframebox{\qrcode{https://idl-live.prepamath.fr/ILTNSI/05-09.py}}}
\vspace*{-10pt}
\begin{listing}{Chemins d'un sommet à un autre en Python}{05-09.py}
\end{listing}

\Par

Expliquons ce programme :

\begin{itemize}
\item on commence par définir le sommet d'origine et le sommet de destination;

\item on initialise ensuite une liste qui contiendra des couples de la forme:
\begin{center}
\texttt{(sommet de départ , [chemin à partir du sommet de départ])}
\end{center}

\item tant que la pile n'est pas vide, on définit le couple \texttt{S,path} comme étant la tête de la pile, et on dépile;

\item on construit alors la liste \texttt{list}\_\texttt{nodes} comme étant tous les sommets reliés à \texttt{S} qui ne sont pas déjà dans la liste \texttt{path} (représentant le chemin);

\item on parcourt alors la liste \texttt{list}\_\texttt{nodes} : si l'élément \texttt{i} sur lequel nous sommes est le sommet d'arrivée alors on affiche le chemin complet en y ajoutant \texttt{i}, qui est le sommet de destination; sinon, on ajoute à la pile le couple composé de \texttt{i} accompagné du chemin auquel nous avons ajouté le sommet \texttt{i}.
\end{itemize}

Ce programme affiche alors :

\Par

{\ttfamily
['A', 'E', 'F', 'G', 'H']

['A', 'E', 'G', 'H']

['A', 'D', 'E', 'F', 'G', 'H']

['A', 'D', 'E', 'G', 'H']

['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']

['A', 'B', 'C', 'D', 'E', 'G', 'H']
}

\subsection{Recherche d'un plus court chemin}

\NathanLiveVideo[\PictoVideo\ Retrouvez en vidéo le principe de l'algorithme de Dijkstra.]{dijkstra}{https://www.youtube.com/watch?v=rHylCtXtdNs}

\qrset{height=1.1cm,version=5}\rput(-1,0.4){
\psframebox{\qrcode{https://media.prepamath.fr/ILTNSIch05crs01}}}
\vspace*{-20pt}
\Par

Pour la recherche de plus courts chemins, l'algorithme le plus connu est l'algorithme de Dijkstra.\index{Graphes!Dijkstra (algorithme)}

Il recherche autant de \og plus courts chemins \fg qu'il existe de sommets accessibles depuis le sommet de départ.
C'est pour cela qu'il ne reçoit pas, en entrée, le sommet de destination souhaité.



Dans cet algorithme, 

\begin{itemize}
\item $G = (V,E)$ est un graphe pondéré;
\item \texttt{L} est une liste contenant les distances du sommet de départ vers les autres\linebreak sommets;
\item \texttt{P} est une liste contenant le prédécesseur dans le chemin le plus court à partir du sommet de départ;
\item \texttt{M} est une liste de tous les sommets déjà traités;
\item \texttt{poids(A,B)} désigne le poids de l'arc ou arête qui va de A à B.
\end{itemize}

\begin{algorithme}{Algorithme de Dijkstra}
*-- initialisation --*

D $\leftarrow$ sommet de départ
L[D] $\leftarrow$ 0
P[D] $\leftarrow$ D
Pour tout S (sommet) $\neq$ D:
\quad Si S est un successeur de D:
\qquad L[S] $\leftarrow$ poids(D,S)
\qquad P[S] $\leftarrow$ D
\quad Sinon:
\qquad L[S] $\leftarrow$ "0"
\qquad P[S] $\leftarrow$ ""
\quad Fin du Si
Fin du Pour
M $\leftarrow$ S

*-- Traitement --*
Tant que M $\neq$ V:
\quad Choisir S $\in$ $V\setminus M$ tel que $\forall J \in V\setminus M$, L[S] $\leqslant$ L[J]
\quad Pour $J\in V\setminus M$ tel que $J$ successeur de S:
\qquad Si L[J] > L[S] + poids(S,J):
\qquad\quad L[J] $\leftarrow$ L[S] + poids(S,J)
\qquad\quad P[J] $\leftarrow$ S
\qquad Fin du Si
\quad Fin du Pour
Ajouter à M le sommet S
Fin du Tant que
\end{algorithme}

\Par

\qrset{height=1.1cm,version=5}\rput(-1,0){
\psframebox{\qrcode{https://idl-live.prepamath.fr/ILTNSI/05-13.py}}}
\textit{Téléchargez l'implémentation de Dijkstra en Python.}
\label{dijkstra}

\subsection{Recherche d'un  cycle}

\begin{defin}
Un \textit{cycle} est un chemin dont l'origine et l'extrémité sont identiques.
\end{defin}

\begin{Exemple}
dans le graphe de la figure \ref{ex:parcours-largeur} page \pageref{ex:parcours-largeur}, le chemin :
\begin{center}
A -- B -- C -- D -- A
\end{center}
est un cycle.
\end{Exemple}

Pour obtenir tous les cycles d'un graphe, on peut s'inspirer de l'algorithme de recherche d'un chemin. 

\newpage

Voici ce que cela donne en Python:

\qrset{height=1.1cm,version=5}\rput(-1,-1){
\psframebox{\qrcode{https://idl-live.prepamath.fr/ILTNSI/05-10.py}}}
\vspace*{-10pt}
\begin{listing}{Recherche d'un cycle en Python}{05-10.py}\end{listing}

\Par


\enlargethispage*{5em}
\begin{solintro}
Nous pouvons avant tout construire la matrice d'adjacence de ce graphe :
\[
\NiceMatrixOptions{code-for-first-row=\color{DB}\scriptstyle,code-for-last-col=\color{DB}\scriptstyle}
M = \begin{pNiceMatrix}[first-row,last-col=10]
P & A  & B & C & D & E & F & G  & H\\
0 & 8 & 6 & 28 & 5 & 0 & 0 & 0 & 0 & P\\
8 & 0 & 9 & 0 & 15 & 0 & 0 & 0 & 0 & A\\
6 & 9 & 0 & 13 & 0 & 0 & 0 & 38 & 0 & B\\
28 & 0 & 13 & 0 & 14 & 0 & 21 & 17 & 0 & C\\
5 & 15 & 0 & 14 & 0 & 10 & 17 & 0 & 0 & D\\
0 & 0 & 0 & 0 & 10 & 0 & 19 & 0 & 0 & E\\
0 & 0 & 0 & 21 & 17 & 19 & 0 & 5 & 17 & F\\
0 & 0 & 38 & 17 & 0 & 0  &5  & 0&16 & G\\
0 & 0 & 0 & 0 & 0 & 0 & 17 & 16  & 0 & H
\end{pNiceMatrix}
\]

\Break

À l'aide de la classe page \pageref{graphe-pondere-classe-matrice}, on peut alors implémenter le graphe. Mais on peut aussi utiliser le programme \og \texttt{dijkstra} \fg fourni page \pageref{dijkstra}.

\Par\Par

\qrset{height=1.1cm,version=5}\rput(-1.2,0){
\psframebox{\qrcode{https://idl-live.prepamath.fr/ILTNSI/05-11.py}}}
\textit{Téléchargez le programme.}


\Par\Par

Les sommets sont représentés par des nombres (ici, de 0 à 8) et on cherche le plus court chemin de 0 à 8.


Ce programme affiche :

\Par

\hrulefill

{\ttfamily
Plus courts chemins de...

Longueur 5 : 0 -> 4

Longueur 6 : 0 -> 2

Longueur 8 : 0 -> 1

Longueur 15 : 0 -> 4 -> 5

Longueur 19 : 0 -> 4 -> 3

Longueur 22 : 0 -> 4 -> 6

Longueur 27 : 0 -> 4 -> 6 -> 7

Longueur 39 : 0 -> 4 -> 6 -> 8
}

\hrulefill

\Par

Ainsi, le chemin le plus court est : P -- D -- F -- H.
\end{solintro}