\def\NomChapitre{Parcours de graphes}
\def\Type{TP}
\LeTitre{\Type}{\NomChapitre}

\shorthandoff{:} 
%%%%%%%%%%%%%%%%%%%%% Styles %%%%%%%%%%%%%%%%%%%%%
\pgfdeclarelayer{background}
\pgfsetlayers{background,main}
\tikzstyle{preno}=[semithick] % arêtes non orientées.
\tikzstyle{pre}=[->,>=stealth,semithick] % arêtes orientées.
\tikzstyle{select}=[-,cap=round,style=nearly transparent,line width=6pt] %
\tikzstyle{fl_actif}=[-,cap=round,style=nearly transparent,line width=6pt,color=black!50!red]
\tikzstyle{infini} =[circle,thick,inner sep=0pt,minimum size=6mm,node
distance=20mm,draw=black!50,fill=blue!2, text=red]

\section{Notions élémentaires} 

\begin{exo}
\begin{enumerate}
\item 
\lstinline{Lex1 = [[1, 2, 3, 4], [0, 2, 3], [0, 1, 3], [0, 1, 2], [0, 5], [4], [7], [6]]}
\item Le sommet \lstinline$2$ a pour degré $d(2)=3$ (arêtes vers \lstinline$0$, \lstinline$1$ et \lstinline$3$), et le
  sommet \lstinline$5$ a pour degré $d(5)=1$ (arête vers \lstinline$4$).
\item Le chemin \lstinline$[3, 0, 4, 5]$ relie \lstinline$3$ à \lstinline$5$,
  et est de longueur $3$ ($3$ arêtes).

Le chemin \lstinline$[3, 2, 1, 0, 4, 5]$ convenait aussi, et est de longueur
$5$. 
\item Cycle de longueur $4$ : \lstinline$[3, 2, 1, 0, 3]$.
De longueur $3$ : \lstinline$[3, 0, 1, 3]$ (il y en a d'autres).

\item Composantes connexes : le sous-graphe constitué des sommets
  \lstinline$[6, 7]$, et celui des sommets \lstinline$[0, 1, 2, 3, 4, 5]$.
\end{enumerate}
\end{exo}


\begin{exo}
\begin{enumerate}
\item 
\lstinline{L=[[1, 2], [2, 3], [1, 3], [4], [0]]}
\item $d_-(2)=2$ et $d_+(2)=2$. $d_-(3)=2$ et $d_+(3)=1$.
\item \lstinline$[0, 2, 3, 4]$ (longueur $3$) ou \lstinline$[0, 1, 3, 4]$
  (idem).
\item Cycle de longueur $2$ : \lstinline$[2, 1, 2]$.
Cycle de longueur $4$ : \lstinline$[0, 1, 3, 4, 0]$.
\end{enumerate}
\end{exo}

\begin{exo}
~\\
\vspace{-1.8cm}
\begin{nunumerate}{.97}{1}{1.3}
\itemnu Le graphe est orienté : Il n'y a pas d'arête depuis le sommet $3$, alors
  qu'il y a des arêtes vers $3$. &
%\setcounter{enumi}{2}
\itemnu 
\vspace{-.6cm}
\begin{tikzpicture}[>=stealth,scale=1,baseline=(current bounding box.center)]
  \node[infini]      (0)                      {$0$};
  \node[infini]      (5)        [right of=0]  {$5$};
  \node[infini]      (4)        [above of=0]  {$4$};
  \node[infini]      (1)        [right of=4]  {$1$};
  \node[infini]      (2)        [right of=5]  {$2$};
  \node[infini]      (3)        [above of=2]  {$3$};
\draw[pre,bend right=20] (0) to  (4) ;
\draw[pre,bend right=20] (0) to  (5) ;
\draw[pre] (1) to  (3) ;
\draw[pre,bend right=20] (1) to  (5) ;
\draw[pre] (2) to  (3) ;
\draw[pre] (2) to  (4) ;
\draw[pre,bend right=20] (2) to  (5) ;
\draw[pre,bend right=20] (4) to  (0) ;
\draw[pre] (4) to  (1) ;
\draw[pre,bend right=20] (5) to  (0) ;
\draw[pre,bend right=20] (5) to  (1) ;
\draw[pre,bend right=20] (5) to  (2) ;
\end{tikzpicture}\\
\itemnu $M = \begin{pmatrix}
 0&0&0&0&1&1\\
 0&0&0&1&0&1\\
 0&0&0&1&1&1\\
 0&0&0&0&0&0\\
 1&1&0&0&0&0\\
 1&1&1&0&0&0
\end{pmatrix}$ 
\end{nunumerate}
\end{exo}


 \section{Parcours en largeur} 

Vous trouverez ici :
\begin{center}
\url{http://mpechaud.fr/scripts/parcours/index.html}
\end{center}
une très belle animation de plusieurs algorithmes de parcours de graphe.


\begin{exo}
\begin{enumerate}
\setcounter{enumi}{7}
\item Posons $n = |S|$.
Il y $3n$ ($+2$) affectations lors de l'initialisation. 

 La boucle \lstinline$while$ dure autant qu'il y a d'éléments qui passent dans
 \lstinline$f$.

 Or chaque sommet passe dans \lstinline$f$ une fois et une seule (passage de
 blanc à gris).

 Donc il y a exactement $n$ passages dans la boucle \lstinline$while$.

Plus généralement (boucles \lstinline$while$ et \lstinline$for$), il y a
autant d'affectations que 
\begin{itemize}
\item de passage de blanc à gris (\lstinline$c[a]$, \lstinline$p[a]$,
\lstinline$d[a]$), donc $n$ 
\item de passage de gris à noir (c[u]='n') donc n
\end{itemize}
Ainsi le nombre d'affectation est en O(|S|)

Pour la taille des boucles, les boucles \lstinline$for$ parcourent les arêtes partant de \lstinline$u$,
et \lstinline$u$ parcourt l'ensemble des sommets une fois et une seule. On
parcourt donc l'ensemble des arêtes une fois et une seule. La taille cumulée
des boucles \lstinline$for$ est donc $|A|$.

La complexité est donc en $O(|S|+|A|)$.
\end{enumerate}
\end{exo}


\section{Parcours en profondeur} 


\begin{exo}
\begin{enumerate}
\setcounter{enumi}{3}
\item Toujours avec $n=|S|$. Il y a toujours $O(n)$ affectations lors de
  l'initialisation.

La coloration blanc $\longrightarrow$ gris assure que 
la fonction \lstinline$visiter_sommet$
est appellée une fois et une seule sur chaque sommet, elle est donc appellée
exactement $n=|S|$ fois. 

Dedans il y a au moins $2$ affectations
(\lstinline$c[u]$ à gris,
puis noir). Les boucles \lstinline$for$ dans leur ensemble parcourent chaque
arête une fois 
et une seule : il y a donc $|A|$ passages dans les boucles \lstinline$for$.
 
En conclusion, l'algorithme est de complexité $O(|S|+|A|)$

\end{enumerate}
\end{exo}



%%% Local Variables:
%%% mode: latex
%%% TeX-PDF-mode: t
%%% TeX-master: FeuilleGraphesParcoursCorr_2022
%%% End:
