\chapter{Théorie des graphes (Spécialité ES)}

\enlargethispage*{3em}
\begin{exointro}{Lycée Jules Ferry, Conflans-Sainte-Honorine}
  \begin{questions}
  \item Une grande surface est conçue de telle façon que six secteurs
    (alimentation, hifi, ...) notés $A$, $B$, $C$, $D$, $E$ et $F$ sont
    reliés par des allées selon le graphe ci-dessous.
\begin{center}
    \includegraphics{011_cours-p291_070}
	\end{center}
	Faire un tableau donnant le degré de chaque sommet du graphe.

      Un visiteur désire parcourir l'ensemble des allées en ne passant par
      celles-ci qu'une seule fois. Démontrer que son souhait est réalisable.


  \item On considère quatre villes ${v_{{1}},v_{{2}},v_{{3}},v_{{4}}}$
    dans un pays où le trafic aérien est encore très réduit. Il existe
    seulement un vol direct de ${v_{{1}}}$ vers ${v_{{2}}}$ et vers
    ${v_{{4}}}$, de ${v_{{2}}}$ vers ${v_{{3}}}$, de ${v_{{3}}}$ vers
    ${v_{{1}}}$ et vers ${v_{{4}}}$, de ${v_{{4}}}$ vers ${v_{{2}}}$.

    \begin{questions}
    \item Représenter ces données par un graphe.

    \item Montrer que pour deux villes quelconques
      ${v_{{i}},v_{{j}}(i\neq j)}$ il existe au moins un vol de
      ${v_{{i}}}$ vers ${v_{{j}}}$ comportant au plus deux escales.
    \end{questions}

  \item Une grande entreprise propose à ses employés deux types d'horaires
    mensuels : fixes ou variables. Chaque trimestre, tous les employés sont
    consultés sur le type d'horaires qu'ils désirent adopter au trimestre
    suivant.

    Au début de l'expérience, 60\,\% des employés sont favorables aux
    horaires fixes. Autrement dit l'état probabiliste initial est décrit
    par la matrice ligne $E_0=\begin{pmatrix}
    0,6 & 0,4\end{pmatrix}$.

    On estime qu'un employé préférant les horaires fixes un trimestre
    garde sept fois sur dix le même avis au trimestre suivant, alors qu'un
    employé préférant les horaires variables change d'avis une fois sur
    cinq au trimestre suivant.
    \vspace*{-2em}
\BreakWithoutItem
    \begin{questions}
    \item Traduire cette situation à l'aide d'un graphe probabiliste.

    \item Donner l'état probabiliste deux trimestres après le début de
      l'expérience.

    \item Déterminer l'état probabiliste stable. Interpréter le résultat
      obtenu.
    \end{questions}
    
    \item  Le plan d'une série de parcelles est donnée sur la page suivante. On ne veut pas avoir deux cultures identiques sur des parcelles adjacentes. Combien faut-il cultiver de plantes différentes, et comment organiser les cultures pour y parvenir ?
\Par
\begin{minipage}{3.8cm}
\begin{center}
\includegraphics{11_fig_08}
\Par
Plan
\end{center}
\end{minipage}
\hfill
\begin{minipage}{3.8cm}
\begin{center}
\includegraphics{11_fig_05}\Par
Graphe
\end{center}
\end{minipage}

\Par

Les sommets du graphe $\mathcal{G}$ représentent les champs, les arêtes représentent les bordures communes.
\begin{questions}
\item Tracer les arêtes d'après le plan.
\item Colorier le graphe $\mathcal{G}$ et en déduire une répartition possible des cultures.
\end{questions}
  \end{questions}
  \vspace*{-1.7em}
\end{exointro}

\vspace*{-0.7em}\enlargethispage*{3em}
\section{Graphes non orientés}

\subsection{Généralités}

\begin{defins}
  \begin{itemize}
  \item Un graphe non orienté est constitué de sommets dont certains sont reliés par des arêtes.
  \item Deux sommets reliés par une arête sont dits adjacents.
  \item Un graphe complet est un graphe dont tous les sommets sont adjacents.
  \item Le nombre de sommets présents dans un graphe est l'ordre du graphe.
  \item Le degré d'un sommet est le nombre d'arêtes dont ce sommet est une extrémité.
  \item Un sous-graphe d'un graphe $\mathcal{G}$ d'ordre $k$ est constitué de $k$ sommets de $\mathcal{G}$ et de toutes les arêtes de $\mathcal{G}$ reliant deux de ces $k$ sommets.
  \end{itemize}
\end{defins}

\begin{thm}\label{thm-somme-degres}
  La somme des degrés d'un graphe non orienté est égal à deux fois le  nombre d'arêtes du graphe.
\end{thm}

\subsection{Matrice associée à un graphe non orienté}

\begin{defin}
  La matrice d'adjacence associée à un graphe non orienté d'ordre $n$ dont les
  sommets sont numérotés de 1 à $n$ est la matrice carrée symétrique d'ordre $n$ où le terme à l'intersection de la $i$\ieme{}  ligne et de la $j$\ieme{} colonne est égal au nombre d'arêtes reliant $i$ et $j$ (on mettra 0 s'il n'y a pas d'arête entre $i$ et $j$).
\end{defin}

\subsection{Chaîne et cycle}


\begin{defins}
  \begin{itemize}
  \item Une chaîne est une liste ordonnée de sommets telle que chaque sommet de la liste soit adjacent au suivant.
  \item La longueur d'une chaîne est le nombre d'arêtes qui la composent.
  \item Une chaîne fermée est une chaîne dont l'origine et l'extrémité sont confondues.
  \item Un cycle est une chaîne fermée composée d'arêtes toutes distinctes.
  \item La distance entre deux sommets est la plus courte longueur des chaînes qui les relient.
  \item Le diamètre d'un graphe est la plus grande distance entre deux sommets du graphe.
  \end{itemize}
\end{defins}

\begin{thm}\label{thm:11-majchi}
  Si $A$ est la matrice d'adjacence associée à un graphe, le terme $a_{ij}$ (ligne $i$, colonne $j$) de la matrice $A^r$ donne le nombre de chaînes de longueur $r$ reliant $i$ à~$j$.
\end{thm}


\subsection{Graphe connexe}

\begin{defin}
On dit qu'un graphe est connexe s'il existe toujours une chaîne entre deux sommets distincts.
\end{defin}

\subsection{Chaîne eulérienne et cycle eulérien}

\begin{defin}
  Une chaîne eulérienne est une chaîne qui contient une et une seule fois chaque arête du graphe. Si cette chaîne est un cycle, on parle
  de cycle eulérien.
\end{defin}

\begin{thm}[d'Euler]\label{thm:11-euler}
  Un graphe connexe admet une chaîne eulérienne si et seulement si le
  nombre de sommets de degré impair vaut 0 ou 2.

  Un graphe connexe admet un cycle eulérien si et seulement si tous ses
  sommets sont de degré pair.
\end{thm}

\subsubsectionnn{Algorithme d'Euler}

Cet algorithme sert à déterminer une chaîne eulérienne dans le cas où le théorème d'Euler a prouvé son existence.
\begin{questions}
\item 
\begin{itemize}
\item s'il y a deux sommets de degré impair, on construit une chaîne joignant ces deux sommets (peu importe la chaîne).
\item s'il n'y a pas deux sommets de degré impair (seul autre cas possible), on construit un cycle à partir d'un sommet quelconque.
\end{itemize}
Si toutes les arêtes sont marquées, on a obtenu une chaîne eulérienne, sinon :

\item On choisit un sommet de la chaîne précédente et on insère une chaîne fermée, donc allant de ce sommet à ce même sommet, ne contenant pas deux fois la même arête et, bien sûr, ne contenant aucune des arêtes déjà utilisées.

Si toutes les arêtes sont marquées, on a obtenu une chaîne eulérienne.

Sinon, on recommence cette deuxième étape jusqu'à ce que toutes les arêtes soient marquées.
\end{questions}

\subsection{Coloration d'un graphe}

Colorier un graphe consiste à affecter une couleur à chaque sommet, de sorte que deux sommets adjacents ne portent pas la même couleur.

Le nombre chromatique du graphe est le plus petit nombre de couleurs nécessaires à son coloriage. 

Voici une méthode pour colorier un graphe :

\subsubsectionnn{Algorithme de Welch-Powell}

\begin{questions}
\item Ranger les sommets du graphe dans l'ordre décroissant de leurs degrés  (pour les ex-{\ae}quo, faire un choix arbitraire).
\item Choisir une nouvelle couleur, dite « courante » et colorier ainsi le premier sommet de la liste non encore colorié.
\item Dans la liste des sommets, colorier avec la couleur courante, en suivant l'ordre choisi initialement, tous les sommets non encore coloriés et qui ne sont pas adjacents à un sommet colorié avec cette couleur.
\item Si tous les sommets ne sont pas encore coloriés, revenir à l'étape 2.
\end{questions}

Cette technique peut être utile quand on a des incompatibilités entre deux \og tâches \fg{} : des exemples de sujets font référence à des produits ne pouvant pas être transportés dans le même camion, ou des poissons ne pouvant cohabiter dans le même aquarium par exemple.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Graphes orientés}

\subsection{Généralités}

\begin{defins}
  \begin{itemize}
  \item Un graphe orienté est un graphe dont les arêtes sont orientées.
    Une boucle est une arête orientée dont l'origine et l'extrémité sont
    les mêmes.
  \item On définit de même une chaîne orientée, une chaîne eulérienne
    orientée, un cycle orienté.
  \end{itemize}
\end{defins}

\subsection{Matrice d'adjacence associée à un graphe orienté}

\begin{defin}
  La matrice d'adjacence associée à un graphe orienté d'ordre $n$ dont les sommets
  sont numérotés de 1 à $n$ est une matrice carrée d'ordre $n$,
  où le terme à l'intersection de la $i$\ieme{} ligne et de la $j$\ieme{}
  colonne est égal au nombre d'arêtes dont l'origine est $i$ et
  l'extrémité $j$.\\
  Comme il y a souvent au maximum une arête allant de $i$ à $j$, la matrice ne comprend très souvent que des 1 et des 0.
\end{defin}

\begin{thm}
  Si $A$ est la matrice d'adjacence associée à un graphe, le terme $a_{ij}$ (ligne $i$, colonne $j$) de la matrice $A^r$ donne le nombre de chaînes de longueur $r$ partant de $i$ et aboutissant en $j$.
\end{thm}

\newpage

\subsection{Graphe étiqueté}

\begin{defins}
  \begin{itemize}
  \item Un graphe étiqueté est un graphe orienté dont les arêtes sont
    affectées d'étiquettes (mots, nombres, \dots).
  \item Un graphe pondéré est un graphe étiqueté dont toutes les
    étiquettes sont des nombres positifs.
  \item Le poids d'une chaîne est la somme des poids des arêtes
    orientées qui la composent.
  \item Une plus courte chaîne entre deux sommets est parmi les chaînes
    qui les relient, une chaîne de poids minimum.
  \end{itemize}
\end{defins}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Recherche de la plus courte chaîne}
Dans plusieurs situations, il est intéressant de trouver la plus courte chaîne allant d'un sommet à un autre d'un graphe pondéré connexe. \\
L'algorithme de Dijkstra permet dans des cas assez simples de résoudre ce problème. 
En voici une description :

\subsectionnn{Algorithme de la plus courte chaine ou algorithme de Dijkstra}

\begin{questions}
\item Placer tous les sommets du graphe dans la 1\iere{} ligne d'un tableau.

Sur la 2\ieme{} ligne du tableau, écrire le coefficient \og 0 \fg{} sous le point de départ E et le coefficient \og $\infty$ \fg{}  sous les autres sommets.

\item Repérer le sommet X de coefficient minimal. Commencer une nouvelle ligne et rayer toutes les cases vides sous X.

\item 
Pour chaque sommet Y adjacent à X, calculer la somme $p$ du coefficient de X et du poids de l'arête reliant X à Y ;
\begin{itemize}
\item Si $p$ est strictement inférieur au coefficient de Y, inscrire $p$ et X dans la case correspondante de la colonne « Y » ;
\end{itemize}
Pour les sommets non adjacents à X, compléter la ligne par les coefficients de la ligne précédente.

\item S'il reste des sommets non sélectionnés, retourner à l'étape 2.

Sinon, passer à l'étape 5.

\item La longueur minimale est le nombre lu sur la dernière ligne et on l'obtient en remontant les lettres.
\end{questions}


\section{Graphes probabilistes}


\begin{defins}
  \begin{itemize}
  \item Un graphe probabiliste est un graphe orienté, pondéré, tel que
    la somme des poids des arêtes sortant de chaque sommet donné vaut 1.
    Les sommets du graphe sont les états possibles et le poids d'une
    arête orientée issue du sommet i et d'extrémité j est la probabilité
    de transition de l'état i à l'état j.
  \item L'état probabiliste est une loi de probabilité sur l'ensemble
    des états possibles représentée par une matrice ligne, donc la somme des termes vaut 1.
  \item La matrice de transition d'un graphe probabiliste d'ordre $n$ est
    une matrice carrée d'ordre $n$. Le terme à l'intersection de la i-ième
    ligne et de la j-ième colonne a pour valeur le poids de l'arête
    allant de i vers j si cette arête existe, 0 sinon, les sommets du graphes étant numérotés de 1 à $n$.
  \end{itemize}
\end{defins}

\begin{Remarque}on peut donc vérifier que la somme des termes de chaque ligne est égale à 1.
\end{Remarque}

\begin{thm}
  Si $M$ est la matrice de transition d'un graphe probabiliste, si $P_0$
  est la matrice ligne décrivant l'état initial et $P_k$ l'état
  probabiliste à l'étape $k$, on a\linebreak $P_k=P_0\times M^k$.
\end{thm}

\begin{thm}
  Pour tout graphe probabiliste d'ordre 2 dont la matrice ne comporte
  pas de 0, l'état $P_k$ à l'étape $k$, converge vers un état $P$
  indépendant de l'état initial $P_0$. De plus, on a : $P=PM$.
\end{thm}

$P$ est appelé l'état stable du graphe probabiliste.

\begin{Remarque}consultez le site WIMS http\string://wims.auto.u-psud.fr pour des
  exercices interactifs sur les graphes (notamment sur l'algorithme de
  Dijkstra).
\end{Remarque}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{solintro}
\begin{questions}
\item Le graphe ci-dessous donne la liaison entre les différents secteurs de la grande surface.
\begin{center}
\includegraphics{011_coursSolintro1-p297_071}
\end{center}
\vspace*{-2em}
\BreakWithoutItem %%%%%%%%%%%%%%%%%%%%%%%%%%%%% Break
Le degré de chaque sommet du graphe est donné par le tableau suivant :
\Par
\begin{tabularx}{\linewidth}{|L|*6{>{\centering\arraybackslash}X|}}
\hline
Sommet & A & B & C & D & E & F\\
\hline
Degré & 4 & 3 & 4 & 4 & 3 & 2 \\
\hline
\end{tabularx}
\Par
	Ce graphe est connexe, de plus il y a exactement 2 sommets de degré
	impair donc, d'après le théorème d'Euler, le graphe admet une chaîne
	eulérienne, ce qui veut dire qu'il existe une chaîne qui contient une
	fois et une seule chaque arête du graphe. Cela veut dire
	\emph{qu'il est possible de parcourir l'ensemble des allées en ne
	  passant par celles-ci qu'une seule fois}. Par exemple le chemin :
	EDCBFDAECAB (E et B sont les deux sommets de degré impair).  
	\begin{Remarque}un graphe connexe admet une chaîne eulérienne si et seulement
	  si le nombre de sommets de degré impair vaut 0 ou 2.
	\end{Remarque}
    
  \item
    \begin{questions}
    \item Représentons les données par un graphe orienté à quatre sommets
      numérotés 1 à 4, le sommet $i$ représentant la ville $v_i$,
      une arête orientée allant de $i$ vers $j$ s'il existe un vol de la ville
      $v_i$ vers la ville $v_j$.
   
      Le graphe est représenté ci-dessous : 

      \begin{center}
        \includegraphics{011_coursSolintro1-p297_072}
      \end{center}

    \item La question revient à montrer qu'il existe toujours un chemin de
      longueur inférieure ou égale à 3  (au plus deux escales, donc au plus
      trois étapes par vol) allant d'un sommet quelconque $i$ à un sommet
      quelconque $j$ $(i{\neq}j)$.

      La matrice M associée au graphe est :
      ${M=\left(\begin{matrix}0&1&0&1\\0&0&1&0\\1&0&0&1\\0&1&0&0\end{matrix}\right)}$.

      Calculons les matrices $M^2$ et $M^3$ avec une calculatrice :
      \[{M^{{2}}=\left(\begin{matrix}0&1&1&0\\1&0&0&1\\0&2&0&1\\0&0&1&0\end{matrix}\right)}
	  \qquad \text{ et } \qquad 
	  {M^{{3}}=\left(\begin{matrix}1&0&1&1\\0&2&0&1\\0&1&2&0\\1&0&0&1\end{matrix}\right)}
	  \]

      Le coefficient ${\alpha}_{ij}$ de la matrice $M$ donne le nombre de
      vols entre $i$ et $j$ en une étape (vol direct).

     
     % \vspace*{-2em}
      
		\BreakWithoutItem %%%%%%%%%%%%%%%%%%%%% Break
		Le coefficient ${\alpha}_{ij}$ de la matrice $M^2$ donne le nombre de
      vols entre $i$ et $j$ en deux étapes.
      
      Le coefficient ${\alpha}_{ij}$ de la matrice $M^3$ donne le nombre de
      vols entre $i$ et $j$ en trois étapes.

      Soit la matrice $S=M+M^2+M^3$, $S=(s_{ij})$.

      Le nombre de chemins allant du sommet $i$ au sommet $j$ de longueur
      1, 2 ou 3, c'est-à-dire le nombre de vols recherchés de la ville $i$ à
      la ville $j$ est donné par $s_{ij}$.

      Déterminons $S$ :
      \[{S=M+M^{{2}}+M^{{3}}=\left(\begin{matrix}1&2&2&2\\1&2&1&2\\1&3&2&2\\1&1&1&1\end{matrix}\right)}.\]
      Par exemple, il existe 3 vols en 1, 2 ou 3 étapes reliant la ville
      $v_3$ à la ville $v_2$.
	  
      Il n'y a aucun 0 dans la matrice $S$, il existe donc toujours un vol
      de $v_i$ vers $v_j$ comportant au plus deux escales.
    \end{questions}

  \item
    \begin{questions}

    \item On définit un graphe $\mathcal{G}$ à deux états (sommets) : $F$ (horaires
      fixes) et $V$ (horaires variables).

      Une arête de $\mathcal{G}$ représente une transition entre deux états d'un
      trimestre à l'autre.

      Sachant que les employés ayant des horaires fixes un trimestre
      conserve cet état le trimestre suivant sept fois sur dix, la boucle
      $F{\rightarrow}F$ est pondérée par 0,7.

      De même, l'arête $V{\rightarrow}F$ est pondérée par 0,2 car les employés
      ayant des horaires variables un trimestre change d'état le trimestre
      suivant une fois sur cinq.

		
		 
      On obtient le graphe probabiliste ci-dessous :
	  
      \begin{center}
        \includegraphics{011_coursSolintro1-p299_073}
      \end{center}


    \item Les sommets $F$ et $V$ étant nommés dans cet ordre (comme pour
      $E_0$), la matrice de transition associée à ce graphe est
      ${M=\left(\begin{matrix}0,7&0,3\\0,2&0,8\end{matrix}\right)}$.
 
      L'état probabiliste deux trimestres après le début de l'expérience est
      $E_2=E_0\times M^2$.
\BreakWithoutItem %%%%%%%%%%%%%%%%%%%%%%%%%%%%% Break
      On trouve
      $M^{{2}}=\left(\begin{matrix}0,\text{55}&0,\text{45}\\0,3&0,7\end{matrix}\right)$.\\
      Ainsi,     $E_{{2}}=\left(\begin{matrix}0,6&0,4\end{matrix} \right)\times\left(\begin{matrix}0,\text{55}&0,\text{45}\\0,3&0,7\end{matrix}\right)$, 
      soit
      $E_{{2}}=\left(\begin{matrix}0,\text{45}&0,\text{55}\end{matrix}\right)$.


    \item Le graphe probabiliste est d'ordre 2 et sa matrice ne comporte pas
      de 0, l'état $E_k$ à l'étape $k$, converge vers un état $E$
      indépendant de l'état initial $E_0$, de plus $E=E\times M$.

      Soit ${E=\left(\begin{matrix}x&y\end{matrix}\right)}$ avec $x$ et $y$
      réels positifs et $x+y=1$.
\begin{align*}
E=E\times M & \iff \begin{pmatrix}x&y\end{pmatrix}=\begin{pmatrix}x&y\end{pmatrix}\begin{pmatrix}0,7&0,3\\0,2&0,8\end{pmatrix}\\
& \iff \begin{pmatrix}x&y\end{pmatrix}=\begin{pmatrix}0,7x+0,2y&0,3x+0,8y\end{pmatrix}
\end{align*}
Il faut les deux réels $x$ et $y$ positifs tels que $E=E\times M$ et\\ $x+y=1$.

On aboutit aux systèmes suivants :
\Par
\hspace*{-1em}
\mbox{$\left\{
\begin{array}{r@{\,=\,}l}
0,7x+0,2y&x\\
0,3x+0,8y&y\\
x+y&1
\end{array}
\right.
\Leftrightarrow
\left\{
\begin{array}{r@{\,=\,}l}
-0,3x+0,2y&0\\
0,3x-0,2y&0\\
x+y&1
\end{array}
\right.
\Leftrightarrow
\left\{
\begin{array}{r@{\,=\,}l}
0,3x&0,2y\\
x+y&1
\end{array}
\right.$}
\Par
On obtient finalement $x=0,6$ et $y=0,4$. 

L'état probabiliste stable E du graphe est donc $\begin{pmatrix}0,4 & 0,6\end{pmatrix}$.

Ainsi, après un très grand nombre de trimestres, 60\,\% du personnel sera favorable aux horaires variables et seulement 40\,\% aux horaires fixes.
\end{questions}


\item 
\begin{questions}
\item Voici le graphe complété par ses arêtes :

\begin{center}
\includegraphics{11_fig_06}
\end{center}

\Break %%%%%%%%%%%%%%%%%%%%%%% Break

\item \raisebox{-0.7em}{\begin{tabularx}{\linewidth}{|L|*7{>{\centering\arraybackslash}X|}}
\hline
Sommet & $b$ & $g$ & $a$ & $c$ & $d$ & $e$ & $f$\\
\hline
Degré & 5 & 5 & 4 & 4 & 4 & 4 & 4\\
\hline
\end{tabularx}}
\end{questions}

\Par

On choisit par exemple la couleur rouge, qu'on affecte à $b$, puis à $g$ qui n'est pas adjacent. Tous les autres sommets sont adjacents à $b$, donc on prend une autre couleur, par exemple bleu, et on l'affecte au sommet suivant de la liste, donc $a$, ainsi que $e$ qui ne lui est pas adjacent. Les sommets restants sont adjacents à $a$ ou à $e$, ou déjà coloriés.

On choisit donc une troisième couleur, jaune, et on l'affecte à $c$ et à $d$. Tous les autres sommets sont soit coloriés, soit adjacents à $c$ ou à $d$.

Il nous faut donc une quatrième couleur, par exemple vert, pour colorier~$f$.
\begin{center}
\includegraphics{11_fig_07}
\end{center}
Donc il faudra faire une première culture sur $b$ et $g$, une deuxième sur $a$ et $e$, une troisième sur $c$ et $d$, et une dernière sur $f$.

\end{questions}
\end{solintro}

\endinput
