\documentclass{tpcaml}

\tp{9}{Algorithme de Prim}

\usepackage{graphicx}

\begin{document}

  \maketitle

\section{Définitions}

\sideimage{graphe.png}
  Un \em graphe \em est un ensemble de \em n\oe uds \em pouvant être 
  reliés deux à deux par des \em arêtes\em. Un \em graphe pondéré \em 
  est un graphe où une valeur numérique appellée \em poids \em est associée
  à chaque arête.

  Un \em arbre couvrant \em d'un graphe est un ensemble d'arêtes 
  de ce graphe tel que, si $M$ et $N$ sont deux n\oe uds du graphe,
  alors il existe exactement un chemin constitué d'arêtes de l'arbre
  joignant $M$ à $N$.

  On appelle \em poids \em de l'arbre la somme des poids des arêtes qu'il
  contient. Un \em arbre couvrant minimal \em est un arbre couvrant dont le
  poids est minimal parmi tous les arbres couvrants d'un graphe
  donné. 

  \vspace{12pt}
\begin{question}
  À titre d'échauffement, donner un arbre couvrant minimal du graphe
  ci-contre. Quel est son poids?
\end{question}

\section{Algorithme de Prim}

  L'algorithme de Prim est un algorithme permettant de construire un arbre
  couvrant minimal d'un graphe. Pour les besoins de l'exercice, on
  représentera les n\oe uds du graphe comme des entiers de $\{0\ldots
  n-1\}$ et les arêtes comme des paires d'entiers associées à un poids
  entier.

  \vspace{12pt}

  Le principe de l'algorithme de Prim est de construire l'arbre couvrant
  minimal arête par arête: pour ajouter une arête à un arbre partiellement
  construit, il considère l'ensemble des arêtes dont une extrémité est
  connectée à l'arbre déjà construit, et l'autre extrémité ne l'est pas, et
  il choisit dans cet ensemble une arête de poids minimal qu'il ajoute à
  l'arbre. L'algorithme commence avec un arbre couvrant contenant un n\oe
  ud et zéro arêtes, et ajoute successivement $n-1$ arêtes.

  \vspace{12pt}

\begin{question}
  Construire une structure de données permettant de représenter l'ensemble
  des n\oe uds qui n'ont pas encore été reliés à l'arbre. On pourra
  stocker, pour chaque n\oe ud de l'ensemble, le n\oe ud de l'arbre qui en
  est le plus proche, et la distance correspondante.

  \'Ecrire une
  fonction \code{trouver\_proche ()} qui renvoie l'arête la plus courte
  reliant un n\oe ud de l'arbre à un n\oe ud de cet ensemble, en temps
  $O(n)$. 

  \'Ecrire une fonction \code{retirer\_noeud r a} qui retire le
  n\oe ud \code{r} de cet ensemble, et qui prend en argument la liste
  \code{a} des n\oe uds reliés à \code{r} et la distance qui les sépare,
  en temps $O(n)$.
\end{question}

  \vspace{12pt}

\begin{question}
  Utiliser cette structure de données pour écrire l'algorithme de Prim. On
  choisira avec soin le format des données fournies en entrée à
  l'algorithme. Tester cet algorithme sur le graphe ci-dessus.
\end{question}

  \vspace{12pt}

\begin{question}
  Prouver que l'algorithme de Prim construit bien un arbre couvrant. On
  pourra distinguer la \em connexité \em (il existe au moins un chemin) et
  l'\em acyclicité \em (il existe au plus un chemin).
\end{question}

  \vspace{12pt}

\begin{question}
  Prouver que l'algorithme de Prim construit bien un arbre couvrant \em
  minimal\em. On pourra pour cela considérer un arbre couvrant minimal $A$,
  et tout particulièrement la plus petite arête de l'arbre généré par
  l'algorithme de Prim qui ne se trouve pas dans $A$. 
\end{question}

  \vspace{12pt}

\begin{question}
  \textbf{(difficile)} La complexité de cet algorithme est $O(n^2)$. Proposer
  une méthode pour améliorer sa complexité, en fonction du nombre d'arêtes
  $a$ et du nombre de n\oe uds $n$.
\end{question}

 
\end{document}