<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">

La notion de graphe gÃ©nÃ©ralise amplement la notion de relation sur un ensemble ; elle s'intÃ©resse Ã&nbsp; 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 Ã&nbsp; 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 Ã&nbsp; prÃ©sent la possibilitÃ© de pondÃ©rer les arÃªtes d'un graphe non orientÃ© (la dÃ©finition de graphe est alors Ã&nbsp; adapter) :

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


% \begin{Exo}
% On a 6 wagons Ã&nbsp; 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 Ã&nbsp; 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} Ã&nbsp; partir du sommet $s$ s'il existe une chaÃ®ne menant de $s$ Ã&nbsp; $s'$.
\end{Def}

\begin{Rem}
On dit aussi qu'on peut \emph{atteindre} $s'$ Ã&nbsp; 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$ Ã&nbsp; $s'$.
\end{Th}


\begin{Exo}
RÃ©flÃ©chir Ã&nbsp; 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 Ã&nbsp; 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 Ã&nbsp; 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 Ã&nbsp; $\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 Ã&nbsp; un nombre pair plus $i_0$. Quand on met tout bout Ã&nbsp; 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 Ã&nbsp; ses connaissances (et uniquement Ã&nbsp; 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Ã© Ã&nbsp; 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Ã© Ã&nbsp; un des sommets  de $I$, sinon il ne serait reliÃ© qu'Ã&nbsp; 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 Ã&nbsp; 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, Ã&nbsp; 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$ Ã&nbsp; $s'$).
\end{Def}


\begin{Rem}
C'est en particulier le cas lorsqu'Ã&nbsp; 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 Ã&nbsp; 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 Ã&nbsp; 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 Ã&nbsp; 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 Ã&nbsp; 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 Ã&nbsp; 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Ã© Ã&nbsp; 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 Ã&nbsp; $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 Ã&nbsp; l'autre est possible pour un cavalier (par exemple, entre $a_1$ et $b_3$). On oriente alors les arÃªtes, suivant les parcours Ã&nbsp; 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Ã&nbsp; calculÃ© son nombre d'arÃªtes : $(n-1)+...+1 = \dfrac{n(n-1)}{2}$. Rajouter des boucles revient, dans le cas le pire, Ã&nbsp; rajouter une arÃªte sur chaqu'un des n sommets. On ajoute donc $n$ Ã&nbsp; 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Ã&nbsp; : il faut donc trouver d'autres faÃ§ons de reprÃ©senter les graphes.

La solution consiste Ã&nbsp; 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$ Ã&nbsp; 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Ã© Ã&nbsp; 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 Ã&nbsp; chaque sommet.




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

$$\left(
\begin{array}{ccccccccc}
 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
 0 &amp; 1 &amp; 1 &amp; 0 &amp; 1 &amp; 0 &amp; 0 &amp; 1 &amp; 0 \\
 0 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 0 &amp; 0 &amp; 1 &amp; 1 \\
 0 &amp; 0 &amp; 0 &amp; 1 &amp; 0 &amp; 0 &amp; 2 &amp; 0 &amp; 1 \\
 0 &amp; 0 &amp; 1 &amp; 1 &amp; 0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 \\
 0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 \\
 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 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 Ã&nbsp; 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 Ã&nbsp; 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 &amp; 0 &amp; 1 &amp; 1 &amp; 1\\
0 &amp; 0 &amp; 1 &amp; 0 &amp; 0\\
1 &amp; 1 &amp; 0 &amp; 1 &amp; 1\\
1 &amp; 0 &amp; 1 &amp; 0 &amp; 1\\
1 &amp; 0 &amp; 1 &amp; 1 &amp; 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 Ã&nbsp; 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 &amp; 1 &amp; 0 &amp; 1 \\ 0 &amp; 1 &amp; 1 &amp; 0 \\ 0 &amp; 0 &amp; 1 &amp; 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 Ã&nbsp; $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}}
</pre></body></html>