% \documentclass[xcolor=hyperref,hyperef={naturalnames,pdfpagelabels},french,envcountsect
% ]{beamer}
\RequirePackage{atbegshi}
\documentclass[french]{beamer}
\usepackage{etex}
\usepackage[beamer,utf8,fourier]{preambuleTrm}
%\usepackage[french,vlined,boxed]{algorithm2e}
\usepackage{bookmark,multido}
\usepackage{xlop}
\usepackage{tikz}
\usetikzlibrary{arrows,automata,fit,trees,positioning,shadows}
\usepackage{tkz-graph,tkz-berge}
%\usepackage{multimedia}
% \usepackage{cclicenses}
% \usepackage{cclicence}
\setbeamertemplate{theorems}[numbered]

\usepackage{algo}

\renewcommand{\algocommentfont}{\small\ttfamily\itshape}

\newcommand\nor{\downarrow}
\newcommand\nand{\mid}

\newtheorem{exercice}{Exercice}


\setlength{\columnseprule}{0pt}


\graphicspath{{/home/moi/Lycee/TDmaple/2006_7/}{/home/moi/Figures/Arbres_Graphes/}{/home/moi/Figures/FigSTI/}{/home/moi/Figures/FigMaple/}{/home/moi/Photos/Maths/}{/home/moi/Photos/Tehessin/}{/home/moi/Figures/FigSTI/}{/home/moi/Figures/FigSeconde/}{/home/moi/Lycee/Informatique/XCAS/2008_9/}{/home/moi/Lycee/TDmaple/2008_9/}{/home/moi/IUT/Thierry/Conversions/}{/home/moi/Photos/informathix/}{/home/moi/Lycee/Informatique/PafAlgo/}}




\newcommand\sage{\lstset{numbers=none,language=sage,xleftmargin=10pt,%
keywordstyle =\color{orange!40}\usefont{OT1}{cmtt}{b}{n},basicstyle=\ttfamily\color{white},commentstyle=\normalfont\scriptsize\slshape,breaklines=true,backgroundcolor=\color{black!90!red},frame=trBL,framerule=1pt,framesep=4pt,rulesep=1pt,showstringspaces=false,stringstyle=\slshape,captionpos=b}
}


\newcommand\caml{
\lstset{numbers=none,language=Caml,xleftmargin=10pt,%
keywordstyle =\color{blue!40}\usefont{OT1}{cmtt}{b}{n},basicstyle=\ttfamily\color{white},commentstyle=\normalfont\scriptsize\slshape,breaklines=true,backgroundcolor=\color{black!90!blue},frame=trBL,framerule=1pt,framesep=4pt,rulesep=1pt,showstringspaces=false,stringstyle=\slshape,captionpos=b}
}





\newcommand\lat{
\lstset{numbers=none,language=[LaTeX]{TeX},xleftmargin=10pt,%
keywordstyle =\color{yellow!40}\usefont{OT1}{cmtt}{b}{n},basicstyle=\ttfamily\color{white},commentstyle=\normalfont\scriptsize\slshape,breaklines=true,backgroundcolor=\color{black!90!yellow},frame=trBL,framerule=1pt,framesep=4pt,rulesep=1pt,showstringspaces=false,stringstyle=\slshape,captionpos=b}
}





\renewcommand\FancyVerbFormatLine[1]{\colorbox{green}{#1}}


\mode<presentation>
{
  \usetheme[secheader]{Madrid}
  % or ...Warsaw

  \setbeamercovered{highly dynamic}
  % or whatever (possibly just delete it)
}
\usepackage{elephantbird}



\begin{document}


\title[] % (optional, use only with long paper titles)
{Les graphes: un jeu pour grands enfants}

\subtitle{ }

\author[] % (optional, use only with lots of authors)
{Guillaume CONNAN }
% - Give the names in the same order as the appear in the paper.
% - Use the inst{?} command only if the authors have different
%   affiliation.

\institute{\textsc{IUT} de Nantes - Dpt d'informatique }% (optional, but mostly needed)

%\logo{\includegraphics[scale=0.15]{big_connan}}

\date[] % (optional, should be abbreviation of conference name)
{\today}
% - Either use conference name or its abbreviation.
% - Not really informative to the audience, more for people (including
%   yourself) who are reading the slides online

\subject{ }


\beamerdefaultoverlayspecification{<+->}

\AtBeginSubsubsection[]
{
  \begin{frame}<beamer>
    \frametitle{Sommaire}
 {\scriptsize
\begin{multicols}{2}
    \tableofcontents[currentsection,currentsubsection]
       \end{multicols}
}

  \end{frame}
}




\AtBeginSubsection[]
{
  \begin{frame}<beamer>
    \frametitle{Sommaire}
 {\scriptsize
\begin{multicols}{2}
    \tableofcontents[currentsection,currentsubsection]
       \end{multicols}
}

  \end{frame}
}





\AtBeginSection[]
{
  \begin{frame}<beamer>
    \frametitle{Sommaire}
 {\scriptsize
\begin{multicols}{2}
    \tableofcontents[currentsection]
       \end{multicols}
}

  \end{frame}
}


% If you wish to uncover everything in a step-wise fashion, uncomment
% the following command: 

\beamerdefaultoverlayspecification{<+->}







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

\begin{frame}
 \frametitle{Sommaire}
{\scriptsize
\begin{multicols}{2} 
 \tableofcontents
\end{multicols}
}

 
 \end{frame}



 \begin{frame}

Pendant  30  ans,  les   mathématiques  à  l'IUT  d'informatique  furent
passionnément enseignées par Thierry \textsc{Brugère}:


%\begin{figure}
\begin{center}
  \includegraphics[width=0.6\linewidth]{thierry}
\end{center}
%\end{figure}

Le cours  qui vous sera proposé cette  année lui doit beaucoup  et on le
retrouvera souvent désigné comme \og Le Maître\fg{}...


\end{frame}




\section{Comment un mathématicien regarde une carte}


\begin{frame}


\begin{center}
  \includegraphics[width=0.8\linewidth]{konigsberg}
\end{center}


\end{frame}

%

\begin{frame}

\begin{figure}[h!]
\begin{center}
\begin{tikzpicture}
\SetGraphUnit{2.5}
%\GraphInit[vstyle=Shade]

\SetVertexNormal[Shape
= circle,%
LineWidth = 2pt,%
FillColor = green!50]
\tikzset{LabelStyle/.style= {draw,
fill = blue!10,
text = red}}
\Vertex{B}
\NO(B){A}
\SO(B){C}
\SetGraphUnit{4}
% modifie la distance entre les nodes
\EA(B){D}
\SetUpEdge[color=white]
\Edge[label=1](B)(D)
\tikzset{EdgeStyle/.append style = {bend left}}
\Edge[label=4](A)(B)
\Edge[label=5](B)(A)
\Edge[label=6](B)(C)
\Edge[label=7](C)(B)
\Edge[label=2](A)(D)
\Edge[label=3](D)(C)
\end{tikzpicture}
\caption{Graphe des ponts de Königsberg}
\end{center}
\end{figure}

\end{frame}

\sage
\begin{frame}[fragile]
\begin{lstlisting}[caption={}]
sage:  g = Graph({'A':['B','B','D'],'D':['B','C'],'C':['B','B']})
\end{lstlisting}



\begin{lstlisting}[caption={}]
sage: g.show()
\end{lstlisting}


\end{frame}


%




\begin{frame}
\begin{center}
  \includegraphics[scale=0.5]{kali}
\end{center}
\end{frame}




\begin{frame}
\begin{center}
  \includegraphics[width=0.6\linewidth]{kaliningrad}
\end{center}
\end{frame}




\section{Les bases}


\subsection{Graphes symétriques}



%

\begin{frame}
 \begin{center}
\begin{tikzpicture}
\SetGraphUnit{2}
\SetVertexNormal[Shape
= circle,%
LineWidth = 2pt,%
FillColor = gray!50]
\Vertices{circle}{1,3,5,2,4}
\SetUpEdge[color=white]
\Edges(2,3,4,5)
\Edge(5)(3)
\end{tikzpicture}
\end{center}
\begin{columns}
\begin{column}{6cm}
 \begin{itemize}
  \item Un \textbf{graphe simple non orienté}
\item les \textbf{sommets}
\item les \textbf{arêtes}
\item sommets \textbf{adjacents}
\item sommet \textbf{voisin}
  \end{itemize}
\end{column}
\begin{column}{6cm}
  \begin{itemize}
\item arête \textbf{incidente} 
\item \textbf{extrémités}
    \item Le \textbf{degré} d'un sommet
\item sommet \textbf{isolé}
\item sommet \textbf{pendant} / \textbf{feuille}
  \end{itemize}
\end{column}
\end{columns}
\end{frame}




\begin{frame}
 \begin{center}
\begin{tikzpicture}
\SetGraphUnit{2}
\SetVertexNormal[Shape
= circle,%
LineWidth = 2pt,%
FillColor = gray!50]
\Vertices{circle}{1,3,5,2,4}
\SetUpEdge[color=white]
\Edges(2,3,4,5)
\Edge(5)(3)
\end{tikzpicture}
\end{center}

$\Gamma(i)$

\end{frame}












\subsection{Sous-graphes et réunion de graphes}

\begin{frame}
  \begin{itemize}
  \item $\GR$ est un \textbf{sous-graphe} de $\GR'$
\item $\GR$ est un \textbf{sous-graphe partiel} de $\GR'$ 
\item $\GR$  est  un \textbf{graphe  partiel}  de $\GR'$
  \end{itemize}
\end{frame}


\begin{frame}


\begin{center}
\begin{tikzpicture}
%\SetGraphColor{yellow}{blue}{maagenta}
\SetGraphUnit{1.5}
\SetVertexNoLabel
\Vertices{circle}{A,B,C,D,E}
\SetUpEdge[color=white]
\Edges(A,B,C,D,E,A,C,E,B,D)
\end{tikzpicture}
\begin{tikzpicture}
%\SetGraphColor{yellow}{blue}{maagenta}
\SetGraphUnit{1.5}
\SetVertexNoLabel
\Vertices{circle}{A,B,C,D,E}
\SetUpEdge[color=white]
\Edges(A,B,C,D,E,A,C,E,B,D)
\SetUpEdge[lw=4pt,color=white]
\Edges(B,D,E)
\end{tikzpicture}
\begin{tikzpicture}
%\SetGraphColor{yellow}{blue}{maagenta}
\SetGraphUnit{1.5}
\SetVertexNoLabel
\Vertices{circle}{A,B,C,D,E}
\SetUpEdge[color=white]
\Edges(A,B,C,D,E,A,C,E,B,D)
\SetUpEdge[lw=4pt,color=white]
\Edges(B,D,E,B)
\end{tikzpicture}
\end{center}


\end{frame}




\begin{frame}
  \begin{exercice}
    Sept ordinateurs a, b, c, d, e, f et g forment un réseau:
    \begin{itemize}
    \item a est directement relié à 6 ordinateurs;
\item a est directement relié à 5 ordinateurs;
\item c et d sont directement reliés à 3 ordinateurs;
\item e et f sont directement reliés à 2 ordinateurs;
\item g est relié à un ordinateur.
    \end{itemize}

À quels ordinateurs sont directement reliés chacun des six membres du réseau?

  \end{exercice}
\end{frame}


\begin{frame}
La   réunion  de   deux  graphes   simples  $   \GR_1=(X_1,A_1)$   et  $
\GR_2=(X_2,A_2)$ 

\pause
\begin{center}
\begin{tikzpicture} \SetGraphUnit{1.25}
\Vertex{E}
\NOWE(E){D}
\NOEA(E){B}
\NOEA(D){A}
\SOEA(B){C}
%\EA(E){F}
\SetUpEdge[color=white]
\Edges(E,C,B,A,D,E,B)
\end{tikzpicture}
\begin{tikzpicture} \SetGraphUnit{1.25}
%\GraphInit[vstyle=Classic]
\Vertex{D}
\NOEA(D){A}
\SOEA(A){B}
\SOEA(B){C}
\SOWE(C){F}
\SetUpEdge[color=white]
\Edges(A,B,C,F,B,D)
\end{tikzpicture}
\end{center}

\end{frame}









\begin{frame}
Le complémentaire $\overline{\GR}$ d'un graphe simple $\GR$

\pause

\begin{center}
\begin{tikzpicture} \SetGraphUnit{1.25}
\Vertex{E}
\NOWE(E){D}
\NOEA(E){B}
\NOEA(D){A}
\SOEA(B){C}
%\EA(E){F}
\SetUpEdge[color=white]
\Edges(E,C,B,A,D,E,B)
\end{tikzpicture}
\end{center}

\end{frame}




\subsection{Quelques graphes simples particuliers}



\begin{frame}
  Les \textbf{graphes complets} $K_n$:


\begin{columns}
\multido{\i=1+1}{5}{%
\begin{column}{2cm}
\includegraphics[width=2.2cm]{k\i}
\end{column}
}
\end{columns}
\end{frame}



\begin{frame}
  Les \textbf{cycles élémentaires} $C_n$:


\begin{columns}
\multido{\i=1+1}{5}{%
\begin{column}{2cm}
\includegraphics[width=2.2cm]{C\i}
\end{column}
}
\end{columns}
\end{frame}


\begin{frame}
  Les \textbf{roues} $W_n$:


\begin{columns}
\multido{\i=1+1}{5}{%
\begin{column}{2cm}
\includegraphics[width=2.2cm]{W\i}
\end{column}
}
\end{columns}
\end{frame}




\begin{frame}
  \begin{exercice}
    Un  \textbf{\textit{n}-cube}  $Q_n$  est  le  graphe  dont  les  sommets
représentent les $2^n$ chaînes de bits de longueur $n$ et tel que deux sommets
sont  adjacents  si,  et  seulement  si,  les  chaînes  de  bits  qu'ils
représentent diffèrent d'un bit. Dessinez  $Q_2$ et $Q_3$.
  \end{exercice}
\end{frame}



\begin{frame}
  Un graphe $\GR=(X,A)$ est biparti si


\pause


Le   \textbf{graphe    biparti   complet}   $K_{m,n}$ 
\end{frame}




\begin{frame}

  \begin{itemize}
\item \textbf{Score} du graphe $\GR$
    \item Graphe \textbf{régulier}
\item Graphe \textbf{\textit{n}-régulier}
  \end{itemize}

 
\end{frame}


\subsection{Graphes orientés}

\begin{frame}

\begin{center}
\begin{tikzpicture}
\SetGraphUnit{2}
\Vertex{a}
\EA(a){b}
\EA(b){c}
\SO(a){e}
\SO(b){d}
\SetUpEdge[style={->},color=white]
\Edge(a)(b)
\Edge(b)(d)
\Edge(c)(b)
\Edge(d)(c)
\Edge[style={->,bend left}](a)(c)
\Edge[style={->,bend left}](e)(a)
\Edge[style={->,bend left}](a)(e)
\Edge[style={->,bend right}](d)(e)
\Edge[style={->,bend right}](e)(d)
\Loop[dist=1cm,dir=NOWE,style={thick,->},color=white](a)
\Loop[dist=1cm,dir=SO,style={thick,->},color=white](e)
\end{tikzpicture}

\end{center}



  \begin{columns}
\begin{column}{6cm}
 \begin{itemize}
  \item Un \textbf{graphe orienté}
\item les \textbf{sommets}
\item les \textbf{arcs}
\item \textbf{origine} et \textbf{extrémité}
\item \textbf{successeur} et \textbf{prédécesseur}
  \end{itemize}
\end{column}
\begin{column}{6cm}
  \begin{itemize}
\item \textbf{chemin} 
\item \textbf{chemin simple} \pause \textbf{élémentaire}\pause \textbf{fermé}
\item \textbf{circuit}
\item La \textbf{longueur} d'un chemin
\item $\Gamma^+$ \pause $\Gamma^-$
  \end{itemize}
\end{column}
\end{columns}
\end{frame}



\begin{frame}

\begin{center}
\begin{tikzpicture}
\SetGraphUnit{2}
\Vertex{a}
\EA(a){b}
\EA(b){c}
\SO(a){e}
\SO(b){d}
\SetUpEdge[style={->},color=white]
\Edge(a)(b)
\Edge(b)(d)
\Edge(c)(b)
\Edge(d)(c)
\Edge[style={->,bend left}](a)(c)
\Edge[style={->,bend left}](e)(a)
\Edge[style={->,bend left}](a)(e)
\Edge[style={->,bend right}](d)(e)
\Edge[style={->,bend right}](e)(d)
\Loop[dist=1cm,dir=NOWE,style={thick,->},color=white](a)
\Loop[dist=1cm,dir=SO,style={thick,->},color=white](e)
\end{tikzpicture}

\end{center}



  \begin{columns}
\begin{column}{6cm}
 \begin{itemize}
  \item \textbf{degré d'entrée} \pause \textbf{demi-degré intérieur}
\item \textbf{degré de sortie} \pause \textbf{demi-degré extérieur}
\item \textbf{graphe symétrique sous-jacent}
  \end{itemize}
\end{column}
\begin{column}{6cm}
  \begin{itemize}
\item \textbf{descendant}
\item \textbf{accessible}
\item \textbf{ascendant}
  \end{itemize}
\end{column}
\end{columns}
\end{frame}

\begin{frame}


\begin{center}
  \begin{tikzpicture}
\SetGraphUnit{1.5}
\tikzset{EdgeStyle/.style={->},color=white}
\Vertices{circle}{2,4,1,5,3}
\SetUpEdge[color=white]
\Edges(5,3,2,4,1)
\Edges(5,2)
\Edges(5,4)
\end{tikzpicture}
\end{center}


$\displaystyle\bigcup\limits_{k=1}^{+\infty }\GR ^{k}\left(
\left\{ x_{i}\right\} \right) =\GR ^{+}\left( \left\{ x_{i}\right\}
\right) =\displaystyle\bigcup\limits_{k=1}^{n}\GR ^{k}\left( \left\{ x_{i}\right\}
\right) $

\pause

$\displaystyle\bigcup\limits_{k=1}^{+\infty }\GR ^{-k}\left(
\left\{ x_{i}\right\} \right) =\displaystyle\bigcup\limits_{k=1}^{n}\GR ^{-k}\left(
\left\{ x_{i}\right\} \right) ,$

\pause

$\GR ^{-}\left(
\left\{ x_{i}\right\} \right) .$

\end{frame}








\begin{frame}
  \begin{theorem}
Pour tout graphe $\GR=(X,A)$ symétrique, nous avons:

$$\displaystyle\sum_{s\in X}\deg_{\GR}(s)=...?$$
\end{theorem}

\pause

Que peut-on dire du nombre de sommets de degré impair dans un graphe?

\pause
\begin{theorem}
Pour tout graphe $\GR=(X,A)$ orienté, nous avons:

$$\displaystyle\sum_{s\in X}\deg_{\GR}^-(s)+\sum_{s\in X}\deg_{\GR}^+(s)=...?$$
\end{theorem}


\end{frame}



\begin{frame}
\begin{exercice}
À  Infoland, le  Lac de  la mort  contient sept  îles et  de  chaque île
partent un, trois ou cinq ponts.   Montrez qu'au moins un des ponts mène
sur la rive du lac de la mort?
\end{exercice}
\end{frame}




\subsection{Matrices d'adjacence}

\begin{frame}
  \begin{columns}
    \begin{column}{6cm}
  \begin{tikzpicture} \SetGraphUnit{1.75}
\Vertex{E}
\NOWE(E){D}
\NOEA(E){B}
\NOEA(D){A}
\SOEA(B){C}
\SetUpEdge[color=white]
\Edges(E,C,B,A,D,E,B)
\end{tikzpicture}
\end{column}
\begin{column}{6cm}
    \begin{center}
             \begin{tabularx}{\linewidth}{Y{0}}
	     \whline
             Sommets & Sommets adjacents\\
             \whline
             A & B,D\\
             B & A,C,E\\
             C & B,E\\
             D & A,E\\
             E & B,C,D\\
             \whline
             \end{tabularx}
             \end{center}
\end{column}
  \end{columns}





\end{frame}





\begin{frame}
  

\begin{definition}
Soit $\GR=(X,A)$  un graphe à $n$ sommets.  Notons $s_1$, $s_2$,...$s_n$
les sommets dans un ordre arbitraire. La \textbf{matrice d'adjacence} de
$\GR$  relativement à  la numérotation  choisie sur  les sommets  est la
matrice de taille $n\times n$, $M_\GR=(m_{ij})_{1 \leqslant i,j \leqslant
  n}$, définie par:

$$ m_{ij}=
\begin{cases}
  1 \quad \text{si } \{s_i,s_j\}\in A\\
  0 \quad \text{sinon}
\end{cases}
$$
\end{definition}

\end{frame}






\begin{frame}
  \begin{columns}
    \begin{column}{6cm}
  \begin{tikzpicture} \SetGraphUnit{1.75}
\Vertex{E}
\NOWE(E){D}
\NOEA(E){B}
\NOEA(D){A}
\SOEA(B){C}
\SetUpEdge[color=white]
\Edges(E,C,B,A,D,E,B)
\end{tikzpicture}
\end{column}
\begin{column}{6cm}
    \begin{center}
             \begin{tabularx}{\linewidth}{Y{0}}
	     \whline
             Sommets & Sommets adjacents\\
             \whline
             A & B,D\\
             B & A,C,E\\
             C & B,E\\
             D & A,E\\
             E & B,C,D\\
             \whline
             \end{tabularx}
             \end{center}
\end{column}
  \end{columns}





\end{frame}







\begin{frame}
  \begin{alertblock}{Remarque}
    Une matrice  occupe un espace  mémoire de l'ordre de  $\card(X)^2$ alors
qu'un  tableau  présentant  les  listes  d'adjacence  de  chaque  sommet
n'occupe qu'un espace de l'ordre de $\card(X)+\card(A)$...
  \end{alertblock}
\end{frame}






\section{Isomorphisme de graphes}




\begin{frame}
  \begin{definition}
Les   graphes   simples   $\GR=(X,A)$   et  $\GR'=(X',A')$   sont   dits
\textbf{isomorphes} s'il  existe une bijection  $f : X\to X'$  telle que
nous  ayons, pour  tout couple  de sommets  distincts du  premier graphe
$(x,y)\in X^2$, $x\neq x'$,

$$ \text{l'arête  }\bigl\{x,y\bigr\} \in A  \text{ si, et  seulement si,
  l'arête }
\bigl\{f(x),f(y)\bigr\}\in A'$$


Une  telle  fonction $f$  est  appelée  \textbf{isomorphisme} entre  les
graphes $\GR$ et $\GR'$ et nous notons $\GR \cong \GR'$.
\end{definition}
\end{frame}

\begin{frame}
\begin{center}
\begin{columns}
\begin{column}{6cm}
\begin{tikzpicture}
\SetGraphUnit{1.5}
\Vertices{circle}{A,B,C,D,E,F}
\SetUpEdge[color=white]
\Edges(A,B,C,D,E,F,A)
\Edge(A)(D)
\Edge(B)(E)
\Edge[style={bend left}](C)(F)
\end{tikzpicture}
\end{column}

\begin{column}{6cm}
\begin{tikzpicture}
\SetGraphUnit{1.75}
\Vertex{1}
\EA(1){2}
\NO(1){4}
\EA(2){3}
\NO(2){5}
\NO(3){6}
\SetUpEdge[color=white]
\Edges(1,6,3,4,1,5,3,4,2,6)
\Edge(5)(2)
\end{tikzpicture}
\end{column}
\end{columns}
\end{center}
\end{frame}



\begin{frame}

Comparez le  nombre de sommets,
le nombre d'arêtes,  le nombre de sommets selon  leur degré: tout semble
se conserver, et pourtant....


\begin{center}
\begin{tikzpicture}
\SetGraphUnit{1.5}
\Vertex{d}
\NOEA(d){h}
\NO(h){e}
\NOWE(e){a}
\EA(h){g}
\SOEA(g){c}
\NO(g){f}
\NOEA(f){b}
\SetUpEdge[color=white]
\Edges(d,c,b,a,d,h,g,f,e,h)
\Edge(f)(b)
\end{tikzpicture}
\hfill
\begin{tikzpicture}
\SetGraphUnit{1.5}
\Vertex{v}
\NOEA(v){z}
\NO(z){w}
\NOWE(w){s}
\EA(z){y}
\SOEA(y){u}
\NO(y){x}
\NOEA(x){t}
\SetUpEdge[color=white]
\Edges(w,z,y,x,w,s,t,u,v,z)
\Edge(v)(s)
\end{tikzpicture}
\end{center}

\pause

Quel  est le degré  de a?  Vers quel(s)  sommet(s) peut-il  être envoyé?
Observez les degrés des sommets adjacents des candidats et concluez.


\end{frame}










\section{Connexité}


\subsection{Chaînes et chemins}


\begin{frame}
Chaîne de longueur $n$...

\pause

Chaîne fermée....


\pause

Chaîne élémentaire...

\pause


Chaîne simple...


\pause


Cycle...

\end{frame}



\begin{frame}
Sur le graphe suivant, nous voulons aller de 0 jusqu'à 3.



\begin{center}
  \begin{tikzpicture}
    \SetGraphUnit{1.5}
\Vertices{circle}{0,1,2,3,4,5}
\SetUpEdge[color=white]
\Edges(4,3,2,4,1,5,0,1,2,4,5)
  \end{tikzpicture}
\end{center}


Décomposez les chaînes élémentaires. Quelle est la plus courte?
\end{frame}



\begin{frame}
\begin{center}
% Set the overall layout of the tree
\tikzstyle{level 1}=[level distance=.5cm, sibling distance=5.75cm]
\tikzstyle{level 2}=[level distance=.5cm, sibling distance=2.3cm]
\tikzstyle{level 3}=[level distance=.5cm, sibling distance=1.1cm]
\tikzstyle{level 4}=[level distance=.5cm, sibling distance=.7cm]
\begin{tikzpicture}[
state/.style={circle, draw=none, fill=blue!20, circular drop shadow,
        text centered, anchor=north, text=red},
    fact/.style={rectangle, draw=none, rounded corners=1mm, fill=blue, drop shadow,
        text centered, anchor=north, text=white},
     growth parent anchor=south
]

\node[state]{0}
   child{
     node{1}
       child{
         node{5}
           child{
             node{4}
               child{
                 node{2}
                   child{
                     node[fact]{3}
                   }
               }
               child{
                 node[fact]{3}
               }
           }
       }
       child{
         node{4}
             child{
                 node{2}
                   child{
                     node[fact]{3}
                   }
               }
             child{
               node[fact]{3}
             }
            child{
               node{5}
             }
       }
       child{
         node{2}
           child{
             node[fact]{3}
           }
           child{
             node{4}
               child{
                 node[fact]{3}
               }
               child{
                 node{5}
               }
           }
       }
   }
   child{
    node{5}
      child{
        node{1}
          child{
            node{2}
              child{
                node{4}
                  child{
                    node[fact]{3}
                  }
              }
              child{
                node[fact]{3}
              }
          }
          child{
            node{4}
              child{
                node{2}
                  child{
                    node[fact]{3}
                  }
              }
              child{
                node[fact]{3}
              }
          }
      }
      child{
        node{4}
          child{
            node[fact]{3}
          }
          child{
            node{2}
              child{
                node{1}
              }
              child{
                node[fact]{3}
              }
          }
          child{
            node{1}
              child{
                node{2}
                  child{
                    node[fact]{3}
                  }
              }
          }
      }
   }
   


;
        
\end{tikzpicture}
\end{center}
\end{frame}






\subsection{Nombre de chaînes et matrice d'adjacence}



\begin{frame}
\begin{theorem}\label{th::mat_dist}
Soit $\GR=(X,A)$,  avec $X=\bigl\{x_1,x_2,...,x_n\bigr\}$, un  graphe de
nature quelconque de matrice d'adjacence 
$M$  selon un  ordre fixé  des sommets.  Soit $m_{ij}^{(k)}$  l'élément de
position $(i,j)$ de la matrice $M^k$ avec $k$ un entier naturel.


Alors $m_{ij}^{(k)}$ est égal au nombre de chaînes de longueur $k$ entre
le sommet $x_i$ et le sommet $x_j$ dans le graphe $\GR$.
\end{theorem}
\end{frame}








\begin{frame}
  

\begin{definition}
Soit   $\GR=(X,A)$   un   graphe   \textit{connexe}.   On   définit   la
\textbf{distance} entre deux sommets $(x,x')\in X^2$, qu'on note
${\rm}d_{_\GR}(x,x')$, comme la longueur de la chaîne simple la plus courte
existant entre $x$ et $x'$ dans $\GR$.
\end{definition}

\end{frame}




\begin{frame}
  
Voici un réseau  routier où chaque sommet est une  ville et chaque arête
représente une route de longueur 100 km. 

 


\begin{center}
  \begin{tikzpicture}
    \SetGraphUnit{1.5}
\Vertices{circle}{0,1,2,3,4,5}
\SetUpEdge[color=white]
\Edges(4,3,2,4,1,5,0,1,2,4,5)
  \end{tikzpicture}
\end{center}


Quelle est sa matrice d'adjacence? 

Combien y a-t-il de trajets de longueur  300 km de la ville 0 à la ville
3?

Est-ce la plus petite distance possible?




\end{frame}





\begin{frame}

\begin{theorem}
Avec les notations du  théorème \vref{th::mat_dist}, soit $x_i$ et $x_j$
deux sommets d'un graphe $\GR$. Alors:
$$
{\rm d}_{\GR}(x_i,x_j)=\min \bigl\{k \geqslant 0 \mid m_{ij}^{(k)}\neq 0\bigr\}
$$
\end{theorem}

\end{frame}




\begin{frame}
  

\begin{center}
  \begin{tikzpicture}
    \SetGraphUnit{1.5}
\Vertices{circle}{0,1,2,3,4,5}
\SetUpEdge[color=white]
\Edges(4,3,2,4,1,5,0,1,2,4,5)
  \end{tikzpicture}
\end{center}


Quelle est sa matrice d'adjacence? Comment utiliser le théorème précédent?

\end{frame}

\sage

\begin{frame}[fragile]
\begin{lstlisting}[caption={}]
sage: M=matrix([[0,1,0,0,0,1],
                [1,0,1,0,1,1],
                [0,1,0,1,1,0],
                [0,0,1,0,1,0],
                [0,1,1,1,0,1],
                [1,1,0,0,1,0]])
sage: M^2
[2 1 1 0 2 1]
[1 4 1 2 2 2]
[1 1 3 1 2 2]
[0 2 1 2 1 1]
[2 2 2 1 4 1]
[1 2 2 1 1 3]
sage: M^3
[2 6 3 3 3 5]
[6 6 8 3 9 7]
[3 8 4 5 7 4]
[3 3 5 2 6 3]
[3 9 7 6 6 8]
[5 7 4 3 8 4]
\end{lstlisting}
\end{frame}


\begin{frame}[fragile]
\begin{lstlisting}[caption={}]
sage: def d_G(M,i,j):
    m=M
    k=1
    while m[i][j]==0:
        m*=M
        k+=1
    return k
....: ....: ....: ....: ....: ....: ....: 
sage: d_G(M,0,3)
3
\end{lstlisting}
\end{frame}




\subsection{Connexité des graphes non orientés}


\begin{frame}
  
\begin{definition}
On  dit qu'un  graphe  $\GR=(X,A)$ est  \textbf{connexe}  si, pour  tous
sommets $x$ et $y$ de $X$, $\GR$ contient un chaîne entre $x$ et $y$
\end{definition}


\end{frame}


\begin{frame}
  

\begin{center}
  \begin{tikzpicture}
\SetGraphUnit{1.5}
\Vertices{circle}{a,b,c,d,e}
\SetUpEdge[color=white]
\Edges(a,c,e,b,d,a)
\end{tikzpicture}
\hspace{3cm}
\begin{tikzpicture}
\SetGraphUnit{1.5}
\Vertices{circle}{a,b,c,d,e,f}
\SetUpEdge[color=white]
\Edges(a,c,e,a)
\Edges(f,b,d,f)
\end{tikzpicture}
\end{center}


\end{frame}



\begin{frame}
  
\begin{theorem}
Il existe  une chaîne  simple entre chaque  paire de  sommets (distincts)
d'un graphe simple connexe.
\end{theorem}

Démontrez  ce résultat.  Vous n'oublierez  pas la  notion de  plus petit
élément vue l'an dernier.
\end{frame}

\begin{frame}
  
\begin{theorem}
Si  un  graphe n'est  pas  connexe,  c'est  la réunion  de  sous-graphes
connexes qui n'ont pas de sommets en commun deux à deux.

On appelle ces sous-graphes les \textbf{composantes connexes} du graphe initial.

On appelle \textbf{connectivité} le nombre de composantes connexes d'un graphe.
\end{theorem}

\end{frame}







\begin{frame}
  \begin{center}
    \begin{tikzpicture}
\SetGraphUnit{1.5}
\Vertices{circle}{a,b,c,d,e,f}
\SetUpEdge[color=white]
\Edges(a,c,e,a)
\Edges(f,b,d,f)
\end{tikzpicture}

  \end{center}
\end{frame}

\begin{frame}
  
On peut définir assez simplement  un algorithme de connexité qui renvoie
la connectivité d'un graphe.

Notons $c$ cette connectivité et $\GR=(X,A)$ le graphe.
\end{frame}


\begin{frame}

\begin{algo}
\VAR
\DECLVAR{S}{liste de sommets}
\DECLVAR{c}{entier}
\ENDVAR
\BEGIN
\STATE{S\recoit{}X}
\STATE{c\recoit{}0}
\WHILE{S est non vide}
\STATE{Choisir s dans S}
\STATE{Lister tous les sommets joignant s par n'importe quel chaîne}
\STATE{Supprimer ces sommets et s  de S et les arêtes adjacentes}
\STATE{c \recoit{}c+1}
\ENDWHILE
\END
\end{algo}
\end{frame}

\begin{frame}
  
\begin{theorem}[Sommets connectés et relation d'équivalence]
Deux sommets  sont \textbf{connectés} s'il  existe une chaîne  ayant ces
deux sommets  pour extrémités.  On construit ainsi  une \textbf{relation
  d'équivalence}. Les  \textbf{classes d'équivalence} de  cette relation
sont  appelées \textbf{composantes  connexes}. Un  graphe  ne comportant
qu'une seule composante connexe est dit \textbf{connexe}
\end{theorem}
\end{frame}

\subsection{Point d'articulation}

\begin{frame}
  
\begin{definition}
Un \textbf{point d'articulation} de $\GR $ est un sommet dont la
suppression augmente le nombre de composantes connexes. Un \textbf{isthme}
est une ar\^{e}te dont la suppression a le m\^{e}me effet.
\end{definition}


\begin{center}
\color{white}
\input{../../../Thierry/Conversions/IsthmeNB.pdf_tex}
\end{center}


\end{frame}


\subsection{Connexité des graphes orientés}





\begin{frame}
  
\begin{definition}
Un graphe orienté  est \textbf{fortement connexe} s'il existe un  chemin de $a$ à
$b$ et  un chemin de $b$  à $a$ pour toute  paire $\bigl\{a,b\bigr\}$ de
sommets du graphe.

 Une
partie (non vide) $Y$ de $X$ est fortement connexe si, et seulement si, le
sous graphe d\'{e}fini par $Y$ ou engendr\'{e} par $Y,$ c'est-\`{a}-dire la
restriction du graphe $\GR =\left( X,A\right) $ \`{a} $Y,$ $\left(
Y,A\cap \left( Y\times Y\right) \right) ,$ est fortement connexe ; cela
signifie que pour toute paire de sommets de $Y,$ il existe un chemin de l'un 
\`{a} l'autre n'utilisant que des sommets de $Y$. La partie $Y$ est
fortement connexe maximale s'il n'existe pas de partie fortement connexe $Z$
de $X$ contenant strictement $Y.$
\end{definition}

\end{frame}



\begin{frame}
  
\begin{definition}
Un  graphe orienté  est \textbf{faiblement  connexe} si  son  graphe non
orienté sous-jacent est connexe.
\end{definition}
\end{frame}


\begin{frame}
  
\begin{center}
  \begin{tikzpicture}
    \SetGraphUnit{1.5}
\Vertices{circle}{c,b,a,e,d}

\Edges[style={->},color=white](b,c,d,e,a,b,d)
  \end{tikzpicture}
\hspace{3cm}
\begin{tikzpicture}
    \SetGraphUnit{1.5}
\Vertices{circle}{c,b,a,e,d}

\Edges[style={->},color=white](d,b,c,d,e,a)
\Edge[style={->},color=white](b)(a)
  \end{tikzpicture}
\end{center}

Pour le graphe qui n'est  pas fortement connexe, pouvez-vous trouver ses
trois composantes fortement connexes?

\end{frame}







\begin{frame}
  
\begin{theorem}
$Y=\left( \GR ^{+}\left( \left\{ x_{i}\right\} \right) \cap \GR
^{-}\left( \left\{ x_{i}\right\} \right) \right) \cup \left\{ x_{i}\right\} $
est une partie fortement connexe maximale du graphe $\GR .$ 
\end{theorem}
\end{frame}


\begin{frame}
  \begin{exampleblock}{Exemple}
    La sc\`{e}ne se passe dans une administration qui veut am\'{e}liorer le
cadre de vie de ses 9 employ\'{e}s $a,$ $b,$ $c,d,$ $e,$ $f,$ $g,$ $h$ et $i$
et qui travaillent dans une m\^{e}me salle. Ils \'{e}changent entre eux des
documents, le graphe suivant indique de quelle fa\c{c}on :%

\end{exampleblock}
\end{frame}


\begin{frame}
 \begin{exampleblock}{Exemple (suite)}
\begin{center}
\begin{tikzpicture}
\SetGraphUnit{2.75}
%\GraphInit[vstyle=Art]
\tikzset{EdgeStyle/.style={->}}
\Vertices{circle}{d,e,f,g,h,i,a,b,c}
\Edges[color=white](a,c,d,e,a,h)
\Edges[color=white](b,f,h)
\Edges[color=white](a,d,e,a)
\Edge[color=white](d)(g)\Edge[color=white](i)(f)
\Edge[style={bend left},color=white](b)(g)
\Edge[style={bend left},color=white](g)(b)
\Edge[style={bend left},color=white](h)(i)
\Edge[style={bend left},color=white](i)(h)
\Edge[style={bend left=90},color=white](d)(a)
\end{tikzpicture}
\end{center}

\end{exampleblock}
\end{frame}



\begin{frame}
 \begin{exampleblock}{Exemple (fin)}

On voudrait leur permettre de travailler dans de meilleures conditions et,
pour cela, les r\'{e}partir dans plusieurs bureaux en s\'{e}parant le moins
possible les employ\'{e}s entre lesquels les documents circulent.

  \end{exampleblock}
\end{frame}



\section{Parcours de graphes}

\subsection{Parcours en largeur}





\begin{frame}
  \begin{center}
  \begin{tikzpicture}
\SetGraphUnit{1.5}
\Vertex{1}
\SOEA(1){3}
\NOEA(3){2}
\SOEA(3){4}
\SOWE(3){5}
\SO(5){7}
\SO(4){8}
\SOEA(7){6}
%\tikzset{EdgeStyle/.style={->},color=white}
\SetUpEdge[color=white,style={->}]
\Edges(1,2,3,1)
\Edges(1,5,4,3)
\Edges(8,7,5)
\Edges(8,6,7)
\Edges(8,4)
\Edges(2,4)
\Edge[style={bend right,->},color=white](6)(8)
\Edge[style={bend right,->},color=white](1)(4)
\end{tikzpicture}
\end{center}
\end{frame}






\begin{frame}
  
Dessinez  l'arbre \og  d'exploration\fg{} avec  à  côté la  file et  une
patate contenant les sommets déjà traités.

\end{frame}




\begin{frame}[fragile]
\begin{algo}
\FORGEN{tout $ x\in X$ }
\STATE{etat[$ x$]\recoit{} non\_atteint}
\ENDFOR
\STATE{index\recoit{} 1}
\STATE{à\_traiter\recoit{}$ \emptyset$}
\FORGEN{tout $ z\in X$ }
\IF{etat[$z$]=non\_atteint}
\STATE{pere[$ z$]\recoit{}NIL}
\STATE{ordre[$z$]\recoit{}index}
\STATE{index ++}
\STATE{à\_traiter.AjouterEnQueue($ z$)}
\WHILE{à\_traiter$ \neq \emptyset$}
\STATE{$x$\recoit{}Tete(à\_traiter)}
\FORGEN{$y$ voisin de $x$}
\end{algo}
\end{frame}


\begin{frame}[fragile]
\begin{algo}[continue]
\IF{etat[$y$]=non\_atteint}
\STATE{etat[$y$]\recoit{}atteint}
\STATE{ordre[$y$]\recoit{}index}
\STATE{index $++$}
\STATE{pere[$y$]\recoit{}$x$}
\STATE{à\_traiter.AjouterEnQueue($ y$)}
\ENDIF
\ENDFOR
\STATE{à\_traiter.EnleverTete()}
\STATE{etat[$ x$]\recoit{}traite}
\ENDWHILE
\ENDIF
\ENDFOR
\end{algo}

\end{frame}





\subsection{Parcours en profondeur}

\begin{frame}
  
Concrètement, on part d'un sommet, on  va voir un de ses voisins puis un
voisin du voisin, etc., jusqu'à être bloqué, alors on va en arrière.

Ici,  le  critère de  choix  sera que  le  dernier  sommet atteint  sera
examiné.
 On utilisera cette fois une pile (Last In First Out).

\end{frame}




\begin{frame}
    \begin{center}
  \begin{tikzpicture}
\SetGraphUnit{1.5}
\Vertex{1}
\SOEA(1){3}
\NOEA(3){2}
\SOEA(3){4}
\SOWE(3){5}
\SO(5){7}
\SO(4){8}
\SOEA(7){6}
%\tikzset{EdgeStyle/.style={->},color=white}
\SetUpEdge[color=white,style={->}]
\Edges(1,2,3,1)
\Edges(1,5,4,3)
\Edges(8,7,5)
\Edges(8,6,7)
\Edges(8,4)
\Edges(2,4)
\Edge[style={bend right,->},color=white](6)(8)
\Edge[style={bend right,->},color=white](1)(4)
\end{tikzpicture}
\end{center}
Tracer \og l'arbre des visites\fg{}, la pile correspondant et les patate
des sommets visités.

\end{frame}

\begin{frame}[fragile]
  \begin{algo}
\PROC{parcours\_pro}{\pfarg{x}{sommet}}
\BEGIN
\STATE{etat[$ x$]\recoit{}atteint}
\STATE{ordre[$ x$]\recoit{}index}
\STATE{index $++$}
\FORGEN{$y$ voisin de $x$}
\IF{etat[$ y$]=non\_atteint}
\STATE{pere[$ y$]\recoit{x}}
\STATE{parcours\_pro($ y$)}
\ENDIF
\ENDFOR
\STATE{etat[$ x$]\recoit{} traite}
\END
\end{algo}
\end{frame}






\begin{frame}[fragile]

\begin{algo}
\FORGEN{tout $ x\in X$ }
\STATE{etat[$ x$]\recoit{} non\_atteint}
\ENDFOR
\STATE{index\recoit{} 1}
\FORGEN{ chaque $x\in X$}
\IF{etat[$ x$]=non\_atteint}
\STATE{pere[$ x$]\recoit{}NIL}
\STATE{parcours\_pro($ x$)}
\ENDIF
\ENDFOR
\end{algo}


\end{frame}



\section{Chaînes, chemins, circuits et cycles eulériens}

\subsection{Graphes symétriques}

\begin{frame}
  
\begin{center}
  \begin{tikzpicture}
    \SetGraphUnit{1.5}
\GraphInit[vstyle=Art]
\Vertices{circle}{1,2,3,4,5,6}
\SetUpEdge[color=white]
\Edges(3,4,5,6,1,2,6,3,2,5,3)
  \end{tikzpicture}
\end{center}

\end{frame}



\begin{frame}
  
%\begin{figure}
\begin{center}
  \includegraphics[scale=0.5]{gribouillage}
\end{center}
%\end{figure}

\end{frame}



\begin{frame}
  \begin{center}
\begin{tikzpicture}
\SetGraphUnit{2.5}
%\GraphInit[vstyle=Shade]
\SetVertexNormal[Shape
= circle,%
LineWidth = 2pt,%
FillColor = green!50]
\tikzset{LabelStyle/.style= {draw,
fill = blue!10,
text = red}}
\Vertex{B}
\NO(B){A}
\SO(B){C}
\SetGraphUnit{4}
% modifie la distance entre les nodes
\EA(B){D}
\Edge[label=1](B)(D)
\SetUpEdge[color=white,style={bend left}]
\Edge(A)(B)
\Edge(B)(A)
\Edge(B)(C)
\Edge(C)(B)
\Edge(A)(D)
\Edge(D)(C)
\end{tikzpicture}
\end{center}
\end{frame}

\begin{frame}
  
\begin{theorem}
Un graphe symétrique $\GR=(X,A)$ est eulérien si, et seulement si, il est connexe
et si chaque sommet est de degré pair.
\end{theorem}

\end{frame}





\begin{frame}
  

\begin{theorem}
Un graphe symétrique admet une chaîne eulérienne si deux sommets $s$ et $t$
sont  de degré impair  et que  tous les  autres sont  de degré  pair, la
chaîne ayant pour extrémité $s$ et $t$.
\end{theorem}

\end{frame}


\begin{frame}
  
\begin{center}
  \begin{tikzpicture}
       \SetGraphUnit{1.5}
\GraphInit[vstyle=Art]
\Vertices{circle}{1,2,3,4,5}
\SetUpEdge[color=white]
\Edges(1,5,4,3,2,4,1,2,5)
  \end{tikzpicture}
\end{center}

\end{frame}

\begin{frame} \frametitle{Algorithme de \bsc{Fleury}}
  \begin{enumerate}
  \item Choisir un sommet au hasard;
\item depuis ce sommet, choisir une  arête selon la règle: \og ne jamais
  emprunter  un isthme du  sous-graphe engendré  en enlevant  les arêtes
  déjà parcourues sauf s'il n'y a pas d'autre choix\fg{};
\item Colorier cette arête;
\item L'emprunter;
\item on continue jusqu'à revenir au sommet de départ.
  \end{enumerate}
\end{frame}


\begin{frame}
\begin{center}
  \begin{tikzpicture}
       \SetGraphUnit{1.5}
\GraphInit[vstyle=Art]
\Vertices{circle}{f,d,b,a,c,e}
\SetUpEdge[color=white]
\Edges(f,d,b,a,c,e)
\Edges(f,c,d,a)
\Edges[style={bend left}](e,a)
  \end{tikzpicture}
\end{center}
\end{frame}

\subsection{Graphes orientés}

\begin{frame}
  \begin{theorem}
  Un graphe \textit{orienté} possède  un circuit eulérien si, et seulement
  si,  il est faiblement  connexe et  que le  nombre d'arcs  arrivant en
  chaque sommet est égal au nombre d'arcs sortant de ce sommet.
\end{theorem}

\end{frame}




\begin{frame}
  
\begin{center}
  \begin{tikzpicture}\label{bruijn}
     \SetGraphUnit{1.5}
\Vertex{0}
\SOEA(0){1}
\SOWE(0){4}
\SOWE(1){2}
\SO(2){5}
\SOEA(5){3}
\SOWE(5){6}
\SOEA(6){7}
\SetUpEdge[color=white]
\Edges[style={->}](0,1,3,7,6,5,3,6,4,1,2,4,0)
\Edge[style={->,bend left}](2)(5)
\Edge[style={->,bend left}](5)(2)
\Loop[dist=1cm,dir=NO,style={->}](0)
\Loop[dist=1cm,dir=SO,style={->}](7)
  \end{tikzpicture}
\end{center}


\begin{center}
             \begin{tabularx}{\linewidth}{Y{15}}
	     \whline
             or&0&0&1&1&2&2&3&3&4&4&5&5&6&6&7&7\\
\whline
             ext&0&1&2&&4&&&&0&&&&&&&\\
             \whline
             \end{tabularx}
             \end{center}

\end{frame}








\section{Chaînes, chemins, circuits et cycles hamiltoniens}

\begin{frame}
  

%\begin{figure}
\begin{center}
  \includegraphics[width=0.5\linewidth]{icojeu}
\end{center}
%\end{figure}


\begin{center}
  \includegraphics[width=0.5\linewidth]{dodekajeu}
\end{center}


\end{frame}




\section{Les graphes avec Python}



\subsection{fonctions}




\begin{frame}[fragile]
\begin{lstlisting}[caption={}]
>>> def f(x):
...     return x**2
... 
>>> f(2)
4
\end{lstlisting}
\end{frame}



\subsection{La structure conditionnelle}





\begin{frame}[fragile]
\begin{lstlisting}[caption={}]
def max2(a, b):
    if a <= b:
        return b
    else:
        return a
\end{lstlisting}
\end{frame}






\subsection{Les boucles \og tant que\fg{}}


\begin{frame}[fragile]
\begin{lstlisting}[caption={}]
def pgcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a
\end{lstlisting}
\end{frame}


\subsection{Les listes}


\begin{frame}[fragile]
\begin{lstlisting}[caption={}]
>>> liste = [12,11,18,7,15,3]
>>> liste[0]
12
>>> liste[:2]
[12, 11]
>>> liste[2:]
[18, 7, 15, 3]
>>> liste[2:4]
[18, 7]
>>> liste[-1]
3
>>> tete=liste.pop(0)
>>> tete
12
>>> liste
[11, 18, 7, 15, 3]
>>> len(liste)
5
\end{lstlisting}
\end{frame}




\begin{frame}[fragile]
\begin{center}
    \begin{tabular}{ll}
la méthode & son effet \\
\hline
\verb?list.append(x)? & ajoute l'élément \verb?x? en fin de liste    \\
\verb?list.extend(L)? & ajoute en fin de liste les éléments de L     \\
\verb?list.insert(i, x)? & insère un élément \verb?x? en position \verb?i?  \\
\verb?list.remove(x)? & supprime  la première occurence de \verb?x?    \\
\verb?list.pop(i)?  & supprime l'élément d'indice \verb?i? et le renvoie  \\
\verb?list.index(x)?  & renvoie l'indice de la première occurence de \verb?x?  \\
\verb?list.count(x)?  & renvoie le nombre d'occurences de \verb?x?   \\
\verb?list.sort()?    & modifie la liste en la triant \\
\verb?list.reverse()? & modifie la liste en inversant l'ordre des éléments  \\
\hline
\end{tabular}
\end{center}
\end{frame}



\subsection{Les dictionnaires}



\begin{frame}[fragile]
\begin{lstlisting}[caption={}]
>>> tel={'Roger' : '02 40 00 00 00', 'Marcelle' : '02 40 00 00 01'} 
>>> tel['Marcelle']
'02 40 00 00 01'
\end{lstlisting}
\begin{lstlisting}[caption={}]
>>> tel.has_key('Roger')
True
>>> tel.keys()
['Marcelle', 'Roger']
\end{lstlisting}
\end{frame}






\subsection{Les boucles \og pour\fg{}}


\begin{frame}[fragile]
  \begin{lstlisting}[caption={}]
>>> r=range(5)
>>> r
[0, 1, 2, 3, 4]
>>> s=range(3,9)
>>> s
[3, 4, 5, 6, 7, 8]
>>> t=range(3,9,2)
>>> t
[3, 5, 7]
\end{lstlisting}
\end{frame}

\begin{frame}[fragile]
\begin{lstlisting}[caption={}]
>>> def f(n):
    for i in range(n):
        print('Je me répète '+str(n)+' fois')
... ... ... 
>>> f(3)
Je me répète 3 fois
Je me répète 3 fois
Je me répète 3 fois
\end{lstlisting}
\end{frame}




\subsection{La classe \og graphe\fg{}}


\begin{frame}[fragile]
\begin{lstlisting}[caption={}]
class graphe(object):
	def __init__(self, liste_adj =None):
		self.__liste_adj = liste_adj

	def __str__(self):
		return str(self.__liste_adj)
\end{lstlisting}
\end{frame}






\begin{frame}
\begin{center}
\begin{tikzpicture}\label{grafpyt}
\SetGraphUnit{1.5}
\Vertices{circle}{3,2,1,4}
\EA(3){5}
\EA(5){7}\NOEA(5){6}
\SetUpEdge[color=white]
\Edges(3,2,1,4,3,5,7,6,5)
\end{tikzpicture}
\end{center}
\end{frame}

\begin{frame}[fragile]
\begin{lstlisting}[caption={}]
>>> g=graphe( { '1':['2','4'],
                '2':['1','3'],
                '3':['2','4','5'],
                '4':['1','3'],
                '5':['3','6','7'],
                '6':['5','7'],
                '7':['5','6'] 
            } )
\end{lstlisting}
\end{frame}




\begin{frame}[fragile]
  \begin{lstlisting}[caption={}]
## méthode pour avoir les adjacents d'un sommet
	def adjacents(self, a):
		if self.__liste_adj is not None:
			if self.__liste_adj.has_key(a):
				return self.__liste_adj[a]
		return []
              \end{lstlisting}
\end{frame}


\begin{frame}[fragile]
  \begin{lstlisting}[caption={}]
## teste si a et b sont adjacents
	def est_adjacent(self, a, b):
		return (b in self.adjacents(a))

## liste les adjacents de a
	def liste_adjacence(self):
		return self.__liste_adj
  \end{lstlisting}
\end{frame}

\begin{frame}[fragile]
  \begin{lstlisting}[caption={}]
## donne la liste des sommets
	def sommets(self):
		if self.__liste_adj is None:
			return []
		else:
			t = self.__liste_adj.keys()
			t.sort()
			return t
  \end{lstlisting}
\end{frame}

\begin{frame}[fragile]
  \begin{lstlisting}[caption={}]
## donnele nombre de sommets d'un graphe
	def nombre_sommets(self):
		return len(self.sommets())
  \end{lstlisting}
\end{frame}

% \section{Chemins de longueur minimum}


% \subsection{Graphe pondéré}


% \subsection{Algorithme de \textsc{Dijkstra}}


% \section{Coloration}



% \section{Quelques applications}


% \subsection{Ordonnancement}



% %\subsubsection{Repr\'{e}sentation MPM}


% %\subsubsection{Repr\'{e}sentation PERT}


% \subsection{Codage de Pr\"{u}fer}


%\section{Fermeture transitive}

\end{document}
%%% Local Variables: 
%%% TeX-master: t
%%% End: 
