<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">
Dans ce chapitre, diffÃ©rents problÃ¨mes classiques autour des graphes seront prÃ©sentÃ©s. On verra successivement les problÃ¨mes suivants, et on en proposera des solutions :
\begin{itemize}
\item Existence d'un circuit eulÃ©rien.
\item CaractÃ©risation des graphes extraits d'un graphe donnÃ©.
\item CaractÃ©risation des graphes planaires.
\item DÃ©nombrement des rÃ©gions induites par un graphe planaire.
\item Existence d'un circuit hamiltonien.
\end{itemize}

\section{Circuits eulÃ©riens}


\subsection{Introduction : les ponts de K\"onigsberg}

 La question Ã&nbsp; l'origine de la thÃ©orie des graphes est due Ã&nbsp; Euler\footnote{Leonhard Euler, mathÃ©maticien suisse (1707{}-1783). A consacrÃ© prÃ¨s de 900 mÃ©moires aux mathÃ©matiques, Ã&nbsp; l'optique, Ã&nbsp; la science navale, Ã&nbsp; la musique, l'atronomie, la thÃ©orie des assurance... Un monstre, appelÃ© l'aigle des mathÃ©matiques. Le plus grand mathÃ©maticien du dix-huitiÃ¨me siÃ¨cle, l'un des plus grands de tous les temps.}, en 1736 : dans cette partie de la ville de K\"onigsberg :



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

\noindent peut{}-on, lors d'une promenade, revenir Ã&nbsp; notre point de dÃ©part en empruntant une, et une seule fois, chaque pont ?

 Pour y rÃ©pondre, Euler a introduit le graphe suivant (les arcs symbolisent les ponts ; les sommets, les quatre zones terrestres) :


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


Le problÃ¨me de dÃ©part se ramÃ¨ne alors Ã&nbsp; la question suivante : peut{}-on trouver un circuit permettant d'emprunter une, et une seule fois chaque arÃªte, en retournant Ã&nbsp; son point de dÃ©part ?

\medskip

La rÃ©ponse, dans ce cas particulier, est non : comme
\begin{itemize}
\item le point de dÃ©part $s$ est aussi le point d'arrivÃ©e,
\item on ne peut pas emprunter deux fois une mÃªme arÃªte,
\end{itemize}
on en conclut forcÃ©ment que le degrÃ© de $s$ est pair. Or, dans le graphe ci-dessus, tous les sommets ont un degrÃ© impair.

\subsection{DÃ©finitions}

Ce problÃ¨me, introduit par Euler, conduit aux dÃ©finitions suivantes...

\begin{Def}[ChaÃ®ne eulÃ©rien]
On appelle \emph{chaÃ®ne eulÃ©rienne}\index{chaÃ®ne!eulÃ©rienne} une chaÃ®ne contenant une et une seule fois toutes les arÃªtes du graphe.
\end{Def}


\begin{Def}[Circuit eulÃ©rien]
On appelle \emph{circuit eulÃ©rien}\index{circuit!eulÃ©rien} un circuit contenant une et une seule fois toutes les arÃªtes du graphe.
\end{Def}

\begin{Rem}
On n'a plus affaire Ã&nbsp; une chaÃ®ne, mais Ã&nbsp; un circuit : le point de dÃ©part et celui d'arrivÃ©e coÃ¯ncident.
\end{Rem}

\begin{Def}[Graphe eulÃ©rien]
Un \emph{graphe eulÃ©rien}\index{graphe!eulÃ©rien} est un graphe possÃ©dant un circuit eulÃ©rien.
\end{Def}


\begin{Rem}
On peut passer plusieurs fois par un sommet donnÃ©, pourvu que les arÃªtes empruntÃ©es soient toutes diffÃ©rentes.
\end{Rem}


\begin{Exo}
Donnez des exemples de graphes possÃ¨dant des circuits eulÃ©riens, et d'autres exemples de graphes n'en possÃ©dant pas.
\end{Exo}



\subsection{RÃ©sultat d'Euler}

Du problÃ¨me initial d'Euler, on peut en dÃ©duire le rÃ©sultat suivant (rappelons qu'il s'agit ici de graphes non orientÃ©s)...


\begin{Th}
Il y a Ã©quivalence entre :
\begin{itemize}
\item possÃ©der une chaÃ®ne eulÃ©rienne,
\item Ãªtre connexe, avec O ou 2 sommets de degrÃ© impair.
\end{itemize}
De plus, s'il n'y a pas de sommet de degrÃ© impair,  alors le graphe est EulÃ©rien.
\end{Th}



\begin{Pre}
En parcourant un chemin ou un circuit, pour chaque sommet visitÃ©, on utilise une arÃªte pour arriver Ã&nbsp; ce sommet et une arÃªte pour en repartir, ces deux arÃªtes ne devant plus Ãªtre utilisÃ©es par la suite.

Le nombre d'arÃªtes utilisables en ce sommet diminue donc de deux. Si un sommet est d'ordre impair, une de ses arÃªtes aboutissant Ã&nbsp; ce sommet doit donc Ãªtre soit sur la premiÃ¨re arÃªte d'un chemin, soit sur la derniÃ¨re.

Un chemin n'ayant que deux extrÃ©mitÃ©s, le nombre de sommets d'ordre impair ne peut excÃ©der deux.
\end{Pre}


\begin{Exo}
Soit G un graphe connexe non eulÃ©rien. Est-il toujours possible de rendre G eulÃ©rien en lui rajoutant un sommet et quelques arÃªtes?
\end{Exo}

\textit{\underline{RÃ©ponse :}} Oui. Quand on ajoute un nouveau sommet, son nombre d'arÃªtes doit Ãªtre pair, pour ne pas poser de nouveaux problÃ¨mes. On peut donc ainsi corriger le problÃ¨me d'imparitÃ© pour un nombre pair de sommets : en reliant chaque couple de deux sommets de degrÃ© impairs, Ã&nbsp; un sommet que l'on crÃ©e uniquement pour ce couple. Or, tout graphe simple possÃ¨de un nombre pair de sommets de degrÃ© impair...


\subsection{Exercice : les dominos}


\begin{Exo}
On considÃ¨re des dominos dont les faces sont numÃ©rotÃ©es 1, 2, 3, 4 ou 5.

\begin{enumerate}
\item En excluant les dominos doubles, de combien de dominos dispose-t-on ?
\item Montrez que l'on peut arranger ces dominos de faÃ§on Ã&nbsp; former une boucle fermÃ©e (en utilisant la rÃ¨gle habituelle de contact entre les dominos).
\item Pourquoi n'est-il pas nÃ©cessaire de considÃ©rer les dominos doubles ?
\item Si l'on prend maintenant des dominos dont les faces sont numÃ©rotÃ©es de 1 Ã&nbsp; n, est-il possible de les arranger de faÃ§on Ã&nbsp; former une boucle fermÃ©e ?
\end{enumerate}
\end{Exo}

\noindent\textit{\underline{RÃ©ponses :}}
\begin{enumerate}
\item On dispose de 4+3+2+1 = 10 dominos.
\item ConsidÃ©rons $K_5$, le pentagramme complet. A l'arÃªte $(1,2)$, par exemple, est associÃ©e le domino $(1,2)$. Arriver Ã&nbsp; constituer une boucle fermÃ©e de dominos revient donc Ã&nbsp; trouver un circuit eulÃ©rien dans $K_5$. C'est possible : $K_5$ est connexe, avec tous ses sommets de degrÃ© pairs.
\item ConsidÃ©rer les dominos doubles revient Ã&nbsp; placer une boucle Ã&nbsp; chaque sommet de $K_5$. On ne change pas sa connexitÃ©, ni la paritÃ© de ses sommets.
\item On obtient, dans ce cas, $K_n$, dont chaque sommet a pour degrÃ© $n-1$. Pour arriver Ã&nbsp; consitituer une boucle fermÃ©e, il faut donc (et il suffit) que $n$ soit impair.
\end{enumerate}



\section{Graphes partiels et sous-graphes}

\subsection{Introduction}

Dans cette section, on va chercher Ã&nbsp; Ã©tudier quels sont les diffÃ©rents types de graphes que l'on peut obtenir Ã&nbsp; partir d'un graphe $G$, en lui enlevant soit des arÃªtes, soit des sommets.

Prenons l'exemple d'un ordinateur, avec imprimante, souris, etc. Chaque appareil est un sommet du graphe de l'installation informatique, et chaque cÃ¢ble est une arÃªte. On peut alors, au choix, enlever des cÃ¢bles Ã©lectriques, ou des appareils (avec leurs cÃ¢bles), pour obtenir ainsi une nouvelle installation informatique, c'est-Ã&nbsp;-dire construire un nouveau graphe Ã&nbsp; partir d'un graphe donnÃ©.

\medskip

On considÃ¨re, dans tout ce paragraphe, les graphes $G_1$ et $G_2$ suivants
\begin{center}
\includegraphics[scale=0.7]{graphes/graphe7.eps}
\includegraphics[scale=0.7]{graphes/graphe2.eps}
\end{center}
Ils nous serviront Ã&nbsp; illustrer les dÃ©finitions Ã&nbsp; venir.

\subsection{Graphe partiel et sous-graphe}

\subsubsection{Graphe partiel}

\begin{Def}[Graphe partiel]
Soit G = (S, A) un graphe. Le graphe G' = (S, A') est un \emph{graphe partiel}\index{graphe!partiel} de G, si A' est inclus dans A.
\end{Def}

\begin{Rem}
Autrement dit, on obtient G' en enlevant une ou plusieurs arÃªtes au graphe G (sans toucher Ã&nbsp; ses sommets).
\end{Rem}


\begin{Ex}[Graphe partiel de $G_1$]
Voici un exemple de graphe partiel de $G_1$
\begin{center}
\includegraphics[scale=0.7]{graphes/graphe8.eps}
\end{center}
Ici,
\begin{itemize}
\item S'=S,
\item A'=\{$e_3, e_4, e_5$\}.
\end{itemize}
\end{Ex}

\begin{Exo}
Trouver un graphe partiel de $G_2$.
\end{Exo}

\subsubsection{Sous-graphe}

\begin{Def}[Sous-graphe]
On dit que le graphe $(S',A')$ est un \emph{sous{}-graphe}\index{graphe!sous-} du graphe $(S,A)$ si
\begin{enumerate}
\item $S' \subset S$,
\item $A' \subset A$,
\item $A'=\{(x,y)\mid (x,y) \in A \land x \in S' \land y \in S'\}$
\end{enumerate}
\end{Def}

\begin{Rem}
Un sous{}-graphe d'un graphe donnÃ© est donc obtenu en enlevant certains sommets, et toutes les arÃªtes incidentes Ã&nbsp; ces sommets.
\end{Rem}

\begin{Ex}[Sous-graphe de $G_1$]
Voici un exemple de sous-graphe de $G_1$ :
\begin{center}
\includegraphics[scale=0.7]{graphes/graphe9.eps}
\end{center}
Ici,
\begin{itemize}
\item V'=\{$v_1, v_3, v_4, v_5$\},
\item E'=\{$e_3, e_4, e_5$\}.
\end{itemize}
\end{Ex}

\begin{Exo}
Trouver un sous-graphe de $G_2$.
\end{Exo}

\begin{Exo}
Combien un graphe $G$ d'ordre $n$ possÃ¨de-t-il de sous-graphes ?
\end{Exo}

\noindent\textit{\underline{RÃ©ponse :}} $2^n-1$, si l'on ne compte pas $G$.


\subsection{Sous-graphes particuliers}

\subsubsection{Sous-graphe partiel}

\begin{Def}[Sous-graphe partiel]
Un graphe partiel d'un sous-graphe est un \emph{sous-graphe partiel}\index{sous-graphe!partiel} de G.
\end{Def}

\begin{Rem}
Cette fois-ci, on enlÃ¨ve des sommets (et leurs arÃªtes incidentes), puis des arÃªtes.
\end{Rem}


\begin{Ex}[Sous-graphe partiel de $G_1$]
Voici un sous-graphe partiel de $G_1$ :
\begin{center}
\includegraphics[scale=0.7]{graphes/graphe10.eps}
\end{center}
Ici,
\begin{itemize}
\item V'=\{$v_1, v_2, v_3, v_4$\},
\item E'=\{$e_1, e_4$\}.
\end{itemize}
\end{Ex}


\begin{Exo}
Trouver un sous-graphe partiel de $G_2$.
\end{Exo}

\subsubsection{Clique}

\begin{Def}[Clique]
On appelle \emph{clique}\index{clique} un sous-graphe complet de G.
\end{Def}

\begin{Rem}
On a donc rÃ©ussi, en enlevant des sommets, Ã&nbsp; faire en sorte que chaque sommet est adjacent Ã&nbsp; tous les autres sommets.
\end{Rem}


\begin{Ex}[Une clique de $G_1$]
Exemple de clique de $G_1$ :
\begin{center}
\includegraphics[scale=0.7]{graphes/clique.eps}
\end{center}
Ici,
\begin{itemize}
\item V'=\{$v_1,v_2,v_3$\},
\item E'=\{$e_1, e_2, e_3$\}.
\end{itemize}
\end{Ex}

\begin{Exo}
Trouver une clique de $G_2$.
\end{Exo}

\subsubsection{Stable}

\begin{Def}[Stable]
On appelle \emph{stable}\index{stable} un sous-graphe de $G$ sans arÃªtes.
\end{Def}

\begin{Rem}
On enlÃ¨ve donc des sommets, et leurs arÃªtes adjacentes. On obtient un stable que si, en ayant enlevÃ© un certain nombre de sommets Ã&nbsp; $G$, le sous-graphe rÃ©sultant ne possÃ¨de plus d'arÃªte.
\end{Rem}


\begin{Ex}[Un stable de $G_1$]
Voici un stable de $G_1$ :
\begin{center}
\includegraphics[scale=0.7]{graphes/stable.eps}
\end{center}
Ici,
\begin{itemize}
\item V'=\{$v_1, v_4, v_5$\},
\item E'=\{\}.
\end{itemize}
\end{Ex}


\begin{Exo}
Trouver un stable de $G_2$.
\end{Exo}

\subsection{Exercices}

\begin{Exo}
On considÃ¨re le graphe $G$ suivant :
\begin{center}
\includegraphics[scale=0.7]{graphes/graphe1b.eps}
\end{center}
En extraire : un graphe partiel, un sous-graphe, un sous-graphe partiel, une clique et un stable.
\end{Exo}




\begin{Exo}
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).


Montrez que cela n'est plus nÃ©cessairement vrai dans un groupe de cinq personnes.
\end{Exo}

\noindent\textit{\underline{RÃ©ponse :}} Cela revient Ã&nbsp; dire que, dans un graphe $G$ Ã&nbsp; six sommets, il est toujours possible d'obtenir un sous-graphe (\emph{i.e.}, en enlevant trois sommets), qui est :
\begin{itemize}
\item soit une clique (les trois sommets sont adjacents deux Ã&nbsp; deux),
\item soit un stable (aucun arc).
\end{itemize}

Cela n'est plus valable pour les graphes Ã&nbsp; cinq sommets.




\section{Graphe planaire}



\subsection{DÃ©finition}
On rappelle la dÃ©finition suivante...

\begin{Def}[Graphe planaire]
Un graphe est dit \emph{planaire}\index{graphe!planaire} s'il admet une re\-prÃ©\-sen\-ta\-ti\-on graphique dans le plan telle que deux arÃªtes quelconques ne se coupent pas.
\end{Def}


\begin{Rem}
Rappelons que les arÃªtes ne sont pas forcÃ©ment rectilignes.
\end{Rem}

Outre l'intÃ©rÃªt thÃ©orique (thÃ©orÃ¨me des quatre couleurs, etc.), ou une reprÃ©sentation plus sympathique, chercher si un graphe possÃ¨de une reprÃ©sentation planaire peut s'avÃ©rer pratiquement important. Par exemple, il Ã©tait plus facile de concevoir les tout premiers circuits imprimÃ©s Ã&nbsp; transistors quand le graphe du circuit Ã©tait planaire : on Ã©vitait alors de devoir recourir au procÃ©dÃ© bicouche ou Ã&nbsp; des "straps" fragiles pour s'Ã©chapper du plan du circuit imprimÃ©.

\begin{Exo}
Un graphe peut-il Ãªtre planaire s'il possÃ¨de un sous-graphe qui ne l'est pas ?
\end{Exo}

\noindent\textit{\underline{RÃ©ponse :}} Non : une fois dessinÃ© dans un plan, un graphe planaire a forcÃ©ment tous ses sous-graphes qui le sont aussi.



\subsection{Exemples}

\begin{Ex}[$K_{3,3}$]
Il est non planaire
 \begin{center}
\includegraphics[scale=0.7]{graphes/k33}
\end{center}
\end{Ex}


\begin{Ex}[$K_n$]
On rappelle que l'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. Alors $K_5$ n'est pas planaire :
\begin{center}
\includegraphics[scale=0.7]{graphes/k5}
\end{center}
\end{Ex}



\begin{Exo}
Dessiner $K_1$, $K_2$, $K_3$ et $K_4$. Sont-ils planaires ? Et qu'en est-il de $K_n, n \geqslant 5$ ?
\end{Exo}

\noindent\textit{\underline{RÃ©ponse :}} $K_1$, $K_2$, $K_3$ et $K_4$ sont planaires. $K_5$, on l'a vu, ne l'est pas. Comme $K_5$ est un sous-graphe de $K_n, n \geqslant 5$, on en dÃ©duit qu'Ã&nbsp; partir de $n=5$, tous les $K_n$ ne sont plus planaires.





\subsection{CaractÃ©risation des graphes planaires}

Pendant de nombreuses annÃ©es, les mathÃ©maticiens ont tentÃ© de caractÃ©riser les graphes planaires. Ce problÃ¨me a Ã©tÃ© rÃ©solu en 1930 par le mathÃ©maticien polonais K. Kuratowski.

\subsubsection{Expansion d'un graphe}

\begin{Def}[Expansion d'un graphe]
L'expansion d'un graphe est le rÃ©sultat de l'ajout d'un ou plusieurs sommets sur une ou plusieurs arÃªtes (par exemple, transformation de l'arÃªte $\bullet - \bullet$ en $\bullet - \bullet - \bullet$).
\end{Def}

\begin{Exo}
ReprÃ©sentez deux graphes, le second Ã©tant une expansion du premier.
\end{Exo}


\subsubsection{ThÃ©orÃ¨me de Kuratowski}

La rÃ©ponse au problÃ¨me de caractÃ©risation des graphes planaires est...

\begin{Th}[Kuratowski]
\index{thÃ©orÃ¨me!Kuratowski}
Un graphe fini est planaire si et seulement s'il ne contient pas de sous-graphe qui est une expansion de $K_5$ ou $K_{3,3}$.
\end{Th}



%\begin{Exo}
%En admettant, comme nous y invite le rÃ©sultat prÃ©cÃ©dent, que $K_5$ n'est pas planaire, dÃ©terminer les valeurs de $n$ pour lesquelles $K_n$ est planaire.
%\end{Exo}

%\noindent\textit{\underline{RÃ©ponse :}} On a vu (exercice prÃ©cÃ©dent) que $K_n$ est planaire pour $n \leqslant 4$. $K_5$ n'est pas planaire. Enfin, pour $n \geqslant 5$, $K_n$ contient des sous-graphes $K_5$...




\section{DÃ©nombrement des rÃ©gions d'un graphe planaire}


Le prochain problÃ¨me classique que l'on prÃ©sentera s'intÃ©resse au nombre de rÃ©gions qu'un graphe planaire dÃ©coupe. La cÃ©lÃ¨bre formule d'Euler permettra de relier ce nombre aux nombres d'arÃªtes et de sommets du graphe considÃ©rÃ©.

\subsection{Cartes, rÃ©gions}

\begin{Def}[Carte, rÃ©gions]
Une \emph{carte}\index{carte} est une reprÃ©sentation particuliÃ¨re d'un graphe planaire. On dit qu'une carte est \emph{connexe}\index{carte!connexe} si son graphe l'est. Une carte divise le plan en plusieurs \emph{rÃ©gions}\index{rÃ©gions}.
\end{Def}

\begin{Ex}
Par exemple, la carte ci-dessous, avec six sommets et neuf arÃªtes, divise le plan en cinq rÃ©gions (A, B, C, D, E).
\begin{center}
\includegraphics[scale=0.7]{graphes/carte.eps}
\end{center}

On remarque que quatre rÃ©gions sont limitÃ©es alors que la cinquiÃ¨me (E), extÃ©rieure au diagramme, ne l'est pas.
\end{Ex}



\subsection{DegrÃ© d'une rÃ©gion}

\begin{Def}[DegrÃ© d'une rÃ©gion]
Le \emph{degrÃ©}\index{degrÃ©!d'une rÃ©gion} d'une rÃ©gion r, notÃ© d(r), est la longueur du cycle ou de la chaÃ®ne fermÃ©e qui limite r.
\end{Def}

\begin{Ex}
Dans le graphe ci-dessus, d(A)=4, d(B)=3, d(C)=3, d(D)=5, d(E)=3.
\end{Ex}

\begin{Rem}
On remarque que toute arÃªte limite deux rÃ©gions, ou est contenue dans une rÃ©gion et est alors comptÃ©e deux fois dans la chaÃ®ne fermÃ©e. Nous avons donc...
\end{Rem}


\subsection{Lemme des rÃ©gions}

\begin{Th}[Lemme des rÃ©gions]
La somme des degrÃ©s des rÃ©gions d'une carte connexe est Ã©gale Ã&nbsp; deux fois le nombre d'arÃªtes.
\end{Th}


\begin{Exo}
DÃ©montrez ce rÃ©sulat.
\end{Exo}

\noindent\textit{\underline{RÃ©ponse :}} Il y a deux types d'arÃªtes, celles sÃ©parant deux rÃ©gions donnÃ©es, et celles incluses Ã&nbsp; l'intÃ©rieur d'une rÃ©gion...

\subsection{Formule d'Euler}

Euler a Ã©tabli une formule qui relie le nombre de sommets S, le nombre d'arÃªtes A et le nombre de rÃ©gions R d'une carte connexe :

\begin{Th}[Euler]
$$S - A + R = 2$$
\end{Th}

\subsection{Exercices}

\begin{Exo}
Utilisez le rÃ©sultat d'Euler pour retrouver le fait que $K_{3,3}$ n'est pas planaire.
\end{Exo}


\begin{Def}[PolyÃ¨dres rÃ©guliers, Solides de Platon]
Un polyÃ¨dre est dit rÃ©gulier\index{polyÃ¨dres rÃ©guliers} s'il est constituÃ© de faces toutes identiques et rÃ©guliÃ¨res, et que tous ses sommets sont identiques. Ils sont au nombre de neuf, dont cinq seulement sont convexes. Ces derniers Ã©taient connus de Platon :
\begin{itemize}
\item le tÃ©traÃ¨dre rÃ©gulier (4 faces en triangle Ã©quilatÃ©ral),
\item le cube,
\item l'octaÃ¨dre rÃ©gulier (8 faces en triangle Ã©quilatÃ©ral),
\item le dodÃ©caÃ¨dre rÃ©gulier (12 faces en pentagone),
\item l'icosaÃ¨dre rÃ©gulier (20 faces en triangle Ã©quilatÃ©ral).
\end{itemize}  

Pour cette raison, ces cinq polyÃ¨dres rÃ©guliers convexes sont appelÃ©s \emph{Solides de Platon}\index{solides de Platon}.
\end{Def}


\begin{Rem}
On appelle parfois polyÃ¨dres rÃ©guliers uniquement les 5 solides de Platon.
\end{Rem}


\begin{Exo}
Les solides platoniciens peuvent Ãªtre considÃ©rÃ©s comme des graphes, qui de plus sont planaires. VÃ©rifier la formule d'Euler sur ces solides Platoniciens :
\begin{itemize}
\item le nombre de sommets,
\item moins le nombre d'arÃªtes,
\item plus le nombre de faces
\end{itemize}
\noindent ...est toujours Ã©gal Ã&nbsp; 2.
\end{Exo}





\section{Circuit hamiltonien}

\subsection{Les dodÃ©caÃ¨dres de Hamilton}

Le dodÃ©caÃ¨dre est Ã&nbsp; l'origine d'un autre problÃ¨me cÃ©lÃ¨bre, dÃ» Ã&nbsp; Hamilton\footnote{William Rowan Hamilton, mathÃ©maticien et physicien irlandais (1805{}-1865). Inventeur des quaternions.} : comment passer une, et une seule fois, par chacun des sommets du dodÃ©caÃ¨dre, de telle maniÃ¨re que le dernier sommet visitÃ© est aussi le premier.


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



\subsection{DÃ©finition}

\begin{Def}[Circuit et graphes hamiltoniens]
\index{circuit!hamiltonien}\index{graphes!hamiltonien}
Un circuit hamiltonien est un circuit qui passe par tous les sommets du graphe, une et une seule fois. Un graphe possÃ©dant un tel circuit est qualifiÃ© d'hamiltonien.
\end{Def}

\begin{Rem}
C'est un circuit : le sommet de dÃ©part doit aussi Ãªtre le sommet d'arrivÃ©e.
\end{Rem}

\begin{Ex}
Les graphes complets $K_n$ sont hamiltoniens, pour tout $n$.
\end{Ex}

\begin{Pre}
On peut inscrire $K_n$ dans un polygone rÃ©gulier Ã&nbsp; $n$ sommets : il suffit alors de parcourir ce polygone, sommet par sommet, dans le sens trigonomÃ©trique par exemple, jusqu'Ã&nbsp; retrouver son point de dÃ©part.
\end{Pre}


\begin{Rem}
Il peut y avoir plusieurs circuits hamiltoniens dans un graphe hamiltonien.
\end{Rem}


Le problÃ¨me de la caractÃ©risation des graphes Hamiltoniens n'est pas aussi simple que celui des graphes EulÃ©riens. On peut cependant Ã©noncer quelques conditions, respectivement nÃ©cessaires, puis suffisantes, pour qu'un graphe le soit...

\subsection{Conditions nÃ©cessaires}

\begin{Th}
Un graphe hamiltonien d'ordre $n \geqslant 3$ ne possÃ¨de pas de sommet de degrÃ© 1.
\end{Th}

\begin{Pre}
Si un sommet $s$ est de degrÃ© 1, il est connectÃ© Ã&nbsp; un (unique) autre sommet $s'$, qui sera forcÃ©ment parcouru deux fois (pour aller en $s$, et pour en sortir).
\end{Pre}

\begin{Rem}
$K_2$ est hamiltonien, et a tous ses sommets d'ordre 1...
\end{Rem}

\begin{Th}
Si un graphe hamiltonien possÃ¨de un sommet de degrÃ© 2, alors les deux arÃªtes incidentes Ã&nbsp; ce sommet doivent faire partie du cycle hamiltonien.
\end{Th}

\begin{Pre}
Supposons que $s$ est de degrÃ© 2, connectÃ© Ã&nbsp; $s_1$ par l'arÃªte $a_1$, et Ã&nbsp; $s_2$ par $a_2$. On est arrivÃ© Ã&nbsp; $s$ Ã&nbsp; partir d'une arÃªte, mettons $a_1$ ; si on rÃ©empruntait $a_1$ pour sortir de $s$, alors on repasserait par $a_1$, ce qui est impossible.
\end{Pre}


\subsection{Conditions suffisantes}

\begin{Th}[ThÃ©orÃ¨me de Ore]\index{thÃ©orÃ¨me!de Ore}
Soit G = (V, E) un graphe simple d'ordre $n\geqslant 3$. Si pour toute paire \{x,y\} de sommets non adjacents, on a $d(x) + d(y) \geqslant n$, alors G est hamiltonien.
\end{Th}

\begin{Th}[Corollaire de Dirac]\index{Corollaire de Dirac}
Soit G = (V, E) un graphe simple d'ordre $n\geqslant 3$. Si pour tout sommet x de G, on a $d(x) \geqslant n/2$, alors G est hamiltonien.
\end{Th}

\begin{Pre}
En effet, un tel graphe vÃ©rifie les conditions du thÃ©orÃ¨me prÃ©cÃ©dent. Si x et y ne sont pas adjacents, on a bien :
$$d(x) + d(y) \geqslant n/2 + n/2 = n$$
\end{Pre}


\begin{Exo}
Dessinez un graphe d'ordre au moins 5 qui est...
\begin{enumerate}
\item hamiltonien et eulÃ©rien,
\item hamiltonien et non eulÃ©rien,
\item non hamiltonien et eulÃ©rien,
\item non hamiltonien et non eulÃ©rien.
\end{enumerate}
\end{Exo}


\subsection{Le problÃ¨me du voyageur de commerce}

Trouver un cycle hamiltonien pour un graphe donnÃ© est un problÃ¨me difficile sur le plan algorithmique -- de type NP-complet --, reliÃ© au problÃ¨me dit \emph{du voyageur de commerce}\index{problÃ¨me!du voyageur de commerce} : un voyageur de commerce  doit visiter un ensemble de villes, en minimisant son temps de parcours.

\medskip

Ce problÃ¨me se formalise aisÃ©ment en thÃ©orie des graphes :
\begin{itemize}
\item Les villes sont les sommets d'un graphe pondÃ©rÃ©.
\item Les arÃªtes correspondent aux routes reliant ces villes.
\item La pondÃ©ration correspond soit Ã&nbsp; la distance entre deux ville (en kilomÃ¨tres), soit Ã&nbsp; la durÃ©e nÃ©cessaire pour passer d'une ville Ã&nbsp; l'autre.
\item Ce graphe peut Ãªtre orientÃ©, si l'on souhaite intÃ©grer des routes Ã&nbsp; sens unique.
\end{itemize}

On cherche alors Ã&nbsp; visiter tous les sommets du graphe (\emph{i.e.} toutes les villes) en minimisant le \og poids \fg{} du parcours (la distance parcourue, ou le temps total).

\medskip

Le problÃ¨me du voyageur de commerce correspond donc Ã&nbsp; la recherche d'un cycle hamiltonien de poids minimal, dans un graphe pondÃ©rÃ© complet. Ce problÃ¨me est NP-complet, donc impossible Ã&nbsp; rÃ©soudre exactement quand le nombre de villes est grand.



\gsaut
\centerline{\x{Fin du Chapitre}}
</pre></body></html>