modif algo euclide

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

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 à l'origine de la théorie des graphes est due à Euler\footnote{Leonhard Euler, mathématicien suisse (1707{}-1783). A consacré près de 900 mémoires aux mathématiques, à l'optique, à la science navale, à 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 à 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 à la question suivante : peut{}-on trouver un circuit permettant d'emprunter une, et une seule fois chaque arête, en retournant à 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 à une chaîne, mais à 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 à 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 à 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, à 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 à 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 à n, est-il possible de les arranger de façon à 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 à constituer une boucle fermée de dominos revient donc à 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 à placer une boucle à 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 à 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 à étudier quels sont les différents types de graphes que l'on peut obtenir à 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-à-dire construire un nouveau graphe à 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 à illustrer les définitions à 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 à 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 à 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, à faire en sorte que chaque sommet est adjacent à 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 à $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 à dire que, dans un graphe $G$ à 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 à deux),
\item soit un stable (aucun arc).
\end{itemize}

Cela n'est plus valable pour les graphes à 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 à transistors quand le graphe du circuit était planaire : on évitait alors de devoir recourir au procédé bicouche ou à 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'à 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 à 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 à 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 à 2.
\end{Exo}





\section{Circuit hamiltonien}

\subsection{Les dodécaèdres de Hamilton}

Le dodécaèdre est à l'origine d'un autre problème célèbre, dû à 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 à $n$ sommets : il suffit alors de parcourir ce polygone, sommet par sommet, dans le sens trigonométrique par exemple, jusqu'à 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é à 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 à ce sommet doivent faire partie du cycle hamiltonien.
\end{Th}

\begin{Pre}
Supposons que $s$ est de degré 2, connecté à $s_1$ par l'arête $a_1$, et à $s_2$ par $a_2$. On est arrivé à $s$ à 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 à la distance entre deux ville (en kilomètres), soit à la durée nécessaire pour passer d'une ville à l'autre.
\item Ce graphe peut être orienté, si l'on souhaite intégrer des routes à sens unique.
\end{itemize}

On cherche alors à 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 à la recherche d'un cycle hamiltonien de poids minimal, dans un graphe pondéré complet. Ce problème est NP-complet, donc impossible à résoudre exactement quand le nombre de villes est grand.



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