typo ensemble13.tex

[cours-maths-dis.git] / graphes / GraphesNonOrientes.tex

La notion de graphe généralise amplement la notion de relation sur un ensemble ; elle s'intéresse à la façon dont sont liés les objets. Avec les plans de métro, les cartes routières, les schémas de circuits électriques, les formules des molécules, les organigrammes, les arbres généalogiques, on utilise chaque jour des graphes...

\section{Définitions et premiers exemples}


\subsection{Définitions}

\begin{Def}[Graphe non orienté, sommet, arête]
Un \emph{graphe non orienté}\index{graphe!non orienté} $G = (S, A)$ est défini par l'ensemble fini $S = \{s_1, s_2, ..., s_n\}$ dont les éléments sont appelés \emph{sommets}\index{sommet}, et par l'ensemble fini $A = \{a_1, a_2, ..., a_m\}$ dont les éléments sont appelés \emph{arêtes}\index{arête}.

Une arête $a$ de l'ensemble $A$ est définie par une paire non-ordonnée de sommets, appelés les \emph{extrémités} \index{extrémités} de $a$. Si les extrémités coïncident, on parle de \emph{boucle}\index{boucle}.

Si l'arête $a$ relie les sommets $s_i$ et $s_j$, on dira que ces sommets sont \emph{adjacents}\index{sommet!adjacent}, ou incidents avec $a$, ou encore que l'arête $a$ est incidente avec les sommets $s_i$ et $s_j$.

On notera qu'un graphe a au moins un sommet ; on notera par la suite \emph{ordre}\index{graphe!ordre}\index{ordre d'un graphe} d'un graphe son nombre de sommets.
\end{Def}

%
% \begin{Rem}
% On peut définir autrement cet objet, et certains auteurs choisissent celle-ci : \og Un \emph{graphe non orienté}\index{graphe!non orienté} est un triplet $(S, A, \delta )$, où
% \begin{enumerate}
% \item $S$ est un ensemble fini non vide,
% \item $A$ est un ensemble fini,
% \item $\delta$ est une fonction de $A$ dans $S_2 \cup S$, où $S_2$ est l'ensemble des parties à 2 éléments de $S$.
% \end{enumerate}\fg{}
% Ces définitions sont évidemment équivalentes. Il se pourra, dans la suite de cours, que l'on utilise par moment cette deuxième définition...
% \end{Rem}


\begin{Rem}
Dans le présent chapitre, et ses proches successeurs, graphe signifie graphe non orienté (même quand cela n'est pas spécifié). Il existe aussi des graphes orientés ; ils seront étudiés plus loin.
\end{Rem}

\begin{Rem}
La définition précédente n'interdit pas la possibilité que deux mêmes sommets soient reliés par deux arêtes différentes.
\end{Rem}



\subsection{Représentation graphique et notion de graphes pondérés}

Les graphes non orientés admettent une représentation graphique permettant leur visualisation :

\begin{center}
\includegraphics[scale=0.7]{graphes/completK5}
\end{center}


\newpage
Signalons aussi dès à présent la possibilité de pondérer les arêtes d'un graphe non orienté (la définition de graphe est alors à adapter) :

\begin{center}
\includegraphics[scale=0.7]{graphes/exemples.eps}
\end{center}


% \begin{Exo}
% On a 6 wagons à trier. Dans la gare de triage, les wagons entrent dans l'ordre 2, 5, 3, 6, 1, 4 et doivent sortir dans l'ordre croissant. Deux wagons i et j peuvent être mis sur la même voie si et seulement s'ils entrent dans l'ordre dans lequel ils doivent sortir.
% \begin{enumerate}
% \item Dessinez un graphe illustrant la situation, en indiquant ce que représentent les sommets et les arêtes de votre graphe.
% \item Quel sera le nombre minimal de voies nécessaires au tri?
% \end{enumerate}
% \end{Exo}



\subsection{Degré, chaîne}

\subsubsection{Degré d'un sommet, d'un graphe}

\begin{Def}[Degré d'un sommet]
On appelle \emph{degré} d'un sommet $s$, noté $d(s)$, le nombre d'arêtes dont le sommet $s$ est une extrémité (les boucles comptent pour deux).
\end{Def}

\begin{Th}[Lemme des poignées de mains]
La somme des degrés des sommets d'un graphe est égale à deux fois le nombre d'arêtes.
\end{Th}


\begin{Def}[Degré d'un graphe]
Le degré d'un graphe est le degré maximum de tous ses sommets.
\end{Def}

\begin{Exo}
Calculez les degrés des sommets, et le degré des graphes ci-dessus.
\end{Exo}



\begin{Def}[Graphe régulier]
Un graphe dont tous les sommets ont le même degré est dit \emph{régulier}\index{graphe!régulier}. Si le degré commun est k, alors on dit que le graphe est k-régulier.
\end{Def}

\begin{Exo}
Les graphes précédent sont-ils réguliers ?
\end{Exo}

\begin{Exo}
Représentez un graphe 3-régulier.
\end{Exo}

On reviendra sur cette notion dans la section exercices de la fin du paragraphe.

\subsubsection{Chaîne}

\begin{Def}[Chaîne]
Une chaîne dans G, est une suite de la forme $$(s_0, a_1, s_1, a_2, ..., s_{k-1}, a_k, s_k)$$
\begin{itemize}
\item ayant pour éléments alternativement des sommets ($s_i$) et des arêtes ($a_i$),
\item commençant et se terminant par un sommet,
\item et telle que les extrémités de $a_i$ soient $s_{i-1}$ et $s_i$, $i = 1, ..., k$.
\end{itemize}
\end{Def}

\noindent $s_0$ est appelé le \emph{départ} de la chaîne et $s_k$ l'\emph{arrivée}.

\begin{Rem}
On a choisi ici de réserver le terme de \emph{chemin} aux graphes orientés.
\end{Rem}


\begin{Def}[Sommet accessible]
Dans un graphe (orienté ou non), on dit que le sommet $s'$ est \emph{accessible}\index{sommet!accessible} à partir du sommet $s$ s'il existe une chaîne menant de $s$ à $s'$.
\end{Def}

\begin{Rem}
On dit aussi qu'on peut \emph{atteindre} $s'$ à partir de $s$.
\end{Rem}

\begin{Def}[Chaîne élémentaire]
Une chaîne dans laquelle tous les sommets sont différents s'appelle une \emph{chaîne élémentaire} \index{chaîne!élémentaire}.
\end{Def}

\begin{Rem}
On parle aussi de chaîne \emph{simple}\index{chaîne!simple}.
\end{Rem}

\begin{Rem}
Une chaîne simple a forcément toutes ses arêtes différentes, et ne contient évidemment pas de boucle.
\end{Rem}


\begin{Th}[Existence de chaînes élémentaires]
\'Etant donné une chaîne qui joint $s$ et $s'$ (différents), on peut toujours lui enlever arêtes et sommets pour obtenir une chaîne \emph{élémentaire} joignant $s$ à $s'$.
\end{Th}


\begin{Exo}
Réfléchir à la preuve de cette existence.
\end{Exo}


\subsection{circuit{}-cycle}

\begin{Def}[Circuit]
Une chaîne de longueur $n$ dont le départ et l'arrivée co\"incident s'appelle un \emph{circuit}\index{circuit} de longueur $n$.
\end{Def}



\begin{Ex}
Une boucle est un circuit de longueur 1.
\end{Ex}



\begin{Def}[Cycle]
Un circuit dont tous les sommets et toutes les arêtes sont différentes, s'appelle un \emph{cycle.}\index{cycle}
\end{Def}

\begin{Exo}
Représentez un graphe qui admet :
\begin{enumerate}
\item un circuit,
\item un cycle.
\end{enumerate}
\end{Exo}




\begin{Def}[Graphe simple]
Un graphe est dit \emph{simple}\index{graphe!simple}, s'il ne contient pas de boucles et s'il n'y a pas plus d'une arête reliant deux mêmes sommets.
\end{Def}

\begin{Exo}
Représentez un graphe simple (resp. qui n'est pas simple).
\end{Exo}


\subsection{Exercices}

\begin{Exo}
On s'intéresse aux graphes 3-réguliers simples.
\begin{enumerate}
\item Essayez de construire de tels graphes ayant 4 sommets, 5 sommets, 6 sommets, et 7 sommets.
\item Qu'en déduisez-vous?
\end{enumerate}
\end{Exo}

\textit{\underline{Réponse :}} D'après le lemme des poignées de mains, la somme des degrés des sommets est égale au double du nombre d'arêtes. Si chaque sommet est de degré 3, la somme des degrés des sommets est :
\begin{itemize}
\item paire, si le nombre de sommets est pair,
\item impaire, sinon.
\end{itemize}
Comme cette somme doit être égale à un nombre pair (le double du nombre d'arêtes), seuls les graphes 3-réguliers ayant 4, ou 6 sommets, sont possibles.


\begin{Exo}
Montrez qu'un graphe simple a un nombre pair de sommets de degré impair.
\end{Exo}


\textit{\underline{Réponse :}} D'après le lemme des poignées de mains, la somme $S$ des degrés des sommets est égale au double du nombre d'arêtes, donc cette somme est paire. D'autres part, $S$ est égale à la somme :
\begin{itemize}
\item des degrés pairs,
\item des degrés impairs
\end{itemize}
La somme des degrés pairs est paire. \'Etudions la somme $S'$ des degrés impairs : notons $i_0$ le nombre de sommets de degrés impairs. Cette somme $S'$ est égale à $\sum_{k=1}^{i_0} (2 k_i + 1)$, puisque chaque degré est ici impairs. Donc $S' = 2 \left(\sum_{k=1}^{i_0} k_i \right) + i_0$, soit $S'$ est égale à un nombre pair plus $i_0$. Quand on met tout bout à bout, on obtient finalement l'équation en parité : pair + pair + $i_0$ = pair, soit $i_0$ est pair !

\begin{Exo}
Est-il possible de relier 15 ordinateurs de sorte que chaque appareil soit relié avec exactement trois autres?
\end{Exo}


\textit{\underline{Réponse :}} Non, application directe de l'exercice précédent.

\begin{Exo}
Un groupe de 15 fans d’un chanteur célèbre, possède les deux particularités suivantes :
\begin{itemize}
\item Chaque personne connaît au moins 7 autres
\item Toute information détenue par une personne est répercutée dans la minute qui suit à ses connaissances (et uniquement à elles)
\end{itemize}
Quel est le temps maximal entre le moment où une des 15 fans apprend une chose nouvelle sur leur idole, et celui où le groupe entier est au courant ?
\end{Exo}


\textit{\underline{Réponse :}} L'éméteur de l'information est un sommet relié à au moins 7 autres. Notons $I$ l'ensemble de ces sommets.
Il reste au plus 7 sommets (15-(7+1)). Notons $J$ cet ensemble.
Chacun des sommets de $J$ est nécessairement relié à un des sommets  de $I$, sinon il ne serait relié qu'à 6 sommets.
L'information met donc au plus 2 mins.



\section{Quelques types particuliers de graphes}

\subsection{Graphes planaires}
\begin{Def}[Graphe planaire]
Si on arrive à dessiner le graphe sans qu'aucune arête n'en coupe une autre (les arêtes ne sont pas forcément rectilignes), on dit que le graphe est \emph{planaire}\index{graphe!planaire}.
\end{Def}

\begin{Exo}
Représentez un graphe planaire.
\end{Exo}

\begin{Exo}
Représentez un graphe non planaire.
\end{Exo}

\begin{Rem}
Les graphes planaires seront plus systématiquement étudiés au chapitre suivant.
\end{Rem}


\subsection{Multigraphes}

En général, dans ce cours, les graphes étudiés sont simples. On a cependant vu qu'il pouvait, pour un graphe quelconque, exister des boucles, voire des arêtes multiples : on parle, dans ce cas, de \index{multigraphe}\emph{multigraphe}.

\begin{Ex}
Un exemple de multigraphe :

\begin{center}
\includegraphics[scale=0.7]{graphes/grapheNonSimple.eps}
\end{center}
\noindent S = \{1, 2, 3, 4\}

\noindent A = \{(1,1), (1,3), (1,4), (2,3), (2,3), (3,4)\}
 \end{Ex}

\subsection{Graphes connexes}

\begin{Def}[Graphe connexe]
Un graphe est \emph{connexe}\index{graphe!connexe} s'il est possible, à partir de n'importe quel sommet, d'atteindre n'importe quel autre sommet du graphe (si, pour tout couple de sommets $(s, s')$, il existe une chaîne reliant $s$ à $s'$).
\end{Def}


\begin{Rem}
C'est en particulier le cas lorsqu'à partir d'un sommet on peut atteindre tous les autres sommets.
\end{Rem}



\begin{Exo}
Représenter un graphe (non orienté) connexe, et un graphe non connexe.
\end{Exo}






\begin{Def}[Composantes connexes]
Un graphe non connexe se décompose en \emph{composantes connexes}\index{composantes connexes!d'un graphe}.
\end{Def}


\begin{Ex}
Exemple d'un graphe n'étant pas connexe :
\begin{center}
\includegraphics[scale=0.7]{graphes/grapheNonConnexe.eps}
\end{center}

\noindent S = \{1, 2, 3, 4, 5, 6\}

\noindent A = \{(1,3), (1,4), (2,3), (3,4), (5,6)\}\\


Ici, les composantes connexes sont \{1, 2, 3, 4\} et \{5, 6\}.
\end{Ex}

\subsection{Graphes complets}

\subsubsection{Définition}

\begin{Def}[Graphe complet]
Un graphe est \emph{complet}\index{graphe!complet} si chaque sommet du graphe est relié directement à tous les autres sommets.
\end{Def}

\subsubsection{Exemples et exercices}

\begin{Def}[$K_n$]
On note $K_n$ tout graphe non orienté simple d'ordre $n$, tel que toute paire de sommets est reliée par une unique arête.
\end{Def}

\begin{Th}
$\forall n, K_n$ est complet.
\end{Th}

\begin{Ex}[Graphe complet $K_5$]
Exemple d'un graphe complet :
\begin{center}
\includegraphics[scale=0.7]{graphes/completK5.eps}
\end{center}

S = \{1, 2, 3, 4, 5\}

A = \{(1,2), (1,3), (1,4), (1,5), (2,3), (2,4), (2,5), (3,4), (3,5), (4,5)\}
\end{Ex}


\begin{Exo}
Combien d'arêtes possède le graphe $K_n$ ?
\end{Exo}


\noindent\textit{\underline{Réponse :}} Chacun des $n$ sommets possède $n-1$ arêtes, et chaque arête est ainsi comptée deux fois... $\dfrac{n(n-1)}{2}$.



\begin{Exo}
Un tournoi d'échecs oppose 6 personnes. Chaque joueur doit affronter tous les autres.
\begin{enumerate}
\item Construisez un graphe représentant toutes les parties possibles.
\item Quel type de graphe obtenez-vous?
\item Si l'on ne joue qu'un match par jour, combien de jours faudra-t-il pour terminer le tournoi ?
\item Aidez-vous du graphe pour répondre aux problèmes suivants :
\begin{itemize}
\item Si chaque joueur ne joue qu'un match par jour, combien de jours faudra-t-il pour terminer le tournoi?
\item Proposer un calendrier des matches.
\end{itemize}
\end{enumerate}
\end{Exo}


\subsection{Graphes biparti}

\subsubsection{Définition et premières propriétés}

\begin{Def}[Graphes biparti]
Un graphe est \emph{biparti}\index{graphe!biparti} si ses sommets peuvent être divisés en deux ensembles X et Y, de sorte que toutes les arêtes du graphe relient un sommet dans X à un sommet dans Y.
\end{Def}

On peut se rendre compte que les graphes biparti sont les graphes que l'on peut colorier avec au plus deux couleurs, de sorte que deux sommets adjacents ne possèdent jamais la même couleur. En d'autres termes, les graphes bipartis sont les graphes dont le nombre chromatique est inférieur ou égal à 2 (ce terme sera défini plus proprement dans la suite du cours).


\begin{Exo}
Responsables d'organiser des speed datings, on souhaite placer les différents individus inscrits à une soirée donnée, dans différentes salles, de telles sorte que nul ne se connaît dans une salle donnée.
\begin{enumerate}
\item Donner un exemple où cela n'est pas possible.
\item Comment modéliser ce problème à l'aide d'un graphe ?
\item Peut-on n'utiliser que deux salles, s'il est possible de placer 3 individus autour d'une table de telle sorte que chaque individu connaît ses trois voisins ? Que se passe-t-il si on remplace 3 par 5, par 7 ?
\end{enumerate}
\end{Exo}


Le résultat suivant se déduit assez aisément...

\begin{Th}
Un graphe est biparti si et seulement il ne contient pas de cycle impair.
\end{Th}

\begin{Exo}
Relier les notions de graphe biparti et de relation binaire.
\end{Exo}

\begin{Exo}
Relier les graphes N-parti aux relations N-aires, aux bases de données.
\end{Exo}



\subsubsection{Graphe biparti complet}

\begin{Def}{Graphes biparti complet}
Un graphe biparti est dit \emph{biparti complet} (ou encore est appelé une biclique) si chaque sommet de U est relié à chaque sommet de V.
\end{Def}

\begin{Ex}[Graphe biparti complet]

Exemple d'un graphe biparti complet :

\begin{center}
\includegraphics[scale=0.7]{graphes/biparti.eps}
\end{center}

S = \{1, 2, 3, 4, 5\}

A = \{(1,2), (1,4), (2,3), (2,5), (3,4), (4,5)\}

Avec les notations de la définition, on a U=\{1, 3, 5\} et V=\{2, 4\}, ou vice versa.
\end{Ex}

Un tel graphe se note $K_{3,2}$. Plus généralement,

\begin{Notation}
On note $K_{m,n}$ un graphe biparti complet liant $m$ sommets à $n$ sommets.
\end{Notation}

\begin{Th}
Ces graphes $K_{m,n}$ possèdent $mn$ arêtes.
\end{Th}




\subsection{Exercices}

\begin{Exo}
Sur un échiquier 3x3, les deux cavaliers noirs sont placés sur les cases a1 et c1, les deux cavaliers blancs occupant les cases a3 et c3.
Aidez-vous d'un graphe pour déterminer les mouvements qui permettront aux cavaliers blancs de prendre les places des cavaliers noirs, et vice versa.
\end{Exo}

\noindent\textit{\underline{Réponse :}} Faire un graphe biparti :
\begin{itemize}
\item $a_1, a_3, c_1, c_3$ d'un côté,
\item $a_2, b_1, b_2, b_3, c_2$ de l'autre.
\end{itemize}
avec des arêtes quand le passage d'une case à l'autre est possible pour un cavalier (par exemple, entre $a_1$ et $b_3$). On oriente alors les arêtes, suivant les parcours à réaliser par les cavaliers. De $a_1$, on peut envoyer le cavalier en $b_3$ ou $c_2$. Mais si on l'envoie en $c_2$, il se retrouve le coup d'après en $a_3$.


\begin{Exo}
Quel est le nombre maximal d'arêtes dans un graphe non orienté d'ordre $n$ qui ne possède pas d'arêtes parallèles ? Et si l'on suppose qu'il ne possède pas de boucle ?
\end{Exo}

\noindent\textit{\underline{Réponse :}} Le cas le pire correspond au graphe complet $K_n$, et on a déjà calculé son nombre d'arêtes : $(n-1)+...+1 = \dfrac{n(n-1)}{2}$. Rajouter des boucles revient, dans le cas le pire, à rajouter une arête sur chaqu'un des n sommets. On ajoute donc $n$ à ce qui précède, pour trouver : $\dfrac{n(n+1)}{2}$.




\section{Représentation des graphes}

Nous aimons bien communiquer par des dessins, mais les machines n'en sont pas encore là : il faut donc trouver d'autres façons de représenter les graphes.

La solution consiste à utiliser des matrices, et il y a différentes méthodes. Dans ce qui suit, on considère des graphes non pondérés, mais ces représentations s'adaptent sans problème aux graphes pondérés.

\subsection{Matrice d'incidence}

\subsubsection{Présentation}

La \emph{matrice d'incidence}\index{matrice!d'incidence} d'un graphe non orienté est une matrice $J$ à coefficients entiers dont les lignes sont repérées par les sommets d'un graphe et les colonnes par ses arêtes :

\begin{Def}[Matrice d'incidence]
Par définition, $J_{s,\varepsilon}$ vaut :
\begin{itemize}
\item 1 quand $s$ est une extrémité de l'arête $\varepsilon$ si celle-ci n'est pas une boucle,
\item 2 quand $s$ est une extrémité de la boucle $\varepsilon$,
\item 0 si $s$ n'est pas une extrémité de $\varepsilon$.
\end{itemize}
\end{Def}


On peut reconstituer un graphe non orienté à partir de sa matrice d'incidence, car elle donne le nombre de sommets, le nombre d'arêtes et elle dit comment chaque arête est liée à chaque sommet.




\begin{Exo}
Représentez le graphe non orienté dont la matrice d'incidence est :

$$\left(
\begin{array}{ccccccccc}
 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 & 0 \\
 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 \\
 0 & 0 & 0 & 1 & 0 & 0 & 2 & 0 & 1 \\
 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 \\
 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\
 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
\end{array}
\right)
$$
\end{Exo}



\begin{Exo}
 Représentez les matrices d'incidences des graphes de ce chapitre.
\end{Exo}

\begin{Exo}
Réfléchir aux avantages et inconvénients d'un tel mode de représentation des graphes.
\end{Exo}

\subsubsection{Résultat}

\begin{Th}
Si $s_1,\hdots, s_n$ sont les sommets d'un graphe non orienté, alors :
$$\left( \begin{array}{c} d(s_1) \\ d(s_2) \\ \vdots \\  d(s_n) \end{array} \right) = J \left( \begin{array}{c} 1 \\ 1 \\ \vdots \\ 1 \end{array} \right)$$
\end{Th}


\begin{Exo}
Trouvez pourquoi.
\end{Exo}


\subsection{Matrice d'adjacence}

\subsubsection{Présentation}
On peut représenter un graphe non orienté par une matrice d'adjacence.

\begin{Def}[Matrice d'adjacence]
Dans une \emph{matrice d'adjacences}\index{matrice!d'adjacence}, les lignes et les colonnes représentent les sommets du graphe.
\begin{itemize}
\item Un 1 à la position (i,j) signifie que le sommet i est adjacent au sommet j.
\item Sinon, on place un 0.
\end{itemize}
En cas de boucle (pour le sommet $i$, par exemple), on place un 1 sur la diagonale (en position $(i,i)$).
\end{Def}

\begin{Rem}
On aurait pu convenir de placer un 2 en cas de boucle. L'avantage serait de continuer à obtenir le degré des sommets en faisant les sommes par lignes. Par contre, on perdrait la possibilités, évoquée ci-dessous, de déterminer les chemins de longueur $k$.
\end{Rem}



\subsubsection{Exemple}

Considérons le graphe $G$ :

\begin{center}
\includegraphics[scale=0.75]{graphes/graphe1bx.eps}
\end{center}

Voici la matrice d'adjacences du graphe G :

$$M = \left(
\begin{array}{ccccc}
0 & 0 & 1 & 1 & 1\\
0 & 0 & 1 & 0 & 0\\
1 & 1 & 0 & 1 & 1\\
1 & 0 & 1 & 0 & 1\\
1 & 0 & 1 & 1 & 0\\
\end{array}
\right)
$$




\begin{Exo}
Décrivez le graphe G ci-dessous par une matrice d'adjacences.
\begin{center}
\includegraphics[scale=0.7]{graphes/graphe2.eps}
\end{center}
\end{Exo}


\begin{Exo}
 Représentez les matrices d'adjacences des graphes de ce chapitre.
\end{Exo}

\begin{Exo}
Réfléchir à la possibilité d'extension des matrices d'adjacences aux graphes :
\begin{itemize}
\item orientés,
\item pondérés.
\end{itemize}
\end{Exo}

\subsubsection{Propriétés de la matrice d'adjacence}
Cette matrice a plusieurs caractéristiques :

\begin{Th}
\begin{enumerate}
\item Elle est carrée : il y a autant de lignes que de colonnes.
\item Un 1 sur la diagonale indique une boucle. Si le graphe n'a pas de boucle, alors la diagonale de sa matrice d'adjacence est nulle.
\item La matrice d'adjacence d'un graphe non orienté est symétrique : $m_{ij} = m_{ji}$.
\end{enumerate}
\end{Th}




\begin{Exo}
Calculez $M^2$ et $M^3$ pour la matrice d'adjacence $M$ ci-dessus. Comparer ces matrices aux chaînes de longueur 2 et 3 reliant deux sommets quelconques.
\end{Exo}


\begin{Th}
Soit $A$ la matrice d'adjacence d'un graphe $G$. Le coefficient $(s,t)$ de $A^k$ est le nombre de chaînes de longueur $k$ qui mènent du sommet $s$ au sommet $t$.
\end{Th}

\begin{Exo}
Démontrez ce résultat, par récurrence.
\end{Exo}


\begin{Exo}
On pose :
$$J=\left( \begin{array}{cccc} 2 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 \\ \end{array}\right)$$
\begin{enumerate}
\item Dessinez le graphe non orienté ayant $J$ pour matrice d'incidence.
\item Déterminez sa matrice d'adjacence B.
\item Vérifiez les formules précédentes :
\begin{itemize}
\item le lien entre matrice d'incidence et degré des sommets,
\item le lien entre $B^k$ et les chaînes de longueur $k$.
\end{itemize}
\end{enumerate}
\end{Exo}

\begin{Exo}
Quels sont les avantages et les inconvénients de cette méthode de représentation des graphes ? Comparez-la aux matrices d'incidences.

En particulier, pour un graphe à $m$ sommets et $n$ arêtes, quelle représentation est la plus gourmande en espace mémoire ? Cela dépend du nombres d'arêtes ?
\end{Exo}


\subsection{Listes d'adjacence}


\subsubsection{Présentation}


\begin{Def}[Liste d'adjacence]
On peut encore représenter un graphe en donnant pour chacun de ses sommets la liste des sommets auxquels il est adjacent. On parle alors de \emph{liste d'adjacence}\index{liste!d'adjacence}.
\end{Def}

\begin{Ex}
On considère le graphe $G$ suivant :
\begin{center}
\includegraphics[scale=0.7]{graphes/graphe1b.eps}
\end{center}

\noindent Voici les listes d'adjacences de $G$ :

1 : 3, 4, 5

2 : 3

3 : 1, 2, 4, 5

4 : 1, 3, 5

5 : 1, 3, 4

\end{Ex}

\begin{Exo}
 Représentez les listes d'adjacences des graphes de ce chapitre.
\end{Exo}

\begin{Exo}
Discuter des avantages et des inconvénients de cette méthode de représentation. On la comparera aux matrices d'adjacence et d'incidence.
\end{Exo}





\gsaut
\centerline{\x{Fin du Chapitre}}