cours_ARE.tex

\documentclass{beamer}

\usepackage[french]{babel}
\usepackage[T1]{fontenc}
\usepackage[utf8x]{inputenc}
%\usepackage{rotating}
\usepackage{array}

\usepackage{ragged2e}

\usepackage{xcolor}
\usepackage{textcomp}
\usepackage{listings}
\lstset{
  literate=%
         {à}{{\`a}}1
         {é}{{\'e}}1
         {è}{{\`e}}1
         {î}{{\^i}}1
         {ù}{{\`u}}1
         {û}{{\^u}}1
         {ê}{{\^e}}1,
 tabsize=4,
 language=python,
 upquote=true,
 %aboveskip={1.5\baselineskip},
 columns=fixed,
 showstringspaces=false,
 extendedchars=true,
 breaklines=true,
 prebreak = \raisebox{0ex}[0ex][0ex]{\ensuremath{\hookleftarrow}},
 showtabs=false,
 showspaces=false,
 showstringspaces=false,
 identifierstyle=\ttfamily,
 keywordstyle=\color[rgb]{0,0,1},
 commentstyle=\color[rgb]{0.133,0.545,0.133},
 stringstyle=\color[rgb]{0.627,0.126,0.941},
 %numbers=left,
 %numberstyle=\tiny\color{gray},
}

\usepackage[french,onelanguage]{algorithm2e}

\usepackage{ifthen}
\lstnewenvironment{code}[2][]
 {\ifthenelse{\isundefined{#2}}{\newsavebox{#2}}{}\lstset{#1}\global\setbox#2\vbox\bgroup}
 {\egroup}

\lstdefinelanguage{consoledisplay}{
  alsoletter={>+-/*\%},
  morekeywords=[1]{>>>},
  keywordstyle=[1]\color{red},
  morekeywords=[2]{\$},
  keywordstyle=[2]\color{green},
  morekeywords=[3]{+, -, *, /, \%, //, **},
  keywordstyle=[3]\color{blue!50!white}
}
\newcommand{\codeinput}[2]{\ifthenelse{\isundefined{#2}}{\newsavebox{#2}}{}\global\setbox#2\vbox{\lstinputlisting[language=consoledisplay, linewidth=2\textwidth]{#1}}}

\usepackage{tikz}
\usetikzlibrary{arrows,shapes}
\tikzstyle{vertex}=[circle,fill=black!25,minimum size=20pt,inner sep=0pt]
\tikzstyle{edge} = [draw,thick,-, minimum size=1cm]
\tikzstyle{selected vertex} = [vertex, fill=red!24]

\usetheme{Ilmenau}

\title[Cours ARE]{Ateliers de Recherches Encadrées}
\author[Guillaume Turchini]{Guillaume Turchini (guillaume.turchini@lip6.fr)}
\institute{SmartGrid}
\date{Fev. 2016}

\setbeamertemplate{navigation symbols}{}
\addtobeamertemplate{navigation symbols}{}{
    \usebeamerfont{footline}
    \usebeamercolor[fg]{footline}
    \hspace{1em}
    \insertframenumber/\inserttotalframenumber
}

\let\oldsubsubsection\subsubsection
\renewcommand{\subsubsection}[2][]{\def\currentsubsubsection{#2}\oldsubsubsection[#1]{#2}}

\setcounter{secnumdepth}{4}

\begin{document}

\begin{frame}
  \titlepage
\end{frame}

\begin{frame}
  \setcounter{tocdepth}{2}
  \tableofcontents
  \setcounter{tocdepth}{4}
\end{frame}

\let\oldframe\frame
\let\endoldframe\endframe
\renewenvironment{frame}{\oldframe\frametitle{\currentsubsubsection}}{\endoldframe}

\section{Rappels python}
\subsection{Introduction}

\subsubsection{Langage de programmation}

\begin{frame}
  \begin{itemize}
    \item Langage de programmation $\Rightarrow$ permet de rendre un langage compréhensible par l'homme en un langage compréhensible par l'ordinateur (binaire)
    \item Python créé en 1991 par Guido van Rossum
    \item Langage interprété : transcrit au fur et a mesure\\($\neq$ langage compilé)
  \end{itemize}
\end{frame}

\subsubsection{Python}

\begin{frame}
    \begin{itemize}
        \item Probème de compatibilité entre 2.x et 3.x\\(on utilisera donc 3.x)
      
        \item Utilisation
        \begin{itemize}
            \item En ligne de commande (interactif) : `python`\\
            \quad ou `python3` selon les distributions (linux)\\
            \quad (quitter avec Ctrl+D)\\
            \qquad $\Rightarrow$ On tape l'opération, elle est exécutée
          
            \item Dans un fichier .py puis `python3 fichier.py`
        \end{itemize}
    \end{itemize}
\end{frame}

\codeinput{python-out/basic-ops}{\codebox}

\subsubsection{Opérations}

\begin{frame}
   \begin{itemize}
        \item Addition +, Soustraction -, Multiplication *, Division /, Division entière //, Modulo \%, Exposant **
    \end{itemize}
    \scalebox{0.5}{\usebox\codebox}
\end{frame}

\subsubsection{Variables}

\begin{code}{\codebox}
variable = 3*3 # = 9
variable += 2  # = 11
variable -= 5  # = 6
#  On a aussi :  *=  /=  //=  %=  **= ...
\end{code}
\begin{frame}
   \begin{itemize}
        \item Permet de stocker les résultats des opérations (mémoire)\\
        \usebox\codebox
  
        \item Chaîne de caractères (texte) : \lstinline{"..."}, \lstinline{'...'}, \lstinline{""" texte multi-ligne """}
    \end{itemize}
\end{frame}

\subsubsection{Appel de fonction}

\begin{frame}
   \begin{itemize}
        \item Pour savoir le type d'une variable : \lstinline{type(variable)}\\
        Types : int = entier, float = chiffre a virgule, str = chaine... \\[1cm]
  
        \item Afficher quelque chose : \lstinline{print("V = ", variable, "!")} \\[1cm]
  
        \item Afficher l'aide : \lstinline{help("fonction")} (par exemple help(``print''))
    \end{itemize}
\end{frame}

\subsection{Blocs de contrôle et fonctions}

\subsubsection{Opérateurs de comparaison}

\begin{frame}
  \begin{itemize}
  \item Plus~petit~<, Plus~grand~>, Plus~petit~ou~égal~<=, Plus~grand~ou~égal >=, Egal~==, Différent~!=\\[0.5cm]
    
\item a \lstinline{and} b si a \textbf{et} b sont vrais\\
  a \lstinline{or} b si a \textbf{ou} b sont vrais (ou les deux)\\
  \lstinline{not} a si a n'est pas vrai (inverse le résultat)\\[0.5cm]
  
  \item Renvoient True (vrai) ou False (faux)
  \end{itemize}

\end{frame}

\subsubsection{Conditions}

\begin{code}{\codeboxa}
if a < 18:
    #L'indentation/décalage est obligatoire
    print("Trop jeune!")
\end{code}
\begin{code}{\codeboxb}
if a < 18:
    # L'indentation/décalage est obligatoire
    print("Trop jeune!")
elif a >= 60:
    print("Trop vieux!")
\end{code}
\begin{code}{\codeboxc}
if a < 18:
    # L'indentation/décalage est obligatoire
    print("Trop jeune!")
elif a >= 60:
    print("Trop vieux!")
else:
    print("Tout est OK, tu peux entrer")
\end{code}
\begin{frame}
  \begin{itemize}
  \item ``Si ... alors'' $\Rightarrow$ \lstinline{if}\\
    ``Sinon, si ... alors'' $\Rightarrow$ \lstinline{elif}\\
    ``Sinon, faire ...'' $\Rightarrow$ \lstinline{else}
  \end{itemize}
  
    \begin{overprint}
    \onslide<1>\usebox\codeboxa
    \onslide<2>\usebox\codeboxb
    \onslide<3>\usebox\codeboxc
    \end{overprint}
\end{frame}

\subsubsection{Boucles}

\begin{code}{\codeboxa}
while a < 10:
    # Faire quelque chose
\end{code}
\begin{code}{\codeboxb}
for lettre in "chaine":
    if lettre == 'i':
        continue
    print(lettre)
\end{code}
\begin{code}{\codeboxc}
for chiffre in range(1,5):
    print(chiffre)
    if chiffre == 3:
        break
\end{code}
\begin{frame}
   \begin{itemize}
  \item ``Tant que ..., faire'' $\Rightarrow$ \lstinline{while}\\
    ``Pour chacun ... dans ..., faire'' $\Rightarrow$ \lstinline{for ... in}\\
    ``Passer au suivant'' $\Rightarrow$ \lstinline{continue}\\
    ``Arrêter la boucle'' $\Rightarrow$ \lstinline{break}\\[1cm]
  \end{itemize}
  \begin{overprint}
    \onslide<1>\usebox\codeboxa
    \onslide<2>\usebox\codeboxb
    \onslide<3>\usebox\codeboxc
  \end{overprint}
\end{frame}

\subsubsection{Fonctions}

\begin{code}{\codebox}
def fonction(param1, param2, ..., paramN):
    """Documentation
    blablabla"""
    # contenu
    return param1 * (param2 + param3)
\end{code}

\begin{frame}
  \begin{itemize}
  \item \lstinline{return} définit la valeur de retour de la fonction\\[1cm]
  \end{itemize}
  \usebox\codebox
\end{frame}

\begin{code}{\codebox}
def f(a=1, b=2, c=3): # Valeurs par défaut
    # contenu
    return a + b * c
\end{code}
\begin{frame}
  \usebox\codebox
  
  Appel : \lstinline{f() f(4) f(4, 5) f(c=9, a=3)}
\end{frame}

\subsubsection{Import}
\begin{code}{\codeboxa}
import math
math.sqrt(16)
  
from math import sqrt
                 *
sqrt(16)
\end{code}
\begin{code}{\codeboxb}
# Aléatoire
import random
  
random.randrange(50) # 0 <= r <= 49

random.randrange(1,7) # 1 <= r <= 6
\end{code}
\begin{frame}
  \begin{itemize}
  \item \lstinline{import} permet de récupérer des fonctions déjà écrites\\[0.6cm]
  \end{itemize}
  \begin{overprint}
    \onslide<1>\usebox\codeboxa
    \onslide<2>\usebox\codeboxb
  \end{overprint}
\end{frame}


\subsection{Listes, Dictionnaires et Entrées-Sorties}

\subsubsection{Listes}

\begin{code}{\codeboxa}
liste = list() # pareil que liste = []
liste = [1,2,3,4,5]

liste.append(42)
liste.insert(4, "bonjour")
l1 += l2 # pareil que l1.extend(l2)
  
del liste[2] # supprime le 3ème élément
liste.remove("bonjour")
# supprime la première occurence de l'élément
\end{code}
\begin{code}{\codeboxb}
for elem in liste:
  
for i, elem in enumerate(liste):
  
chaine.split(" ")
" ".join(liste)
\end{code}
\begin{code}{\codeboxc}
liste = [1,2,3,4,5]
  
[nb*nb for nb in liste] # [1,4,9,16,25]
  
[nb for nb in liste if nb%2 == 0] # [2,4]
  
liste2 = sort(liste)
  
print(*liste)
\end{code}
\begin{frame}
  \begin{overprint}
    \onslide<1>\usebox\codeboxa
    \onslide<2>\usebox\codeboxb
    \onslide<3>\usebox\codeboxc
  \end{overprint}
\end{frame}

\subsubsection{Dictionnaires}
\begin{code}{\codebox}
d = dict()
d = {"cle1" : "val1", "cle2" : "val2"}
  
d["pseudo"] = "orion"

for k in d.keys():
for v in d.values():
for k,v in d.items():

def f(*liste_non_nommees, **dict_nommees):

f(**named_params)
\end{code}
\begin{frame}
  \usebox\codebox
\end{frame}

\subsubsection{Entrées-Sorties}
\begin{code}{\codeboxa}
os.chdir("/home/...")
  
os.getcwd()
  
f = open("fichier", "r") 
# r = read, w = write, a = append, + = r + w
# ...
f.close()
\end{code}
\begin{code}{\codeboxb}
f.read() # lis le fichier
  
f.write("blablabla") # écrit dans le fichier
  
with open("fichier", "w") as fichier:
    # ferme automatiquement le fichier
    # à la fin du bloc
\end{code}
\begin{frame}
  \begin{overprint}
    \onslide<1>\usebox\codeboxa
    \onslide<2>\usebox\codeboxb
  \end{overprint}
\end{frame}

\section{Théorie des graphes}
\subsection{Définitions}
\subsubsection{Domaines d'applications}
\begin{frame}
    \begin{itemize}
        \item Chimie : Modélisation des molécules
        
        \item Mécanique : Treillis
        
        \item Biologie : Réseau de neurones, Séquencement du génome
        
        \item Sciences sociales : Modélisation des relations

        \item Et bien sûr dans divers domaines de l'informatique
    \end{itemize}
\end{frame}

\subsubsection{Graphe}
\begin{frame}
    \begin{itemize}
        \item Un graphe orienté $G$ c'est un couple $(S,A)$ avec :
        \begin{itemize}
            \item $S$ un ensemble fini : ensemble des sommets
            \item $A$ une relation binaire sur $S$ : ensemble des arcs
        \end{itemize}
        \item Un graphe NON orienté $G$ c'est un couple $(S,A)$ :
        \begin{itemize}
            \item $S$ un ensemble fini : ensemble des sommets
            \item $A$ paires non ordonnées : ensemble des arêtes
        \end{itemize}
    \end{itemize}
\end{frame}

\begin{frame}
    \centering
    \begin{tabular}{cc}
    Orienté & Non orienté\\
    \begin{tikzpicture}[auto,swap]
    \foreach \pos/\name in {{(1,0)/1}, {(0,-2)/2}, {(2,-2)/3}, {(0,-4)/5}, {(2,-4)/4}}
        \node[vertex] (\name) at \pos {$\name$};
        
    \foreach \source/ \dest in {1/2, 1/3, 2/3, 2/5, 5/3, 3/4, 4/5}
        \path[edge, ->] (\source) -- node {} (\dest);
    
    % \foreach \vertex / \fr in {1/1,2/2,3/3,4/4,5/5}
        % \path<\fr-> node[selected vertex] at (\vertex) {$\vertex$};
    \end{tikzpicture} &
    \begin{tikzpicture}[auto,swap]
    \foreach \pos/\name in {{(1,0)/1}, {(0,-2)/2}, {(2,-2)/3}, {(0,-4)/5}, {(2,-4)/4}}
        \node[vertex] (\name) at \pos {$\name$};
        
    \foreach \source/ \dest in {1/2, 1/3, 2/3, 2/5, 5/3, 3/4, 4/5}
        \path[edge] (\source) -- node {} (\dest);
        
    \end{tikzpicture}
    \end{tabular}
\end{frame}

\subsubsection{Degré d'un sommet}
\begin{frame}
    \begin{itemize}
        \item Dans un graphe non orienté :
        \begin{itemize}
            \item On appelle degré d'un sommet le nombre d'arrêtes qui lui sont incidentes
        \end{itemize}
        \item Dans un graphe orienté :
        \begin{itemize}
            \item On appelle degré sortant d'un sommet le nombre d'arcs qui partent de ce sommet
            \item On appelle degré entrant d'un sommet le nombre d'arcs qui arrivent à ce sommet
            \item On appelle degré d'un sommet la somme des degrés entrant et sortant du sommet
        \end{itemize}
    \end{itemize}
\end{frame}

\subsubsection{Chemin}
\begin{frame}
\begin{itemize}
        \item Un chemin d'un sommet $u$ au sommet $u'$ est une séquence de sommets $(v_{0},v_{1},v_{2}, ..., v_{k-1},v_{k})$ tel que :\\[0.2cm]

\centering$u = v_{0}, u' = v_{k}$ et $\forall i \in \left[ 0,k \right], \left(v_{i-1},v_{i}\right) \in A$
\\[0.2cm]

\item\justifying On dit que ce chemin a une longueur k

\item Ce chemin est élémentaire ssi $\forall \left(i,j\right) \in \left[ 0,k \right], v_{i} \neq v_{j}$

\item Un sommet $u$ est accessible depuis un sommet $v$ ssi il existe un chemin du sommet $u$ au sommet $v$
\end{itemize}
\end{frame}
\begin{frame}
    \begin{itemize}
    \item Dans un graphe orienté :
    \begin{itemize}
    \item Un chemin $(v_{0},v_{1},...,v_{k})$ forme un circuit ssi $v_{0}= v_{k}$

    \item Ce circuit est élémentaire ssi $\forall \left(i,j\right) \in \left[1,k-1\right], v_{i} \neq v_{j}$

    \item Une boucle est un circuit de longueur 1

    \item Un graphe est acyclique ssi il ne contient aucun circuit
    \end{itemize}
    \item Dans un graphe non orienté :
    \begin{itemize}
    \item Un chemin $(v_{0},v_{1},...,v_{k})$ forme un cycle ssi
    \\[0.2cm]\centering$v_{0}= v_{k} \wedge \left(\forall \left(i,j\right) \in \left[1,k-1\right], v_{i} \neq v_{j}\right)$\\[0.2cm]

    \item \justifying Un graphe est acyclique ssi il ne contient aucun cycle
    \end{itemize}
    \end{itemize}
\end{frame}

\subsection{Propriétés d'un graphe}
\subsubsection{Réflexif}
\begin{frame}
    \begin{tabular}{ll}
    \raisebox{-0.5\height}{\begin{tikzpicture}[auto,swap]
    \foreach \pos/\name in {{(0,0)/1}}
        \node[vertex] (\name) at \pos {$\name$};
        
    \path[edge, red!25, ->] (1) edge[loop] node {} (1);
        
    \end{tikzpicture}}&
    $\forall u_{i} \in S, \left(u_{i},u_{i}\right) \in A$
    \end{tabular}
\end{frame}
\subsubsection{Irréflexif}
\begin{frame}
    \begin{tabular}{ll}
    \raisebox{-0.5\height}{\begin{tikzpicture}[auto,swap]
    \foreach \pos/\name in {{(0,0)/1}}
        \node[vertex] (\name) at \pos {$\name$};
        
    \path[edge, ->] (1) edge[loop] node {} (1);
    
    \path[edge, red!25] (0.2,0.9) -- (-0.2,1.3);
    \path[edge, red!25] (0.2,1.3) -- (-0.2,0.9);
    
    \end{tikzpicture}}&
    $\forall u_{i} \in S, \left(u_{i},u_{i}\right) \notin A$
    \end{tabular}
\end{frame}
\subsubsection{Transitif}
\begin{frame}
    \begin{tabular}{ll}
    \raisebox{-0.5\height}{\begin{tikzpicture}[auto,swap]
    \foreach \pos/\name in {{(1,0)/1}, {(0,-2)/2}, {(2,-2)/3}}
        \node[vertex] (\name) at \pos {$\name$};
        
    \foreach \source/ \dest in {2/1, 1/3}
        \path[edge, ->] (\source) -- node {} (\dest);
    \path[edge, red!25, ->] (2) -- node {} (3);
    \end{tikzpicture}}&
    \vbox{$\forall \left(u_{i},u_{j},u_{k}\right) \in S^{3},$
    \newline\hspace*{0.5cm}$\left(u_{i},u_{j}\right) \in A \wedge \left(u_{j},u_{k}\right) \in A \Rightarrow \left(u_{i},u_{k}\right) \in A$}
    \end{tabular}
\end{frame}
\subsubsection{Symétrique}
\begin{frame}
    \begin{tabular}{ll}
    \raisebox{-0.5\height}{\begin{tikzpicture}[auto,swap]
    \foreach \pos/\name in {{(0,0)/1}, {(2,0)/2}}
        \node[vertex] (\name) at \pos {$\name$};
        
    \path[edge, ->] (1) edge[bend left] node {} (2);
    \path[edge, red!25, ->] (2) edge[bend left] node {} (1);
        
    \end{tikzpicture}}&
    \vbox{$\forall \left(u_{i},u_{j}\right) \in S^{2},$
    \newline\hspace*{0.5cm}$\left(u_{i},u_{j}\right) \in A \Rightarrow \left(u_{j},u_{i}\right) \in A$}
    \end{tabular}
\end{frame}
\subsubsection{Antisymétrique}
\begin{frame}
    \begin{tabular}{ll}
    \raisebox{-0.5\height}{\begin{tikzpicture}[auto,swap]
    \foreach \pos/\name in {{(0,0)/1}, {(2,0)/2}}
        \node[vertex] (\name) at \pos {$\name$};
        
    \foreach \source/ \dest in {2/1, 1/2}
        \path[edge, ->] (\source) edge[bend left] node {} (\dest);
    
    \path[edge, red!25] (0.8,-0.2) -- (1.2,-0.6);
    \path[edge, red!25] (1.2,-0.2) -- (0.8,-0.6);
    \end{tikzpicture}}&
    \vbox{$\forall \left(u_{i},u_{j}\right) \in S^{2},$
    \newline\hspace*{0.5cm}$\left(u_{i},u_{j}\right) \in A \wedge \left(u_{j},u_{i}\right) \in A \Rightarrow u_{i}=u_{j}$}
    \end{tabular}
\end{frame}
\subsubsection{Connexité}
\begin{frame}
    \begin{itemize}
        \item On dit d'un graphe non orienté qu'il est :
        \begin{itemize}
            \item Connexe ssi pour toute paire de sommets $\left(u,v\right)$ il existe une chaîne entre les sommets $u$ et $v$.
            \item Complet ssi tous les sommets sont ``reliés'' 2 à 2 :
            \\\centering$\forall u,v \in S^{2}, \left(u,v\right) \in A$
        \end{itemize}
        \item\justifying On dit d'un graphe orienté qu'il est :
        \begin{itemize}
            \item Connexe ssi le graphe non-orienté correspondant est connexe
            \item Fortement connexe ssi pour tout $\left(u,v\right)$ il existe un chemin de $u$ à $v$ et de $v$ à $u$
            \item Complet ssi tous les sommets sont «reliés» 2 à 2 : 
            \\\centering$\forall u,v \in S^{2} , \left(u,v\right) \in A \vee \left(v,u\right) \in A$
        \end{itemize}
    \end{itemize}
\end{frame}

\subsubsection{Graphes remarquables}

\newsavebox{\arbre}
\setbox\arbre\vbox{
\begin{tikzpicture}[->,>=stealth',level/.style={sibling distance = 5cm/#1, level distance = 0.7cm}]
    \node {1}
        child{node {2} 
            child{node {3}
                child{node {4}}
                child{node {5}}
            }
            child{node {6}
                child{node {7}}
                child{node {8}}
            }
        }
        child{node {9}
            child{node {10}
                child{node {11}}
                child{node {12}}
            }
            child{node {13}
                child{node {14}}
                child{node {15}}
            }
        }; 
\end{tikzpicture}
}
\begin{frame}
    \begin{itemize}
        \item Biparti : partitionnable en deux ensembles $S_{1}$ et $S_{2}$ tel que :
        \\\centering $\forall \left(u,v\right) \in A, \left(u \in S_{1} \wedge v \in S_{2}\right) \vee \left(v \in S_{1} \wedge u \in S_{2}\right)$
    \end{itemize}
\end{frame}

\begin{frame}
    \begin{itemize}
        \item Arbre : graphe Acyclique et Connexe
        \\($\Leftrightarrow$ graphe connexe à $n$ sommets et $n-1$ arrêtes)
        \\\usebox\arbre
        \\[0.3cm]
        \item Forêt : ensemble d'arbres
    \end{itemize}
\end{frame}

\subsection{Représentations d'un graphe}
%\subsubsection{Liste d'adjacence}
%\begin{frame}
%    a
%\end{frame}
\subsubsection{Matrice d'adjacence}
\begin{frame}
\begin{overprint}
   \onslide<1>
    \begin{tabular}{ll}
    \raisebox{-0.5\height}{\begin{tikzpicture}[auto,swap]
    \foreach \pos/\name in {{(1,0)/1}, {(0,-2)/2}, {(2,-2)/3}, {(0,-4)/5}, {(2,-4)/4}}
        \node[vertex] (\name) at \pos {$\name$};
        
    \foreach \source/ \dest in {1/2, 1/3, 2/3, 2/5, 5/3, 3/4, 4/5}
        \path[edge, ->] (\source) -- node {} (\dest);
        
    \end{tikzpicture}}&
    \raisebox{-0.5\height}{\vbox{Pour un graphe orienté\newline
    $\forall \left(i,j\right) \in S^{2}, a_{ij} = \left\{\begin{matrix}
    1 & si \left(i,j\right) \in A\\
    0 & sinon
    \end{matrix}\right.$
    \vspace{0.5cm} \newline
    $MatAdj\left(S,A\right)=\begin{bmatrix}
    0 & 1 & 1 & 0 & 0\\ 
    0 & 0 & 1 & 0 & 1\\ 
    0 & 0 & 0 & 1 & 0\\
    0 & 0 & 0 & 0 & 1\\
    0 & 0 & 1 & 0 & 0
    \end{bmatrix}$}}
    \end{tabular}
   \onslide<2>
   \begin{tabular}{ll}
    \raisebox{-0.5\height}{\begin{tikzpicture}[auto,swap]
    \foreach \pos/\name in {{(1,0)/1}, {(0,-2)/2}, {(2,-2)/3}, {(0,-4)/5}, {(2,-4)/4}}
        \node[vertex] (\name) at \pos {$\name$};
        
    \foreach \source/ \dest in {1/2, 1/3, 2/3, 2/5, 5/3, 3/4, 4/5}
        \path[edge] (\source) -- node {} (\dest);
        
    \end{tikzpicture}}&
    \raisebox{-0.5\height}{\vbox{Pour un graphe non orienté\newline
    $\forall \left(i,j\right) \in S^{2}, a_{ij} = \left\{\begin{matrix}
    1 & si \left(i,j\right) \in A\\
    0 & sinon
    \end{matrix}\right.$
    \vspace{0.5cm} \newline
    $MatAdj\left(S,A\right)=\begin{bmatrix}
    0 & 1 & 1 & 0 & 0\\ 
    1 & 0 & 1 & 0 & 1\\ 
    1 & 1 & 0 & 1 & 1\\
    0 & 0 & 1 & 0 & 1\\
    0 & 1 & 1 & 1 & 0
    \end{bmatrix}$}}
    \end{tabular}
\end{overprint}
\end{frame}
\subsubsection{Matrice d'incidence}
\begin{frame}
    \begin{tabular}{lc}
    \raisebox{-0.5\height}{\begin{tikzpicture}[>=stealth',shorten >=1pt, auto,node distance=5.5cm,semithick]]
    \foreach \pos/\name in {{(1,0)/1}, {(0,-2)/2}, {(2,-2)/3}, {(0,-4)/5}, {(2,-4)/4}}
        \node[vertex] (\name) at \pos {$\name$};
          
    \path[edge, ->] (1) -- node[minimum width = 0, minimum height = 0,above left, font=\small]{a} (2);
    \path[edge, ->] (1) -- node[minimum width = 0, minimum height = 0,above right, font=\small]{b} (3);
    \path[edge, ->] (2) -- node[minimum width = 0, minimum height = 0,above, font=\small]{c} (3);
    \path[edge, ->] (2) -- node[minimum width = 0, minimum height = 0,left, font=\small]{d} (5);
    \path[edge, ->] (5) -- node[minimum width = 0, minimum height = 0,above left, font=\small]{e} (3);
    \path[edge, ->] (3) -- node[minimum width = 0, minimum height = 0,right, font=\small]{f} (4);
    \path[edge, ->] (4) -- node[minimum width = 0, minimum height = 0,below, font=\small]{g} (5);
        
    \end{tikzpicture}}&
    \raisebox{-0.5\height}{\vbox{$\forall i \in S, \forall j \in A, a_{ij} = \left\{\begin{matrix}
    1 & si\ \overrightarrow{j} = \left(i,x\right)\\
    -1 & si\ \overrightarrow{j} = \left(x,i\right)\\
    0 & sinon
    \end{matrix}\right.$
    \vspace{0.5cm} \newline
    \scalebox{0.9}{
    $\begin{bmatrix}
      & a & b & c & d & e & f & g\\
    1 & 1 & 1 & 0 & 0 & 0 & 0 & 0\\ 
    2 &-1 & 0 & 1 & 1 & 0 & 0 & 0\\ 
    3 & 0 &-1 &-1 & 0 &-1 & 1 & 0\\
    4 & 0 & 0 & 0 & 0 & 0 &-1 & 1\\
    5 & 0 & 0 & 0 & -1& 1 & 0 &-1
    \end{bmatrix}$}}}
    \end{tabular}
\end{frame}

\subsection{Parcours}

\newsavebox{\initdfs}
\setbox\initdfs\vbox{
    \begin{algorithm}[H]
        \DontPrintSemicolon
        \KwData{Graphe $G=\left(S,A\right)$}
        \;
        date $\leftarrow$ 0 \;
        \ForEach{sommet $\in$ $S$}{
            couleur(sommet) $\leftarrow$ Blanc\;
        }
        \;
        \ForEach{sommet $\in$ $S$}{
            \If{couleur(sommet) == Blanc}{
                DFS(G, sommet)
            }
        }
    \end{algorithm}
}

\newsavebox{\dfs}
\setbox\dfs\vbox{
    \begin{algorithm}[H]
        \DontPrintSemicolon
        \KwData{Graphe $G$}
        \KwIn{Sommet $s$}
        \Begin{
            couleur($s$) $\leftarrow$ Rouge \;
            dateDebut($s$) $\leftarrow$ date++ \;
            
            \ForEach{$v$ $\in$ adjascent($s$)}{
                \If{couleur($v$) == Blanc}{
                    pere($v$) $\leftarrow$ $s$ \;
                    DFS($G$,$v$) \;
                }
            }
            
            couleur($s$) $\leftarrow$ Noir \;
            dateFin($s$) $\leftarrow$ date++ \;
        }
    \end{algorithm}
}
\subsubsection{DFS (parcours en profondeur ou préfixe)}
\begin{frame}
    \begin{overprint}
        \onslide<1>\centering\usebox\initdfs
        \onslide<2>\centering\scalebox{0.8}{\usebox\dfs}
    \end{overprint}
\end{frame}
\subsubsection{Exemple DFS}
\begin{frame}
     \begin{overprint}
       \onslide<18> DFS $\rightarrow$ Forêt en profondeur
     \end{overprint} \vspace{0.5cm}
     
    \begin{tikzpicture}[auto, ->, scale=2]
    
    \tikzstyle{vertex}=[circle,minimum size=20pt,inner sep=0pt]
    \tikzstyle{white vertex}=[vertex, fill=black!10]
    \tikzstyle{red vertex}=[vertex, fill=red!40]
    \tikzstyle{black vertex}=[vertex, fill=black, text=white]
    
    \tikzstyle{edge} = [draw, thick, minimum size=1cm]
    \tikzstyle{explored edge} = [edge, red!50]
    
    \foreach \pos/\name/\style/\time/\label/\labelpos in {{(0,0)/A/white vertex/1/-$\sim$-/above},
                                                            {(0,0)/A/red vertex/2-12/1$\sim$-/above},
                                                            {(0,0)/A/black vertex/13-/1$\sim$12/above},
                                                            {(1,0)/B/white vertex/1-2/-$\sim$-/above},
                                                            {(1,0)/B/red vertex/3-11/2$\sim$-/above},
                                                            {(1,0)/B/black vertex/12-/2$\sim$11/above},
                                                            {(2,0)/C/white vertex/1-3/-$\sim$-/above},
                                                            {(2,0)/C/red vertex/4-8/3$\sim$-/above},
                                                            {(2,0)/C/black vertex/9-/3$\sim$8/above},
                                                            {(3,0)/D/white vertex/1-13/-$\sim$-/above},
                                                            {(3,0)/D/red vertex/14-16/13$\sim$-/above},
                                                            {(3,0)/D/black vertex/17-/13$\sim$16/above},
                                                            {(0,-1)/E/white vertex/1-9/-$\sim$-/below},
                                                            {(0,-1)/E/red vertex/10/9$\sim$-/below},
                                                            {(0,-1)/E/black vertex/11-/9$\sim$10/below},
                                                            {(1,-1)/F/white vertex/1-5/-$\sim$-/below},
                                                            {(1,-1)/F/red vertex/6/5$\sim$-/below},
                                                            {(1,-1)/F/black vertex/7-/5$\sim$6/below},
                                                            {(2,-1)/G/white vertex/1-4/-$\sim$-/below},
                                                            {(2,-1)/G/red vertex/5-7/4$\sim$-/below},
                                                            {(2,-1)/G/black vertex/8-/4$\sim$7/below},
                                                            {(3,-1)/H/white vertex/1-14/-$\sim$-/below},
                                                            {(3,-1)/H/red vertex/15/14$\sim$-/below},
                                                            {(3,-1)/H/black vertex/16-/14$\sim$15/below}}
        \node<\time>[\style, label=\labelpos:date \label] (\name) at \pos {$\name$};
        
    \foreach \from/\to/\style/\time in {{A/B/edge/1-2},
                                       {A/B/explored edge/3-},
                                       {A/E/edge/1-17},
                                       {B/E/edge/1-9},
                                       {B/E/explored edge/10-},
                                       {E/F/edge/1-17},
                                       {F/B/edge/1-17},
                                       {B/C/edge/1-3},
                                       {B/C/explored edge/4-},
                                       {C/F/edge/1-17},
                                       {C/G/edge/1-4},
                                       {C/G/explored edge/5-},
                                       {G/F/edge/1-5},
                                       {G/F/explored edge/6-},
                                       {D/G/edge/1-17},
                                       {D/H/edge/1-14},
                                       {D/H/explored edge/15-},
                                       {H/G/edge/1-17}}
        \path<\time>[\style] (\from) -- (\to);
        
        \node<18-> (fakenode) at (0,0) {};
    \end{tikzpicture}
\end{frame}
\subsubsection{BFS (parcours en largeur)}

\newsavebox{\initbfs}
\setbox\initbfs\vbox{
    \begin{algorithm}[H]
        \DontPrintSemicolon
        \KwData{Graphe $G=\left(S,A\right)$}
        \KwIn{Sommet $s$}
        \;
        \ForEach{sommet $\in$ $S$}{
            couleur(sommet) $\leftarrow$ Blanc\;
            distance(sommet) $\leftarrow$ $\infty$\;
        }
        \;
        couleur($s$) $\leftarrow$ Rouge\;
        distance($s$) $\leftarrow$ 0\;
        $F$ $\leftarrow$ $\left\{s\right\}$\;
    \end{algorithm}
}
\newsavebox{\bfs}
\setbox\bfs\vbox{
    \begin{algorithm}[H]
        \DontPrintSemicolon
        \KwData{Graphe $G=\left(S,A\right)$}
        \KwIn{File $F$}
        \;
        \Begin{
            \While{$\neg$ FileVide($F$)}{
                $s$ $\leftarrow$ Defiler($F$)\;
                \ForEach{$v$ $\in$ adjascent($s$)}{
                    \If{couleur($v$) == Blanc}{
                        couleur($v$) $\leftarrow$ Rouge\;
                        distance($v$) $\leftarrow$ distance($s$) + 1\;
                        pere($v$) $\leftarrow$ $s$\;
                        Enfiler($F$, $v$)\;
                    }
                }
                couleur($s$) $\leftarrow$ Noir\;
            }
        }
    \end{algorithm}
}
\begin{frame}
    \begin{overprint}
        \onslide<1>\centering\usebox\initbfs
        \onslide<2>\centering\scalebox{0.7}{\usebox\bfs}
    \end{overprint}
\end{frame}
\subsubsection{Exemple BFS}
\begin{frame}
    \begin{overprint}
       \onslide<8> BFS $\rightarrow$ Arborescence en largeur et plus court chemin à partir de A
     \end{overprint} \vspace{0.5cm}

    \raisebox{-0.5\height}{\begin{tikzpicture}[auto, ->, scale=2]
    
    \tikzstyle{vertex}=[circle,minimum size=20pt,inner sep=0pt]
    \tikzstyle{white vertex}=[vertex, fill=black!10]
    \tikzstyle{red vertex}=[vertex, fill=red!40]
    \tikzstyle{black vertex}=[vertex, fill=black, text=white]
    
    \tikzstyle{edge} = [draw, thick, minimum size=1cm]
    \tikzstyle{explored edge} = [edge, red!50]
    
    \foreach \pos/\name/\style/\time/\label/\labelpos in {{(0,0)/A/red vertex/1/0/above},
                                                            {(0,0)/A/black vertex/2-/0/above},
                                                            {(1,0)/B/white vertex/1/$\infty$/above},
                                                            {(1,0)/B/red vertex/2/1/above},
                                                            {(1,0)/B/black vertex/3-/1/above},
                                                            {(2,0)/C/white vertex/1-2/$\infty$/above},
                                                            {(2,0)/C/red vertex/3-4/2/above},
                                                            {(2,0)/C/black vertex/5-/2/above},
                                                            {(3,0)/D/white vertex/1-/$\infty$/above},
                                                            {(0,-1)/E/white vertex/1/$\infty$/below},
                                                            {(0,-1)/E/red vertex/2-3/1/below},
                                                            {(0,-1)/E/black vertex/4-/1/below},
                                                            {(1,-1)/F/white vertex/1-3/$\infty$/below},
                                                            {(1,-1)/F/red vertex/4-5/2/below},
                                                            {(1,-1)/F/black vertex/6-/2/below},
                                                            {(2,-1)/G/white vertex/1-4/$\infty$/below},
                                                            {(2,-1)/G/red vertex/5-6/3/below},
                                                            {(2,-1)/G/black vertex/7-/3/below},
                                                            {(3,-1)/H/white vertex/1-/$\infty$/below}}
        \node<\time>[\style, label=\labelpos:{dist=\label}] (\name) at \pos {$\name$};
        
    \foreach \from/\to/\style/\time in {{A/B/edge/1},
                                       {A/B/explored edge/2-},
                                       {A/E/edge/1},
                                       {A/E/explored edge/2-},
                                       {B/E/edge/1-7},
                                       {E/F/edge/1-3},
                                       {E/F/explored edge/4-},
                                       {F/B/edge/1-7},
                                       {B/C/edge/1-2},
                                       {B/C/explored edge/3-},
                                       {C/F/edge/1-7},
                                       {C/G/edge/1-4},
                                       {C/G/explored edge/5-},
                                       {G/F/edge/1-7},
                                       {D/G/edge/1-7},
                                       {D/H/edge/1-7},
                                       {H/G/edge/1-7}}
        \path<\time>[\style] (\from) -- (\to);
        
        \node<8-> (fakenode) at (0,0) {};
    \end{tikzpicture}}
    \raisebox{-0.5\height}{\begin{tikzpicture}[auto]
        \tikzstyle{vertex}=[rectangle, minimum size=20pt,inner sep=0pt]
        \tikzstyle{edge} = [draw, thick, minimum size=1cm]
        
        \node<1>[vertex, draw] (A) at (0,0) {A};
        \node<2>[vertex, draw] (E) at (0,0) {E};
        \node<2>[vertex, draw] (B) at (1,0) {B};
        \node<3>[vertex, draw] (C) at (0,0) {C};
        \node<3>[vertex, draw] (E) at (1,0) {E};
        \node<4>[vertex, draw] (F) at (0,0) {F};
        \node<4>[vertex, draw] (C) at (1,0) {C};
        \node<5>[vertex, draw] (G) at (0,0) {G};
        \node<5>[vertex, draw] (F) at (1,0) {F};
        \node<6>[vertex, draw] (G) at (0,0) {G};
        \node<7>[vertex] (fakenode) at (0,0) {};
        
        \path<1-7>[edge, ->] (-0.5,0.7) -- node[minimum width = 0, minimum height = 0,above]{File} (1.5,0.7);
    \end{tikzpicture}}
\end{frame}
\end{document}