\chapterimage{planjap}
\chaptertext{Tout à commencé au  XVIII\up{e} siècle avec une histoire de
  ponts  résolue par  \textsc{Euler} puis  ce gadget  s'est  fait oublier
  jusque  dans  les années  1960  où on  a  enfin  découvert toutes  les
  richesses   qui   permettent  de   résoudre   de  nombreux   problèmes
  informatiquement: circuits électriques,  réseaux de transport, réseaux
  d'ordinateurs,  mise  au  point  d'un planning,  recherche  d'optimum,
  etc. 

Par exemple, vous branchez votre  GPS et donnez une destination: paf! Un
plus  court   chemin  apparaît...Déterminer  si  des   villes  sont  \og
connectables\fg{}, trouver le plus court chemin d'un point à un autre du
réseau sont des exemples de problèmes que nous allons traiter.

C'est un thème très actuel  car chaque jour ou presque naît un
  nouvel  algorithme   plus  efficace  pour  résoudre   toute  sorte  de
  problèmes.

Cependant,   le  célèbre  et   illustre  mathématicien   français  Alain
\textsc{Connes} estime que les  connaissances sur la théorie des graphes
ne forment pas une théorie mais \og un savoir, une série de faits\og{}.
}

\chapter{Graphes}


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


Voici  une vue  de l'antique  ville de  Königsberg  (aujourd'hui appelée
Kaliningrad et  située sur  l'enclave russe séparant  la Lituanie  de la
Pologne):


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




Comme  vous pouvez  le  constater sur  cette  carte datant  de 1651,  la
rivière Pregel entoure  deux îles reliées entre elles et  au reste de la
ville  par  sept  ponts.  \textsc{Euler}, entre  deux  théorèmes,  s'est
demandé s'il était possible de  se promener en traversant les sept ponts
mais sans  traverser deux fois le même  tout en revenant à  son point de
départ. 

Dans la tête d'\textsc{Euler}, la carte avait plutôt cette allure:

\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}
\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}

Les étiquettes  rectangulaires numérotent les  ponts, B correspond  à la
petite île rectangulaire, A est la rive droite, C la rive gauche et D la
seconde île.

Nous aurons besoin d'étudier les  graphes un peu plus en profondeur pour
répondre au problème (avez-vous une idée?).

Dans ce graphe, A, B, C et D sont des sommets (\textit{vertices} en anglais)
et 1, 2, 3, 4, 5, 6, et 7 sont des arêtes ou arcs (\textit{edges} en anglais).

Un  graphe n'est en  fait qu'un  ensemble de  sommets et  d'arêtes qu'on
dénote par un couple (X,A).

Le logiciel \Sage sera notre ami pour vérifier nos raisonnements. 


\sage

On  commence  par  déterminer  le  graphe, par  exemple  à  partir  d'un
dictionnaire associant à chaque sommet  la liste de ses voisins. On peut
même oublier certains voisins quand ils ont été évoqués auparavant.

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

On peut obtenir un dessin:

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



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

Répondre  au  problème  reviendra,  comme  nous le  verrons  bientôt,  à
déterminer si le graphe est eulérien. Demandons-le à \Sage:

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


Au fait, voici une vue actuelle de Kaliningrad: que deviendrait ce problème aujourd'hui?...


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


Nous distinguerons toute sorte de graphes mais il existe avant tout deux
grandes catégories: les graphes orientés et les autres. 

Le graphe précédent n'était pas orienté. Si nous étudions par exemple le
graphe du réseau internet: chaque sommet représente une page et on relie
le sommet $a$ au  sommet $b$ s'il existe un lien de  la page $a$ vers la
page $b$: ce graphe est orienté.

\begin{recherche}
Imaginer un graphe illustrant le programme suivant:

\begin{Verbatim}
L1 x:=0
L2 x:=x+1
L3 y:=2
L4 z:=y
L5 x:=x+2
L6 y:=x+z
l7 z:=4
\end{Verbatim}

\end{recherche}



En fait  un graphe  non orienté  est un graphe  orienté: chaque  arc non
orienté en  cache deux  orientés de manière  opposée. C'est  pourquoi on
appelle les  graphes non orientés  des graphes symétriques car  c'est la
\og  réunion\fg{} d'un  graphe  orienté et  de  son \og  symétrique\fg{}
relativement aux sens  de parcours. Par exemple, dans  notre problème de
pont, on peut parcourir chaque pont dans n'importe quel sens.

\medskip

Il y a d'autres distinctions: 

\begin{itemize}
\item  \textit{graphes simples}:  graphes  symétriques où  toutes  les arêtes  sont
  simples;

\item  \textit{multigraphes}:  graphes  symétriques pouvant  contenir  des
  arêtes multiples;

\item \textit{pseudographes}: multigraphes symétriques pouvant contenir des
  boucles;

\item \textit{multigraphes orientés}: on devine ce que ça désigne...

\end{itemize}





\section{Les bases}


\subsection{Graphes symétriques}

Donnons une définition qui peut s'adapter aux autres types de graphes:

\begin{definition}
Un  \textbf{graphe simple  non  orienté} est  un  couple $(X,A)$  où  $X$ est  un
ensemble quelconque et  $A$ un ensemble formé de  sous-ensembles de deux
points de $X$. 

Les éléments de $X$ sont appelés les \textbf{sommets} et ceux de $A$ les \textbf{arêtes}.
\end{definition}

Vous  aurez remarqué qu'un  graphe n'est  pas un  dessin mais  un couple
d'ensembles.

La notation  $\GR=(X,A)$ signifiera  donc que $\GR$  est un  graphe dont
l'ensemble des sommets est $X$ et l'ensemble des arêtes est $ A$.

On conviendra que $A$ peut être vide mais pas $X$.


\begin{recherche}
  Pour  rigoler,  quelle  notation   est  correcte:  $A\in  X\times  X$?
  $A\subseteq X\times X$? $A\in \PR(X\times X)$? Aucune des trois? 
\end{recherche}


On pourra noter  ${X \choose k}$ l'ensemble des  sous-ensembles de $X$ à
$k$ éléments. Ainsi $A\subseteq {X \choose 2}$.

\begin{definition}
Si $\bigl\{s,t\bigr\}$ est  une arête d'un graphe $\GR$,  on dit que les
sommets  $s$  et   $t$  sont  \textbf{adjacents}  ou  que   $s$  est  un
\textbf{voisin}   de  $t$   ou  que   l'arête   $\bigl\{s,t\bigr\}$  est
\textbf{incidente} aux  sommets $s$ et  $t$ ou que  $s$ et $t$  sont les
\textbf{extrémités} de l'arête.
\end{definition}

Par        exemple,       comment        dessiner        le       graphe
$\GR=\left(\bigl\{1,2,3,4,5\bigr\},\bigl\{\{1,2\},\{2,3\},\{3,4\},\{4,5\},\{5,1\}\bigr\}\right)$?



Demandons à \Sage:

\begin{lstlisting}[caption={}]
sage: g=Graph()
sage: g.add_vertices([1,2,3,4,5])
sage: g.add_edges([(1,2),(2,3),(3,4),(4,5),(5,1)])
sage: g.show()
\end{lstlisting}



%\begin{figure}
\begin{center}
  \includegraphics[scale=0.4]{cycle1}
\end{center}
%\end{figure}



Mais on aurait très bien pu dessiner ça:

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

ou ça:


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



Ce  sont les  représentations du  même  graphe $\GR$:  même ensemble  de
sommets, même ensemble d'arêtes.


Parfois  les dessins deviennent  compliqués mais  peuvent avoir  un intérêt
esthétique...Admirez par  exemple le  graphe complet d'ordre  23 (noté
aussi $K_{23}$ en l'honneur de C.\textsc{Kuratowski}):

\begin{lstlisting}[caption={}]
sage: h=graphs.CompleteGraph(23)
sage: h.show()
\end{lstlisting}



%\begin{figure}
\begin{center}
  \includegraphics[scale=0.4]{k23}
\end{center}
%\end{figure}




\begin{definition}
  Le  \textbf{degré} d'un sommet  d'un graphe  symétrique est  le nombre
  d'arêtes  qui  lui  sont  incidentes.  (En cas  de  boucle,  celles-ci
  comptent pour deux unités).

On note le degré du sommet $s$ $\deg_{\GR}(s)$ ou $\deg(s)$ quand il n'y
a pas d'ambiguïté.

Un sommet de degré zéro est dit \textbf{isolé}.

Un sommet de degré un est une \textbf{feuille} (on dit aussi qu'il est \textbf{pendant}).

\end{definition}



Par exemple, chaque sommet du graphe  précédent a pour degré 22. Dans le
graphe des ponts, C, A, et D ont pour degré 3 et B a pour degré 5.


\begin{definition}\label{th::som_deg}
Notons  $s_1$, $s_2$,...,$s_n$  les sommets  d'un graphe  $\GR$  dans un
ordre quelconque alors la
suite:

$$\left(\deg_{\GR}(s_1),\deg_{\GR}(s_2),...,\deg_{\GR}(s_n)\right)$$
est appelée le \textbf{score} du graphe $\GR$.
\end{definition}



L'ordre n'est  pas important.  On a cependant  l'habitude de  donner les
scores dans l'ordre croissant.

Bon,  maintenant,  on  peut  observer  la somme  des  degrés  de  chaque
sommet. Pour  le graphe du  pont on obtient  $3+3+3+5=14$...et il y  a 7
arêtes...

Pour le graphe en pentagone, $2+2+2+2+2=10$ ...et il y a 5 arêtes...


Pour $K_{23}$...euh...je vous laisse le faire.


C'est assez  immédiat: chaque arête contient deux  sommets et intervient
donc deux fois dans le calcul du degré de chacune de ses extrémités.

On en déduit le théorème suivant:


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

$$\displaystyle\sum_{s\in X}\deg_{\GR}(s)=2\times \card(X)$$
\end{theoreme}


Ainsi,  la somme  des degrés  d'un graphe  symétrique est  paire.  On en
déduit le lemme suivant:

\begin{theoreme}[Théorème des poignées de main]
  Tout graphe fini possède un nombre pair de sommets de degré impair.
\end{theoreme}

Proposez une démonstration...


\begin{definition}
 Un graphe simple est dit  \textbf{régulier} si son score est composé de
 nombres tous égaux.

Un graphe simple est dit  \textbf{\textit{n}-régulier} si son score est composé de
 nombres tous égaux à $n$.

\end{definition}

\subsection{Graphes orientés}


Quelques menus changements sont à noter: cette fois, il faut tenir compte de l'ordre.





\begin{definition}
Un  \textbf{graphe  orienté} est  un  couple $(X,A)$  où  $X$ est  un
ensemble  quelconque  et $A$  un  sous-ensemble  de  $X\times X$  appelé
ensembles des \textbf{arcs}. 

Les éléments de  $X$ sont toujours appelés les  \textbf{sommets} et ceux
de $A$ sont maintenant des \textbf{arcs} (pensez flèches).


Un  arc  $a=(s,t)$   a  pour  \textbf{origine}  le  sommet   $s$  et  pour
\textbf{extrémité} le sommet $t$.

On note $or(a)=s$ et $ext(a)=t$.

Le  sommet  $t$  est  un  \textbf{successeur}  de $s$  qui  est  lui  un
\textbf{prédécesseur} de $t$.


Un \textbf{chemin} $c$ du graphe  $\GR=(X,A)$ est une suite finie d'arcs
$a_1$, $a_2$,...,$a_n$ telle que, $\forall i, \ 1 \leqslant i \leqslant
n, \ or(a_{i+1})=ext(a_i)$. 
L'origine d'un chemin est l'origine  du premier arc et son extrémité est
l'extrémité du dernier arc.

Un chemin  est \textbf{simple}  s'il ne comporte  pas plusieurs  fois le
même arc et  il est \textbf{élémentaire} s'il ne rencontre pas plusieurs
fois le même sommet.


La \textbf{longueur} d'un chemin est son nombre d'arcs. 

Un chemin tel que $or(c)=ext(c)$ est appelé un \textbf{circuit}.
\end{definition}





\begin{center}
\begin{tikzpicture}
\SetGraphUnit{2}
\Vertex{a}
\EA(a){b}
\EA(b){c}
\SO(a){e}
\SO(b){d}
\SetUpEdge[style={->}]
\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,->}](a)
\Loop[dist=1cm,dir=SO,style={thick,->}](e)
\end{tikzpicture}

\end{center}


\begin{definition}
Soit  $\GR=(X,A)$  un graphe  orienté.  Le  \textbf{degré d'entrée}  (ou
\textbf{demi-degré intérieur}) d'un
sommet $s$  est noté $\deg_{\GR}^-(s)$  et correspond au  nombre d'arêtes
dont $s$ est l'extrémité.

Le \textbf{degré de sortie} (ou \textbf{demi-degré extérieur}) d'un
sommet $s$  est noté $\deg_{\GR}^+(s)$  et correspond au  nombre d'arêtes
dont $s$ est l'origine.
\end{definition}

Amusez-vous avec le graphe représenté précédemment.




À  partir  du  théorème  \vref{th::som_deg}, on  obtient  le  corollaire
suivant:

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

$$\displaystyle\sum_{s\in X}\deg_{\GR}^-(s)+\sum_{s\in X}\deg_{\GR}^+(s)=\card(X)$$
\end{theoreme}



Parfois, le fait  qu'un graphe soit orienté ou  non n'est pas important:
on travaille alors avec le \textbf{graphe symétrique sous-jacent} obtenu
en remplaçant les arcs par des arêtes...




\begin{definition}
On dit que $x_{k}$ est un \textbf{descendant} du sommet $x_{i}$ si, et
seulement si, il existe un chemin d'origine $x_{i}$ et d'ext\'{e}mit\'{e} $%
x_{k}$ ; on dit aussi que $x_{k}$ est \textbf{accessible} \`{a} partir de $x_{i}$. Le
sommet $x_{i}$ est alors un \textbf{ascendant} ou un anc\^{e}tre du sommet $x_{k}.$
\end{definition}

Comme le graphe $\GR $ n'est rien d'autre qu'une
relation binaire et, comme un descendant de $x_{i}$ est un suivant d'un
suivant $\ldots $ d'un suivant de $x_{i},$ les suivants de $x_{i}$ sont les 
\'{e}l\'{e}ments de $\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) $ puisque nous savons que $\GR
^{+}=\displaystyle\bigcup\limits_{i=1}^{n}\GR ^{i}$ pour toute relation binaire sur
un ensemble poss\'{e}dant $n$ \'{e}l\'{e}ments. De m\^{e}me, un \textbf{%
ascendant} de $x_{i}$ est un pr\'{e}c\'{e}dent d'un pr\'{e}c\'{e}dent
\ldots\ d'un pr\'{e}c\'{e}dent de $x_{i},$ l'ensemble des pr\'{e}c\'{e}dents
de $x_{i}$ est donc $\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) ,$ ensemble que nous notons $\GR ^{-}\left(
\left\{ x_{i}\right\} \right) .$

Par exemple, considérons ce graphe:

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

Le sommet $1$ n'a pas de descendant, $\GR ^{+}\left( \left\{ 1\right\}
\right) =\emptyset .$ Ses ascendants sont tous les autres sommets, $\GR
^{-}\left( \left\{ 1\right\} \right) =\left\{ 2,3,4,5\right\} .$ Pour ce qui
concerne les descendants et les ascendants du sommet 5, on a%
$$
\GR ^{+}\left( \left\{ 5\right\} \right) =\left\{ 1,2,3,4\right\} \text{
et }\GR ^{-}\left( \left\{ 5\right\} \right) =\emptyset
$$









\subsection{Quelques graphes simples particuliers}


\begin{definition}
Le \textbf{graphe complet} $K_n$ est tel que $X=\{1,2,...,n\}$ et $A={X
  \choose 2}$:

\end{definition}


\multido{\i=1+1}{5}{%
\includegraphics[width=0.19\linewidth]{k\i}
}




\begin{definition}
Le \textbf{cycle élémentaire} $C_n$ est tel que $X=\{1,2,...,n\}$ et $A=\bigl\{\{1,2\},\{2,3\},...,\{n,1\}\bigr\}$:

\end{definition}




\multido{\i=1+1}{5}{%
\includegraphics[width=0.19\linewidth]{C\i}
}




\begin{definition}
La   \textbf{roue}   $W_n$    est   telle   que   $X=\{0,1,2,...,n\}$   et
$A=\bigl\{\{1,2\},\{2,3\},...,\{n,1\}\bigr\}\cup \bigl\{\{0,1\},\{0,2\},...,\{0,n\}\bigr\}$:
\end{definition}





\multido{\i=1+1}{5}{%
\includegraphics[width=0.19\linewidth]{W\i}
}


\begin{definition}
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.
\end{definition}


Attention! Il y a un piège dans $Q_3$...




\multido{\i=1+1}{5}{%
\includegraphics[width=0.19\linewidth]{Q\i}
}




Avant d'introduire notre prochain candidat, un peu de vocabulaire:

\begin{definition}[Graphe biparti]
Un  graphe $\GR=(X,A)$  est  biparti si  $X$  peut être  divisé en  deux
ensembles disjoints $X_1$ et $X_2$ de  sorte que chaque arête de A relie
un sommet de $X_1$ et un sommet de $X_2$.

Ainsi $A\subseteq \bigl\{\{x_1,x_2\}, x_1\in X_1, x_2\in X_2\bigr\}$.
\end{definition}


Ce qui nous permet d'agrandir notre famille:


\begin{definition}
Le   \textbf{graphe    biparti   complet}   $K_{m,n}$    est   tel   que
$X=\bigl\{x_1,x_2,...,x_n\bigr\}\cup   \bigl\{y_1,y_2,...,y_m\bigr\}$  et
$A=\bigl\{\{x_i,y_j\}\mid i\in\{1,2,..,n\}, j\in\{1,2,..,m\}\bigr\}$
\end{definition}

Qui est qui?




\multido{\i=0+1}{5}{%
\includegraphics[width=0.19\linewidth]{WW\i}
}





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


\begin{definition}
  Soit $\GR=(X,A)$ et $\GR'=(X',A')$ deux graphes.

On dit  que $\GR$ est  un \textbf{sous-graphe} de $\GR'$  si $X\subseteq
X'$ et $A=A' \cap {X \choose 2}$.

On  dit que  $\GR$  est  un \textbf{sous-graphe  partiel}  de $\GR'$  si
$X'\subseteq X$ et $A\subseteq A'$.

On  dit que  $\GR$  est  un \textbf{graphe  partiel}  de $\GR'$  si
 $A\subseteq A'$.

\end{definition}


Ah,  ça  devient  subtil.  En  fait non!  Concrètement,  on  obtient  un
sous-graphe à partir d'un graphe donné en supprimant certains sommets et
les arêtes qui les contenaient.

On  fait  de même  avec  un sous-graphe  partiel,  mais  on peut  enlever
quelques arêtes en plus.

Un graphe partiel contient les  mêmes sommets que le graphe initial mais
a des arêtes en moins.


Un sous-graphe et deux sous-graphes partiels en gras se cachent dans les dessins
suivant:


\begin{center}
\begin{tikzpicture}
%\SetGraphColor{yellow}{blue}{maagenta}
\SetGraphUnit{1.5}
\SetVertexNoLabel
\Vertices{circle}{A,B,C,D,E}
\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}
\Edges(A,B,C,D,E,A,C,E,B,D)
\SetUpEdge[lw=4pt]
\Edges(B,D,E)
\end{tikzpicture}
\begin{tikzpicture}
%\SetGraphColor{yellow}{blue}{maagenta}
\SetGraphUnit{1.5}
\SetVertexNoLabel
\Vertices{circle}{A,B,C,D,E}
\Edges(A,B,C,D,E,A,C,E,B,D)
\SetUpEdge[lw=4pt]
\Edges(B,D,E,B)
\end{tikzpicture}
\end{center}



Au lieu d'extraire, on peut combiner des graphes:

\begin{definition}
La   réunion  de   deux  graphes   simples  $   \GR_1=(X_1,A_1)$   et  $
\GR_2=(X_2,A_2)$   est  le   graphe  simple   $  \GR_1\cup\GR_2=(X_1\cup
X_2,A_1\cup A_2)$ 
\end{definition}


Voici deux graphes et leur réunion:


\begin{tikzpicture} \SetGraphUnit{1.25}
\Vertex{E}
\NOWE(E){D}
\NOEA(E){B}
\NOEA(D){A}
\SOEA(B){C}
%\EA(E){F}
\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}
\Edges(A,B,C,F,B,D)
\end{tikzpicture}
\begin{tikzpicture} \SetGraphUnit{1.25}
%\GraphInit[vstyle=Classic]
\Vertex{E}
\NOWE(E){D}
\NOEA(E){B}
\NOEA(D){A}
\SOEA(B){C}
\SOEA(B){C}
\SOEA(E){F}
\Edges(D,E,B,D,A,B,C,E,B,F,C)
\end{tikzpicture}


\begin{definition}
Le complémentaire $\overline{\GR}$ d'un graphe simple $\GR$ a les mêmes
sommets que $\GR$ mais deux sommets sont adjacents dans $\overline{\GR}$
si, et seulement si, ils ne le sont pas dans $\GR$.
\end{definition}


\begin{tikzpicture} \SetGraphUnit{1.25}
\Vertex{E}
\NOWE(E){D}
\NOEA(E){B}
\NOEA(D){A}
\SOEA(B){C}
%\EA(E){F}
\Edges(E,C,B,A,D,E,B)
\end{tikzpicture}
\hfill
\begin{tikzpicture} \SetGraphUnit{1.25}
\Vertex{E}
\NOWE(E){D}
\NOEA(E){B}
\NOEA(D){A}
\WE(A){C}
%\EA(E){F}
\Edge(E)(A)
\Edge(D)(B)
\Edge(C)(A)
\Edge(C)(D)
\end{tikzpicture}




\subsection{Matrices d'adjacence}


Nous avons vu que nous pouvons  représenter un graphe par un dessin mais
ça ne  dit rien  à un ordinateur.  Sur \Sage,  on peut entrer  un graphe
comme un dictionnaire ou en entrant  la liste de ses sommets et la liste
de ses arêtes.

Pour  simplifier les  calculs, il  va s'avérer  efficace  d'utiliser des
matrices en s'inspirant de ce qui avait été fait pour les relations binaires.


Reprenons par exemple un des graphes vus précédemment.

\medskip

\begin{minipage}[t]{0.5\linewidth}
  \begin{tikzpicture} \SetGraphUnit{1.75}
\Vertex{E}
\NOWE(E){D}
\NOEA(E){B}
\NOEA(D){A}
\SOEA(B){C}
%\EA(E){F}
\Edges(E,C,B,A,D,E,B)
\end{tikzpicture}
\end{minipage}\hspace{0.5cm}
\begin{minipage}[t]{0.45\linewidth}\vspace{-4.3cm}
  \hspace{5.5cm} 
  \begin{flushright}
    \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{flushright}
\end{minipage}


\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}


Dans l'exemple précédent, avec l'ordre alphabétique, cela donne:

$$
M=
\begin{pmatrix}
0&1&0&1&0\\
1&0&1&0&1\\
0&1&0&0&1\\
1&0&0&0&1\\
0&1&1&1&0\\
\end{pmatrix}
$$

Dans le cas d'un graphe simple, la matrice est symétrique et n'a que des
zéros sur la diagonale.


\begin{NB}
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{NB}






















\section{Parcours de graphes}

On peut être amené à déterminer les plus courts chemins, des composantes
connexes, etc.

On aura donc souvent besoin de parcourir un graphe.


\subsection{Algorithme général}


Le  principe  est  le suivant:  on  sélectionne  un  sommet, on  le  \og
traite\fg{}: on détermine ses voisins.


Par exemple:



\begin{algo}
\FORGEN{tout $x\in X$}
\STATE{etat[$x$] \recoit{} non\_atteint}
\ENDFOR
\STATE{T\recoit{}$\emptyset$}
\STATE{à\_traiter\recoit{} $\emptyset$}
\FORGEN{ tout $x\in X$}
\IF{etat[$ x$]=non\_atteint}
\STATE{à\_traiter\recoit{}à\_traiter $ \cup \bigl\{x\bigr\}$}
\STATE{etat[$ x$]\recoit{}atteint}
\WHILE{à\_traiter $ \neq \emptyset$}
\STATE{$ y$\recoit{}choix(à\_traiter)}
\STATE{à\_traiter\recoit{}à\_traiter$ \backslash \bigl\{y\bigr\}$}
\FORGEN{tout $z$ voisin de $y$}
\IF{etat[$ z$] = non\_atteint}
\STATE{T\recoit{}$ T\cup \bigl\{(y,z)\bigr\}$}
\STATE{etat[$ z$]\recoit{}atteint}
\STATE{à\_traiter\recoit{}à\_traiter$ \cup \bigl\{z\bigr\}$}
\ENDIF
\ENDFOR
\STATE{etat[$ y$]\recoit{}examine}
\ENDWHILE
\ENDIF
\ENDFOR
\end{algo}



Cet  algorithme demeure  cependant un  peu  trop général,  surtout à  un
moment précis: où?....


\subsection{Parcours en largeur}

Le critère de  choix sera le fait qu'un sommet  atteint sera toujours un
sommet  examiné, c'est-à-dire que  la variable  \texttt{à\_traiter} sera
une file (vous savez, \og First In First Out\fg{}, comme au RU).

Ensuite,  on numérotera  les sommets  et on  les parcourra  dans l'ordre
croissant.

Lorsque l'on fait un parcours en largeur à partir d'un sommet
voisins de $x$,
on atteint d'abord les voisins,
ensuite les voisins des voisins (sauf ceux qui sont déjà atteints) et ainsi de suite.
C'est pourquoi le parcours en largeur est aussi appelé
parcours concentrique. Il sert notamment
à le recherche des plus courts chemins dans un graphe. 






Voyons d'abord un EXEMPLE:






\begin{center}
  \begin{tikzpicture}
\SetGraphUnit{1.5}
\tikzset{EdgeStyle/.style={->}}
\Vertex{1}
\SOEA(1){3}
\NOEA(3){2}
\SOEA(3){4}
\SOWE(3){5}
\SO(5){7}
\SO(4){8}
\SOEA(7){6}
\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}](6)(8)
\Edge[style={bend right}](1)(4)
\end{tikzpicture}
\end{center}



\begin{itemize}
\item on commence donc par regarder 1 et ses voisins 2, 4 et 5;
\item on regarde le plus petit voisin de 1 qui est 2;
\item on  regarde les voisins  de 2 qui  sont 3 et 4  mais 4 a  déjà été
  regardé donc on ne tient pas compte de l'arc (2,4);
\item le sommet suivant est 4. Son seul voisin est 3 qui a déjà été vu;
\item le sommet suivant est 5. Son seul voisin est 4, qui a déjà été vu;
\item le  sommet suivant  est 3.  Le seul voisin  est 1  qui a  déjà été
  traité;
\item  la file  est maintenant  vide. On  remonte donc  maintenant  à un
  sommet non encore atteint dans l'ordre des numéros croissant;
\item il s'agit donc du sommet 6 dont les voisins sont 7 et 8;
\item on traite 7 dont le seul voisin est 5 qui a déjà été traité;
\item on traite 8 dont les voisins 4, 6 et 7 ont tous été déjà traités;
\item la file est maintenant vide et tous les sommets ont été traités.
\end{itemize}




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


Passons à  l'algorithme. On a besoin  de traiter une  file qu'on nommera
\texttt{à\_traiter}   et   qui    permet   d'effectuer   deux   actions:
\texttt{AjouterEnQueue} et \texttt{EnleverTete}.

\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$}
\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}





Comment peut-on utiliser cet  algorithme pour déterminer les composantes
connexes  du graphe?  Pour  chercher  un plus  court  chemin entre  deux
sommets?


\subsection{Parcours en profondeur}


Contrairement au parcours en largeur, lorsque l'on fait un parcours en profondeur à partir
d'un sommet
$x$,
on tente d'avancer le plus loin possible dans le graphe, et ce n'est que lorsque
toutes les possibilités de progression sont bloquées que l'on revient (étape de backtrack) pour
explorer un nouveau chemin ou une nouvelle chaîne. 

Le parcours en profondeur correspond
aussi à l'exploration d'un labyrinthe. 

Les applications de ce parcours sont peut-être moins évidentes que pour le parcours en
largeur, mais le parcours en profondeur permet de résoudre efficacement des problèmes plus
difficiles comme la recherche de composantes fortement connexes dans un graphe orienté.

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).



Reprenons l'exemple précédent:

\begin{itemize}
\item on commence par 1;
\item on visite ensuite un voisin de 1: 2;
\item on visite ensuite un voisin de 2: 3;
\item on est alors bloqué. On revient  à 2 et on visite son autre voisin
  4;
\item  on est  bloqué et  on revient  à 1  et on  visite le  seul voisin
  restant, 5;
\item on est bloqué. Il faut prendre un nouveau sommet: 6;
\item on visite 7, voisin de 6 et on est bloqué;
\item on retourne à 6 et on visite le seul voisin restant, 8 et c'est terminé.
\end{itemize}

Tracer \og l'arbre des visites\fg{}, la pile correspondant et les patate
des sommets visités.


Voici un exemple d'algorithme qui est composé de deux parties.


\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}


L'algorithme principal:

\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}









\section{Fermeture transitive}



$\GR =\left( X,A\right) $ \'{e}tant une relation binaire, nous savons que
la fermeture transitive de $\GR $ est la relation $\GR
^{+}=\displaystyle\bigcup  \limits_{i=1}^{n}\GR ^{i}$ (la fermeture transitive et r\'{e}%
flexive de $\GR $ est donn\'{e}e par $\GR ^{\ast
}=\displaystyle\bigcup  \limits_{i=0}^{n-1}\GR ^{i})$ c'est la plus petite relation
transitive contenant $\GR $ (rappelons-nous encore qu'une relation
binaire est assimil\'{e}e \`{a} un ensemble). 

Nous savons aussi que la
matrice bool\'{e}enne de $\GR ^{\ast }$ est $\displaystyle\sum \limits_{k=0}^{n-1}M^{k}
$ et que son calcul effectif peut \^{e}tre laborieux (mais on a \Sage...). 


L'autre m\'{e}thode
est la suivante :


\begin{theoreme}
 Nous notons $M_{0}$ la matrice bool\'{e}enne de $\GR $
et $\theta _{i}$ l'op\'{e}rateur qui consiste \`{a} ajouter, au sens de
l'addition bool\'{e}enne, la $i^{\grave{e}me}$ ligne de $M_{i-1}$ \`{a}
toute ligne de $M_{i-1}$ poss\'{e}dant un $1$ en colonne num\'{e}ro $i$ ; le
r\'{e}sultat se notant $M_{i}=\theta _{i}\left( M_{i-1}\right) .$ La matrice 
$M_{n}$ donne alors la matrice de la fermeture transitive de $\GR .$
\end{theoreme}





Si nous notons $M=\left( m_{i,j}\right) $ la matrice carr\'{e}e bool\'{e}%
enne d'ordre $n$ de $\Gamma ,$ l'algo se traduit par :



La d\'{e}monstration est un peu compliquée...

% L'op\'{e}rateur $\theta _{x_{i}}$ revient \`{a} ajouter (si besoin) \`{a} $%
% A$ les arcs $\left( x_{j},x_{k}\right) $ si $\left( x_{j},x_{i}\right) $ et $%
% \left( x_{i},x_{k}\right) $ sont des arcs de $A.$ Si $B$ est un ensemble
% d'arcs, nous notons 
% $$
% \theta _{x_{i}}\left( B\right) =B\cup \left\{ \left( x_{j},x_{k}\right) \mid
% \left( x_{j},x_{i}\right) \text{ et }\left( x_{i},x_{k}\right) \in B\right\} 
% $$%
% On remarque imm\'{e}diatement que $A\subseteq \theta _{x_{i}}\left( A\right) 
% $ et que $\theta _{x_{i}}$ ne cr\'{e}e pas de nouveaux arcs du type $\left(
% u,x_{i}\right) $ ou $\left( x_{i},v\right) $.

% \begin{itemize}
% \item D\'{e}montrons que $\theta _{x_{i}}\left( \theta _{x_{i}}\left(
% A\right) \right) =\theta _{x_{i}}\left( A\right) $ : la remarque que nous
% venons de faire nous donne $\theta _{x_{i}}\left( A\right) \subseteq \theta
% _{x_{i}}\left( \theta _{x_{i}}\left( A\right) \right) .$ Si $\left(
% u,v\right) \in \theta _{x_{i}}\left( \theta _{x_{i}}\left( A\right) \right) $
% cela signifie que soit $\left( u,v\right) \in \theta _{x_{i}}\left( A\right) 
% $ soit $\left( u,x_{i}\right) \in \theta _{x_{i}}\left( A\right) $ et $%
% \left( x_{i},v\right) \in \theta _{x_{i}}\left( A\right) $ par d\'{e}%
% finition de $\theta _{x_{i}}.$ Or%
% \begin{eqnarray*}
% \left( u,x_{i}\right) &\in &\theta _{x_{i}}\left( A\right) \Rightarrow
% \left( u,x_{i}\right) \in A\text{ et} \\
% \left( x_{i},v\right) &\in &\theta _{x_{i}}\left( A\right) \Rightarrow
% \left( x_{i},v\right) \in A
% \end{eqnarray*}%
% par cons\'{e}quent $\left( u,v\right) \in \theta _{x_{i}}\left( A\right) .$
% Nous venons de prouver que%
% $$
% \theta _{x_{i}}\left( \theta _{x_{i}}\left( A\right) \right) \subseteq
% \theta _{x_{i}}\left( A\right) 
% $$%
% ce qui ach\`{e}ve la d\'{e}monstration.

% \item D\'{e}montrons que $\forall \left( x,y\right) \in E\times E,\theta
% _{x}\left( \theta _{y}\left( A\right) \right) =\theta _{y}\left( \theta
% _{x}\left( A\right) \right) .$ Consid\'{e}rons pour cela $\left( u,v\right)
% \in \theta _{x}\left( \theta _{y}\left( A\right) \right) .$ Nous avons

% \begin{itemize}
% \item soit $\left( u,v\right) \in \theta _{y}\left( A\right) $ et comme $%
% \theta _{x}\left( A\right) $ contient $A,$ il est s\^{u}r que $\left(
% u,v\right) \in \theta _{y}\left( \theta _{x}\left( A\right) \right) $ ;

% \item soit $\left( u,x\right) $ et $\left( x,v\right) $ sont des \'{e}l\'{e}%
% ments de $\theta _{y}\left( A\right) .$ Diff\'{e}rents cas peuvent se pr\'{e}%
% senter : $\left( u,x\right) \in A$ et $\left( x,v\right) \notin A$ ou $%
% \left( u,x\right) \notin A$ et $\left( x,v\right) \in A$ ou etc ...
% Examinons le cas $\left( u,x\right) \in A$ et $\left( x,v\right) \notin A,$
% puisque $\left( u,x\right) \in A$ on a $\left( u,x\right) \in \theta
% _{x}\left( A\right) .$ Comme $\left( x,v\right) \notin A$ et $\left(
% x,v\right) \in \theta _{y}\left( A\right) $ on en d\'{e}duit que $\left(
% x,y\right) $ et $\left( y,v\right) $ sont des \'{e}l\'{e}ments de $A$ et
% donc de $\theta _{x}\left( A\right) $ ; $\left( u,x\right) $ et $\left(
% x,y\right) $ appartenant \`{a} $A$ on a alors $\left( u,y\right) \in \theta
% _{x}\left( A\right) $ et comme $\left( y,v\right) \in \theta _{x}\left(
% A\right) $ on conclut $\left( u,v\right) \in \theta _{y}\left( \theta
% _{x}\left( A\right) \right) .$ Les autres cas se traitant de fa\c{c}on
% similaire nous prouvent alors que $\theta _{x}\left( \theta _{y}\left(
% A\right) \right) \subseteq \theta _{y}\left( \theta _{x}\left( A\right)
% \right) .$ Comme $x$ et $y$ jouent des r\^{o}les sym\'{e}triques, la double
% inclusion est acquise et $\theta _{x}\left( \theta _{y}\left( A\right)
% \right) =\theta _{y}\left( \theta _{x}\left( A\right) \right) .$
% \end{itemize}

% \item Notons $A^{+}$ le graphe de la fermeture transitive de $\GR $ et d%
% \'{e}montrons que 
% $$
% A^{+}=\theta _{x_{n}}\left( \theta _{x_{n-1}}\left( \cdots \left( \theta
% _{x_{1}}\left( A\right) \right) \cdots \right) \right) 
% $$%
% Il nous faut d\'{e}montrer une double inclusion, l'inclusion 
% $$
% \theta _{x_{n}}\left( \theta _{x_{n-1}}\left( \cdots \left( \theta
% _{x_{1}}\left( A\right) \right) \cdots \right) \right) \subseteq A^{+} 
% $$%
% est claire, il est s\^{u}r que pour obtenir la fermeture transitive de $%
% \GR ,$ il est n\'{e}cessaire d'appliquer tous les op\'{e}rateurs $\theta
% _{x_{i}}.$ Si $\left( x,y\right) \in A^{+},$ c'est qu'il existe un chemin de 
% $x$ \`{a} $y$ empruntant des arcs de $A$ :

% \begin{itemize}
% \item si $\left( x,y\right) \in A$ alors $\left( x,y\right) \in \theta
% _{x_{n}}\left( \theta _{x_{n-1}}\left( \cdots \left( \theta _{x_{1}}\left(
% A\right) \right) \cdots \right) \right) $ qui contient $A$ ;

% \item si $\left( x,y\right) \notin A,$ le chemin est

% \begin{itemize}
% \item soit du type $\left( x,u_{1},y\right) $ et donc $\left( x,y\right) \in
% \theta _{u_{1}}\left( A\right) ,$

% \item soit du type $\left( x,u_{1},u_{2},y\right) ,$ dans ce cas nous avons 
% $$
% \left( x,u_{1}\right) ,\left( u_{1},u_{2}\right) \text{ et }\left(
% u_{2},y\right) 
% $$%
% qui sont des \'{e}l\'{e}ments de $A$ et on en d\'{e}duit $\left(
% u_{1},y\right) \in \theta _{u_{2}}\left( A\right) $ et $\left(
% x,u_{1}\right) \in \theta _{u_{2}}\left( A\right) $ soit $\left( x,y\right)
% \in \theta _{u_{1}}\left( \theta _{u_{2}}\left( A\right) \right) $ ;

% \item soit du type $\left( x,u_{1},u_{2},\ldots ,u_{p},y\right) $ et en
% reprenant le raisonnement pr\'{e}c\'{e}dent on obtient 
% $$
% \left( x,y\right) \in \theta _{u_{1}}\left( \theta _{u_{2}}\left( \cdots
% \left( \theta _{u_{p}}\left( A\right) \right) \cdots \right) \right) 
% $$
% \end{itemize}

% \item Pour terminer, on remarque que $\theta _{u_{1}}\left( \theta
% _{u_{2}}\left( \cdots \left( \theta _{u_{p}}\left( A\right) \right) \cdots
% \right) \right) $ peut s'\'{e}crire en permutant \`{a} loisir les $\theta
% _{u_{i}}$ et comme $\theta _{u_{i}}\left( \theta _{u_{i}}\left( B\right)
% \right) =\theta _{u_{i}}\left( B\right) $ et que $B\subseteq \theta
% _{u_{i}}\left( B\right) $ il est s\^{u}r que 
% $$
% \theta _{u_{1}}\left( \theta _{u_{2}}\left( \cdots \left( \theta
% _{u_{p}}\left( A\right) \right) \cdots \right) \right) \subseteq \theta
% _{x_{n}}\left( \theta _{x_{n-1}}\left( \cdots \left( \theta _{x_{1}}\left(
% A\right) \right) \cdots \right) \right) 
% $$%
% Conclusion $\left( x,y\right) \in \theta _{x_{n}}\left( \theta
% _{x_{n-1}}\left( \cdots \left( \theta _{x_{1}}\left( A\right) \right) \cdots
% \right) \right) .$
% \end{itemize}
% \end{itemize}


% OUF!

% \medskip

Consid\'{e}rons par exemple le graphe $\GR $ d\'{e}fini par:




\begin{center}
  \begin{tikzpicture}
\SetGraphUnit{1.5}
\tikzset{EdgeStyle/.style={->}}
\Vertices{circle}{3,2,1,5,4}
\Edges(3,4,2)
\Edge[style={bend left}](1)(2)
\Edge[style={bend left}](2)(1)
\Edges(3,5)
\Loop[dist=1cm,dir=WE](1)
\end{tikzpicture}
\end{center}




Sa matrice d'incidence est $M=M_{0}=\left( 
\begin{array}{ccccc}
1 & 1 & 0 & 0 & 0 \\ 
1 & 0 & 0 & 0 & 0 \\ 
0 & 0 & 0 & 1 & 1 \\ 
0 & 1 & 0 & 0 & 0 \\ 
0 & 0 & 0 & 0 & 0%
\end{array}%
\right) $, \vspace{0.2cm}appliquons $\theta _{1},$ nous allons ajouter (au
sens bool\'{e}en) la ligne num\'{e}ro 1 sur toute ligne poss\'{e}dant un 1
en colonne num\'{e}ro 1, seule la deuxi\`{e}me ligne est concern\'{e}e%
\vspace{0.2cm}, on obtient $M_{1}=\theta _{1}\left( M_{0}\right) =\overset{}{%
\left( 
\begin{array}{ccccc}
1 & 1 & 0 & 0 & 0 \\ 
1 & \mathbf{1} & 0 & 0 & 0 \\ 
0 & 0 & 0 & 1 & 1 \\ 
0 & 1 & 0 & 0 & 0 \\ 
0 & 0 & 0 & 0 & 0%
\end{array}%
\right) }.$ Appliquons \vspace{0.2cm}maintenant $\theta _{2}$ \`{a} $M_{1},$
nous allons ajouter la ligne num\'{e}ro 2 \`{a} toute ligne poss\'{e}dant un
1 en colonne num\'{e}ro 2, les lignes 1, 2 et 4 sont concern\'{e}es\footnote{%
Ajouter (en calcul bool\'{e}en) la ligne num\'{e}ro $i$ \`{a} la ligne num%
\'{e}ro $i$ ne la modifie pas.}. Nous obtenons $\theta _{2}\left(
M_{1}\right) =\left( 
\begin{array}{ccccc}
1 & 1 & 0 & 0 & 0 \\ 
1 & 1 & 0 & 0 & 0 \\ 
0 & 0 & 0 & 1 & 1 \\ 
\mathbf{1} & 1 & 0 & 0 & 0 \\ 
0 & 0 & 0 & 0 & 0%
\end{array}%
\right) .$ Aucune ligne n'a de 1 en colonne 3, donc $\theta _{3}\left(
M_{2}\right) =M_{3}=M_{2}.$ La ligne 3 a un 1 en colonne 4\vspace{0.2cm}, $%
\theta _{4}\left( M_{3}\right) =\left( 
\begin{array}{ccccc}
1 & 1 & 0 & 0 & 0 \\ 
1 & 1 & 0 & 0 & 0 \\ 
\mathbf{1} & \mathbf{1} & 0 & 1 & 1 \\ 
1 & 1 & 0 & 0 & 0 \\ 
0 & 0 & 0 & 0 & 0%
\end{array}%
\right) =M_{4}$ et $\theta _{5}$ ne changeant rien, la matrice de la
fermeture transitive est $M_{5}=\overset{\text{ }}{\left( 
\begin{array}{ccccc}
1 & 1 & 0 & 0 & 0 \\ 
1 & 1 & 0 & 0 & 0 \\ 
1 & 1 & 0 & 1 & 1 \\ 
1 & 1 & 0 & 0 & 0 \\ 
0 & 0 & 0 & 0 & 0%
\end{array}%
\right) }$ qui nous donne le graphe de la fermeture transitive de $\GR .$%



\begin{center}
  \begin{tikzpicture}
\SetGraphUnit{1.5}
\tikzset{EdgeStyle/.style={->}}
\Vertices{circle}{3,2,1,5,4}
\Edges(3,4,1)
\Edges(3,5)
\Edges(3,1)
\Edge(3)(2)
\Edge(4)(2)
\Edge[style={bend left}](1)(2)
\Edge[style={bend left}](2)(1)
\Loop[dist=1cm,dir=WE](1)
\Loop[dist=1cm,dir=EA](2)
\end{tikzpicture}
\end{center}




\begin{remarque}
Si on s'interdit les boucles, il suffit, apr\`{e}s avoir d\'{e}termin\'{e}
la fermeture transitive, de les supprimer.
\end{remarque}













\section{Isomorphisme de graphes}


Nous  avons observé  que  l'ordre des  sommets,  leurs noms,  pouvaient
varier au moment de représenter un graphe.

Imaginez un  graphe représenté à l'aide  de fils en pâte  à modeler dont
les  sommets ne  sont pas  nommés. Vous  placez des  étiquettes  sur les
sommets,  vous prenez  une photo,  vous enlevez  les étiquettes  puis vous
déformez les arêtes  sans les casser et vous  renommez aléatoirement les
sommets.

Les deux  graphes obtenus auront beaucoup de  propriétés communes. Comme
ils ont été construits avec  la même structure (le même \og corps\fg{}),
on dit qu'ils sont \textit{isomorphes} (puisque  vous avez  étudié  le Grec  ancien,
  vous avez reconnu les racines $ i \sigma o \varsigma$ qui signifie \og
  le même\fg{} et  $\mu o \rho \varphi o \varsigma$  qui signifie \og le
  corps\fg{}...).

Donnons une définition plus formelle:

\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}


Un  isomorphisme  conserve  donc  \og l'adjacence\fg{}  des  sommets  et
conserve donc les degrés.

Montrez par exemple que les graphes suivants sont isomorphes:




\begin{center}
\begin{tikzpicture}
\SetGraphUnit{1.5}
\Vertices{circle}{A,B,C,D,E,F}
\Edges(A,B,C,D,E,F,A)
\Edge(A)(D)
\Edge(B)(E)
\Edge[style={bend left}](C)(F)
\end{tikzpicture}
\hspace{3cm}
\begin{tikzpicture}
\SetGraphUnit{1.75}
\Vertex{1}
\EA(1){2}
\NO(1){4}
\EA(2){3}
\NO(2){5}
\NO(3){6}
\Edges(1,6,3,4,1,5,3,4,2,6)
\Edge(5)(2)
\end{tikzpicture}
\end{center}


Cela peut parfois devenir plus subtil.

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}
\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}
\Edges(w,z,y,x,w,s,t,u,v,z)
\Edge(v)(s)
\end{tikzpicture}
\end{center}

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.



\begin{DANGER}
Il ne faut pas confondre bijection et isomorphisme!

Trouver une bijection entre les  sommets, ce n'est pas forcément trouver
un isomorphisme.

Si  on a  une bijection  \og  candidate\fg{}, on  peut vérifier  qu'elle
convient en comparant les matrices d'adjacence.
\end{DANGER}





Il est paradoxal de remarquer qu'on ne connaît pas d'algorithme efficace
pour reconnaître  si deux graphes sont  isomorphes (on ne  sait même pas
si c'est envisageable) alors que le problème
paraît facile a priori. 

Cependant  \Sage, par  exemple,  peut  vous aider  pour  des graphes  de
taille raisonnable:

\begin{lstlisting}[caption={}]
sage: K = graphs.KneserGraph(5,2)
sage: P = graphs.PetersenGraph()
sage: K.is_isomorphic(P)
True
\end{lstlisting}

Et voici leurs têtes:

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

\begin{center}
\includegraphics[scale=0.4]{Kiso}
\includegraphics[scale=0.4]{Piso}
\end{center}

\section{Connexité}


\subsection{Chaînes et chemins}


Nous  avons déjà  parlé de  chemins au  sujet des  graphes  orientés. Le
pendant    pour   les   graphes    symétriques   est    parfois   appelé
\textit{chaîne}.  


\begin{definition}\label{def::chemin}
Soit $\GR=(X,A)$  un graphe non  orienté. Une \textbf{chaîne  de longueur
  \textit{n}}  de $s$ à  $t$ dans  $\GR$ est  une suite  d'arêtes $a_1$,
$a_2$,...,$a_n$   de    $\GR$   telle   que   $a_1=\bigl\{s,x_1\bigr\}$,
$a_2=\bigl\{x_1,x_2\bigr\}$,...,$a_n=\bigl\{x_{n-1,t}\bigr\}$.


Si le graphe est simple, on  peut juste donner la suite des sommets $s$,
$x_1$,...,$x_{n-1}$, $t$.

La chaîne est \textbf{fermée} si elle commence là où elle se termine et
que sa longueur est non nulle.

On dit que le chaîne \textbf{passe} par les sommets $x_i$.

Un chaîne est \textbf{élémentaire} si elle ne passe qu'une fois par un même
sommet et \textbf{simple} si elle n'utilise pas deux fois la même arête.

La chaîne est un \textbf{cycle} si elle est fermée et simple.

\end{definition}



On peut comptabiliser toutes les chaînes élémentaires allant d'un sommet à un autre à
l'aide d'un arbre.

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}
\Edges(4,3,2,4,1,5,0,1,2,4,5)
  \end{tikzpicture}
\end{center}


Décomposons les chaînes simples:

\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}

Il y  a donc treize  chaînes simples  qui vont de  0 jusqu'à 3.  Les plus
courtes chaînes ont pour longueur 3 et sont au nombre de 3.



\begin{recherche}
Cela permet d'avoir une première  idée d'algorithme pour trouver la plus
courte chaîne d'un point à un autre: lequel? Avantages? Inconvénients?
\end{recherche}


\begin{NB}
On  peut montrer  que l'existence  d'un  cycle de  longueur donné  est
invariant  à isomorphisme près:  comparer les  cycles de  deux graphes
peut permettre de  conclure que deux graphes ne  sont pas isomorphes (cf
exercice \vref{exo::cycle_iso}).
\end{NB}


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

Voici un théorème important qui montre tout l'avantage que nous pouvons
tirer de l'utilisation de matrices:


\begin{theoreme}\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{theoreme}


Pour le plaisir, voici une petite démonstration par récurrence sur $k$ de ce
théorème.

Pour  $k=1$, la  proposition correspond  à la  définition de  la matrice
d'adjacence: on met un 1 s'il existe une chaîne entre $x_i$ et $x_j$.

Soit $k>1$: on suppose la proposition vraie pour $k-1$.

Soit $x_i$ et $x_j$ deux sommets quelconques et une chaîne de
longueur $k$ entre  eux: on peut le décomposer en  une arête entre $x_i$
et un voisin, disons $x_p$ et une chaîne entre $x_p$ et $x_j$ de longueur
$k-1$.

On peut donc appliquer la relation de récurrence à ce dernier chaîne: le
nombre  de chaînes entre  $x_p$ et  $x_j$ est  donc égal  au coefficient
$m_{pj}^{(k-1)}$. 

Il se  peut qu'il y  ait plusieurs arêtes  entre $x_i$ et $x_p$  donc le
nombre de  chaînes de longueur  $k$ passant par $x_p$  est $m_{ip}\times
m_{pj}^{(k-1)}$.

Au passage,  on peut  remarquer que cette  relation fonctionne  aussi si
$x_p$ n'est pas un voisin de $x_i$ car à ce moment-là, $m_{ip}$ est nul.

Finalement, pour avoir toutes les chaînes de longueur $k$, on calcule:

$$\displaystyle\sum_{p=1}^{n}m_{ip}m_{pj}^{k-1}$$

Or vous qui connaissez bien votre cours sur le produit de matrices, vous
savez que le calcul précédent  donne exactement le terme $m_{ij}^{k}$ ce
qui achève notre démonstration.



\medskip

Ce théorème  a une conséquence très  utile pour nous. Il  nous faut tout
d'abord introduire une nouvelle définition:



\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}

Un  problème très  important à  résoudre est  de trouver  la  plus courte
chaîne  entre deux  sommets  d'un  graphe. Le  théorème  suivant nous  y
aidera:



\begin{theoreme}
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{theoreme}

Reprenons   par    exemple   le   graphe    illustrant   la   définition
\vref{def::chemin}.

Sa  matrice d'adjacence  en  suivant l'ordre  croissant  des numéros  de
sommet est:


$$
M=
\begin{pmatrix}
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  
\end{pmatrix}
$$

Pour ne  pas se fatiguer  à calculer les  produits de matrices,  on peut
s'aider de \Sage:

\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}

Hop: le plus petit $m_{03}^{(k)}$ non  nul est bien obtenu pour $k=3$ et
il y a  trois chaînes de longueur minimale 3 entre  les sommets $x_0$ et
$x_3$.

On aurait pu s'aider d'un petit programme maison:


\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}

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


\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}


Parmi les deux graphes suivant, qui est connexe et qui ne l'est pas?


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


Certains  auteurs   parlent  de  graphe  connecté  au   lieu  de  graphe
connexe. C'est plus parlant mais la notion de connexité se retrouve dans
de nombreux domaines  en mathématiques et désigne quelque  chose qui est
en un seul morceau.

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

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

\begin{theoreme}
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{theoreme}


Nous n'aborderons pas la démonstration mais \og ça se voit bien\fg{}.


Par  exemple, cherchez les  composantes connexes  du graphe  non connexe
étudié précédemment.

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.



\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 correspondantes}
\STATE{c \recoit{}c+1}
\ENDWHILE
\END
\end{algo}



\begin{NB}
 Pour rechercher les composantes connexes
maximales en nombre de sommets, on utilise les algos de recherche en
largeur ou en profondeur puisque pour trouver une composante connexe
maximale contenant un sommet donn\'{e}, il suffit de trouver tous les
descendants et les ascendants de ce sommet.
\end{NB}


Une  définition  équivalente et  qui  permet  d'obtenir plus  rapidement
certains résultats est la suivante:

\begin{theoreme}[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{theoreme}

C'est plus mathématique mais tellement plus élégant...


\subsection{Point d'articulation}

\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}
\input{../../../Thierry/Conversions/Isthme.pdf_tex}
\end{center}



Les sommets 5, 6 et et 9 sont les points d'articulation et l'ar\^{e}te $%
\left[ 5,6\right] $ est un isthme.





Il doit \^{e}tre clair qu'un point d'articulation ne peut appartenir \`{a}
un cycle du graphe et que si $x$ est un point d'articulation c'est qu'il
existe au moins $u$ et $v$ deux sommets distincts et distincts de $x$ de
sorte que toute cha\^{\i}ne de $u$ \`{a} $v$ passe par $x.$

Voici un algorithme 
qui nous donne les points d'articulation d'un graphe connexe ainsi qu'une
arborescence des sommets visit\'{e}s :


\begin{algo}
\VAR
\DECLVAR{U}{ensemble}
\DECLVAR{prévisite, hauteur}{entiers}
\ENDVAR
\BEGIN
\STATE{prévisite\recoit{}1}
\STATE{U\recoit{}$\emptyset$}
\STATE{empiler s}
\STATE{prévisite[s]\recoit{}prévisite}
\STATE{hauteur[s]\recoit{}1}
\STATE{prévisite\recoit{}prévisite+1}
\WHILE{pile non vide}
\STATE{$x$\recoit{}sommet de la pile}
\IF{$ \exists$ $y$ non sélectionné et voisin de $x$}
\STATE{empiler $y$}
\STATE{U\recoit{}$ U\cup \bigl\{(x,y)\bigr\}$}
\STATE{prévisite[$y$]\recoit{}prévisite}
\STATE{prévisite\recoit{}prévisite+1}
\STATE{hauteur\recoit{}prévisite[$y$]}
\ELSE
\STATE{dépiler $x$}
\FORGEN{ tout sommet $z$ voisin de $x$ avec $(z,x)\not\in U$}
\STATE{hauteur[x]\recoit{}min$\bigl\{$          hauteur[$x$],
  hauteur[$y$]$\bigr\}$}
\ENDFOR
\ENDIF
\ENDWHILE
\end{algo}

\begin{algo}[continue]

\IF{$s$ a au moins 2 successeurs dans U}
\STATE{$s$ est un sommet d'articulation}
\ENDIF
\IF{$x\neq s$ et $(x,y)\in U$ et hauteur[$y$]$\geqslant $prévisite[$x$]}
\STATE{$x$ est un sommet d'articulation}
\ENDIF
\END
\end{algo}










\subsection{Connexité des graphes orientés}

Comme  le sens  intervient, on  distingue  deux notions  de connexité  à
présent.

\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}

Un graphe orienté  peut cependant ne pas être  fortement connexe tout en
étant \og en un seul morceau\fg{}:

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

Que dire alors des deux graphes suivants:

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

\Edges[style={->}](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={->}](d,b,c,d,e,a)
\Edge[style={->}](b)(a)
  \end{tikzpicture}
\end{center}

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



\begin{remarque}
Une partie restreinte \`{a} un seul sommet, un singleton de $X,$ ne
contredit pas la d\'{e}finition, c'est une partie fortement connexe.
\end{remarque}

Voici un théorème qui va nous donner  un premier algorithme pour d\'{e}terminer les parties
fortement connexes maximales.



\begin{theoreme}
$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{theoreme}





La sc\`{e}ne se passe dans une administration\footnote{%
Exemple extrait d'un (tr\`{e}s vieux) polycopi\'{e} de Mr. Ganachaud
professeur \`{a} l'universit\'{e} de Nantes.} 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 :%





\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(a,c,d,e,a,h)
\Edges(b,f,h)
\Edges(a,d,e,a)
\Edge(d)(g)\Edge(i)(f)
\Edge[style={bend left}](b)(g)
\Edge[style={bend left}](g)(b)
\Edge[style={bend left}](h)(i)
\Edge[style={bend left}](i)(h)
\Edge[style={bend left=90}](d)(a)
\end{tikzpicture}
\end{center}


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. Une
solution est donn\'{e}e par l'obtention des parties fortement connexes
maximales, la voici. Choisissons le sommet $a$ par exemple; l'ensemble de
ses descendants est:

$$
\bigl\{ b,c,d,e,f,g,h,i\bigr\}
$$

et l'ensemble de ses ascendants est

$$
\bigl\{ c,d,e\bigr\}
$$

La partie $$\left\{ a,c,d,e\right\} =\left( \left\{ b,c,d,e,f,g,h,i\right\} \cap \left\{
c,d,e\right\} \right) \cup \left\{ a\right\}$$

est fortement connexe maximale.

 En choisissant maintenant le sommet $b$, on
prouve que la partie $\left\{ b,g\right\} $ est fortement connexe maximale
et le choix de $f$ donne la derni\`{e}re partie fortement connexe maximale $%
\left\{ f,h,i\right\} .$ Utilisons ces r\'{e}sultats pour d\'{e}terminer une
autre repr\'{e}sentation du graphe:




%\begin{figure}
\begin{center}
  \includegraphics{ResultPartieFortConnMax}
\end{center}
%\end{figure}




Cette repr\'{e}sentation du graphe  (que vous compléterez en étiquetant
les sommets) nous donne une solution pour une
r\'{e}partition possible des employ\'{e}s dans trois bureaux. 





\subsection{Petit résumé du vocabulaire}

\begin{NB}
$\GR =\left( X=\left\{ x_{1},x_{2},...,x_{n}\right\} ,A\right) $ est un
graphe orient\'{e} avec $\func{Card}\left( A\right) \geq 2$ et on note $%
\GR _{NO}$ le graphe non orient\'{e} associ\'{e} \`{a} $\GR $

\begin{enumerate}
\item \textit{Que signifie \og $x_{i}$ est un sommet isolé\fg{} ?} $%
x_{i}$ n'a pas de voisin.

\item  \textit{On vous dit que la suite $\left(
y_{1},y_{2},...,y_{k}\right) $ avec $y_{i}\in X$ est une cha\^{\i}ne,
qu'est-ce que cela signifie?} $i\in \left\{ 1,2,...,n-1\right\} $ on a $%
\left( y_{i},y_{i+1}\right) $ ou $\left( y_{i+1},y_{1}\right) \in A$.
\item\textit{ On vous dit que la suite $\left(
y_{1},y_{2},...,y_{k}\right) $ avec $y_{i}\in X$ est un chemin, qu'est-ce
que cela signifie ?} $\forall i\in \left\{ 1,2,...,n-1\right\} $ on a $\left(
y_{i},y_{i+1}\right) \in A.$

\item \textit{Que sigifie $\GR $ est connexe ?} Que pour
toute paire $\left\{ x_{i},x_{j}\right\} $ de sommets de $\GR $ il existe
une cha\^{\i}ne entre $x_{i}$ et $x_{j}.$

\item \textit{ Que signifie $\GR $ est fortement connexe ?}
Que pour tout couple de sommets distincts $\left( x_{i},x_{j}\right) \in
X\times X$ il existe un chemin de $x_{i}$ \`{a} $x_{j}.$

\item\textit{ D\'{e}finir parfaitement le sous graphe de $%
\GR $ engendr\'{e} par $Y\subseteq X.$} C'est le graphe $\GR
_{Y}=\left( Y,A\cap \left( Y\times Y\right) \right) .$

\item  \textit{On vous dit que $Y\subseteq X$ est une partie
connexe du graphe $\GR ,$ qu'est-ce que cela signifie ?} Que $\GR _{Y}$
est connexe.

\item \textit{On vous dit que $Y\subseteq X$ est une partie
fortement connexe du graphe $\GR ,$ qu'est-ce que cela signifie ?} Que $%
\GR _{Y}$ est fortement connexe.

\item \textit{ Donner une m\'{e}thode ou une formule ou un
algorithme qui permet de d\'{e}terminer la partie fortement connexe maximale
de $\GR $ qui contient le sommet $x_{i}$.}


C'est $\left\{ x_{i}\right\} \cup \left( \GR ^{+}\left( x_{i}\right) \cap
\GR ^{-}\left( x_{i}\right) \right) $
\end{enumerate}
\end{NB}



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

\subsection{Graphes symétriques}
Vous avez  sûrement joué  à ceci  à la maternelle  (ou pendant  un cours
d'amphi): dessiner  ce graphe  sans lever  le stylo du  papier et  en ne
traçant  chaque arête qu'une  seule fois  en partant  et en  revenant au
même sommet...



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


Une telle chaîne est appelée  un \textbf{cycle eulérien}: c'est un cycle
 qui contient toutes les arêtes du graphe.

Un  graphe  qui  contient   un  cycle  eulérien  est  un  \textbf{graphe
  eulérien}.


On peut ne pas former de cycle  mais seulement une chaîne simple:
une \textbf{chaîne eulérienne} est une chaîne simple qui contient toutes les
arêtes du graphe.

Que pensez-vous du graphe suivant:


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


\begin{NB}
Les  arêtes  n'interviennent  qu'une   fois  mais  les  sommets  peuvent
apparaître plusieurs fois.
\end{NB}




Ce problème avait  déjà été évoqué au début du cours  au sujet des ponts
de Königsberg.




C'est d'ailleurs en cherchant à résoudre ce problème qu'\textsc{Euler} a
émis et démontré le théorème suivant:

\begin{theoreme}
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{theoreme}

Avant  de le démontrer,  que pouvez-vous  en déduire  pour les  ponts de
Königsberg? Peut-on transformer le plan de la ville pour améliorer la situation?


Occupons-nous d'abord de la \textit{condition  nécessaire}: il est évident que le
graphe doit être connexe. De plus, si un cycle arrive en un sommet, il
doit pouvoir en repartir sans emprunter une arête déjà utilisée: on peut
donc mettre  en bijection l'ensemble des arêtes  entrantes et l'ensemble
des arêtes sortantes, ce qui signifie que les sommets sont tous de degré pair.



La \textit{condition} est aussi \textit{suffisante}. Partons d'un sommet
quelconque. On avance en parcourant  des arêtes. À chaque fois qu'on \og
entre\fg{} en un sommet, on en \og sort\fg{} par une autre arête car son degré est pair. On
continue  ainsi à  \og traverser\fg{}  des sommets  sans être  bloqué en
empruntant des  arêtes différentes. Cependant, le nombre  de sommets est
fini et il reste un sommet  emprunté une seule fois, celui de départ: on
y retourne  donc forcément et  on a ainsi \textit{construit}  un cycle
avec a priori une partie des arêtes empruntées une et une seule fois.

Considérons  maintenant une  arête  non empruntée,  s'il  en existe  une
(sinon, on a trouvé un cycle eulérien). Il y
a donc  au moins une de  ses extrémités qui n'appartient  pas au cycle
initial. Comme  le graphe est connexe,  il existe une chaîne  vers un des
sommets du cycle. Éliminons dans  le cycle de départ tous les sommets
sauf celui-là (qu'on notera $s$) et toutes les arêtes empruntées.  Il nous reste un
sous-graphe ayant  un sommet en commun  avec le cycle  initial. Tous ses
sommets sont de degré pair, certes, mais il peut ne pas être connexe. 
On peut cependant construire un cycle eulérien comme précédemment dans
ce sous-graphe et  on fusionne ces deux cycles  qui n'ont aucune arête
en commun.

On réitère ce procédé jusqu'à  ne laisser aucune arête non parcourue. Il
se termine car il y a un nombre fini d'arêtes.


Comme le procédé est constructif, on peut en déduire un premier algorithme qui
renvoie un  cycle eulérien  dans un graphe  connexe dont  les sommets
sont pairs:

\begin{algo}
\FUNC{Euler1}{\pfarg{G}{graphe connexe de sommets pairs}}{cycle}
\VAR
\DECLVAR{C}{cycle   dans  G   qui   commence  en   un  sommet   choisi
  arbitrairement  et  dont  les  arêtes s'ajoutent  jusqu'à  obtenir  un
  cycle}
\DECLVAR{H}{le graphe obtenu en  éliminant de G les arêtes de C}
\ENDVAR
\BEGIN
\WHILE{H contient des arêtes}
\STATE{sousC\recoit{}un cycle dans H  qui commence en un sommet commun
  à H et C}
\STATE{H\recoit{}le  sous-graphe  obtenu  en  éliminant  les  arêtes  de
  \textit{sousC} et tous les sommets isolés}
\STATE{C\recoit{C fusionné avec sousC}}
\ENDWHILE
\RETURN{C}
\END
\end{algo}

Tout est dans la fusion...


\medskip

Voici deux autre théorèmes que nous admettrons mais qui nous permettrons
de répondre à certains problèmes:



\begin{theoreme}
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{theoreme}

Cela nous guide pour résoudre le problème de la maison:


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



Ces   théorèmes  sont   liés   à  un   problème   classique,  celui   du
\textit{postier chinois}, la nationalité du postier étant celle de Meigu
Guan qui le proposa en 1962:  est-ce qu'un postier peut faire sa tournée
en ne repassant jamais par la même rue?


\medskip

Voici un autre problème, qu'on pourrait appeler le problème du musée: si
nous partons de  l'entrée et que nous parcourons les  salles du musée en
  choisissant la suivante parmi celles qui n'ont pas été encore visitées, on peut toujours
revenir à notre point de départ.

Mathématisons un peu:

\begin{definition}
Un graphe  est dit \textbf{aléatoirement  eulérien} en un sommet  $x$ si
chaque chaîne simple maximal qui commence en $x$ est un cycle eulérien
dans ce graphe.
\end{definition}


Voici la clé du problème:

\begin{theoreme}
Un graphe connexe simple $\GR=(X,A)$ dont tous les sommets sont de degré
pair est aléatoirement eulérien en un sommet $x$ si, et seulement si, le
graphe  $\bigl(  X  \backslash   \{x\}\,  ,  \,  \{a\in  A\mid  x\not\in
a\}\bigr)$ ne contient pas de cycle.
\end{theoreme}



\subsection{Graphes orientés}



Si on met des sens uniques pour traverser les ponts:

\begin{theoreme}
  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{theoreme}

Voici une méthode  simple pour trouver un circuit  eulérien dans un graphe
orienté.

Voyons-le sur un exemple: le graphe de \textsc{De Bruijn} d'ordre 3.



\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}
\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}


Nous vérifions tout d'abord qu'un circuit eulérien existe bien.

Remplissons ensuite  le tableau  suivant où nous  mettons tous  les arcs
avec 
sur la première ligne les origines et en bas les extrémités:


\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}


On cherche ensuite des circuits  en prenant les arcs successivement puis
en les éliminant dès qu'un circuit est formé.

Vérifiez  qu'on obtient  les  circuits $(0)$,  $(0124)$,  $ (1364)$,  $
(25)$, $ (3765)$ et $(7)$.

Il ne  reste plus qu'à  les fusionner de  proche en proche. Quel  est le
circuit obtenu?


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



William  \textsc{Hamilton}  a été  un  grand  mathématicien irlandais  à
l'origine de  la théorie  des quaternions. Il  a également,  pendant ses
temps libres, commercialisé un casse-tête en 1857, sous deux formes.

Une   sorte   de  dodécaèdre   tout   d'abord  (\textit{The   Travellers
  Dodecahedron}) où 20 punaises figurent 20 villes
qu'il faut visiter en suivant les arêtes mais en ne passant qu'une seule
fois par chaque ville:


\begin{minipage}[t]{0.5\linewidth}
  
\begin{center}
\begin{pspicture}(-1,-2)(10,5)
\psDodecahedron[Frame=false,Viewpoint=-0.2 0.2 0.2]
\end{pspicture}
\end{center}


\end{minipage}\hspace{0.5cm}
\begin{minipage}[t]{0.45\linewidth}\vspace{-0.5cm}
  \hspace{5.5cm} 
  \begin{flushright}
    
%\begin{figure}
\begin{center}
  \includegraphics[width=\linewidth]{dodekajeu}
\end{center}
%\end{figure}

  \end{flushright}
\end{minipage}



Une autre version (\textit{The Icosian Game}) consiste à parcourir le graphe représenté en suivant les
arêtes et en visitant chaque sommet une, et une seule fois:



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

\end{minipage}\hspace{0.5cm}
\begin{minipage}[t]{0.45\linewidth}\vspace{-4cm}
  \hspace{5.5cm} 
  \begin{flushright}
\begin{center}
  \includegraphics[scale=0.35]{dodeka}
\end{center}
  \end{flushright}
\end{minipage}


C'est  pourquoi  on   appelle  \textbf{cycle  hamiltonien}  d'un  graphe
symétrique une chaîne qui passe par tous les sommets du graphe une, et une
seule fois avant de revenir au sommet de départ.


Un   graphe  qui   contient   un  cycle   hamiltonien   est  appelé   un
\textbf{graphe hamiltonien}.


Malheureusement,  à la  différence des  graphes eulériens,  il n'existe
aucune  propriété  générale permettant  de  conclure  si  un graphe  est
hamiltonien ou non.

Il y a malgré tout  quelques petites propriétés locales qui peuvent nous
aider.


\begin{theoreme}
\begin{itemize}
\item Si un graphe possède un sommet de degré 1, il n'est pas hamiltonien.

\item Si un cycle hamiltonien  existe, il traverse obligatoirement les sommets
de degré 2.
\end{itemize}
\end{theoreme}

Pourquoi?  Cela rend  le  passage par  certaines  arêtes obligatoire  et
permet parfois de conclure.

Par  exemple,  existe-t-il  des  cycles hamiltoniens  dans  les  graphes
suivant:


\begin{center}
  \begin{tikzpicture}
    \SetGraphUnit{1}
\GraphInit[vstyle=Art]
\Vertices{square}{1,2,3,4}
\SO(1){5}\NO(3){7}
\EA(2){6}\WE(4){8}
\Edges(1,2,3,4,1,5,6,7,8,5)
\Edge(1)(5)
\Edge(4)(8)
  \end{tikzpicture}
\begin{tikzpicture}
    \SetGraphUnit{1}
\GraphInit[vstyle=Art]
\Vertices{square}{1,2,3,4}
\SO(1){5}\NO(3){7}
\EA(2){6}\WE(4){8}
\Edges(1,2,3,4,1,5,6,7,8,5)
\Edge(1)(5)
  \end{tikzpicture}
\begin{tikzpicture}
    \SetGraphUnit{1}
\GraphInit[vstyle=Art]
\Vertices{square}{1,2,3,4}
\SO(1){5}\NO(3){7}
\EA(2){6}\WE(4){8}
\Edges(1,2,3,4,1,5,6,7,8,5)
\Edge(1)(5)
\Edge(3)(7)
  \end{tikzpicture}
\end{center}



\section{Chemins de longueur minimum}


\subsection{Graphe pondéré}

C'est un graphe dont les  arêtes sont affectées d'un \og poids\fg{}. Par
exemple,  on peut  penser à  un réseau  routier, les  sommets  étant des
villes, les arêtes des routes entre ces villes pondérées par la distance
séparant les deux  villes sommets de l'arête. On  peut alors chercher le
plus court  chemin d'une ville à  l'autre (GPS) ou le  plus court chemin
passant par tous les sommets (problème du voyageur de commerce).


\begin{definition}
On appelle  \textbf{matrice de  pondération} d'un graphe  $\GR=(X,A)$ la
matrice dont les coefficients correspondant aux sommets $s$ et $t$
vaut:

$$
\begin{cases}
  0 \quad \text{si } s=t\\
  \infty  \quad  \text{si  }  \bigl\{s,t\bigr\}  \text{  n'est  pas  une
    arête}\\
  p \quad \text{si } \bigl\{s,t\bigr\} \text{ est une arête de poids }p
\end{cases}
$$
\end{definition}


Voici un graphe pondéré:

\begin{center}
  \begin{tikzpicture}
    \SetGraphUnit{2}
\Vertices{circle}{f,d,b,a,c,e}
\Edge[label=4](a)(b)
\Edge[label=2](a)(c)
\Edge[label=5](b)(d)
\Edge[label=10](c)(e)
\Edge[label=1](b)(c)
\Edge[label=8](c)(d)
\Edge[label=2](d)(e)
\Edge[label=3](e)(f)
\Edge[label=6](d)(f)
  \end{tikzpicture}
\end{center}


Écrire sa matrice de pondération.


\subsection{Algorithme de \textsc{Dijkstra}}


Edsger  \textsc{Dijkstra}  (prononcer \og  Deïkstra\fg{}  en roulant  le
r...)  est un  mathématicien  néerlandais mort  en  2002 à  l'âge de  72
ans. Il a mis au point  un algorithme permettant d'obtenir le plus court
chemin 
(chaîne) entre deux sommets d'un graphe pondéré simple connexe et dont les
poids sont positifs.

Le plus simple est de remplir un tableau. Voici celui correspondant à la
recherche de la plus courte chaîne entre a et f dans le graphe précédent:


\begin{center}
             \begin{tabularx}{0.8\linewidth}{Y{4}}
	     \whline
Sommets &b&c&d&e&f\\
\whline
a&4&\colorbox{gray!50}{\textbf{2}}&$\infty$&$\infty$&$\infty$\\
\hline
c&\colorbox{gray!50}{\textbf{3}}&-&10&12&$\infty$\\
\hline
b&-&-&\colorbox{gray!50}{\textbf{8}}&$\infty$&$\infty$\\
\hline
d&-&-&-&\colorbox{gray!50}{\textbf{10}}&14\\
\hline
e&-&-&-&-&\colorbox{gray!50}{\textbf{13}}\\
             \whline
             \end{tabularx}
             \end{center}

Sauriez-vous l'expliquer?



%\section{Graphes planaires}

\section{Coloration}




\begin{definition}
Un \textbf{stable} d'un graphe est un sous-graphe sans arête.

Le \textbf{nombre  de stabilité} $\alpha(\GR)$  d'un graphe $\GR$  est la
taille d'un stable maximum.
\end{definition}






\begin{definition}
\textbf{Colorier}\footnote{%
Extrait du dictionnaire Hachette :
\par
\textbf{colorer :} donner une couleur ou de la couleur \`{a} ...
\par
\textbf{colorier :} appliquer des couleurs sur ...
\par
Vous pouvez donc remplacer colorier par colorer si vous pr\'{e}f\'{e}rez.}
\textbf{les sommets} du graphe simple non orient\'{e} $\GR =\left( X,A\right) ,$
c'est affecter une couleur \`{a} chaque sommet de sorte que deux sommets
quelconques adjacents aient toujours des couleurs diff\'{e}rentes. Le nombre
minimal de couleurs n\'{e}cessaires pour colorier les sommets du graphe est
appel\'{e} le \textbf{nombre chromatique} du graphe.

\textbf{Colorier les ar\^{e}tes} du graphe c'est affecter une couleur \`{a} chaque ar%
\^{e}te du graphe de sorte que deux ar\^{e}tes quelconques adjacentes aient
des couleurs diff\'{e}rentes. Le nombre minimal de couleurs pour colorier
les ar\^{e}tes du graphe est l'\textbf{indice chromatique} du graphe.


\end{definition}




\begin{NB}
   Les  ensembles  monochromes sont  stables  donc  la coloration  permet
  d'obtenir une partition de X en un nombre minimum de stables.
\end{NB}


\begin{theoreme}
   $$\chi(\GR)=1 \Leftrightarrow  \GR \text{ est stable}$$



   $$\chi(\GR)=2 \Leftrightarrow  \GR \text{ est biparti}$$
\end{theoreme}

 \begin{theoreme}
    On a pour tout graphe $\GR=(X,A)$:

$$\left\lceil \frac{n}{\alpha(\GR)}\right\rceil \leqslant \chi(\GR)\ie n-\alpha(\GR)+1$$
  \end{theoreme}


 Conséquence:

 \begin{theoreme}
    Le graphe complet $ K_n$ est $n-$coloriable.
 \end{theoreme}


 \begin{definition}
    Un  sous-graphe   complet  d'un  graphe   $  \GR$  est   appelé  une
    \textbf{clique}. 

L'ordre de la plus grande clique dans $ \GR $ est noté $\omega(\GR)$.
  \end{definition}



\begin{theoreme}
    $$\chi(GR)\geqslant \omega(\GR)$$
  \end{theoreme}

 \begin{theoreme}[\bsc{Tutte} 1954]
    Pour   tout  entier   $k   \geqslant  2$,   il   existe  un   graphe
    $k-$chromatique sans clique à 3 sommets (triangle).
  \end{theoreme}






 \begin{theoreme}[\bsc{Nordhaus} et \bsc{Gaddum} - 1960]
    Soit $\GR=(X,A)$ un graphe et $ \overline{\GR}=(X,\overline{A})$ son
    complémentaire.

    \begin{enumerate}
    \item $ \chi(\GR)\cdot\chi(\overline{\GR})\geqslant n$
\item $ \chi(\GR)+\chi(\overline{\GR})\leqslant n+1$
\item $ \chi(\GR)+\chi(\overline{\GR})\geqslant 2 \sqrt{n}$
\item  $ \chi(\GR)\cdot\chi(\overline{\GR})\leqslant \left(\frac{n+1}{2}\right)^2$
    \end{enumerate}
  \end{theoreme}


On admettra le théorème suivant:

  \begin{theoreme}[\bsc{Vizing} - 1964]
    Pour tout graphe $\GR$, $$\Delta(\GR) \leqslant \chi'(\GR) \leqslant \Delta(\GR)+1$$
  
avec $ \Delta(\GR)$ le degré maximum d'un sommet du graphe.
\end{theoreme}







La coloration des sommets d'un graphe est un probl\`{e}me difficile en ce
sens que si le nombre de sommets est grand et si le graphe comporte beaucoup
d'ar\^{e}tes, on ne conna\^{\i}t pas d'algorithme performant pour d\'{e}%
terminer la solution minimale. Par contre l'algorithme suivant donne une
solution satisfaisante m\^{e}me s'il ne donne pas forc\'{e}ment la solution
minimale.

Soit donc le graphe $\GR =\left( X,A\right) $ et on cherche \`{a}
colorier les sommets avec un minimum de couleurs.

La premi\`{e}re \'{e}tape consiste \`{a} d\'{e}terminer sa matrice
sommets-sommets (on a donc ordonn\'{e} les sommets) et \`{a} d\'{e}terminer
le degr\'{e} de chaque sommet.

On note $\GR _{k}=\left( X_{k},A_{k}\right) $ et on affecte la valeur 0 
\`{a} la variable $k,$ $X_{0}=X$ est l'ensemble des sommets non encore colori%
\'{e}s et $A_{0}=A.$

\begin{enumerate}
\item Si $X_{k}\neq \emptyset ,$ on choisit un sommet $s_{k}$ de degr\'{e}
maximal de $X_{k}$ et on lui affecte la couleur $c_{k}$ ; on consid\`{e}re
maintenant $\GR _{k_{1}}$le sous graphe de $\GR _{k}$ obtenu en
supprimant $s_{k}$ et tous ses voisins et, s'il n'est pas vide, on choisit
un sommet $s_{k_{1}}$ de degr\'{e} maximal dans $\GR _{k_{1}}$ et on lui
affecte la couleur $c_{k}.$ $\GR _{k_{2}}$ est le sous graphe de $\GR
_{k_{1}}$ obtenu en ayant supprim\'{e} dans $\GR _{k_{1}}$ le sommet $%
s_{k_{1}}$et tous ses voisins. Etc., jusqu'\`{a} ce que $\GR _{k_{i}}$
soit un graphe vide. \`{A} ce stade un certain nombre de sommets ont la
couleur $c_{k}$ et et $k\leftarrow k+1.$ On note encore $\GR _{k}$ le
sous graphe engendr\'{e} par les sommets non encore colori\'{e}s et on
retourne en 1.

\item Si $X_{k}=\emptyset ,$ on a affect\'{e} une couleur \`{a} chaque
sommet.
\end{enumerate}

%\begin{exemple}
Consid\'{e}rons le graphe%

% \begin{center}
% \input{../../../Thierry/Conversions/ColorationSommet.pdf_tex}
% \end{center}




\begin{center}
\begin{tikzpicture}
\renewcommand*{\VertexLineWidth}{2pt}
\GraphInit[vstyle=Welsh]
\Vertices[unit=2]{circle}{5,4,3,2,1,8,7,6}
\SetVertexNoLabel
%\AddVertexColor{black!80}{2,5,7} \AddVertexColor{gray}{3,8}
%\AddVertexColor{gray!10}{1,6}\AddVertexColor{gray!50}{4}
\Edges(8,7,6,5,4,3,2,1,8,2,4,6,8,4)\Edges(2,6)
\end{tikzpicture}
\end{center}






D\'{e}terminons le degr\'{e} de chaque sommet%
$$
\begin{tabular}{|c|c|c|c|c|c|c|c|c|}
\hline
Sommets & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ \hline
Degr\'{e} & 2 & 5 & 2 & 5 & 2 & 5 & 2 & 5 \\ \hline
\end{tabular}%
$$%
Nous choisissons le sommet 2 et nous lui affectons la couleur $c_{1}.$
Supprimons le sommet 2 et tous ses voisins, nous obtenons%



\begin{center}
\input{../../../Thierry/Conversions/ColorationSommet1.pdf_tex}
\end{center}



et nous affectons la couleur $c_{1}$ aux sommets 5 et 7. Maintenant consid%
\'{e}rons le sous graphe engendr\'{e} par les sommets non encore colori\'{e}%
s :


\begin{center}
\input{../../../Thierry/Conversions/ColorationSommet2.pdf_tex}
\end{center}


Nous avons%
$$
\begin{tabular}{|c|c|c|c|c|c|}
\hline
Sommets & 1 & 3 & 4 & 6 & 8 \\ \hline
Degr\'{e} & 1 & 1 & 3 & 2 & 3 \\ \hline
\end{tabular}%
$$%
et nous choisissons le sommet 8 auquel nous affectons la couleur $c_{2}.$
Supprimons ce sommet et tous ses voisins%








\begin{center}
\input{../../../Thierry/Conversions/ColorationSommet3.pdf_tex}
\end{center}


Nous affectons la couleur $c_{2}$ au sommet 3. Le sous graphe engendr\'{e}
par les sommets non encore colori\'{e}s est 



\begin{center}
\input{../../../Thierry/Conversions/ColorationSommet4.pdf_tex}
\end{center}

Le sommet 6 est un sommet de plus fort degr\'{e}, affectons-lui la couleur $%
c_{3},$ supprimons-le ainsi que tous ses voisins%



\begin{center}
\input{../../../Thierry/Conversions/ColorationSommet5.pdf_tex}
\end{center}


On affecte au sommet 1 la couleur $c_{3}.$ Le sous graphe engendr\'{e} par
les sommets non encore colori\'{e}s est maintenant%









\begin{center}
\input{../../../Thierry/Conversions/ColorationSommet6.pdf_tex}
\end{center}

On affecte au sommet 4 la couleur $c_{4}$ et tous les sommets sont colori%
\'{e}s$.$ Nous avons r\'{e}ussi \`{a} colorier le graphe avec 4 couleurs :%




% \begin{center}
% \input{../../../Thierry/Conversions/ColorationSommet7.pdf_tex}
% \end{center}

\begin{center}
\begin{tikzpicture}
\renewcommand*{\VertexLineWidth}{2pt}
\GraphInit[vstyle=Welsh]
\Vertices[unit=2]{circle}{5,4,3,2,1,8,7,6}
\SetVertexNoLabel
\AddVertexColor{black!80}{2,5,7} \AddVertexColor{gray}{3,8}
\AddVertexColor{gray!10}{1,6}\AddVertexColor{gray!50}{4}
\Edges(8,7,6,5,4,3,2,1,8,2,4,6,8,4)\Edges(2,6)
\end{tikzpicture}
\end{center}




%\end{exemple}

Pour colorier les ar\^{e}tes d'un graphe on peut utiliser l'algorithme pr%
\'{e}c\'{e}dent sur le graphes aux ar\^{e}tes, ce graphe se d\'{e}termine
ainsi, chaque ar\^{e}te est repr\'{e}sent\'{e}e par un sommet et deux
sommets sont reli\'{e}s par une ar\^{e}te si, et seulement si,  ils correspondent \`{a} des ar%
\^{e}tes adjacentes. Consid\'{e}rons le graphe dont nous voulons colorier
les ar\^{e}tes que nous avons num\'{e}rot\'{e}es : 




\begin{center}
\begin{tikzpicture}
\renewcommand*{\VertexLineWidth}{2pt}
\GraphInit[vstyle=Art]
\renewcommand*{\VertexBallColor}{blue!50}
\renewcommand*{\VertexBigMinSize}{12pt}
\SetUpEdge[lw= 1.5pt,
color= black,
labelcolor = white,
labeltext = red,
labelstyle = {draw,text=blue}]
\Vertices[unit=2]{circle}{a,b,c,d,e}
%\SetVertexNoLabel
% \AddVertexColor{black!80}{2,5,7} \AddVertexColor{gray}{3,8}
% \AddVertexColor{gray!10}{1,6}\AddVertexColor{gray!50}{4}
\Edge[label=1](a)(b)
\Edge[label=2](a)(e)
\Edge[label=3](e)(d)
\Edge[label=4](e)(b)
\Edge[label=5](b)(c)
\Edge[label=6](c)(d)
\Edge[label=7](c)(e)
\Edge[label=8](d)(b)
\end{tikzpicture}
\end{center}






% \begin{center}
% \input{../../../Thierry/Conversions/ColorationArete.pdf_tex}
% \end{center}



Son graphe aux ar\^{e}tes est le suivant :%



\begin{center}
\input{../../../Thierry/Conversions/ColorationArete1.pdf_tex}
\end{center}


C'est le sommet 4 qui a le plus fort degr\'{e}, affectons-lui la couleur $%
c_{1}$ et supprimons le sommet 4 ainsi que tous ses voisins, il nous reste
le sommet 6 auquel on affecte la couleur $c_{1}.$ Le sous graphe engendr\'{e}
par les sommets non encore colori\'{e}s est alors%



\begin{center}
\input{../../../Thierry/Conversions/ColorationArete2.pdf_tex}
\end{center}


Choisissons le sommet 8 qui a un plus fort degr\'{e}, affectons-lui la
couleur $c_{2}$, supprimons-le ainsi que tous ses voisins.%



\begin{center}
\input{../../../Thierry/Conversions/ColorationArete3.pdf_tex}
\end{center}


Nous choisissons le sommet 2 (pourquoi pas) auquel nous affectons la couleur 
$c_{2}$. Le sous graphe engendr\'{e} par les sommets non encore colori\'{e}s
est maintenant%




\begin{center}
\input{../../../Thierry/Conversions/ColorationArete4.pdf_tex}
\end{center}


Nous choisissons le sommet 7 et nous lui affectons la couleur $c_{3}$ ainsi
qu'au sommet 1. Les sommets 5 et 3 sont alors colori\'{e}s avec la couleur $%
c_{4}$ : le r\'{e}sultat est%




\begin{center}
\begin{tikzpicture}
\renewcommand*{\VertexLineWidth}{2pt}
\GraphInit[vstyle=Art]
\renewcommand*{\VertexBigMinSize}{12pt}
\renewcommand*{\VertexBallColor}{red!50}
\SetUpEdge[lw= 1.5pt,
color= black,
labelcolor = white,
labeltext = red,
labelstyle = {draw,text=black}]
\Vertices[unit=2]{circle}{a,b,c,d,e}
%\SetVertexNoLabel
% \AddVertexColor{black!80}{2,5,7} \AddVertexColor{gray}{3,8}
% \AddVertexColor{gray!10}{1,6}\AddVertexColor{gray!50}{4}
\Edge[labelcolor=gray!50,color=gray!50,label=1](a)(b)
\Edge[labelstyle = {draw,text=white},labelcolor=blue,color=blue,label=2](a)(e)
\Edge[label=3](e)(d)
\Edge[labelcolor=gray,color=gray,label=4](e)(b)
\Edge[label=5](b)(c)
\Edge[labelcolor=gray,color=gray,label=6](c)(d)
\Edge[labelcolor=gray!50,color=gray!50,label=7](c)(e)
\Edge[labelstyle = {draw,text=white},labelcolor=blue,color=blue,label=8](d)(b)
\end{tikzpicture}
\end{center}

% \begin{center}
% \input{../../../Thierry/Conversions/ColorationArete5.pdf_tex}
% \end{center}


4 couleurs suffisent. Il est inutile de chercher une coloration avec moins
de couleurs car il est \'{e}vident qu'un minimum de 4 couleurs est n\'{e}%
cessaire puisque le graphe poss\`{e}de au moins un sommet de degr\'{e} 4.

Une utilisation de la coloration est la suivante : on d\'{e}sire faire
passer $k$ examens \'{e}crits dans un laps de temps minimum sans cr\'{e}er
d'impossibilt\'{e} \`{a} des \'{e}tudiants inscrits \`{a} plusieurs examens.
On impose, par exemple, que chaque \'{e}tudiant ait au plus un examen par
jour, que tous les \'{e}tudiants inscrits \`{a} un m\^{e}me examen le
passent en m\^{e}me temps et on veut rendre minimum le nombre de jours n\'{e}%
cessaires pour faire passer tous les examens. On repr\'{e}sente chaque
examen par un sommet et deux sommets sont reli\'{e}s par une ar\^{e}te si
les examens ne peuvent avoir lieu le m\^{e}me jour. Une coloration minimale
des sommets nous donne une solution.




\section{Graphe planaire}



  \begin{definition}
    Un graphe planaire est un graphe que l'on peut \textit{dessiner} sur
    un plan sans que ses arêtes ne se croisent.
  \end{definition}


  Dans un graphe plan, il y a des faces internes et une face externe.



  \begin{theoreme}[Formule d'\bsc{Euler}]
    Soit $f$ le nombre de faces d'un graphe planaire:

$$n-m+f=2$$
  \end{theoreme}




\section{Arbres de recouvrement de poids extremum}

\subsection{Généralités}

On rappelle qu'un arbre est un graphe connexe sans cycle.

Soit $G=(X,A)$ un graphe avec $|X|=n$ et $|A|=m$.

On a  montré en exercice (cf  exercice \vref{arbre}) qu'un  arbre de $n$
sommets a $n-1$ arêtes.

\begin{recherche}
  Montrer que chaque arête d'un arbre est un isthme.
\end{recherche}


\begin{definition}
  On appelle \textbf{arbre recouvrant} (ou couvrant ou de recouvrement)
  d'un graphe G, un graphe partiel qui est un arbre.
\end{definition}


Expliquez l'origine du choix du mot \og recouvrant\fg{}.

\begin{theoreme}
Un graphe G admet un arbre de recouvrement si, et seulement si G est connexe.
\end{theoreme}


Pour la condition suffisante, on peut montrer par l'absurde que le graphe partiel sans
cycle contenant un nombre maximal d'arêtes de G est connexe.




\subsection{Algorithme de Kruskal}

Joseph \textsc{Kruskal}, mathématicien et informaticien américain décédé en 2010,
a  proposé   un  algorithme  permettant   de  déterminer  un   arbre  de
recouvrement de poids extrémal en 1956.

En voici une approche simplifiée. On considère un graphe pondéré $G=(X,A,P)$.

\begin{itemize}
\item On trie les arêtes par ordre de poids (dé)croissant;
\item tant qu'on n'a pas obtenu $n-1$ arêtes (pourquoi?) on 
   considère la première arête non examinée. Si elle forme un cycle avec
   les arêtes choisies précédemment, on la rejette, sinon on la garde.
\end{itemize}

On peut  remplacer le test  sur le choix  de l'arête par \og  est-ce que
l'arête  nouvelle  formerait  un   isthme  pour  le  nouveau  graphe  en
formation?\fg{} ou bien  \og est-ce que les deux  sommets de la nouvelle
arête sont dans la même composante connexe du nouveau graphe?\fg{}



Une variante  consiste à enlever du  graphe d'origine les  arcs les plus
légers (ou les plus lourds) dans la mesure où la connexité est conservée.


\section{Flots et réseaux de transport}

\subsection{Réseau de transport}


Un réseau est défini par:

\begin{itemize}
\item un graphe orienté $G=(X,A)$;
\item  une source  $s\in E$  et un  puits $p\in  E-\bigl\{s\bigr\}$ tels
  qu'il existe au moins un chemin de $s$ vers $p$;
\item    une    application   $c$    de    $A$    dans   $\bbr_+    \cup
  \bigl\{+\infty\bigr\}$. On appelle $c(u)$ la capacité de l'arc $u$.
\end{itemize}

En   fait,   $c(u)$   représente   le  débit   maximal   (de   voitures,
d'électricité, d'informations, d'étudiants...)  pouvant transiter par le
réseau.


Par exemple:

\begin{center}
\begin{tikzpicture}
\renewcommand*{\VertexLineWidth}{2pt}
\GraphInit[vstyle=Art]
\renewcommand*{\VertexBallColor}{blue!50}
\renewcommand*{\VertexBigMinSize}{12pt}
\SetUpEdge[lw= 1.5pt,
color= black,
labelcolor = white,
labeltext = red,
labelstyle = {draw,text=blue!50!black},
style = ->]
\Vertices[unit=2.5]{circle}{p,a,b,s,c,d}
\Edge[label=[4]](b)(a)
\Edge[label=[2]](a)(d)
\Edge[label=[1]](a)(p)
\Edge[label=[5]](d)(p)
\Edge[label=[3]](d)(c)
\Edge[label=[2]](c)(b)
\Edge[label=[1]](s)(b)
\Edge[label=[4]](s)(c)
\end{tikzpicture}
\end{center}






\subsection{Flot dans un réseau de transport}




Soit $R=(X,A,s,p,c)$ un réseau de transport. Soit 
$\f$  une application  $\f: A\to  \bbr^+$. Si  $u=(x,y)$,  on écrira
aussi $\f(u)=\f(x,y)$.

On définit, sur X cette fois, les deux applications:

$$\f^+(x)= \displaystyle\sum_{y\in\Gamma(x)}{f(x,y)}$$

$$\f^-(x)= \displaystyle\sum_{y\in\Gamma^{-1}(x)}{f(y,x)}$$


On appellera  $\f^+(x)$ le  flot sortant  en $x$ et  $ \f^-(x)$  le flot
entrant en $ x$.


On   a  pour   tout  graphe   et  toute   application   $  \displaystyle
\displaystyle\sum_{x\in X}\f^+(x)=\sum_{x\in X}\f^-(x)$.


\begin{definition}
  La fonction $  \f$ est un \textbf{flot} sur  $G=(X,A)$ si elle vérifie
  la propriété d'\textbf{équilibre local}:
$$\forall x\in X,\quad \f^+(x)=\f^-(x)$$
\end{definition}




\begin{definition}
  Le flot $\f$ est \textbf{compatible avec le réseau} $ R=(X,A,s,p,c)$ si:
 $$\forall u\in A,\quad \f(u)\leqslant c(u)$$ 
\end{definition}


\begin{definition}
  Un \textbf{arc} $ u$ est dit \textbf{saturé} si $ \f(u)=c(u)$.
\end{definition}


\begin{definition}
  Un \textbf{flot} est dit \textbf{complet}  si tout chemin de $s$ à $p$
  passe par au moins un arc saturé.
\end{definition}


\begin{definition}
  Soit  $ R=(X,A,s,p,c)$  un réseau  de transport  et $\f$  un  flot sur
  $(X,A\cup   \bigl\{(p,s)\bigr\})$.   L'arc   $   (p,s)$   est   appelé
  \textbf{arc  de retour} et  $ \f(p,s)$  est appelée  \textbf{valeur du
    flot}.
\end{definition}


Compte tenu de  la propriété d'équilibre, la valeur du  flot est en fait
égale au flux qui transite de $s$ vers $p$.

\begin{definition}
  On appelle \textbf{valeur  résiduelle} d'un chemin $ \gamma$  de $s$ à
  $p$ le nombre:

$$r(\gamma)=\min_{u\in \gamma} \bigl\{c(u)-\f(u)\bigr\}$$
\end{definition}


\begin{center}
\begin{tikzpicture}
\renewcommand*{\VertexLineWidth}{2pt}
\GraphInit[vstyle=Art]
\renewcommand*{\VertexBallColor}{blue!50}
\renewcommand*{\VertexBigMinSize}{12pt}
\SetUpEdge[lw= 1.5pt,
color= black,
labelcolor = white,
labeltext = red,
labelstyle = {draw,text=blue!50!black},
style = ->]
\Vertices[unit=2.5]{circle}{p,a,b,s,c,d}
\Edge[label=2[4]](b)(a)
\Edge[label=2[2]](a)(d)
\Edge[label=0[1]](a)(p)
\Edge[label=2[5]](d)(p)
\Edge[label=0[3]](d)(c)
\Edge[label=1[2]](c)(b)
\Edge[label=1[1]](s)(b)
\Edge[label=1[4]](s)(c)
\Edge[style={->,bend left, color= gray}, labelstyle = {draw,text=gray},label=2](p)(s)
\end{tikzpicture}
\begin{tikzpicture}
\renewcommand*{\VertexLineWidth}{2pt}
\GraphInit[vstyle=Art]
\renewcommand*{\VertexBallColor}{blue!50}
\renewcommand*{\VertexBigMinSize}{12pt}
\SetUpEdge[lw= 1.5pt,
color= black,
labelcolor = white,
labeltext = red,
labelstyle = {draw,text=blue!50!black},
style = ->]
\Vertices[unit=2.5]{circle}{p,a,b,s,c,d}
\Edge[label=3[4]](b)(a)
\Edge[label=2[2]](a)(d)
\Edge[label=1[1]](a)(p)
\Edge[label=2[5]](d)(p)
\Edge[label=0[3]](d)(c)
\Edge[label=2[2]](c)(b)
\Edge[label=1[1]](s)(b)
\Edge[label=2[4]](s)(c)
\Edge[style={->,bend left, color= gray}, labelstyle = {draw,text=gray},label=3](p)(s)
\end{tikzpicture}
\end{center}



\subsection{Algorithme de Ford et Fulkerson}


\begin{definition}
 Soit $ R=(X,A,s,p,c)$ un réseau de transport et $\f$ un flot sur R.

Un chemin qui relie la source au puits par des arcs tous non saturés est
appelé \textbf{un chemin augmentant}.

Une chaîne qui relie la source au puits par des arêtes $u$ vérifiant:

\begin{itemize}
\item $f(u)<c(u)$ si l'arête est orientée dans le sens $s\to p$,
\item $f(u)>0$ si l'arête est orientée dans le sens $p\to s$,
\end{itemize}
est appelée \textbf{chaîne augmentante}.
\end{definition}


On peut  alors augmenter le flot  de la valeur résiduelle  sur un chemin
augmentant et de cette même  valeur sur les arcs \og positifs\fg{} d'une
chaîne augmentante et  diminuer le flot de la  valeur résiduelle sur les
arcs \og négatifs\fg{}.



\begin{theoreme}
Un flot est alors:
\begin{itemize}
\item \textbf{complet} s'il n'admet pas de chemin augmentant;
\item \textbf{maximal} s'il n'admet pas de chaîne augmentante.
\end{itemize}
\end{theoreme}


L'algorithme  des amis  \bsc{Ford} et  \bsc{Fulkerson} (1956)  se résume
donc à:

\begin{itemize}
\item partir d'un flot quelconque;
\item augmenter le flot tant qu'il existe un chemin augmentant;
\item augmenter le flot tant qu'il existe une chaîne augmentante.
\end{itemize}


Essayer sur le réseau suivant:

\begin{center}
\begin{tikzpicture}
\renewcommand*{\VertexLineWidth}{2pt}
\GraphInit[vstyle=Art]
\renewcommand*{\VertexBallColor}{blue!50}
\renewcommand*{\VertexBigMinSize}{12pt}
\SetUpEdge[lw= 1.5pt,
color= black,
labelcolor = white,
labeltext = red,
labelstyle = {draw,text=blue!50!black},
style = ->]
\Vertices[unit=2.5]{circle}{p,a,s,b}
\Edge[label=[2]](a)(b)
\Edge[label=[1]](s)(a)
\Edge[label=[4]](s)(b)
\Edge[label=[5]](a)(p)
\Edge[label=[3]](b)(p)
\end{tikzpicture}
\end{center}
\section{Quelques autres applications}


\subsection{Ordonnancement}

La r\'{e}alisation d'une recette de cuisine, la construction d'un pont ou
d'une maison, l'\'{e}laboration d'un logiciel, le fonctionnement d'une cha%
\^{\i}ne de fabrication , etc., demandent une coordination d'un ensemble
complexe \og d'unit\'{e}s de travail\fg{}. Les probl\`{e}mes d'ordonnancement sont
de ce type, ils se pr\'{e}sentent sous la forme d'un objectif que l'on
souhaite atteindre et dont la r\'{e}alisation demande l'\'{e}x\'{e}cution
d'un certains nombre de t\^{a}ches soumises \`{a} de nombreuses
contraintes qui peuvent \^{e}tre des contraintes de dur\'{e}e, de mat\'{e}%
riels ou moyens humains disponibles, d'une m\'{e}t\'{e}o favorable, etc..

Nous n'allons \'{e}tudier que le cas particulier de base : les seules
contraintes sont des contraintes de succession dans le temps en ce sens que
les seules contraintes que nous retenons sont du type :%
\begin{eqnarray*}
&&\text{la t\^{a}che }j\text{ ne peut commencer que si la t\^{a}che }i\text{
est termin\'{e}e ou achev\'{e}e} \\
&&\text{et la dur\'{e}e de chaque t\^{a}che est une dur\'{e}e certaine}
\end{eqnarray*}

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

MPM d\'{e}signe \og M\'{e}thode des Potentiels Metra\footnote{%
Metra \'{e}tait, dans les ann\'{e}es 1970, une soci\'{e}t\'{e}
franco-britannique, associ\'{e} \`{a} la SIA (Soci\'{e}t\'{e} d'Informatique
Appliqu\'{e}e) et \`{a} la SEMA (Soci\'{e}t\'{e} de Math\'{e}matiques Appliqu%
\'{e}es) o\`{u} beaucoup de chercheurs fran\c{c}ais de tr\`{e}s haut niveau
ont travaill\'{e}.}\fg{}, on repr\'{e}sen\-te le probl\`{e}me \`{a} l'aide d'un
graphe :

\begin{enumerate}
\item On associe \`{a} chaque t\^{a}che un sommet du graphe.

\item On d\'{e}finit l'arc $\left( i,j\right) $ de valuation ou de longueur $%
d_{i}$ si la t\^{a}che $i$ a une dur\'{e}e $d_{i}$ et si la t\^{a}che $i$
doit \^{e}tre termin\'{e}e avant que la t\^{a}che $j$ ne puisse commencer.%

\begin{center}
\begin{tikzpicture}
\SetGraphUnit{4}
\SetVertexMath
\Vertex{i}
\EA(i){j}
\Edge[style={->,bend left},label=$d_i$](i)(j)
\end{tikzpicture}
\end{center}







Ce graphe se lisant : la t\^{a}che $i$ a une dur\'{e}e $d_{i}$ et la t\^{a}%
che $j$ ne peut d\'{e}marrer qu'apr\`{e}s la r\'{e}alisation de la t\^{a}che 
$i.$

\item On introduit deux t\^{a}ches fictives, la t\^{a}che d\'{e}but des
travaux repr\'{e}sent\'{e}e par le sonmmet $\alpha $ et la t\^{a}che fin des
travaux repr\'{e}sent\'{e}e par le sommet $\omega ,$ ces deux t\^{a}ches
ayant chacune une dur\'{e}e nulle.

\item On relie le sommet $\alpha $ par un arc de valuation nulle \`{a} tout
sommet $i$ repr\'{e}sentant une t\^{a}che ne poss\'{e}dant pas de contrainte
d'ant\'{e}riorit\'{e}.%



\begin{center}
\begin{tikzpicture}
\SetGraphUnit{4}
\SetVertexMath
\Vertex[L=\alpha]{a}
\EA(a){i}
\Edge[style={->,bend left},label=$0$](a)(i)
\end{tikzpicture}
\end{center}



\item On relie le sommet $i$ au sommet $\omega $ par un arc de valuation 
\'{e}gale \`{a} la dur\'{e}e de la t\^{a}che $i$ si la t\^{a}che $i$ ne poss%
\`{e}de pas de contrainte de post\'{e}riorit\'{e}.
\end{enumerate}





\begin{center}
\begin{tikzpicture}
\SetGraphUnit{4}
\SetVertexMath
\Vertex{i}
\EA[L=\omega](i){w}
\Edge[style={->,bend left},label=$d_i$](i)(w)
\end{tikzpicture}
\end{center}



Indiquons tout de suite le traitement de quelques cas particuliers :

\begin{itemize}
\item La contrainte : la t\^{a}che $j$ ne peut commencer avant la moiti\'{e}
(par exemple) de la r\'{e}alisation de la t\^{a}che $i$ se repr\'{e}sente par%




\begin{center}
\begin{tikzpicture}
\SetGraphUnit{4}
\SetVertexMath
\Vertex{i}
\EA(i){j}
\Edge[style={->,bend left},label=$\frac{d_i}{2}$](i)(j)
\end{tikzpicture}
\end{center}


\item La contrainte : la t\^{a}che $j$ ne peut commencer qu'un temps $t$ apr%
\`{e}s la fin de la t\^{a}che $i$ se repr\'{e}sente par%



\begin{center}
\begin{tikzpicture}
\SetGraphUnit{4}
\SetVertexMath
\Vertex{i}
\EA(i){j}
\Edge[style={->,bend left},label=$d_i+t$](i)(j)
\end{tikzpicture}
\end{center}


\item La contrainte : la t\^{a}che $j$ ne peut commencer qu'apr\`{e}s la
date $u_{k}$ se repr\'{e}sente par 


\begin{center}
\begin{tikzpicture}
\SetGraphUnit{4}
\SetVertexMath
\Vertex[L=\alpha]{a}
\EA(i){j}
\Edge[style={->,bend left},label=$u_k$](a)(j)
\end{tikzpicture}
\end{center}



\end{itemize}

\begin{remarque}
Le graphe obtenu doit \^{e}tre sans circuit, sinon cela impliquerait qu'une t%
\^{a}che devrait de succ\'{e}der \`{a} elle m\^{e}me.
\end{remarque}

Étudions l'exemple suivant:


La r\'{e}alisation d'un projet n\'{e}cessite un certain nombre de t\^{a}ches
dont les dur\'{e}es et les contraintes d'ant\'{e}riorit\'{e} (ou de post\'{e}%
riorit\'{e}) sont les suivantes : 
\begin{equation*}
\begin{tabular}{|c|c|c|}
\hline
\textbf{T\^{a}ches} & \textbf{Dur\'{e}es} & \textbf{T\^{a}ches ant\'{e}%
rieures} \\ \hline
A & 7 & - \\ \hline
B & 3 & A \\ \hline
C & 1 & B \\ \hline
D & 8 & A \\ \hline
E & 2 & D, C \\ \hline
F & 1 & D, C \\ \hline
G & 1 & D, C \\ \hline
H & 3 & F \\ \hline
I & 2 & H \\ \hline
J & 1 & E, G, I \\ \hline
\end{tabular}%
\ 
\end{equation*}%
Pour la repr\'{e}sentation du graphe MPM associ\'{e} \`{a} la r\'{e}%
alisation de ce projet, il est fortement conseill\'{e} de tester que le
graphe est sans circuit ; le niveau affect\'{e} \`{a} chaque sommet va nous
permettre d'obtenir une repr\'{e}sentation satisfaisante rapidement.
Allons-y : on obtient 
\begin{equation*}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|}
\hline
Niveau & 0 & 1 & 2 & 1 & 3 & 3 & 3 & 4 & 5 & 6 \\ \hline
Sommets & A & B & C & D & E & F & G & H & I & J \\ \hline
Pr\'{e}c\'{e}dents &  & A & B & A & D, C & D, C & D, C & F & H & E, G, I \\ 
\hline
\end{tabular}%
\end{equation*}%
Une repr\'{e}sentation graphique MPM est alors%


%\begin{figure}
\begin{center}
  \input{../../../Thierry/Conversions/MPM8.pdf_tex}
\end{center}
%\end{figure}



Le projet commen\c{c}ant \`{a} la date $t_{\alpha }=0,$ la dur\'{e}e
minimale de r\'{e}alisation du projet est donc \'{e}gale \`{a} la longueur
des \textbf{plus longs chemins} de $\alpha $ \`{a} $\omega .$ Appliquons un
algorithme de recherche des plus longs chemins, on obtient%


%\begin{figure}
\begin{center}
  \input{../../../Thierry/Conversions/MPM9.pdf_tex}
\end{center}
%\end{figure}


La dur\'{e}e minimale de r\'{e}alisation du projet est de 22 unit\'{e}s de
temps. La marque $t_{i}$ de chaque t\^{a}che $i$ nous donne sa date de d\'{e}%
marrage au plus t\^{o}t en consid\'{e}rant, bien entendu que la t\^{a}che $%
\alpha ,$ d\'{e}but des travaux, d\'{e}bute \`{a} la date 0. Par exemple, la
date de d\'{e}marrage au plus t\^{o}t de la t\^{a}che C est 10, cela
signifie que la t\^{a}che C ne peut d\'{e}marrer qu'au minimum 10 unit\'{e}s
de temps apr\`{e}s la date de d\'{e}marrage des travaux. 



Maintenant se pose
la question \og quelle est la date de d\'{e}marrage au plus tard de chaque t%
\^{a}che ?\fg{}, c'est \`{a} dire, \og\`{a} quelle date maximale peut-on faire d%
\'{e}marrer une t\^{a}che sans augmenter la dur\'{e}e minimale des travaux\fg{}, 
\`{a} savoir, ici, 22 unit\'{e}s de temps. Notons $T_{i}$ la date de d\'{e}%
marrage au plus tard de la t\^{a}che $i,$ en imposant $t_{\omega }=22,$ nous
avons de fa\c{c}on \'{e}vidente%
\begin{equation*}
T_{i}=\limfunc{Min}\left\{ T_{j}-d_{i}\mid j\in \GR \left( \left\{
i\right\} \right) \right\}
\end{equation*}%
La marge de la t\^{a}che $i$ \'{e}tant $m_{i}=T_{i}-t_{i}.$ Les t\^{a}ches
ayant une marge nulle (celles dont la date de d\'{e}marrage au plus t\^{o}t
est \'{e}gale \`{a} la date de d\'{e}marrage au plus tard) sont appel\'{e}es
les t\^{a}ches critiques, ces t\^{a}ches ne souffrent aucun retard. Les t%
\^{a}ches critiques sont les t\^{a}ches correspondant aux sommets des plus
longs chemins de $\alpha $ \`{a} $\omega .$ Dans notre exemple les t\^{a}%
ches critiques sont les t\^{a}ches A, D, F, H, I et J. Les dates de d\'{e}%
marrage au plus tard des t\^{a}ches sont donn\'{e}es par%


%\begin{figure}
\begin{center}
  \input{../../../Thierry/Conversions/MPM10.pdf_tex}
\end{center}
%\end{figure}


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

PERT = Preview Evaluation Research Task, c'est la repr\'{e}sentation \og
am\'{e}%
ricaine\fg{}. Ici une t\^{a}che n'est pas repr\'{e}sent\'{e}e par un sommet mais
par un arc, on donne aux sommets des noms arbitraires, les sommets sont appel%
\'{e}s des \'{e}tapes. L'arc $U_{i},$ qui repr\'{e}sente la t\^{a}che $i,$ pr%
\'{e}c\`{e}de l'arc $U_{j}$ si la t\^{a}che $i$ doit \^{e}tre termin\'{e}e
avant que la t\^{a}che $j$ ne puisse commencer ; chaque arc est valu\'{e}
par la dur\'{e}e de la t\^{a}che \`{a} laquelle il correspond. Chaque \'{e}%
tape (chaque sommet) d\'{e}finit un ensemble de t\^{a}ches d\`{e}j\`{a}
effectu\'{e}es, on introduit une \'{e}tape d\'{e}but et une \'{e}tape fin.
On prend comme d\'{e}finition d'une \'{e}tape les $\GR ^{-1}\left(
\left\{ i\right\} \right) .$

Une repr\'{e}sentation PERT de l'exemple pr\'{e}c\'{e}dent donne%



%\begin{figure}
\begin{center}
  \input{../../../Thierry/Conversions/PERT1.pdf_tex}
\end{center}
%\end{figure}


La construction d'un tel graphe est un peu compliqu\'{e}e et ne se pr\^{e}te
pas bien aux cas particuliers, n\'{e}anmoins les algorithmes sont les m\^{e}%
mes.




\medskip



Étudions l'exemple suivant.

Un contrat vient d'\^{e}tre sign\'{e} pour un projet informatique. Ce projet
a \'{e}t\'{e} d\'{e}compos\'{e} en t\^{a}ches confi\'{e}es \`{a} des ing\'{e}%
nieurs et les contraintes de pr\'{e}c\'{e}dence ainsi que les dur\'{e}es des
t\^{a}ches sont pr\'{e}sent\'{e}es dans le tableau ci-dessous :%
\begin{equation*}
\begin{tabular}{|c|c|c|c|}
\hline
Rang & Libell\'{e} de la t\^{a}che & dur\'{e}e en mois & T\^{a}ches pr\'{e}%
alables \\ \hline
0 & A & 3 &  \\ \hline
1 & B & 8 & A \\ \hline
1 & C & 5 & A \\ \hline
2 & D & 1 & C, G \\ \hline
3 & E & 4 & D \\ \hline
2 & F & 2 & C \\ \hline
0 & G & 6 &  \\ \hline
\end{tabular}%
\end{equation*}%
\textbf{\ }On d\'{e}cide de repr\'{e}senter ce probl\`{e}me d'ordonnancement 
\`{a} l'aide d'un graphe par la m\'{e}thode MPM. En faisant abstraction des
deux t\^{a}ches fictives \og d\'{e}but du projet\fg{} et \og fin du projet\fg{}, nous
affectons un rang \`{a} chaque sommet dans le tableau pr\'{e}c\'{e}dent. Une
repr\'{e}sentation MPM de ce projet est :%



%\begin{figure}
\begin{center}
  \input{../../../Thierry/Conversions/CorrigeExo4CC1Mocab103-04.pdf_tex}
\end{center}
%\end{figure}



La dur\'{e}e minimale de r\'{e}alisation du projet est de 13 mois et, en
s'imposant cette dur\'{e}e minimale de r\'{e}alisation et en choisissant la
date 0 comme date de d\'{e}marrage, la date de d\'{e}marrage au plus t\^{o}t
et au plus tard de chaque t\^{a}che est donn\'{e}e par%
\begin{equation*}
\begin{tabular}{|c|c|c|}
\hline
T\^{a}che & date au plus t\^{o}t & date au plus tard \\ \hline
A & 0 & 0 \\ \hline
B & 3 & 5 \\ \hline
C & 3 & 3 \\ \hline
D & 8 & 8 \\ \hline
E & 9 & 9 \\ \hline
F & 8 & 11 \\ \hline
G & 0 & 2 \\ \hline
\end{tabular}%
\end{equation*}

Les t\^{a}ches critiques sont $A,C,D,E$\ ; tout retard d'une de ces t\^{a}%
ches augmentera la dur\'{e}e minimale des travaux.




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

Le codage de Pr\"{u}fer permet de d\'{e}crire un arbre (graphe non orient%
\'{e} connexe sans cycle simple ou acyclique) de fa\c{c}on condens\'{e}e.
Soit donc $\GR =\left( X,A\right) $ un arbre, $X$ est l'ensemble des
sommets et $A$ est l'ensemble des ar\^{e}tes. Pour appliquer le codage, il
nous faut ordonner, de fa\c{c}on quelconque, les sommets et pour cette
raison on s'impose souvent de noter les $n$ sommets par $1,2,3,...,n$, mais
on peut tout aussi bien les num\'{e}roter de $1$ \`{a} $n$ . Bien comprendre
que cet ordre n'intervient que dans le codage, il n'est en rien associ\'{e} 
\`{a} l'organisation des sommets avec les ar\^{e}tes et on ne cr\'{e}e
aucune hi\'{e}rarchie entre les sommets.

Nous appelons feuille d'un arbre un sommet dont le degr\'{e} est 1 ou, c'est
pareil, un sommet qui n'a qu'un seul voisin ou qui n'a qu'un seul sommet
adjacent.

On rappelle qu'un graphe partiel d'un graphe $\GR $ est le graphe obtenu
en supprimant des ar\^{e}tes mais en aucun cas des sommets et qu'un sous
graphe de $\GR $ est un graphe obtenu en supprimant des sommets et
uniquement les ar\^{e}tes de $\GR $ utilisant ces sommets, si $Y$ est
une partie de $X,$ le sous graphe de $\GR $ ayant pour ensemble de
sommets $Y$ est le sous graphe engendr\'{e} par $Y.$

Le codage de Pr\"{u}fer d'un arbre de $n$ sommets num\'{e}rot\'{e}s de $1$ 
\`{a} $n$ est une suite de $n-2$ entiers de l'ensemble $\left\{
1,2,...,n\right\} $, suite construite par l'agorithme suivant :


\begin{algo}
\VAR
\DECLVAR{T}{arbre courant}
\DECLVAR{S}{ensemble}
\DECLVAR{C}{suite}
\ENDVAR
\BEGIN
\STATE{T\recoit{}(X,A)}
\STATE{S\recoit{}$\emptyset$}
\STATE{C\recoit{}liste vide}
\WHILE{T contient plus de 2 sommets}
\STATE{identifier la feuille $f$ de T ayant le plus petit numéro}
\STATE{S\recoit{}$S\cup \bigl\{j\bigr\}$}
\STATE{ajouter à C le seul sommet $k$ adjacent à $j$ dans T}
\STATE{T est maintenant le sous-graphe engendré par $X-S$}
\ENDWHILE
\END
\end{algo}





Par exemple:


On consid\`{e}re l'arbre $\GR =\left( X,A\right) $ donn\'{e} par 
\begin{center}
\input{../../../Thierry/Conversions/Prufer1.pdf_tex}
\end{center}%


la premi\`{e}re it\'{e}ration nous donne $C=\left( 5\right) $ et $T$ donn%
\'{e} par%










\begin{center}
\input{../../../Thierry/Conversions/Prufer2.pdf_tex}
\end{center}%





la deuxi\`{e}me it\'{e}ration donne $C=\left( 5,5\right) $ et $T$ donn\'{e}
par 




\begin{center}
\input{../../../Thierry/Conversions/Prufer3.pdf_tex}
\end{center}%






la troisi\`{e}me it\'{e}ration donne $C=\left( 5,5,5\right) $ et $T$ donn%
\'{e} par 






\begin{center}
\input{../../../Thierry/Conversions/Prufer4.pdf_tex}
\end{center}%







la troisi\`{e}me it\'{e}ration donne $C=\left( 5,5,5,4\right) $ et $T$ donn%
\'{e} par 







\begin{center}
\input{../../../Thierry/Conversions/Prufer5.pdf_tex}
\end{center}%






l'algorithme s'arr\^{e}te puisque l'abre courant $T$ ne comporte que deux
sommets. L'arbre $\GR =\left( X,A\right) $ est cod\'{e} en $\left(
5,5,5,4\right) .$


Tout ceci n'a d'int\'{e}r\^{e}t que si \og on peut revenir en arri\`{e}re\fg{}.
Voici l'algorithme qui le permet \`{a} partir de la suite $C$ et on sait
qu'on a affaire \`{a} un arbre de $n$ sommets num\'{e}rot\'{e}s de $1$ \`{a} 
$n.$



\begin{algo}
\VAR
\DECLVAR{I}{ensemble}
\ENDVAR
\BEGIN
\STATE{I\recoit{}$\bigl\{1,2,...,n\bigr\}$}
\WHILE{il reste des éléments dans la suite C (le codage)}
\STATE{déterminer le plus petit $i$ de I n'apparaissant pas dans C}
\STATE{relier par une arête $i$ avec le sommet $j$ en tête de C}
\STATE{enlever $i$ de I et $j$ de C}
\ENDWHILE
\STATE{Les deux éléments qui restent dans I nous donnent la dernière arête}
\END
\end{algo}

Appliquons au codage $C=\left( 5,5,5,4\right) $ codage d'un arbre de $6$
sommets not\'{e}s (ou num\'{e}rot\'{e}s) de $1$ \`{a} $6.$

Le plus petit num\'{e}ro n'apparaissant pas dans la suite est $1,$ on cr\'{e}%
e donc l'ar\^{e}te $\left[ 1,5\right] ,$ $I$ devien $I=\left\{
2,3,4,5,6\right\} $ et $C$ devient $C=\left( 5,5,4\right) .$ Le plus petit
num\'{e}ro n'apparaissant pas dans $C$ est 2, on cr\'{e}e l'ar\^{e}te $\left[
5,2\right] ,$ $I$ devient $I=\left\{ 3,4,5,6\right\} $ et $C$ devient $%
C=\left( 5,4\right) .$ Le plus petit num\'{e}ro de $I$ n'apparaissant pas
dans la suite est 3, on cr\'{e}e l'ar\^{e}te $\left[ 5,3\right] .$ $I$
devient $I=\left\{ 4,5,6\right\} $ et $C$ devient $C=\left( 4\right) .$ Le
plus petit num\'{e}ro de $I$ n'apparaissant pas dans la suite $C$ est 5, on
cr\'{e}e l'ar\^{e}te $\left[ 4,5\right] ,$ $I$ devient $I=\left\{
4,6\right\} $ et $C$ devient $C=\left( \text{ }\right) .$ On cr\'{e}e en
dernier l'ar\^{e}te $\left[ 4,6\right] .$







\vfill

\eject






\section{Les graphes avec Python}

La plupart  des résultats présentés  dans cette section sont  issus d'un
merveilleux   ouvrage    qui   paraîtra   en    janvier   aux   éditions
Dunod\footnote{\og Mathématiques et programmation  en \Python - du lycée
  à   la  licence   en   passant  par   la   prépa\fg{}  par   Alexandre
  \textsc{Casamayou}, Pascal \textsc{Chauvin}, Guillaume \textsc{Connan}...}.

\subsection{Présentation}

\Python est disponible sur toute distribution GNU-Linux. C'est un
langage de très haut niveau dont la syntaxe encourage à écrire du code clair et
de qualité. Dans le domaine de la gestion de la mémoire, nombres de détails de
bas niveau de langages comme le C disparaissent. De plus l'apprentissage de \Python
est facilité par l'existence d'une interface interactive.  Ceci dit, son intérêt
ne se réduit pas à l'apprentissage de la programmation ou de l'algorithmique ;
en témoigne sa popularité croissante. Il a été choisi par des acteurs majeurs :
Google, YouTube, la NASA, etc.  Il
favorise la programmation impérative structurée et la programmation orientée
objet; dans une moindre mesure, il permet de programmer dans un style
fonctionnel. Il est doté
d'un typage dynamique fort, d'une gestion automatique de la mémoire par
ramasse-miettes et d'un système de gestion d'exceptions.  C'est un langage
multi-plateforme, polyvalent (jusque dans les domaines comme le web, les
graphiques, le réseau), open source et gratuit.

\subsubsection{fonctions}



Il est tout à fait possible de définir une fonction (au sens du langage \Python) qui
ressemble à une fonction mathématique.
La syntaxe est alors la suivante :


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

Tout d'abord, la déclaration d'une nouvelle
fonction commence par le mot-clé \verb?def?.  Ensuite, toujours sur la même
ligne,  vient le nom de la fonction (ici \verb?f?) suivi du \emph{paramètre
formel} de la fonction,  placé entre parenthèses (le paramètre
formel \verb?x? de la fonction \Python correspond ici à la variable de la fonction
mathématique), le tout ponctué de deux points.  Une fois la première ligne
saisie, on appuie sur la touche \Enter et on constate que les chevrons
de l'invite de commande ont été remplacés par des points ; cela signifie que
l'interpréteur attend obligatoirement une suite à la ligne précédente avant de
lire ce qui sera un bloc d'instruction.  Ensuite, il faut saisir quatre espaces
pour indenter la suite des instructions qui définira la fonction.
Enfin, une ligne vide signifiera à l'interpréteur que l'on a terminé de définir
notre fonction, et qu'il peut désormais lire la totalité du bloc d'instructions
qui définit notre fonction.


\subsubsection{La structure conditionnelle}

Sans surprise mais  on n'oublie pas l'indentation. On  a droit également
au classique \lstinline+elif+. 


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


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

Par exemple:

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

On remarque  au passage que le  calcul modulaire s'effectue  à l'aide de
l'opérateur binaire \%.




\subsubsection{Les listes}


C'est la structure ordonnée de base:

\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}



Quelques méthodes:

\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}

\subsubsection{Les dictionnaires}

Nous utiliserons  des dictionnaires pour définir nos  graphes. Il s'agit
de listes indexées par des objets de n'importe quel type.

Par exemple:
\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}

Une  méthode  importante est  de  pouvoir  vérifier  si le  dictionnaire
contient une entrée donnée grâce à \verb+has_key()+ et de créer la liste
des entrées avec \verb+keys+:

\begin{lstlisting}[caption={}]
>>> tel.has_key('Roger')
True
>>> tel.keys()
['Marcelle', 'Roger']
\end{lstlisting}


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




D'abord, un mot sur \lstinline+range+ :

 
\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}

Puis la boucle elle-même:


\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}


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


Avec  \Python,  on  va  définir  une  classe  d'objets  qu'on  appellera
\verb|graphe|. Le constructeur de classe de \Python s'appelle toujours
\verb|__init__| et prend au moins un argument \verb|self|.

Nous choisissons de  construire un graphe à partir  d'un dictionnaire de
d'adjacence  de  chaque sommet,  les  sommets  seront  entrés comme  des
chaînes de caractères (de type \verb|string|).


\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}

Par exemple, pour entrer le graphe suivant:





\begin{center}
\begin{tikzpicture}\label{grafpyt}
\SetGraphUnit{1.5}
\Vertices{circle}{3,2,1,4}
\EA(3){5}
\EA(5){7}\NOEA(5){6}
\Edges(3,2,1,4,3,5,7,6,5)
\end{tikzpicture}
\end{center}



on tapera:


\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}


Voici maintenant les outils de base:


\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 []


## 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

## 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

## donnele nombre de sommets d'un graphe
	def nombre_sommets(self):
		return len(self.sommets())
\end{lstlisting}

\subsection{Un peu de travail...}

\begin{enumerate}


\item Définissez une fonction \lstinline+degre_sommet(self, a)+ qui renvoie le
degré d'un sommet \texttt{a} du graphe.


Par exemple, avec le graphe précédent:

\begin{lstlisting}[caption={}]
>>> g.degre_sommet('5')
3
\end{lstlisting}




\item
Définissez une  fonction \lstinline+nombre_aretes(self)+ qui  calcule le
nombre d'arêtes du graphe.




\item On suppose à présent qu'on dispose d'une méthode donnant la
  composante connexe d'un sommet.

Écrivez une méthode donnant la  liste de toutes les composantes connexes
d'un graphe et une autre testant si un graphe est connexe.

Écrivez également une méthode testant si deux sommets d'un graphe sont connectés.


Écrivez enfin une méthode testant si une arête est un isthme.


\item On suppose qu'on dispose  d'une méthode listant toutes les chaînes
  reliant deux  sommets donnés. Écrivez  une méthode qui  recherche tous
  les cycles passant par un sommet  donné puis une autre qui teste si un
  graphe est un arbre.













\item
On aura besoin de savoir si un sommet est en queue des sous-listes d'une
liste. Définissez  une fonction \lstinline+arret(liste,s)+  qui effectue
ce test.

On devra par exemple obtenir:

\begin{lstlisting}[caption={}]
>>> ll = [[1,2,3],[4,5,3]]
>>> arret(ll,3)
True
>>> LL = [[1,2,3],[4,5,5]]
>>> arret(LL,3)
False
\end{lstlisting}








\item
Voici une méthode très importante: que fait-elle?...

\begin{lstlisting}[caption={}]
def méthode_mystérieuse_1(self, s):
    p = []
    if s in self.sommets():
        q = []
	q.append(s)
	visite = []
	visite.append(s)
	while len(q) > 0:
	    x = q.pop(0)
            p.append(x)
            for t in self.adjacents(x):
                if t not in visite:
                    q.append(t)
                    visite.append(t)
    p.sort()
    return p
\end{lstlisting}
Transformez-vous en serpent et appliquez  cette fonction au graphe~\vpageref{grafpyt}


\item 
  Voici une nouvelle méthode tout aussi mystérieuse: que fait-elle?...
  \begin{lstlisting}[caption={}]
def méthode_mystérieuse_2(self, a, b):
    ll = []
    ll.append([a])
    while not arret(ll, b):
        q = []
	for p in ll:
	    u = p[-1]
            if u == b:
                q.append(p)
            else:
                s = self.adjacents(u)
		for t in s:
		    if not (t in p):
                        v = [i for i in p]
			v.append(t)
                        q.append(v)
	ll = q
    return ll
  \end{lstlisting}

Appliquez cette  méthode toujours au  graphe~\vpageref{grafpyt} pour les
sommets 1 et 7 (i.e. \lstinline+g.méthode_mystérieuse_2('1','7')+.)







\item À  l'aide de tous les  outils précédents, écrivez  une méthode qui
  teste  l'existence d'une  chaîne eulérienne  dans un  graphe  puis une
  autre qui teste si un graphe est eulérien.


\item Analyser la méthode suivante:

  \begin{lstlisting}[caption={}]
def graphe_reduit(self, a, b):
    h = dict()
    for s in self.sommets():
        l = []
	for t in self.adjacents(s):
	    if (s != a or t != b) and (s != b or t != a):
	        l.append(t)
	if len(l) != 0:
	    h[s] = l
    return graphe(h)
  \end{lstlisting}


\item Analyser la méthode suivante:

  \begin{lstlisting}[caption={}]
def fleury(self):
    g = self
    fin = (g.nombre_aretes() == 1)
    if fin:
	return g.sommets()
    p = []
    choix = []
    for s in g.sommets():
	if g.degre_sommet(s) % 2 == 1:
	    choix.append(s)
    if len(choix) == 0:
	choix = g.sommets()
    a = choix[random.randrange(0, len(choix))]
    while not fin:
	u = g.adjacents(a)
	v = []
	for s in u:
	    if not g.est_un_pont(a, s):
		v.append(s)
            b = v[random.randrange(0, len(v))]
            p.append(a)
            g = g.graphe_reduit(a, b)
            a = b
            fin = (g.nombre_aretes() == 1)
	p.append(a)
	p.append(g.adjacents(a)[0])
	return p
  \end{lstlisting}

On a  utilisé \lstinline+random.randrange(0,n)  + qui renvoie  un entier
aléatoirement choisi entre 0 et $n-1$.


Appliquer cette  méthode au graphe  symétrique sous-jacent du  graphe de
\bsc{De  Bruijn} dessiné  \vpageref{bruijn} en  supprimant une  des deux
arêtes entre 2 et 5.

\end{enumerate}

























\modeexercice % entre en mode exercice
\section{EXERCICES}


\begin{listeexercices}




\subsection{Les bases}


\begin{exercice}
Soit $\GR=(X,A)$ un graphe simple symétrique. Montrer que $\card(A)\leqslant \frac{1}{2}\card(X)(\card(X)-1)$.
\end{exercice}

\begin{exercice}
Soit $\GR=(X,A)$ un graphe simple symétrque. 


Peut-on  avoir un sommet  de degré  0 et un  sommet de
degré $\card(X)-1$?


Montrer qu'il existe deux sommets différents
ayant le même degré.
\end{exercice}

\begin{exercice}\label{exo::circuits}
Analyser l'algorithme suivant appliqué à un graphe orienté $\GR=(X,A)$:

\begin{algo}
\VAR
\DECLVAR{i}{entier positif}
\ENDVAR
\BEGIN
\STATE{i\recoit{}1}
\WHILE{i <= nombre de sommets}
\IF{les arcs du sommet i sont tous aboutissants ou incidents}
\STATE{Effacer le sommet i et ses arcs adjacents}
\STATE{i\recoit{}i+1}
\ELSE
\STATE{i\recoit{}i+1}
\ENDIF
\END
\end{algo}

Appliquer le aux graphes suivant:

\begin{center}
\begin{tikzpicture}
\SetGraphUnit{1.5}
\Vertex{1}
\NO(1){3}
\EA(1){7}
\NOEA(1){8}
\NOEA(3){5}
\SOEA(7){4}
\EA(4){6}
\SOEA(5){2}
\tikzset{EdgeStyle/.style={->}}
\Edge(3)(1)
\Edge(5)(3)
\Edge(3)(8)
\Edge(5)(4)
\Edge(8)(7)
\Edge(7)(4)
\Edge(8)(2)
\Edge(7)(2)
\Edge(4)(6)
\end{tikzpicture}
\begin{tikzpicture}
\SetGraphUnit{1.5}
\tikzset{EdgeStyle/.style={->}}
\Vertex{1}
\EA(1){2}\EA(2){3}
\SO(1){4}\EA(4){5}\EA(5){6}\EA(6){10}
\SO(4){7}\EA(7){8}\EA(8){9}
\Edges(4,3,8,4)
\Edges(10,9,5)
\Edge[style={bend left}](5)(10)
\Edges(4,1,2)
\Edge(3)(2)
\Edge(7)(4)
\Edge(7)(8)
\Edge(9)(6)
\Edge(10)(6)
\end{tikzpicture}
\end{center}


Appliquer maintenant l'algorithme suivant aux graphes précédents:


\begin{algo}[rightmargin=1pt,
leftmargin=1pt]

\STATE{S\recoit{}$\emptyset$}
\STATE{ on  affecte le niveau  ou le rang  0 aux sommets n'ayant  pas de
  pr\'{e}c\'{e}dent}
\IF{cet ensemble de
sommets est vide} 
\BREAK[au moins un circuit]
\ENDIF
\STATE{On met dans S les sommets de degré 0}
\STATE{i\recoit{}1}
\WHILE{$S\neq X$}
\STATE{$\GR _{i}$ \ est le sous graphe engendr\'{e} par $X-S,$%
 on affecte le niveau $i$ aux sommets de $\GR _{i}$%
 n'ayant pas de pr\'{e}c\'{e}dent}
\IF{cet ensemble de sommets est vide} 
\BREAK[au moins un circuit]
\ENDIF
\STATE{On met dans S les sommets de degré $i$}
\STATE{$i ++$}
\ENDWHILE
\end{algo}


Comparer-le au précédent.


Utiliser   enfin   ce  troisième   algorithme   appliqué  aux   matrices
d'adjacences des graphes précédents:
on
supprime \`{a} chaque it\'{e}ration tous les sommets qui n'ont pas de pr\'{e}%
c\'{e}dent, c'est \`{a} dire tous ceux qui correspondent \`{a} une colonne
ne comportant que des z\'{e}ros.

\end{exercice}








\begin{exercice}
  Que pensez-vous de la réunion d'un graphe de $n$ sommets et de son complémentaire?
\end{exercice}


\begin{exercice}
\begin{enumerate}
\item Combien de sommets a un graphe régulier de degré 4 contenant 10 arêtes?
\item Pour quelles valeurs de $n$ les graphes suivant sont-ils réguliers?
\begin{multicols}{4}  
\begin{enumerate}
  \item $K_n$ \item $C_n$ \item $W_n$ \item $Q_n$
  \end{enumerate}
\end{multicols}
\end{enumerate}
\end{exercice}


\begin{exercice}
 Si un graphe a $x$ sommets et $a$ arêtes, combien d'arêtes a son complémentaire?
\end{exercice}


\begin{exercice}
Donner les matrices d'adjacence des graphes suivants:
\begin{multicols}{3}
  \begin{enumerate}
  \item $K_4$ \item $K_{1,4}$ \item $K_{2,3}$
  \item $C_4$ \item $W_4$ \item $Q_3$
  \end{enumerate}
\end{multicols}
\end{exercice}

\begin{exercice}
Dessiner un graphe correspondant aux matrices d'adjacence suivantes:
\begin{multicols}{2}
  \begin{enumerate}
  \item $
    \begin{pmatrix}
      1&1&1&0\\
      0&0&1&0\\
      1&0&1&0\\
      1&1&1&0\\
    \end{pmatrix}
$
\item
$  \begin{pmatrix}
 1&0&1\\
 0&0&1\\
 1&1&1\\
  \end{pmatrix}
$
  \end{enumerate}

\end{multicols}
\end{exercice}

\begin{exercice}
 En \Python par exemple, on peut rentrer naïvement un graphe sous forme de sa
 matrice d'adjacence à l'aide d'une liste de listes.

Déterminer un mini programme qui  détermine le degré de chaque sommet et
le nombre d'arêtes.
\end{exercice}




% \begin{exercice}
% Si l'on
% cherche  les  chemins  de  $x_{i}$  \`{a}  $x_{j}$  de  \textbf{longueur
%   minimum }  et si le  graphe a beaucoup  de sommets, la  m\'{e}thode du
% cours consistant à calculer des puissances de la matrice d'adjacence
% demandant  beaucoup   de  temps  machine   on  pr\'{e}f\`{e}re  utiliser
% l'algorithme de \textsc{Moore}:


% \textit{On va \'{e}tiqueter les sommets, }$x_{i}$ \textit{re\c{c}oit l'\'{e}%
% tiquette 0.}

% \textit{Si }$\left( u,v\right) \in A$\textit{\ et }$u$\textit{\ \'{e}tiquet%
% \'{e} par }$k$\textit{\ et }$v$\textit{\ non \'{e}tiquet\'{e} alors }$v$%
% \textit{\ re\c{c}oit l'\'{e}tiquette }$k+1.$

% \textit{Si }$\left( u,v\right) \in A$\textit{\ et }$u$\textit{\ \'{e}tiquet%
% \'{e} par }$k$\textit{\ et }$v$\textit{\ \'{e}tiquet\'{e} par }$\ell$\textit{\
% alors }$\ell$ \textit{est remplac\'{e} par }$k+1$\textit{\ si }$k+1<\ell.$

% \textit{Si \`{a} la fin }$x_{j}$\textit{\ n'a pas d'\'{e}tiquette c'est qu'il
% n'existe pas de chemin de }$x_{i}$\textit{\ \`{a} }$x_{j}$\textit{\ sinon
% son \'{e}tiquette est le nombre minimum d'arcs permettant d'aller de }$%
% x_{i}$\textit{\ \`{a} }$x_{j}.$

% Pour trouver ces chemins, on recule de $x_{j}$ \`{a} $x_{i}$ en empruntant
% les sommets ayant donn\'{e} la marque.

% Appliquer cet algorithme au graphe suivant:

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



% \end{exercice}






\subsection{Isomorphisme}


\begin{exercice}
Les graphes suivant sont-ils isomorphes?
\begin{enumerate}
\item cinq sommets:

\begin{tikzpicture}
\SetGraphUnit{1.5}
\Vertices{circle}{a,b,c,d,e}
\Edges(a,b,c,d,e,a)
\end{tikzpicture}
\begin{tikzpicture}
\SetGraphUnit{1.5}
\Vertices{circle}{1,2,3,4,5}
\Edges(1,4,2,5,3,1)
\end{tikzpicture}
\item sept sommets:

\begin{tikzpicture}
\SetGraphUnit{1.5}
\Vertices{circle}{a,b,c,d,e,f,g}
\Edges(a,b,c,d,e,f,g,a)
\end{tikzpicture}
\begin{tikzpicture}
\SetGraphUnit{1.5}
\Vertices{circle}{1,2,3,4,5,6,7}
\Edges(1,3,5,7,2,4,6,1)
\end{tikzpicture}
\end{enumerate}
\end{exercice}




\begin{exercice}
On  dit qu'un  graphe  simple est  \textbf{autocomplémentaire} s'il  est
isomorphe à son complémentaire.

Montrez que le graphe suivant est autocomplémentaire:

\begin{center}
  \begin{tikzpicture}
\SetGraphUnit{1.5}
\GraphInit[vstyle=Normal]
\Vertices{square}{a,b,c,d}
\Edges(d,a,b,c)
\end{tikzpicture}
\end{center}
\end{exercice}


\begin{exercice}
Montrer que les trois graphes suivant sont isomorphes:

\begin{center}
\begin{tikzpicture}%
\GraphInit[vstyle=Art]
\grPetersen[form=1,RA=2,RB=1]%
\end{tikzpicture}
\begin{tikzpicture}%
\GraphInit[vstyle=Art]
\grPetersen[form=2,RA=2,RB=1]%
\end{tikzpicture}
\begin{tikzpicture}%
\GraphInit[vstyle=Art]
\grPetersen[form=3,RA=2]%
\end{tikzpicture}
\end{center}
\end{exercice}






\begin{exercice}\label{exo::cycle_iso}
En comparant  certains cycles des graphes suivants,  montrer qu'ils ne
sont pas isomorphes:

\begin{center}
\begin{tikzpicture}
\SetGraphUnit{1.5}
\Vertices{circle}{1,6,5,4,3,2}
\Edges(2,1,6,5,2,3,6,5,4,3)
\end{tikzpicture}
\begin{tikzpicture}
\SetGraphUnit{1.5}
\Vertices{circle}{b,a,f,e,d,c}
\Edges(f,b,a,f,e,d,c,b,c,e)
\end{tikzpicture}
\end{center}





\end{exercice}










\subsection{Connexité}



\begin{exercice}
  Un  graphe est  connexe. Supposons  qu'il contienne  deux sous-graphes
  connexes: que peut-on dire au sujet de ces deux sous-graphes?
\end{exercice}


\subsection{Euler et Hamilton}

\begin{exercice}
  Le mathématicien français Édouard \textsc{Lucas} en 1891
  rapporta  dans ses  \textit{récréations mathématiques}  (disponibles à
  cette adresse: \href{http://gallica.bnf.fr/ark:/12148/bpt6k3943s/f61.table}{http://gallica.bnf.fr/ark:/12148/bpt6k3943s/f61.table}): \og je me suis
  laissé dire que Mahomet
  dessinait  d'un  seul  coup,  avec  la pointe  de  son  cimeterre,  sa
  signature formée de deux croissants opposés\fg{} 


%\begin{figure}
\begin{center}
  \includegraphics[width=0.7\linewidth]{mahomet}
\end{center}
%\end{figure}


Est-ce possible?
\end{exercice}


\begin{exercice}
Combien y a-t-il de cycles hamiltoniens dans le cube:

\begin{center}
  \begin{tikzpicture}
\GraphInit[vstyle=Art]
\grCubicalGraph[RA=2,RB=1]
  \end{tikzpicture}
\end{center}



Imaginer un algorithme qui les compte.

Combien y a-t-il de \og formes\fg{}?

\end{exercice}

\begin{exercice}
Les graphes complets $K_n$ ont-ils des cycles hamiltoniens? Combien?
\end{exercice}


\begin{exercice}[Graphe de \textsc{Petersen}]
Le voici:

\begin{center}
\begin{tikzpicture}%
%\GraphInit[vstyle=Art]
\grPetersen[form=1,RA=2,RB=1]%
\end{tikzpicture}
\end{center}

Il s'agit de montrer que ce graphe n'est pas hamiltonien.

Voici un début de raisonnement.

Supposons qu'il existe un cycle $\CR$ hamiltonien.

Il  faut absolument pouvoir  relier le  pentagone extérieur  et l'étoile
intérieure.   On   doit   donc   emprunter   par   exemple   l'arête   $
\bigl\{a0,b0\bigr\}$  (à   une  symétrie  près,   on  ne  perd   pas  de
généralité).


Pour inclure le  sommet $a0$ dans notre cycle, il  faut donc choisir une
des arêtes  $ \bigl\{a0,a1\bigr\}$ ou $  \bigl\{a0,a4\bigr\}$. Prenons $
\bigl\{a0,a1\bigr\}$ sans perdre de généralité par symétrie.

L'arête  $ \bigl\{a0,a4\bigr\}$  n'est donc  pas utilisée:  pour inclure
$a4$   dans  le   cycle,  il   faut  donc   utiliser  les   deux  arêtes
$\bigl\{a4,a3\bigr\}$ et $ \bigl\{a4,b4\bigr\}$

Redessiner  alors  le  graphe  en  effaçant  les  arêtes  éliminées,  en
dessinant en  trait plein les  arêtes incluses et en  pointillées celles
qui sont encore candidates.

Terminer alors le raisonnement.


\subsection{Plus court chemin}

\begin{exercice}
On considère  un graphe pondéré \texttt{(X,A)}, \texttt{a}  un sommet de
ce graphe et \texttt{p(u,v)} le poids de l'arête $ \bigl\{u,v\bigr\}$.

  Que fait cet algorithme?
\renewcommand{\algotextfont}{\small\ttfamily\upshape}

  \begin{algo}[rightmargin=5pt,
leftmargin=10pt]

\BEGIN
\FORGEN{tout s de X}
\STATE{d(s)\recoit{} p(a,s)}
\STATE{chaîne\recoit{} a}
\ENDFOR
\STATE{Marquer a}
\WHILE{$\exists$ des sommets non marqués}
\STATE{u \recoit{} sommet libre de distance à a mini}
\STATE{Marquer u}
\FORGEN{v non marqué et $\{u,v\}\in A$}
\STATE{dd\recoit{} d(u)+p(u,v)}
\IF{dd<d(v)}
\STATE{d(v)\recoit{}dd}
\STATE{chaîne(v)\recoit{}chaîne(u),v}
\ENDIF
\ENDFOR
\ENDWHILE
\END
  \end{algo}
\end{exercice}

\end{exercice}


\begin{exercice}[Algorithme de \textsc{Bellman-End-Ford}]

Cette  fois, il s'agit  d'un algorithme  dû à  Richard \textsc{Bellman},
Samuel \textsc{End} et  Lester \textsc{Ford}, mathématiciens américains,
qui permet de trouver le plus court chaîne dans un arbre orienté pondéré connexe
ayant des poids éventuellement négatifs.


En voici une présentation qui donne la longueur
des plus courts chaînes du sommet 1 
\`{a} tous les autres dans un graphe orient\'{e} $\GR =\left( X,A\right) $
pouvant avoir des valuations n\'{e}gatives ou qui d\'{e}tecte s'il existe un
circuit de longueur n\'{e}gative. On note $X=\left\{ 1,2,..,i,...\right\} $
et $\GR _{i}^{-1}$ l'ensemble des pr\'{e}c\'{e}dents du sommet $i.$

\begin{enumerate}
\item On pose $\pi ^{0}\left( 1\right) =0$, $\pi ^{0}\left( i\right)
=+\infty $ pour les autres sommets et $k=1$ ;

\item \`{a} l'it\'{e}ration $k,$ faire $\pi ^{k}\left( 1\right) =0$ et pour
tous les autres sommets poser%
$$
\pi ^{k}\left( i\right) =\min \left( \pi ^{k-1}\left( i\right) ,\underset{%
j\in \GR _{i}^{-1}}{\min }\left( \pi ^{k-1}\left( j\right)
+p_{j,i}\right) \right)
$$
\begin{enumerate}
\item si $\pi ^{k}\left( i\right) =\pi ^{k-1}\left( i\right) $ pour tout $i$
alors FIN ;

\item si $k\leq n-1$ aller en 2 avec $k\longleftarrow k+1$ ;

\item si $k=n,$ il existe un circuit de longueur n\'{e}gative.
\end{enumerate}
\end{enumerate}

On consid\`{e}re le graphe orient\'{e} pondéré $\GR =\left( X,A\right) $%
\ d\'{e}fini par la repr\'{e}sentation graphique suivante:%



\begin{center}
\begin{tikzpicture}
\SetGraphUnit{2.2}
\Vertices{circle}{5,4,2,1,3,6}
\tikzset{EdgeStyle/.style={->}}
\Edge[label=$7$](1)(2)
\Edge[label=$1$](1)(3)
\Edge[label=$-2$](3)(2)
\Edge[label=$7$](3)(6)
\Edge[label=$2$](3)(5)
\Edge[label=$-1$](6)(5)
\Edge[label=$5$](5)(4)
\Edge[label=$-2$](5)(2)
\Edge[style={bend right},label=$2$](2)(6)
\Edge[label=$4$](2)(4)
\end{tikzpicture}
\end{center}





Rechercher les plus courts chaînes du sommet 1 aux autres sommets en
utilisant \textbf{obligatoirement} l'algorithme de Bellman. Il vous est
demand\'{e} de donner votre r\'{e}sultat en remplissant le tableau suivant:%
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
$k$ & $i$ & \textbf{1} & \textbf{2} & \textbf{3} & \textbf{4} & \textbf{5} & 
\textbf{6} \\ \hline
\ 0 \  & $\pi ^{0}\left( i\right) $ & \ 0 \ \  & $+\infty $ & $+\infty $ & $%
+\infty $ & $+\infty $ & $+\infty $ \\ \hline
1 & $\pi ^{1}\left( i\right) $ & \ 0 \ \  & \ \ \ \ \  & \ \ \ \ \  & \ \ \
\ \  & \ \ \ \ \  & \ \ \ \ \  \\ \hline
2 & $\pi ^{2}\left( i\right) $ & \ 0 \ \  &  &  &  &  &  \\ \hline
3 & $\pi ^{3}\left( i\right) $ & \ 0 \ \  &  &  &  &  &  \\ \hline
4 & $\pi ^{4}\left( i\right) $ & \ 0 \ \  &  &  &  &  &  \\ \hline
5 & $\pi ^{5}\left( i\right) $ & \ 0 \ \  &  &  &  &  &  \\ \hline
6 & $\pi ^{6}\left( i\right) $ & \ 0 \ \  &  &  &  &  &  \\ \hline
\end{tabular}%
\end{center}%
Donner votre conclusion.








\end{exercice}




\begin{exercice}
D\'{e}terminer les longueurs des plus courts chemins (s'ils existent) du sommet 1 aux autres
sommets en  utilisant un algorithme  du cours (Bellman ou  Dijkstra). Il
vous est demand\'{e} 
de remplir des tableaux. Il est possible que le nombre de lignes du tableau
soit plus grand que n\'{e}cessaire.


\begin{center}
\begin{tikzpicture}
\SetGraphUnit{2.2}
\Vertices{circle}{5,4,2,1,3,6}
\tikzset{EdgeStyle/.style={->}}
\Edge[label=$7$](1)(2)
\Edge[label=$1$](1)(3)
\Edge[label=$-2$](3)(2)
\Edge[label=$7$](3)(6)
\Edge[label=$2$](3)(5)
\Edge[label=$-1$](6)(5)
\Edge[label=$5$](5)(4)
\Edge[label=$-2$](5)(2)
\Edge[style={bend right},label=$2$](2)(6)
\Edge[label=$4$](2)(4)
\end{tikzpicture}
%
\begin{tikzpicture}
\SetGraphUnit{2.2}
\Vertices{circle}{5,4,2,1,3,6}
\tikzset{EdgeStyle/.style={->}}
\Edge[label=$7$](1)(2)
\Edge[label=$1$](1)(3)
\Edge[label=$2$](3)(2)
\Edge[label=$7$](3)(6)
\Edge[label=$2$](3)(5)
\Edge[label=$2$](5)(6)
\Edge[label=$5$](5)(4)
\Edge[label=$2$](5)(2)
\Edge[style={bend right},label=$1$](2)(6)
\Edge[label=$4$](2)(4)
\end{tikzpicture}
%
\begin{tikzpicture}
\SetGraphUnit{2.2}
\Vertices{circle}{5,4,2,1,3,6}
\tikzset{EdgeStyle/.style={->}}
\Edge[label=$7$](1)(2)
\Edge[label=$1$](1)(3)
\Edge[label=$5$](3)(2)
\Edge[label=$7$](3)(6)
\Edge[label=$2$](3)(5)
\Edge[label=$1$](6)(5)
\Edge[label=$2$](5)(4)
\Edge[label=$4$](5)(2)
\Edge[style={bend right},label=$1$](2)(6)
\Edge[label=$2$](4)(2)
\end{tikzpicture}
%
\begin{tikzpicture}
\SetGraphUnit{2.2}
\Vertices{circle}{5,4,2,1,3,6}
\tikzset{EdgeStyle/.style={->}}
\Edge[label=$7$](1)(2)
\Edge[label=$1$](1)(3)
\Edge[label=$5$](3)(2)
\Edge[label=$7$](3)(6)
\Edge[label=$2$](3)(5)
\Edge[label=$-1$](6)(5)
\Edge[label=$-2$](5)(4)
\Edge[label=$4$](5)(2)
\Edge[style={bend right},label=$1$](2)(6)
\Edge[label=$1$](4)(2)
\end{tikzpicture}
%
\begin{tikzpicture}
\SetGraphUnit{2.2}
\Vertices{circle}{5,4,2,1,3,6}
\tikzset{EdgeStyle/.style={->}}
\Edge[label=$7$](1)(2)
\Edge[label=$1$](1)(3)
\Edge[label=$5$](3)(2)
\Edge[label=$7$](3)(6)
\Edge[label=$2$](3)(5)
\Edge[label=$-1$](6)(5)
\Edge[label=$-2$](5)(4)
\Edge[label=$4$](5)(2)
\Edge[style={bend right},label=$1$](2)(6)
\Edge[label=$2$](4)(2)
\end{tikzpicture}
\end{center}


\end{exercice}














\subsection{Coloration}

  \begin{exercice}
    \begin{enumerate}
    \item D\'{e}terminer le graphe aux ar\^{e}tes du graphe
suivant (on a donn\'{e} un nom \`{a} chaque ar\^{e}te) :%

\begin{center}
\input{../../../Thierry/Conversions/ColorationArete.pdf_tex}
\end{center}


\item  Quatre professeurs P1, P2, P3$,$ P4 doivent donner
des heures (1 heure par classe) de cours \`{a} 3 classes C1, C2, C3, les
affectations sont donn\'{e}es par le tableau : 
$$
\begin{tabular}{|c|c|c|c|c|}
\hline
& P1 & P2 & P3 & P4 \\ \hline
C1 & oui &  & oui & oui \\ \hline
C2 & oui & oui &  & oui \\ \hline
C3 &  & oui &  & oui \\ \hline
\end{tabular}%
\ 
$$%
On se pose la question : \og Quel nombre minimum d'heures faut-il pour
dispenser tous les cours ?\fg{}. Il est \'{e}vident qu'un professeur ne peut pas
faire cours \`{a} plus d'une classe dans un m\^{e}me cr\'{e}neau horaire et
qu'une classe ne peut pas avoir cours avec plus d'un prof au m\^{e}me moment
.Il vous est demand\'{e} de transformer ce probl\`{e}me en un probl\`{e}me
de coloration d'un graphe, vous indiquerez donc sur quel graphe le travail
va se faire et vous repr\'{e}senterez ce graphe en expliquant clairement la
notation que vous utiliserez pour nommer les sommets et le pourquoi des ar%
\^{e}tes ; vous pr\'{e}ciserez aussi si c'est une recherche de coloration
des sommets ou des ar\^{e}tes (une coloration doit \^{e}tre \textbf{ici} un
cr\'{e}neau horaire, par exemple rouge = 8h-9h, etc.)
\end{enumerate}



  \end{exercice}



\subsection{Exercices divers}

% \end{listeexercices}




% \section{Exercices supplémentaires sur les graphes}


% \begin{listeexercices}




\begin{exercice}[plus court chemin]
  La distance $\dd(x,y)$ est la  longueur d'une plus courte chaîne entre
  les sommets  $x$ et $y$ si une  telle chaîne existe (sinon  on la note
  $\infty$).

Étant  donné  un sommet  $s$  d'un graphe,  à  l'aide  d'un parcours  en
largeur, écrivez un algorithme qui donne $\dd(s,x)$ pour tout sommet $x$
du graphe.

Voici un début possible:

\begin{algo}
\FORGEN{ tout $x\in X$}
\STATE{d[$ x$]\recoit{}$\infty$}
\ENDFOR
\STATE{d[$ s$]\recoit{}0}
...
\end{algo}



\end{exercice}














  \begin{exercice}[fermeture transitive]
Montrer  que la  méthode vue  en cours  revient à  utiliser l'algorithme
suivant,  si on note  $(m_{ij})$ la  matrice booléenne  d'incidence d'un
graphe donné:

\begin{algo}
\FOR{k}{1}{n}
\FOR{j}{1}{n}
\FOR{i}{1}{n}
\STATE{$m_{ij}$\recoit{}$m_{ij}+m_{ik}\times m_{kj}$}
\ENDFOR
\ENDFOR
\ENDFOR
\end{algo}
  \end{exercice}



  \begin{exercice}[graphe biparti]
  
Une bipartition du graphe $\GR =\left( X,A\right) $ est une paire $\left(
Y,Z\right) $ o\`{u} 
\[
\begin{tabular}{c}
$\emptyset \neq Y\subseteq X,\emptyset \neq Z\subseteq X,Y\cap Z=\emptyset $
\\ 
$\mathcal{P}_{2}\left( Y\right) \cap A=\emptyset ,\mathcal{P}_{2}\left(
Z\right) \cap A=\emptyset $%
\end{tabular}%
\]%
Cela signifie que $\left\{ Y,Z\right\} $ est une partition de $X$ et toute ar%
\^{e}te de $A$ a une de ses extr\'{e}mit\'{e}s dans $Y$ et l'autre dans $Z.$
Un graphe est dit biparti s'il admet une bipartition. Le graphe
suivant est biparti :%

\begin{center}
\input{../../../Thierry/Conversions/Biparti1.pdf_tex}
\end{center}




On le note $\GR =\left( Y,Z,A\right) .$


Si $Y$ a$\ p$ \'{e}l\'{e}ments et $Z$ a $q$ \'{e}l\'{e}ments, le graphe
biparti $\GR =\left( Y,Z,A\right) $ est souvent not\'{e} $%
K_{pq}=K_{qp}$

\begin{enumerate}

\item D\'{e}montrer qu'un graphe biparti n'admet pas de cycle de longueur impaire.

\item Donner une bipartition du graphe suivant :%


\begin{center}
\input{../../../Thierry/Conversions/ArbreDessin.pdf_tex}
\end{center}





\item Donner un graphe biparti qui n'est pas un arbre.

\item En admettant qu'un arbre (non orient\'{e}, c'est sous entendu ici) est forc%
\'{e}ment un graphe biparti, donner un algorithme \textbf{CLAIR }qui donne
une bipartition :%
\[
\begin{tabular}{l}
$\text{en entr\'{e}e : l'arbre }\GR =\left( X,A\right) $ \\ 
$\text{en sortie : une bipartition }\left( Y,Z\right) $%
\end{tabular}%
\]

\end{enumerate}
\end{exercice}


% \end{listeexercices}








% \section{Exercices supplémentaires sur les graphes}


% \begin{listeexercices}



  \begin{exercice}[séquence de De Bruijn]


Nicolaas \textsc{De Bruijn} (\og  de breuyne\fg{}), encore un hollandais,
a réfléchi en  1946 au problème suivant même s'il  avait déjà été résolu
cinquante ans auparavant par Camille\textsc{ Flye Sainte-Marie}.

Le problème est  simple: vous revenez d'un tonus et  vous avez oublié le
code de la porte de  votre appartement que vous aviez pourtant vous-même
mis au point à partir. Il s'agit  en fait d'un code de quatre chiffres à
choisir parmi 0, 1 et 2.

Combien y a-t-il de codes possibles?

Vérifier  qu'il  faut a  priori  appuyer 324  fois  sur  les touches  du
digicode.

Notre ami hollandais a en  fait montré qu'il suffisait d'appuyer sur les
84 touches suivantes:

$00001002101112002201022110101212212012222000200\\
1202221001102011220202121121021111000$

Pourquoi à votre avis?

Pour  faire  plus simple  et  plus  habituel,  considérons à  partir  de
maintenant que nous travaillons sur des codes binaires de longueur $n$.

Combien y a-t-il de codes possibles?

Explorez la situation pour $n=2$ en essayant de donner une séquence de 5
chiffres qui réponde au problème.


L'idée, qui  vient de \textsc{Flye Sainte-Marie} est  de travailler dans
$\bbz/2^n\bbz$.

On part de 0 et on  construit récursivement un arbre en passant au choix,
si la  feuille actuelle vaut  $x$, à $2x$  ou à $2x+1$ modulo  $2^n$. Il
s'avère qu'on parcourt ainsi tout $\bbz/2^n\bbz$.

Essayez dans les cas simples $n=2$ puis $n=3$.
Vous construirez  un arbre  de racine 0,  chaque n\oe ud  admettant deux
successeurs. Si on retombe sur un nombre déjà présent sur la branche, on
\og coupe\fg{} cette branche.


Si nous considérons le graphe orienté dont les sommets sont numérotés de
0 à  $2^{n-1}$ et tel qu'à  partir de chaque sommet $x$ partent deux arêtes
vers les  sommets $2x$  et $2x+1$ (modulo  $2^n$!), il s'agit  de savoir
s'il existe un cycle hamiltonien.

Vérifier  que  l'arbre  que  vous  avez tracé  précédemment  pour  $n=3$
correspond au graphe suivant (que nous noterons $G_3$):



\begin{center}
  \begin{tikzpicture}
     \SetGraphUnit{1.5}
\Vertex[L=000]{0}
\SOEA[L=001](0){1}
\SOWE[L=100](0){4}
\SOWE[L=010](1){2}
\SO[L=101](2){5}
\SOEA[L=011](5){3}
\SOWE[L=110](5){6}
\SOEA[L=111](6){7}
\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}


Il reste à trouver un chemin hamiltonien...

En fait, une propriété fort plaisante que nous admettrons nous donne une
méthode fort pratique:

\textit{À chaque circuit eulérien  de $G_n$ correspond un cycle hamiltonien
de $G_{n+1}$}


Comparez  tout d'abord  le  nombre d'arêtes  de  $G_n$ et  le nombre  de
sommets de $G_{n+1}$.

Dessinez $G_2$. Numérotez l'arête $(ab,bc)$ par $abc$. Remarques? Conclusion?

  \end{exercice}

% \subsection{Graphes assistés par \Sage}

% \begin{exercice}[assignation de tâches]


% Nous sommes dans la situation suivante: en face d'un important chantier,
% 10 personnes  doivent effectuer un total de  10 tâches. Malheureusement,
% aucun  individu   n'a  les  compétences  nécessaires   pour  toutes  les
% effectuer. On  peut associer à chacun  une sous-liste de  tâches dont il
% peut se  charger. Comment distribuer les  travaux de afin  que tout soit
% fait dans les règles de l'art ?  

% Nous commencerons par modéliser le problème par un graphe: il
% sera   biparti,    défini   sur   l'union    $\{w_0,\dots,   w_{9}\}\cup
% \{t_0,\dots,t_{9}\}$ des travailleurs et  des tâches, et nous définirons
% $t_i$ comme adjacent à $w_j$ si $w_j$ est capable d'effectuer $t_i$. 

%  \begin{center}
%     \begin{footnotesize}
%       \begin{tabular}{rl}
%         Travailleurs&Tâches possibles\\
%         \hline
%         $w_0$&$ \left\{2, 3, 5, 7\right\}$\\
%         $w_1$&$ \left\{0, 1, 4\right\}$\\
%         $w_2$&$ \left\{0, 4, 5\right\}$\\
%         $w_3$&$ \left\{0, 1\right\}$\\
%         $w_4$&$ \left\{8\right\}$\\
%         $w_5$&$ \left\{2\right\}$\\
%         $w_6$&$ \left\{8, 9, 7\right\}$\\
%         $w_7$&$ \left\{8, 5, 7\right\}$\\
%         $w_8$&$ \left\{2, 3, 4, 5, 6\right\}$\\
%         $w_9$&$ \left\{8, 1, 2, 5, 6\right\}$\\
%       \end{tabular}
%     \end{footnotesize}
%   \end{center}

% Sous \Sage:

% \begin{lstlisting}[caption={}]
%   sage: tasks = {0: [2, 5, 3, 7],\
%   ...     1: [0, 1, 4], \
%   ...     2: [5, 0, 4], \
%   ...     3: [0, 1], \
%   ...     4: [8], \
%   ...     5: [2], \
%   ...     6: [8, 9, 7], \
%   ...     7: [5, 8, 7], \
%   ...     8: [2, 5, 3, 6, 4], \
%   ...     9: [2, 5, 8, 6, 1]}
%   sage: G = Graph()
%   sage: for i in tasks:
%   ...     G.add_edges( ("w"+str(i), "t"+str(j)) for j in tasks[i] )
% \end{lstlisting}

% Il   ne  nous   reste   plus  maintenant   qu'à   utiliser  la   méthode
% \texttt{matching}, qui nous retournera un ensemble maximum de tâches qui
% peuvent être effectuées simultanément par des travailleurs compétents.


% \begin{lstlisting}[caption={}]
%   sage: for task,worker,_ in sorted(G.matching()):
%   ...     print task+" peut être effectuée par "+str(worker)
%   t0 peut être effectuée par w2
%   t1 peut être effectuée par w3
%   t2 peut être effectuée par w5
%   t3 peut être effectuée par w8
%   t4 peut être effectuée par w1
%   t5 peut être effectuée par w7
%   t6 peut être effectuée par w9
%   t7 peut être effectuée par w0
%   t8 peut être effectuée par w4
%   t9 peut être effectuée par w6
% \end{lstlisting}



  \begin{exercice}
    
  \end{exercice}

  \begin{exercice}
    
  \end{exercice}

  \begin{exercice}
    
  \end{exercice}

  \begin{exercice}
    
  \end{exercice}

% \end{exercice}


\vfill

\eject




 \subsection{Exercices supplémentaires sur les graphes}











  \begin{exercice}[Vocabulaire]
On consid\`{e}re le graphe non orient\'{e} suivant : $\GR =\left(
X,A\right) $:



\begin{center}
  \begin{tikzpicture}
    \SetGraphUnit{2}
\Vertices{circle}{7,5,6,2,1,3,4}
\Edges(7,5,6)
\Edges(1,3,2,1,4)
  \end{tikzpicture}
\end{center}


\begin{enumerate}
\item D\'{e}terminer $X$\ et $A.$

\item D\'{e}terminer le degr\'{e} de chaque sommet.

\item D\'{e}terminer sa matice d'adjacence (on a ordonn\'{e}
les sommets par num\'{e}ros croissants).

\item Donner un graphe partiel de $\GR .$

\item Donner un sous graphe de $\GR .$

\item D\'{e}terminer le sous graphe engendr\'{e} par la partie $Y=\left\{
1,2,3,5\right\} .$

\item D\'{e}terminer une chaîne simple de longueur 3 qui n'est pas un
cycle, est-elle \'{e}l\'{e}mentaire ?

\item D\'{e}terminer les cycles.

\item Donner des parties connexes et non connexes

\item Donner les composantes connexes de $\GR .$
\end{enumerate}


  \end{exercice}


\begin{exercice}[Vocabulaire]
\begin{enumerate}
\item Donner un graphe non orient\'{e} qui admet des cycles non \'{e}%
l\'{e}mentaires.

\item Donner un graphe non orient\'{e} qui n'admet pas de chemin fermé simple.
\end{enumerate}

\end{exercice}




  \begin{exercice}[Vocabulaire]
    
Soit $\GR =\left( X,A\right) $ le graphe orient\'{e} dont voici un
diagramme sagittal :%


\begin{center}
  \begin{tikzpicture}
    \SetGraphUnit{2}
\Vertices{circle}{6,7,2,1,3,5}
\WE(6){4}
\tikzset{EdgeStyle/.style={->}}
\Edges(4,7,6,4)
\Edge(2)(4)
\Edge(1)(4)
\Edge[style={bend left}](4)(5)
\Edge[style={bend left}](5)(4)
\Edge[style={bend left}](1)(2)
\Edge[style={bend left}](2)(1)
  \end{tikzpicture}
\end{center}




\begin{enumerate}
\item Pr\'{e}ciser $X$ et $A.$

\item Donner les suivants ou les successeurs du sommet 2.

\item Donner les suivants ou les successeurs du sommet 4.

\item Donner les voisins du sommet 4.

\item Les sommets 5 et 6 sont-ils adjacents ?

\item Les sommets 6 et 7 sonts-ils adjacents ?

\item Donner les pr\'{e}d\'{e}cesseurs du sommet 4.

\item Donner la matrice d'adjacence   de ce
graphe (on a d\'{e}cid\'{e} d'ordonner les sommets par num\'{e}ros
croissants).

%\item Donner la matrice d'incidence sommets arcs, il est bien \'{e}vident
%qu'on commencera par ordonner les arcs.

\item Donner le dictionnaire des pr\'{e}décesseurs,
et celui des successeurs.

\item Donner le sous-gaphe de $\GR $ engendr\'{e} par la partie $\left\{
4,5,7\right\} .$

\item Donner un sous-graphe partiel de $\GR $ engendr\'{e} par la partie $%
\left\{ 4,5,7\right\} .$

\item Donner le sous-graphe engendr\'{e} par la partie $\left\{
2,4,5,6\right\} .$

\item Donner le sous graphe engendr\'{e} par la partie $\left\{ 3\right\} .$

\item Donner un sous-graphe partiel engendr\'{e} par la partie $\left\{
1,4,6\right\} .$

%\item Donner des arcs adjacents, non adjacents.

\item $\GR $ admet-il des sommets isolés ?

\item $\GR $ est-il un graphe complet ?

\item D\'{e}terminer $\GR \left( \left\{ 4,6\right\} \right) ,\GR
^{-1}\left( \left\{ 4,6\right\} \right) ,\GR ^{3}\left( \left\{ 4\right\}
\right) ,\GR \left( \left\{ 3\right\} \right) .$

\item D\'{e}terminer le  degr\'{e} d'entrée puis le  degr\'{e}
de sortie de chaque sommet.

\item Donner un graphe isomorphe \`{a} $\GR .$

\item Donner des chaînes et  des chemins quelconques, des chaînes et des
  chemins simples, des  chaînes et des chemins non  simples, des chaînes
  et des chemins \'{e}l\'{e}mentaires, non \'{e}l\'{e}%
mentaires, des cycles \'{e}l\'{e}mentaires, non \'{e}l%
\'{e}mentaires, des circuits.


\item Donner tous les descendants du sommet 4.

\item Donner tous les ascendants du sommet 2.

\item On note $$\GR ^{+}\left( \left\{ 2\right\} \right)
=\displaystyle\bigcup\limits_{k=1}^{+\infty }\GR ^{k}\left( \left\{ 2\right\} \right) 
 \text{\ et \ } \GR ^{\ast }\left( \left\{ 2\right\} \right)
=\displaystyle\bigcup\limits_{k=0}^{+\infty }\GR ^{k}\left( \left\{ 2\right\} \right)
$$ D\'{e}terminer ces deux ensembles.



\item $\GR $ est-il connexe ? Fortement connexe ? Pr\'{e}ciser les
parties fortement connexes maximales de $\GR $.

\item $\GR ^{^{\prime }}=\left( X^{\prime }=X-\left\{ 3\right\} ,A\cap
\left( X^{\prime }\times X^{\prime }\right) \right) $ admet-il des circuits
eul\'{e}riens ? Des circuits hamiltoniens ?

\end{enumerate}







  \end{exercice}














   \begin{exercice}
     Dans  un  réseau d'ordinateur,  chaque  ordinateur est  directement
     relié  à au plus  trois ordinateurs.  Depuis chaque  ordinateur, il
     existe un  chemin vers tout autre ordinateur  comportant au maximum
     un relais. Combien d'ordinateurs contient au maximum le réseau?
   \end{exercice}


   \begin{exercice}
     Dans un  réseau il  y a  9 ordinateurs, chacun  étant relié  par un
     câble à au  moins 3 autres ordinateurs. Combien  faut-il au minimum
     prévoir de câbles? %14
   \end{exercice}

\begin{exercice}[cubes]
    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}

   \begin{exercice}[reconnaître un graphe connexe]
     Soit $\GR=(X,E)$  un graphe symétrique ayant  $n$ sommets et
     tel  que  chaque  sommet  ait  un  degré au  moins  supérieur  à  $
     d_0=\frac{n-1}{2}$.

     \begin{enumerate}
     \item Considérer un sommet quelconque $x$ et noter $V_x=\Gamma(x)\cup           \bigl\{x\bigr\}$montrer que $
       \card\left(V_x\right)\geqslant\frac{n+1}{2}$.
\item Considérer $ Y=X \backslash  V_x$. Montrer que son cardinal est au
  plus $\frac{n-1}{2}$. Que représente \og concrètement\fg{} Y?
\item En déduire que $\GR$ est connexe.
     \end{enumerate}

   \end{exercice}



   \begin{exercice}
Soit       $\GR_n=(X_n,A_n)$      un       graphe       simple      avec
$X_n=\bigl\{1,2,...,n\bigr\}$. 

Les sommets $i$  et $j$ sont adjacents si, et  seulement si, les entiers
$i$ et $j$ sont premiers entre eux.

Donnez les matrices d'adjacences (dans l'ordre croissant des sommets) de
$\GR_4$ et $\GR_6$ ainsi que des représentations de ces graphes.


     
   \end{exercice}


   \begin{exercice}[nombre d'arêtes]
     Combien  d'arêtes au maximum  contient un  graphe simple  ayant $n$
     sommets?

Combien  y  a-t-il  de  graphes  non  isomorphes (on  dit  aussi  \og  à
isomorphisme près\fg{}) ayant 10 sommets  et 44 arêtes? 10 sommets et 43
arêtes?


Combien y  a-t-il de graphes  de $n$ sommets étiquetés?  Combien d'entre
eux ont $m$ arêtes?
   \end{exercice}



   \begin{exercice}[cycles]
      \begin{center}
  \begin{tikzpicture}
\SetGraphUnit{1.5}
\Vertex{1}
\NOEA(1){5}
\SOEA(1){2}
\SOWE(2){4}
\SOEA(4){3}
\Edges(2,1,5,2,3,4,2)
\end{tikzpicture}
\end{center}

Trouvez tous les cycles de ce graphe.

Peut-on avoir un cycle dans un graphe ayant deux arêtes? Une arête?

Et si l'on précise que le graphe est simple?
\end{exercice}





\begin{exercice}[graphes réguliers]
On s’intéresse aux graphes dont tous les sommets sont de degré trois.
Construisez de tels graphes ayant 4, 5, 6 ou 7sommets.
Remarque? Preuve?

Et pour les graphes 4-réguliers?
\end{exercice}

\begin{exercice}
Montrez que dans un groupe de six personnes, il y en a nécessairement trois qui se connaissent mutuellement ou trois qui ne se connaissent pas (on suppose que si A connaît B, B connaît également A).

\textit{Considérez une personne qui en connaît trois autres puis le cas contraire}.
\end{exercice}

\begin{exercice}
  Montrez  que  dans  un groupe  de  personnes,  il  y a  toujours  deux
  personnes ayant le même nombre d’amis présents.

\textit{Cet exercice a déjà été traité auparavant...sous une autre forme}
\end{exercice}






\begin{exercice}[modélisation et graphe biparti]
  Une chèvre, un chou  et un loup se trouvent sur la  rive d’un fleuve ;
  un passeur souhaite  les transporter sur l’autre rive  mais, sa barque
  étant trop petite, il ne peut  transporter qu’un seul d’entre eux à la
  fois. Comment doit-il  procéder afin de ne jamais  laisser ensemble et
  sans surveillance  le loup  et la  chèvre, ainsi que  la chèvre  et le
  chou ?

\textit{Deux rives, un couple (RG,RD) à chaque sommet d'un graphe}
\end{exercice}


\begin{exercice}[algorithme mystérieux]
  Que fait l'algorithme suivant sur un graphe simple symétrique $\GR=(X,A)$:
  \begin{algo}
    \STATE{Y\recoit{}X}
\STATE{Choisir un sommet $x$ et le marquer d'un $+$}
\WHILE{Y non vide}
\STATE{Choisir un sommet $y$ marqué dans Y}
\STATE{Marquer tous ses voisins avec le signe opposé}
\IF{ un sommet reçoit deux signes opposés}
\BREAK[sortie de la boucle Tant Que : le graphe n'est pas...]
\ENDIF
\STATE{Y\recoit{}$Y-\{y\}$}
  \end{algo}
Si chque sommet a reçu un seul signe alors $\GR$ est...
\end{exercice}



\begin{exercice}[algorithme mystérieux bis]
On considère  un graphe $\GR=(X,A)$  avec $X=\bigl\{1,2,...,n\bigr\}$ et
sa  matrice d'adjacence  $(m_{ij})$  en prenant  les  sommets par  ordre
croissant.

On considère l'algorithme suivant:

\begin{algo}
\FOR{i}{1}{n}
\STATE{$ a_{ii}$\recoit{}1}
\FOR{j}{1}{n}
\FOR{k}{1}{n}
\STATE{$a_{jk}$\recoit{}max$ \bigl\{a_{jk},a_{ji}a_{ik}\bigr\}$}
\ENDFOR
\ENDFOR
\ENDFOR  
\end{algo}


Appliquer-le au graphe suivant:




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

Que peut-on déduire du fait que $a_{ij}=1$ dans la matrice finale?




\end{exercice}





  \begin{exercice}[ordonnancement]
  
Un contrat vient d'\^{e}tre sign\'{e} pour un projet informatique. Ce projet
a \'{e}t\'{e} d\'{e}compos\'{e} en t\^{a}ches confi\'{e}es \`{a} des ing\'{e}%
nieurs et les contraintes de pr\'{e}c\'{e}dence ainsi que les dur\'{e}es des
t\^{a}ches sont pr\'{e}sent\'{e}es dans le tableau ci-dessous :%
\begin{center}
\begin{tabularx}{\linewidth}{T{2}}
\whline
Rang & Libell\'{e} de la t\^{a}che & dur\'{e}e en mois & T\^{a}ches pr\'{e}%
alables \\ \whline
& A & 3 &  \\ \hline
& B & 8 & A \\ \hline
& C & 5 & A \\ \hline
& D & 1 & C, G \\ \hline
& E & 4 & D \\ \hline
& F & 2 & C \\ \hline
& G & 6 &  \\ \whline
\end{tabularx}%
\end{center}

\begin{enumerate}
\item $\left( 1\right) $ On d\'{e}cide de repr\'{e}senter ce probl\`{e}me
d'ordonnancement \`{a} l'aide d'un graphe par la m\'{e}thode MPM. En faisant
abstraction des deux t\^{a}ches fictives "d\'{e}but du projet" et "fin du
projet", affecter un rang \`{a} chaque sommet en compl\'{e}tant le tableau pr%
\'{e}c\'{e}dent en utilisant l'algorithme qui permet de tester qu'un graphe
est sans circuit.

\item $\left( 1\right) $ Repr\'{e}senter ce probl\`{e}me \`{a} l'aide d'un
graphe MPM en compl\'{e}tant le dessin ci-dessous :%



\begin{center}
  \begin{tikzpicture}
    \SetGraphUnit{1.5}
\GraphInit[vstyle=Art]
\Vertices{circle}{1,2,3,4,5,6,7}
\EA(1){w}
\WE(4){a}
  \end{tikzpicture}
\end{center}







\item $\left( 4\right) $ D\'{e}terminer la dur\'{e}e minimale de r\'{e}%
alisation du projet ainsi que la date de d\'{e}marrage au plus t\^{o}t et au
plus tard de chaque t\^{a}che en supposant que le projet d\'{e}marre \`{a}
la date 0.%
\begin{center}
\begin{tabularx}{\linewidth}{T{1}}
\whline
Libell\'{e} de la t\^{a}che & date au plus t\^{o}t & date au plus tard \\ 
\whline
A &  &  \\ \hline
B &  &  \\ \hline
C &  &  \\ \hline
D &  &  \\ \hline
E &  &  \\ \hline
F &  &  \\ \hline
G &  &  \\ \whline
\end{tabularx}%
\end{center}
\end{enumerate}

  \end{exercice}









\vfill

\eject

\subsection{Exercices semaine 38}

\begin{exercice}
On considère le graphe suivant:


\begin{center}
  \begin{tikzpicture}
    \SetGraphUnit{1.25}
\tikzset{EdgeStyle/.style={->}}
%\GraphInit[vstyle=Art]
\Vertices{circle}{1,2,3,4}
\Edges(1,2,3)
\Edges(4,2)\Edges(1,3)\Edges(4,1)
  \end{tikzpicture}
\end{center}


Donner  sa  matrice  d'adjacence  M,  puis $M^2$,  puis  $M^3$.  Comment
interpréter les coefficients de ces matrices? 

Démontrer ce résultat par récurrence.


\end{exercice}





\begin{exercice}
Les graphes suivants sont-ils fortement connexes? Dans le cas contraire,
donner leurs composantes fortement connexes.

\begin{center}
  \begin{tikzpicture}
    \SetGraphUnit{1.25}
\tikzset{EdgeStyle/.style={->}}
%\GraphInit[vstyle=Art]
\Vertices{circle}{1,2,3,4}
\Edges(1,2,3)
\Edges(3,1,4)\Edges(2,4)\Edges(3,4)
  \end{tikzpicture}
\begin{tikzpicture}
    \SetGraphUnit{1.25}
\tikzset{EdgeStyle/.style={->}}
%\GraphInit[vstyle=Art]
\Vertices{circle}{1,2,3,4,5}
\Edges(1,2,3,1)
\Edges(5,4,2,5)\Edges(5,1)
  \end{tikzpicture}
\begin{tikzpicture}
    \SetGraphUnit{1.25}
\tikzset{EdgeStyle/.style={->}}
%\GraphInit[vstyle=Art]
\Vertices{circle}{1,2,3,4,5}
\Edges(4,2,3,4,5,2)
\Edges(1,4)\Edges(1,5)
  \end{tikzpicture}
\end{center}

\end{exercice}



\begin{exercice}
Voici un réseau de ce que vous voulez:


\begin{center}
\begin{tikzpicture}
    \SetGraphUnit{1.5}
%\tikzset{EdgeStyle/.style={->}}
%\GraphInit[vstyle=Art]
\Vertices{circle}{9,8,5,4,2,1,3,6}
\WE(9){7}
\Edges(9,8,5,4,2,1,3,6,9,7,5,4,3,2)
\Edges(7,6)
  \end{tikzpicture}
\end{center}


Comment obtenir le nombre de chaînes de longueurs 5 entre les sommets 1 et 9?


\end{exercice}



\begin{exercice}
  \begin{enumerate}
  \item Un graphe orienté modélise le réseau routier d'une ville: est-il
    connexe et (ou) fortement connexe?
\item Même question avec un arbre généalogique.
  \end{enumerate}
\end{exercice}

\begin{exercice}
  Soit le graphe G défini par son dictionnaire:

$G(a) = \{c, f \},\, G(b) = \{a, c, d, f \},\,
G(e) = \{a, b, c, d, f \}$

 
$G(c) = \{d, f \},\,
G(d) = \{a, f \},\,
G(f ) = \emptyset$
Déterminer les composantes fortement connexes du graphe G.


\end{exercice}


\begin{exercice}
  \begin{enumerate}
  \item  La relation de  congruence modulo  3 est,  comme vous  le savez
    tous, une relation d'équivalence.  Soit $\GR_3$ le graphe orienté de sommets
    $\bigl\{1,2,3,4,5,6,7,8,9\bigr\}$ tel qu'il  existe un arc entre les
    sommets $a$ et $b$ si, et seulement si, $a\equiv b \, [3]$.

Quelles sont ses composantes connexes?
\item  Soit  $\GR(X,A)$  un  graphe  orienté.  On  définit  la  relation
  suivante:

$$\forall (x,y)\in X,\ x\RR y \Leftrightarrow
\begin{cases}
  x=y\\
\text{ou}\\
\text{il existe une chaîne entre \textit{x} et \textit{y}}
\end{cases}
$$

Montrez qu'il s'agit d'une  relation d'équivalence. Que peut-on dire des
classes d'équivalences?
  \end{enumerate}


\end{exercice}



\begin{exercice}

\begin{enumerate}
\item Soit $ \GR=(X,A)$ un graphe simple, symétrique, sans boucles, ayant $2n$ sommets de
  degrés   au  moins   égal  à   $n$.  Montrer   que  $\GR$   est  alors
  connexe. (\textit{Vous pourrez par exemple raisonner par l'absurde.})
\item Soit $\GR$ un graphe simple, symétrique. Montrer que parmi $ \GR$ et son
  complémentaire, l'un des deux est connexe.
\end{enumerate}

\end{exercice}




\begin{exercice}
  Un graphe est  $k$-connexe  si on peut le déconnecter en retirant $k$ sommets et qu'on ne peut
pas en en supprimant $k – 1$; son  degré de connexité est alors $k$. Cela permet, par
exemple, de mesurer la résistance aux pannes d'un réseau informatique.

Dessinez la représentation d'un graphe 1-connexe; 2-connexe.



On  définit   de  la   même  manière  la   $k$-connexité  au   sens  des
arêtes. Dessinez  la représentation d'un graphe $1$-connexe  au sens des
arêtes; 2-connexe au sens des arêtes.
\end{exercice}



\begin{exercice}
Appliquer  aux graphes  suivant  l'algorithme de  parcours  en largeur  en
faisant figurer l'arbre  (ou la forêt\footnote{Une forêt  est un graphe
  constitué de plusieurs arbres...}) de parcours résultant dans lequel les sommets de
profondeur égale seront mis à la même hauteur:



\begin{center}
\begin{tikzpicture}
    \SetGraphUnit{1.5}
\tikzset{EdgeStyle/.style={->}}
%\GraphInit[vstyle=Art]
\Vertices{circle}{2,1,4,3,6}
\SOWE(3){5}
\Edges(1,2)\Edges(1,3)
\Edges(1,4,3)
\Edges[style={bend left}](3,5,3,6,3,6,5)
  \end{tikzpicture}
%
\end{center}

Faites de même avec le parcours en profondeur.

\end{exercice}

\begin{exercice}\label{arbre}
  \begin{enumerate}
  \item Montrer qu'un arbre ayant $n$  sommets avec $n>1$ a au moins une
    feuille (\textit{considérer  une chaîne simple  de longueur maximale
      d'extrémités $s$ et $t$...}).
\item Montrer alors par récurrence qu'un arbre de $n$ sommets avec $n>0$
  a $n-1$ arêtes.
\item Proposer, à partir de  ces résultats, un algorithme qui vérifie si
  un graphe non orienté 
  et connexe  possède un cycle.  On  suppose qu'un graphe  est connu par
  son dictionnaire d'adjacence. Quel est
  l'inconvénient de cet algorithme?

  \end{enumerate}
\end{exercice}





\begin{exercice}
Est-ce que les graphes suivants sont eulériens? Si oui, exhibez un cycle
eulérien. Si non, existe-t-il au moins une chaîne eulérienne?


\begin{center}
\begin{tikzpicture}
    \SetGraphUnit{1.5}
%\tikzset{EdgeStyle/.style={->}}
\GraphInit[vstyle=Art]
\Vertices{circle}{1,2,3,4,5}
\Edges(5,1,2,3,4,5,2)
  \end{tikzpicture}
\begin{tikzpicture}
    \SetGraphUnit{1.5}
%\tikzset{EdgeStyle/.style={->}}
\GraphInit[vstyle=Art]
\Vertices{circle}{1,2,3,4,5,6}
\Edges(1,2,3,4,5,6,1,2,6,3,5,2)
  \end{tikzpicture}
\begin{tikzpicture}
    \SetGraphUnit{1.5}
%\tikzset{EdgeStyle/.style={->}}
\GraphInit[vstyle=Art]
\Vertices{circle}{1,2,3,4,5,6}
\Edges(1,2,3,4,5,6,1)
\Edges(6,3,5)
  \end{tikzpicture}
\begin{tikzpicture}
    \SetGraphUnit{1.5}
%\tikzset{EdgeStyle/.style={->}}
\GraphInit[vstyle=Art]
\Vertices{circle}{1,2,3,4,5}
\Edges(5,1,2,3,4,5,2)
\Edges(2,4,5,3)
\Edges[style={bend left}](3,1,4)
  \end{tikzpicture}
\end{center}


Montrer que si un graphe  simple symétrique est eulérien, alors tous les
sommets sont de degré pair.

Quelle est la taille d'un cycle eulérien?

\end{exercice}



\begin{exercice}
Effectuer  un parcours  en profondeur  du graphe  suivant et  dresser la
forêt  du parcours  puis déterminer  ses composantes  fortement connexes
(\textit{il y en a 7...}).



\begin{center}
\begin{tikzpicture}
    \SetGraphUnit{1.75}
\tikzset{EdgeStyle/.style={->}}
%\GraphInit[vstyle=Art]
\Vertices[x=0,y=7]{line}{1,2,3,4,5}
\Vertices[x=0,y=3.5]{line}{6,7,8,9,10}
\Vertices[x=0,y=0]{line}{11,12,13,14}
\Edges(1,2,7,8,9)
\Edges(1,6,12,13)
\Edges(12,7)
\Edges(12,8)
\Edges(5,10)
\Edges[style={bend left}](2,6,2)
\Edges[style={bend left}](6,7,6)
\Edges[style={bend left}](6,11,6)
\Edges[style={bend left}](13,14,13)
\Edges[style={bend left}](9,3,9)
\Edges[style={bend left}](4,5,4)
\Edges[style={bend right}](4,1)
 \end{tikzpicture}
%
\end{center}


\end{exercice}




\vfill


\eject



\subsection{Semaine 39: \bsc{Bellman-Ford} et \bsc{Dijkstra}}


\begin{exercice}[Bellman-Ford]
  
On considère un graphe valué sans circuit de valeur négative (ou circuit
absorbant) mais ayant
éventuellement des arcs pondérés négativement.

On s'intéresse  à la  distance d'un sommet  particulier, la  source, aux
différents sommets du graphe.

On note $ \pi(v)$ la distance de la source $s$ à un sommet $v$.

Au  départ, on  pose $  \pi(s)=0$  et pour  tous les  autres sommets  du
graphe, $ \pi(v)=+\infty$.

L'idée est que, pour tout sommet  $v$, si passer par un prédécesseur $u$
de  $v$  raccourcit  la  distance,  alors on  remplace  $\pi(v)$  par  $
\pi(u)+p(u,v)$ avec $ p(u,v)$ la pondération de l'arc $(u,v)$.

La propriété de \bsc{Bellman} est donc la suivante:

$$\pi(v)=\min_{u\in\Gamma^{-1}(v)}\bigl\{\pi(u)+p(u,v)\bigr\}$$

\begin{algo}
\ALGO{Bellman version 1}
\STATE{Un graphe valué G orienté est défini par un dictionnaire}
\STATE{Un sommet $s$ de G est la source}
\DECLVAR{pi}{un dictionnaire indexé par les sommets}
\ENDVAR
\BEGIN
\STATE{$ \pi(s)=0$}
\FORGEN{ tous les sommets du graphe $ \neq s$}
\STATE{$\pi(s)$\recoit{} $ +\infty$}
\ENDFOR
\WHILE{$\pi$ change}
\FORGEN{chaque arc $ (u,v)$ de G}
\IF{$\pi(v)>\pi(u)+p(u,v)$}
\STATE{$\pi(v)$\recoit{}$\pi(u)+p(u,v)$}
\ENDIF
\ENDFOR
\ENDWHILE
\RETURN{$\pi$}
\END
\end{algo}

Appliquer aux graphes suivants:

\begin{center}
\begin{tikzpicture}
\SetGraphUnit{2.2}
\Vertices{circle}{5,4,2,1,3,6}
\tikzset{EdgeStyle/.style={->}}
\Edge[label=$7$](1)(2)
\Edge[label=$1$](1)(3)
\Edge[label=$-2$](3)(2)
\Edge[label=$7$](3)(6)
\Edge[label=$2$](3)(5)
\Edge[label=$-1$](6)(5)
\Edge[label=$5$](5)(4)
\Edge[label=$-2$](5)(2)
\Edge[style={bend right},label=$2$](2)(6)
\Edge[label=$4$](2)(4)
\end{tikzpicture}
%
\begin{tikzpicture}
\SetGraphUnit{2.2}
\Vertices{circle}{5,4,2,1,3,6}
\tikzset{EdgeStyle/.style={->}}
\Edge[label=$7$](1)(2)
\Edge[label=$1$](1)(3)
\Edge[label=$2$](3)(2)
\Edge[label=$7$](3)(6)
\Edge[label=$2$](3)(5)
\Edge[label=$2$](5)(6)
\Edge[label=$5$](5)(4)
\Edge[label=$2$](5)(2)
\Edge[style={bend right},label=$1$](2)(6)
\Edge[label=$4$](2)(4)
\end{tikzpicture}
%
\begin{tikzpicture}
\SetGraphUnit{2.2}
\Vertices{circle}{5,4,2,1,3,6}
\tikzset{EdgeStyle/.style={->}}
\Edge[label=$7$](1)(2)
\Edge[label=$1$](1)(3)
\Edge[label=$5$](3)(2)
\Edge[label=$7$](3)(6)
\Edge[label=$2$](3)(5)
\Edge[label=$1$](6)(5)
\Edge[label=$2$](5)(4)
\Edge[label=$4$](5)(2)
\Edge[style={bend right},label=$1$](2)(6)
\Edge[label=$2$](4)(2)
\end{tikzpicture}
%
\begin{tikzpicture}
\SetGraphUnit{2.2}
\Vertices{circle}{5,4,2,1,3,6}
\tikzset{EdgeStyle/.style={->}}
\Edge[label=$7$](1)(2)
\Edge[label=$1$](1)(3)
\Edge[label=$5$](3)(2)
\Edge[label=$7$](3)(6)
\Edge[label=$2$](3)(5)
\Edge[label=$-1$](6)(5)
\Edge[label=$-2$](5)(4)
\Edge[label=$4$](5)(2)
\Edge[style={bend right},label=$1$](2)(6)
\Edge[label=$1$](4)(2)
\end{tikzpicture}
%
\begin{tikzpicture}
\SetGraphUnit{2.2}
\Vertices{circle}{5,4,2,1,3,6}
\tikzset{EdgeStyle/.style={->}}
\Edge[label=$7$](1)(2)
\Edge[label=$1$](1)(3)
\Edge[label=$5$](3)(2)
\Edge[label=$7$](3)(6)
\Edge[label=$2$](3)(5)
\Edge[label=$-1$](6)(5)
\Edge[label=$-2$](5)(4)
\Edge[label=$4$](5)(2)
\Edge[style={bend right},label=$1$](2)(6)
\Edge[label=$2$](4)(2)
\end{tikzpicture}
\end{center}


Une amélioration consisterait à mémoriser les plus courts chemins et pas
seulement leur longueur.

À chaque fois que le traitement  d'un arc $ (u,v)$ modifie $ \pi(v)$, le
nouveau prédécesseur de $v$ devient $u$ (on dit qu'on \textit{relâche} $
(u,v)$).

On peut donc stocker ces prédécesseurs dans un nouveau dictionnaire.

\begin{algo}
\ALGO{Bellman version 2}
\STATE{Un graphe valué G orienté est défini par un dictionnaire}
\STATE{Un sommet $s$ de G est la source}
\DECLVAR{pi}{un dictionnaire indexé par les sommets}
\ENDVAR
\BEGIN
\STATE{$ \pi(s)=0$}
\FORGEN{ tous les sommets du graphe $ \neq s$}
\STATE{$\pi(s)$\recoit{} $ +\infty$}
\STATE{pred\recoit{} un dictionnaire vide}
\ENDFOR
\WHILE{$\pi$ change}
\FORGEN{chaque arc $ (u,v)$ de G}
\IF{$\pi(v)>\pi(u)+p(u,v)$}
\STATE{$\pi(v)$\recoit{}$\pi(u)+p(u,v)$}
\STATE{pred[$v$]\recoit{} u}
\ENDIF
\ENDFOR
\ENDWHILE
\RETURN{$\pi$, pred}
\END
\end{algo}


\textit{Que se passe-t-il si le graphe contient un circuit négatif?
}
\begin{center}
  \begin{tikzpicture}
\SetGraphUnit{2.2}
\Vertices{circle}{A,B,C,D}
\tikzset{EdgeStyle/.style={->}}
\Edge[label=$-1$](B)(A)
\Edge[label=$-1$](A)(D)
\Edge[label=$-1$](D)(B)
\Edge[label=$2$](C)(B)
\Edge[label=$3$](C)(D)
\end{tikzpicture}
\end{center}


Il  faudrait  pouvoir  détecter  de  tels circuits  dans  des  cas  plus
compliqués.


En fait, on peut montrer  que la boucle \textbf{Tant que}, s'il n'existe
pas de tels circuits \textbf{absorbants}, se termine au maximum en $n-1$
itérations.

\textit{Imaginez un  circuit de  $n$ sommets dont  le plus  court chemin
  donné par l'algorithme soit exactement $n-1$.}

On peut  donc être  amené à effectuer  $n-1$ boucles. Montrons  qu'on ne
peut pas dépasser cette valeur en cas d'absence de circuit absorbant.

Tout d'abord, on va montrer l'\textbf{invariant de boucle}:

\textbf{À  l'étape $i$,  pour tout  sommet $v$,  $ \pi(v)$  est  le plus
  court chemin de $s$ à $v$ contenant au plus $i$ arcs.}


La  preuve d'un  invariant  de  boucle s'effectue  le  plus souvent  par
récurrence.

\textit{Démontrer   l'invariant   de   boucle.   Pour   l'hérédité,   on
  distinguera deux cas.}


Bon, maintenant, un chemin non élémentaire est forcément plus long qu'un
chemin élémentaire: \textit{pourquoi?}

Il  suffit  donc d''étudier  les  chemins élémentaires:  \textit{combien
  contiennent-ils d'arcs au maximum? Conclusion?}

\textit{Comment peut-on alors changer la boucle principale?}

\textit{Comment alors tester si un graphe contient un circuit absorbant?}

Il peut s'avérer que l'on  recherche les plus longs chemins d'un graphe:
\textit{comment  adapter  le travail  précédent  pour  trouver les  plus
  longs chemins partant d'une source?}


\end{exercice}


\begin{exercice}[Algorithme de Dijkstra]

Rappel de l'algorithme:

 \begin{algo}[rightmargin=5pt,
leftmargin=10pt]
\ALGO{\bsc{Dijkstra}}
\BEGIN
\STATE{$ pi$\recoit{} dictionnaire vide}
\STATE{$ \pi$[début]=0}
\STATE{Visités\recoit{} liste vide}
\STATE{Chaîne\recoit{} [début]}
\STATE{x \recoit{} début}
\FORGEN{tout s de X $\backslash \bigl\{\text{début}\bigr\}$}
\STATE{$\pi$(s)\recoit{} $+\infty$}
\STATE{chaîne\recoit{} a}
\ENDFOR
\WHILE{x $ \neq$ fin}
\FORGEN{v $\not\in$ Visités et voisin de x}
\STATE{$\pi$[v]\recoit{}min $\bigl\{\pi[v],\pi[x]+p(x,v)\bigr\}$}
\ENDFOR
\STATE{Extraire  un  sommet $u\not  \in$  Visités  tel que  $\pi[u]=\min
  \bigl\{\pi[y],y\not\in \text{Visités}\bigr\}$}
\STATE{x\recoit{}u}
\STATE{Visités\recoit{}Visités $\cup \bigl\{u\bigr\}$ }
\ENDWHILE
\RETURN{$ \pi$}
\END
  \end{algo}



\textit{Appliquer  l'algorithme  de  \bsc{Dijkstra}    aux  exemples
précédents avec la méthode vue en cours.
Que remarquez-vous?}


\Python  permet  de  gagner  un   peu  de  temps  grâce  à  des  petites
particularités de traitement des dictionnaires.

Voici même une version récursive de l'algorithme. \textit{Décrypter la et écrire
un programme avec  une boucle au lieu de  la récursion selon l'agorithme
présenté précédemment.}

\begin{lstlisting}[caption={}]
#!/usr/bin/python
# -*- coding: utf-8 -*-



"""
Quelques fonctions python utiles ici :

- on va rentrer un graphe comme un dictionnaire de dictionnaires pour pouvoiur pondérer les arêtes:
g = {'a': {'b': 4, 'c': 2},
     'b': {'a' : 4,'d': 5, 'c': 1},
     'c': {'a' : 2, 'b' : 1, 'd' : 8,'e': 10},
     'd': {'b': 5, 'c': 8, 'e': 2},
     'e': {'c': 10, 'd' : 2, 'f': 3},
     'f': {'e' : 3,'d' : 6}}

Ainsi, g['a'] est le dictionnaire des voisins avec leurs poids :

>>> g['a']
{'c': 2, 'b': 4}
>>> g['a']['b']
4
>>> 'c' in g['a']
True

- pour trouver la clé correspondant à la valeur mini d'un dictionnaire, on utilise une syntaxe très pythonesque. Par exemple, pour avoir le voisin le plus proche de 'a' :

>>> min(g['a'],key=g['a'].get)
'c'


- dict.get(cle,defaut) : retourne la valeur de cle si elle se trouve dans le dictionnaire et defaut sinon ;

- float('inf') représente l'infini
"""

def plus_court(graphe,debut,fin,visites,pi,chaine,espion):
    """trouve la plus courte chaine entre debut et fin avec l'algo de Dijkstra
       visites et chaine sont des listes et pi un dictionnaire
       version récursive
    """
    # si on arrive à la fin, on affiche la distance et la chaine en y rajoutant fin
    if debut==fin:
       chaine.append(fin)
       return pi[fin], chaine, espion
    # si c'est la première visite, on met pi(debut) à 0
    if  len(visites) == 0 : pi[debut]=0
    # on commence à tester les voisins
    for voisin in graphe[debut]:
        if voisin not in visites:
            dist_voisin = pi.get(voisin,float('inf'))
            candidat_dist = pi[debut] + graphe[debut][voisin]
            if candidat_dist < dist_voisin:
                pi[voisin] = candidat_dist
                if debut not in chaine:
                    chaine.append(debut)
    # on a regardé tous les voisins : le noeud entier est visité
    visites.append(debut)
    espion+=1
    # on cherche le sommet non visité le plus proche
    non_visites = dict((s, pi.get(s,float('inf'))) for s in graphe if s not in visites)
    noeud_plus_proche = min(non_visites, key=non_visites.get)
    # on applique récursivement en prenant comme début le plus proche 
    return plus_court(graphe,noeud_plus_proche,fin,visites,pi,chaine,espion)


def dij_rec(graphe,debut,fin):
    return plus_court(graphe,debut,fin,[],{},[],1)


if __name__ == "__main__":
    g = {'a': {'b': 4, 'c': 2},
         'b': {'a' : 4,'d': 5, 'c': 1},
         'c': {'a' : 2, 'b' : 1, 'd' : 8,'e': 10},
         'd': {'b': 5, 'c': 8, 'e': 2},
         'e': {'c': 10, 'd' : 2, 'f': 3},
         'f': {'e' : 3,'d' : 6}}
    print 'Version récursive : ',dij_rec(g,'a','f')
\end{lstlisting}


\end{exercice}











\vfill/eject




%\modeexercice % entre en mode exercice
\subsection{Semaine 40: coloration}
%\begin{listeexercices}

\begin{exercice}[Théorème de Tutte]
  \begin{enumerate}
  \item  Construire  un   graphe  sans  clique  de  degré   3  qui  soit
    3-chromatique.
\item Comment obtenir alors un graphe 4-chromatique sans clique de degré
  4?
\item Faites de même pour des graphes 5-chromatique et 6-chromatique.
\item Peut-on généraliser?
  \end{enumerate}
\end{exercice}


%
%

\begin{exercice}
  Cinq routes A, B, C, D et  E se rejoignent en un seul carrefour (ordre
  anti-trigonométrique).

Voici les franchissements possibles: AC, AE, BA, BD, BE, CA, CD, DA, DC,
EC, ED.

Certains franchissements ne  peuvent être simultanés comme AC  et BE, EC
et BD, etc.

Modélisez  la   situation  à  l'aide   d'un  graphe  dont   les  sommets
représentent les franchissements possibles  et les arêtes joignent les
franchissements incompatibles.

Que peut-on dire des ensembles monochromes?

Comment interpréter le nombre chromatique?
\end{exercice}


\begin{exercice}
  Sept étudiants A, B, C, D, E, F et G se sont rendus à la cafétéria aujourd'hui.  Voici la
  liste des rencontres, AD, AE, BD, BE,  BF, BG, CE, CG, DA, DB, DE, EA,
  EB, EC, ED, EF, EG, FB, FE, GB, GC, GE, GF.

En  supposant que  tous  les étudiants  sont  assis à  la cafétéria,  de
combien de chaises (denrée devenue rare à l'IUT) doit disposer la cafétéria?
\end{exercice}




 \begin{exercice}
    \begin{enumerate}
    \item D\'{e}terminer le graphe aux ar\^{e}tes du graphe
suivant (on a donn\'{e} un nom \`{a} chaque ar\^{e}te) :%

\begin{center}
\input{../../../Thierry/Conversions/ColorationArete.pdf_tex}
\end{center}


\item  Quatre professeurs P1, P2, P3$,$ P4 doivent donner
des heures (1 heure par classe) de cours \`{a} 3 classes C1, C2, C3, les
affectations sont donn\'{e}es par le tableau : 
$$
\begin{tabular}{|c|c|c|c|c|}
\hline
& P1 & P2 & P3 & P4 \\ \hline
C1 & oui &  & oui & oui \\ \hline
C2 & oui & oui &  & oui \\ \hline
C3 &  & oui &  & oui \\ \hline
\end{tabular}%
\ 
$$%
On se pose la question : \og Quel nombre minimum d'heures faut-il pour
dispenser tous les cours ?\fg{}. Il est \'{e}vident qu'un professeur ne peut pas
faire cours \`{a} plus d'une classe dans un m\^{e}me cr\'{e}neau horaire et
qu'une classe ne peut pas avoir cours avec plus d'un prof au m\^{e}me moment
.Il vous est demand\'{e} de transformer ce probl\`{e}me en un probl\`{e}me
de coloration d'un graphe, vous indiquerez donc sur quel graphe le travail
va se faire et vous repr\'{e}senterez ce graphe en expliquant clairement la
notation que vous utiliserez pour nommer les sommets et le pourquoi des ar%
\^{e}tes ; vous pr\'{e}ciserez aussi si c'est une recherche de coloration
des sommets ou des ar\^{e}tes (une coloration doit \^{e}tre \textbf{ici} un
cr\'{e}neau horaire, par exemple rouge = 8h-9h, etc.)
\end{enumerate}



  \end{exercice}




  \begin{exercice}
    Un peu de  mécanique pour faire plaisir à  M. \bsc{Mottu}: une boîte
    de vitesse  est un mécanisme qui  permet de changer  la fréquence de
    rotation de  l'arbre intermédiaire  pour une fréquence  constante de
    rotation de l'arbre principal. Cela  est dû à la présence de pignons
    (roues dentées) dans la boîte de vitesse. Un des principaux problèmes
    pour un concepteur  de boîte de vitesse est de  réduire sa taille ce
    qui  revient  souvent à  réduire  la  quantité  d'arbres reliés  aux
    pignons d'engrenage.  Certains pignons  ne peuvent cependant  pas se
    trouver sur le  même arbre car ils pourraient  créer des blocages ou
    leur poids  dépasseraient les capacités de l'arbre  par exemple. Ces
    paires  impossibles  sont les  suivantes,  sachant  qu'il  y a  sept
    pignons a, b, c,  d, e, f et g: ab, ad, ae, ag,  bc, be, bg, ce, cf,
    df, eg, fg. 


   Déterminer le nombre minimum d'arbres qui permet de fixer les pignons.
  \end{exercice}





  \begin{exercice}
    M.  \bsc{Remm} a pris un congé  pour assister aux marchés de Noël en
    Alsace et voilà le département pris au
    dépourvu au moment de mettre au point les emplois du temps du second
    semestre. Le
    jeudi, par  exemple, il  faut placer sept  cours: Maths 1,  Maths 2,
    Maths 3, Algo 1, Algo 2, Tamoul, Couture.

Cependant, certains  cours ne  peuvent avoir lieu  en parallèle  car ils
sont  dispensés par  le même  professeur ou  certains  étudiants doivent
assister à  chacun. C'est  le cas de  m1/m2, m1/a1, m1/c,  m2/m3, m2/a2,
m3/a2, m3/t, m3/c, a1/a2, a1/t et a2/t.

Tous les cours pourront-ils être dispensés le jeudi matin?
  \end{exercice}





  \begin{exercice}[Fonction chromatique]

La fonction chromatique $f$ associe à un  graphe G et à un entier $t$ le
nombre de façons de colorier un graphe G avec $t$ couleurs différentes. 

On  remarquera bien sûr  que la  quantité minimum  $t$ de  couleurs pour
laquelle $f(G,t)>0$ est $\chi(G)$.

\begin{enumerate}
\item Montrer que $f(K_n,t)=t(t-1)(t-2)\cdots(t-n+1)$ si $t \geqslant n$
  et 0 sinon.

\item Dans  le cas  général, le calcul  de $f(G,t)$ est  compliqué. Nous
  allons  cependant   voir  un  théorème  intéressant.   Pour  cela,  on
  considérera  l'opération  de  \textbf{fusion}  de deux  sommets:  deux
  sommets $u_1$  et $u_2$  sont fusionnés pour  former un  unique sommet
  $u_0$ qui sera adjacent à  tous les sommets auxquels étaient adjacents
  $u_1$ et $u_2$.

Voici le théorème:

\textit{Soit $u$ et $v$ deux sommets  non adjacents d'un graphe G. Si le
  graphe $G_1$ est obtenu à partir de G en ajoutant l'arête $(u,v)$ et le
  graphe $G_2$ est  obtenu à partir de la fusion des  sommets $u$ et $v$
  alors:
$$f(G,t)=f(G_1,t)+f(G_2,t)$$
}

Démontrer ce théorème en distinguant les colorations possibles:
\begin{itemize}
\item soit $u$ et $v$ ont la même couleur;
\item soit $u$ et $v$ portent des couleurs différentes.
\end{itemize}


L'idée est alors de découper un graphe en plusieurs graphes selon la méthode précédentes
jusqu'à obtenir des graphes complets afin d'utiliser le résultat sur les
$ K_n$.

Par exemple, toujours à cause  du congé de M. \bsc{Remm}, le département
est  en émoi  pour organiser  l'emploi du  temps. Le  mardi,  cinq cours
doivent être  donnés avec toujours quelques  incompatibilités. On décide
de créer  un quatrième créneau  pour l'après-midi de  18h à 19h20  et de
garder les trois créneaux du matin.

Combien y a-t-il de combinaisons possibles le matin et l'après-midi pour
placer ces cinq cours en une seule demi-journée?

Les incompatibilités sont $C_1/C_2$,  $ C_1/C_3$, $ C_1/C_4$, $C_2/C_3$,
$C_2/C_4$, $C_2/C_5$, $C_3/C_5$, $C_4/C_5$
\end{enumerate}
    
  \end{exercice}

  \begin{exercice}[Algorithme glouton de coloration]
    
Il est  temps d'utiliser Python  pour déterminer un algorithme  qui nous
donnera  une valeur  possible de  coloration d'un  graphe à  l'aide d'un
algorithme glouton.

Soit G un graphe défini par un dictionnaire.  On codera les couleurs par
des entiers dans l'ordre croissant. Considérons un sommet
associé à  une couleur. Cherchons le  prochain sommet non  coloré. On le
colorie avec le plus petit entier non utilisé par ses voisins.

On affiche ensuite le nombre de couleurs utilisées. À vous de jouer...

L'ordre  dans  lequel les  sommets  sont  choisi  a-t-il une  influence?
Essayer  avec un  autre ordre  en créant  une permutation  aléatoire des
sommets.

On  pourra  utiliser  \lstinline+max(g.values())+  qui donne  la  valeur
maximale des valeurs associés aux labels du dictionnaire $g$.


  \end{exercice}








\vfill/eject


 \end{listeexercices}

%\modeexercice % entre en mode exercice
\subsection{Semaine 41:  arbre de recouvrement  et flots }
%\begin{listeexercices}


\begin{exercice}[Algorithme de Prim]
On considère un arbre pondéré. On  choisit un sommet. On a donc un arbre
avec un sommet et zéro arête.

À l'étape $k$, on  a un arbre de $k$ sommets et  $k-1$ arêtes. On choisit
ensuite l'arête  de poids  extrémal telle que  son origine  appartienne à
l'arbre mais pas son extrémité.

Appliquez cet algorithme  à ces graphes, dans le  cas d'une recherche de
recouvrement minimal puis maximal:

\begin{lstlisting}[caption={}]
   g = {'a':{'b':10,'c':1,'d':2,'a':5},
        'b':{'a':10,'e':3,'d':4,'c':6},
        'c':{'b':6,'a':1,'e':9,'d':3},
        'd':{'e':7,'a':2,'b':4,'c':3},
        'e':{'a':5,'b':3,'c':9,'d':7}
       }

    h = {'a': {'b': 1, 'f': 3, 'e': 5},
         'b': {'a' : 1,'g': 2, 'c': 3},
         'c': {'b' : 8, 'h' : 3, 'd': 2},
         'd': {'c' : 6, 'i' : 4, 'e': 4},
         'e': {'d': 3, 'j' : 2, 'a': 5},
         'f': {'a': 4, 'i': 3, 'h': 1},
         'g': {'b' : 1,'j': 2, 'h': 1},
         'h': {'c' : 8, 'f' : 1, 'j': 3},
         'i': {'d' : 6, 'g' : 4, 'f': 1},
         'j': {'e': 2, 'h' : 1, 'g': 4}
         }
\end{lstlisting}

Quand vous  serez en salle  machine, déterminez un programme  python qui
pourra avoir ce squelette:


\begin{lstlisting}[caption={}]
def prim(g,extr):
    T = []
    A = set([choice(list(g))])
    G = set(list(g))-A
    P = 0
    while ...
       ...
    return T,P
\end{lstlisting}

puis vérifiez les solutions trouvées sur papier.
\end{exercice}


\begin{exercice}
Un  réseau  de fibre  optique  va être  installé  pour  équiper les  maisons
représentées  par   les  sommets   du  graphe  ci-dessous.   Par  mesure
d'économie,  les fibres doivent  suivre les  routes reliant  ces maisons
représentées par les arêtes du graphe et pondérées par leur longueur.

Comment procéder  pour utiliser une  longueur minimale de fibre  tout en
équipant chaque maison?

\begin{lstlisting}[caption={}]
    r = {'1':{'4':100,'2':200},
         '2':{'1':200,'5':170,'6':180,'3':150},
         '3':{'2':150,'6':100},
         '4':{'1':100,'5':240,'7':380},
         '5':{'2':170,'4':240,'7':210},
         '6':{'3':100,'2':180,'7':260},
         '7':{'4':380,'5':210,'6':260}
        }
\end{lstlisting}

\end{exercice}



\begin{exercice}
  À Klow, capitale de la Syldavie, on peut se déplacer de n'importe quelle station de
  métro vers n'importe quelle autre.

Le beau-frère du Guide Suprême de la Syldavie dirigeant une entreprise de travaux d'entretien,
il  exige  qu'un  maximum  de  stations de  métro  soient  fermées  pour
réparation mais le Guide Suprême demande de les choisir afin que dans le réseau
restant, de toute station on continue à pouvoir se rendre vers n'importe
quelle autre. Il est à noter que la réparation d'une station empêche les
rames de la traverser.
Le  conseiller technique du  maire, grassement  payé car  ex-étudiant de
l'IUT de Nantes, a la solution: quelle est-elle?

\medskip
(\textit{Il  est à  noter que  le  premier algorithme  donnant un  arbre
  couvrant de  poids minimal  a été donné  par le  Tchécoslovaque Otakar
  \bsc{Bor\r{u}vka} en 1926 afin de concevoir le réseau de distribution
  électrique en Moravie du Sud et ce au moindre coût...})

\end{exercice}


\begin{exercice}
Suite à des  manifestations causées par le trop  grand nombre de travaux
dans la  capitale, le Guide Suprême  de la Syldavie décide  de créer une
nouvelle capitale dans le désert. Son conseiller technique, grassement  payé car  ex-étudiant de
l'IUT de Nantes, lui conseille de  donner à la ville l'aspect d'un carré
de dimension 10 km $\times$ 10 km avec 101 rues rectilignes parallèles à
un des côté du carré et 101 autres perpendiculaires aux premières.

La  distance entre  deux rues  parallèles voisines  est de  100 m  et la
longueur de chaque rue est bien sûr de 10 km.

Le maire a cependant un budget serré, lourdement grevé par le salaire du
conseiller  technique. Il exige  donc de  recouvrir d'asphalte  les rues
mais en utilisant une quantité minimale d'asphalte tout en permettant de
rendre toute intersection accessible.

Combien  de mètres linéaires  d'asphalte doit-il  acheter à  son cousin,
propriétaires de la société \og Syldavian Macadam \& Co\fg{}?
\end{exercice}



\begin{exercice}[Générateur de labyrinthe]
On  considère  une  grille  dont  les traits  horizontaux  et  verticaux
représentent des murs. Un labyrinthe  est alors une grille dont certains
murs ont  été détruits. Il  est parfait lorsque  toute case a  un chemin
simple et un seul vers toute autre case.

Comment associer un labyrinthe parfait à un graphe? Quelle est la nature
de ce graphe?

Comment construire un algorithme en modifiant légèrement l'algorithme de
Prim?

Un projet pourrait  être de créer un générateur de  labyrinthe et qui le
dessine...

\end{exercice}


\begin{exercice}
  Est-ce que tout flot complet est saturé?
\end{exercice}


\begin{exercice}
Déterminer un flot de capacité maximum dans le réseau de transport suivant:


\begin{center}
\begin{tikzpicture}
\SetGraphUnit{2.2}
\renewcommand*{\VertexLineWidth}{2pt}
\GraphInit[vstyle=Art]
\renewcommand*{\VertexBallColor}{blue!50}
\renewcommand*{\VertexBigMinSize}{12pt}
\SetUpEdge[lw= 1.5pt,
color= black,
labelcolor = white,
labeltext = red,
labelstyle = {draw,text=blue!50!black},
style = ->]
\Vertex{1}
\NOEA(1){2}\EA(2){5}\EA(5){8}\SOEA(8){10}
\EA(1){4}\EA(4){7}
\SOEA(1){3}\EA(3){6}\EA(6){9}
\Edge[label=[4]](1)(2)
\Edge[label=[5]](1)(3)
\Edge[label=[6]](1)(4)
\Edge[label=[3]](2)(5)
\Edge[label=[10]](5)(8)
\Edge[label=[7]](8)(10)
\Edge[label=[2]](4)(5)
\Edge[label=[3]](4)(7)
\Edge[label=[6]](4)(6)
\Edge[label=[5]](3)(6)
\Edge[label=[8]](6)(9)
\Edge[label=[15]](9)(10)
\Edge[label=[3]](7)(8)
\Edge[label=[8]](7)(9)
\end{tikzpicture}
\end{center}


\textit{La réponse est 14...}

\end{exercice}



\begin{exercice}
Un serveur S souhaite envoyer des  données à un client P. On suppose que
les  deux postes sont  connectés par  le réseau  Télécom décrit  dans le
graphe suivant:

\begin{center}
\begin{tikzpicture}
\SetGraphUnit{3.5}
\renewcommand*{\VertexLineWidth}{2pt}
%\GraphInit[vstyle=Art]
\renewcommand*{\VertexBallColor}{blue!50}
\renewcommand*{\VertexBigMinSize}{12pt}
\SetUpEdge[lw= 1.5pt,
color= black,
labelcolor = white,
labeltext = red,
labelstyle = {draw,text=blue!50!black},
style = ->]
%\Vertices{circle}{P,1,2,3,4,5,S,6,7,8,9,10,11}
 \Vertex{S}
 \NOEA(S){3}\NO(3){8}\SOEA(S){5}\SO(5){1}
\EA(8){10}\EA(5){2}\EA(1){6}
\EA(10){9}\EA(2){7}\EA(6){4}
\NOEA(7){P}\EA(4){11}
\Edge[label=[10]](S)(8)
\Edge[label=[10]](S)(3)
\Edge[label=[10]](S)(5)
\Edge[label=[20]](S)(1)
\Edge[label=[10]](8)(10)
\Edge[label=[10]](3)(10)
\Edge[label=[10]](3)(2)
\Edge[label=[10]](5)(10)
\Edge[label=[10]](5)(2)
\Edge[label=[10]](1)(5)
\Edge[label=[10]](1)(6)
\Edge[label=[20]](10)(9)
\Edge[label=[20]](10)(7)
\Edge[label=[10]](2)(10)
\Edge[label=[10]](2)(4)
\Edge[label=[10]](2)(6)
\Edge[label=[20]](6)(4)
\Edge[label=[20]](9)(P)
\Edge[label=[20]](7)(P)
\Edge[label=[10]](4)(7)
\Edge[label=[10]](4)(P)
\Edge[label=[10]](4)(11)
\Edge[label=[10]](11)(P)
\end{tikzpicture}
\end{center}


Les valuations des arcs représentent  un débit en Mo/s. Les sommets sont
des routeurs.

On suppose qu'un routeur est  capable de recevoir plusieurs parties d'un
même  message par  des  voisins  différents et  de  les redécouper  pour
l'envoyer à  plusieurs voisins à la fois.  Quelle quantité d'information
peut-on alors faire passer de S à P en une seconde?


\textit{La réponse est 50 Mo...}
\end{exercice}


% \end{listeexercices}
 





\modenormal % restaure les définitions de sections, sous-sections, etc;


%%% Local Variables: 
%%% TeX-master: "poly_graphes_11.tex"
%%% End: 
