
\section{Graphe}

\subsection{définition}

Un graphe orienté est un ensemble de sommets 
et d'arêtes orientées ou arcs reliant des sommets. 
Si $X$ désigne l'ensemble
des sommets du graphe, les arcs sont
représentées par une partie $U$ de $X\times X$. Un chemin 
de longeur $n$ est une suite de sommets $x_0$, $x_1$,
\ldots, $x_n$ tels que :
$$
	\forall i,\quad 0\leq i <n\Longrightarrow  (x_i,x_{i+1} ) \in U,
$$
Dans ce cas on dit que $x$ est connecté à $y$, 
et on note $x\leadsto y$.
Un chemin est dit simple quand il ne passe jamais 
plus d'une fois par un même sommet. Un circcuit est
un chemin fermé i.e. $x_0=x_n$. On définit des notions
analogue dans le cas non orienté, chemin est remplacé
par chaine, circuit par cycle.
Une fonction $f\colon U \rightarrow R$ à valeurs réelles 
sur les arêtes se prolonge aux chemins par addition. On parle
de fonction de coût et un circuit de coût strictement négatif est
dit absorbant pour $f$.


\subsection{connexité}

A condition de poser $x\leadsto x$ pour tout sommet $x$,
la realion $\leadsto$  est une relation d'équivalence : 
réflexive, symétrique et transitive. Les classes d'équivalence
sont des composantes connexes. Dans les graphes orientés,
en général, la relation n'est pas symétrique, on définit
une connexion plus forte en disant que $x$ est équivalent
à $y$ quand $x\leadsto y$ et $y\leadsto x$. Autrement dit,
$x$ et $y$ sont sur un même circuit. Les classes pour
cette relation sont des composantes fortement connexes.

\begin{figure}
\begin{center}
\includegraphics[scale=0.5]{graphe/dg.png}
\caption{\label{COMPO}Un graphe orienté avec
5  composantes fortement connexes et 2
composantes connexes. Il a été réalisé avec 
la commande \shell{neato} à partir de
la source \href{./graphe/dg.dot}{dg.dot}}
\end{center}
\end{figure}

\subsection{Quelques problèmes}

La théorie des graphes a été introduite
par Léonard Euler. Dans un article publié
en 1759, il pose la question de l'existence
d'une promenade passant par les sept pont
de la ville de Koenigsberg.


\begin{center}
\begin{figure}
\includegraphics[scale=0.75]{img/koenigsberg.png}
\caption{\label{KOENIG} Pour des raisons de parité
et de degré, il n'existe pas de
promenade Eulérienne passant par les sept ponts
de la ville de Koenigsberg.}
\end{figure}
\end{center}

Il s'agit d'un problème algorithmiquement 
facile : l'existence
d'un chemin Eulérien dépend du nombre de sommets pairs. L'algorithme
de Dijkstra détermine le plus cours chemin entre deux sommets en un temps
polynomial. Le
problème du voyageur de commerce est difficile 
car il décide en particulier de l'existence d'un 
chemin Hamiltonien, 
un problème dit NP-complet parmi d'autres : colorabilité,
isomorphisme de graphe etc\ldots. 

\begin{exercice}
Montrer qu'un graphe connexe est Eulérien si et seulement
si le nombre de sommets de degrés pairs est 0 ou 2. 
\end{exercice}

\subsection{Parcours de graphe}


\begin{lstlisting}[float, style=algo, emph={arete, arbre}]
globale index : entier
proc pp( x, U )
     v[x] := index++
     pour chaque (x,y) dans U
       si v[y] = 0  alors
	   // arete (x,y)  
           pp( y, U  )
       fsi
     fip


PP( X , U )
index := 0
initialiser v := {0}
pour x dans X
   si 0 == v[x] alors
      // arbre
      pp( x )
  fsi
fip
\end{lstlisting}

L'algorithme \algo{PP(X, U)} effectue un parcours en
profondeur du graphe $(X,U)$. La valeur $v(x)$ contient
l'ordre de visite du sommet $x$. Les arêtes émises lors
de ce parcours constituent une forêt. 




\subsection{Algorithme de Tarjan}

L'algorithme de Tarjan (1972) s'appuie sur une
pile et un parcours en profondeur pour
déterminer les composantes fortement
connexes d'un graphe $(X,U)$.


\begin{lstlisting}[float, style=algo]
cfc-Tarjan( X, U )
globale index : entier
index := 0
pour x dans X
   si ! vu[x] alors
      parcours( x )
   fsi
fip
\end{lstlisting}

\begin{lstlisting}[float, style=algo]
parcours( x : sommet  )
index  := index + 1
rep[x] := num[x] := index
empiler( x )
pour x -> y faire
   si num[ y ] = 0 
     alors
      parcours( y )
      rep [ x ] := min( rep[ y ], rep[ x ] )  
     sinon
      si num[y] < num[x] alors
         si y est sur la pile
            rep[x] := min ( rep[ x ], num[ y ] )
         fsi 
      fsi 
   fsi
fip
si rep[x] = num[x] alors
   cpt := 0
   tant que num[ pile ] >= num[ x ]
        tmp := depiler
        cpt := cpt + 1 
   ftq
   emettre x, cpt
fsi
\end{lstlisting}

\begin{proposition} L'algorithme \algo{cfc-tarjan}
calcule les composante fortement connexes du graphe
$(X,U)$.
\end{proposition}
\begin{proof}
La preuve est assez délicate. On s'appuie sur un
parcours de graphe en profondeur. Au cours d'un tel
parcours, on doit détecter les racines des composantes
fortement connexes. Par définition,  une racine 
est un sommet qui minimise l'ordre de visite sur une
composante fortement connexe.

\begin{center}
       $R(x) = V(x)$  $\iff$ $x$ est une racine.
\end{center}

Il s'agit donc de prouver que l'algorithme calcule 
correctement $R(x)$ dans $rep[x]$. Les sommets 
sont empilés par numéro croissant, et par construction, 
si $y$ est empilé avant $x$ alors il existe un chemin de $y$
vers $x$, un fait qui justifie la seconde  mise-à-jour de
$rep[x]$. Quand un parcours en profondeur termine,
avec $R(x) = rep[x] = V(x)$ alors $x$ est une racine
et tous les sommets empilés au-dessus de $x$ constituent
la composante fortement connexe de $x$.
\end{proof}
 
\subsection{Bellman-Ford}

