% Probl\`eme de l'arbre couvrant minimal
% Alain FRISCH Mars 1998

% d\'eclarations g\'en\'erales

\documentclass[a4paper]{article}

\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{amscd}

\usepackage[cp850]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[french]{babel}
\selectlanguage{french}

\newtheorem{algo}{Algorithme}
\newtheorem{lemme}{Lemme}
\newcommand{\eps}{\varepsilon}
\newcommand{\R}{{\mathbb R}}
\newcommand{\fl}{\rightarrow}

\textwidth 17.8cm
\textheight 23.5 cm
\oddsidemargin -.25in
\evensidemargin -.25in
\topskip 0cm
\headheight 0cm


\title{Recherche de l'arbre couvrant minimal}
\author{Alain \sc{Frisch}}
\date{\today}

\begin{document}
\maketitle

\section{Notations et pr\'eliminaires}
On consid\`ere ici des graphes non orient\'es valu\'es : $G=(E,A,v)$ o\`u
$E$ est un ensemble fini (ensemble des sommets), $A\subset
{\mathcal P_2}(E)$ est l'ensemble des ar\^etes et $v:A \fl \R$
est la fonction de poids. Le poids de $G$ est $\Sigma_{\alpha \in
A} v(\alpha)$.
Un sous-graphe de $G$ est un graphe de la forme $G'=(E',A',v_{|A'})$
o\`u $E' \subset E, A' \subset {\mathcal P_2}(E') \cap A$. Si
$E=E'$, $G'$ est couvrant.

Un chemin de $a$ \`a $b$, $a,b \in E$ est une suite finie de sommets
$(x_1, \ldots, x_n)$ avec $a=x_1$, $b=x_n$.
On dit qu'un chemin est simple si la suite est injective.
On dit que $G$ est connexe s'il existe un chemin entre deux
sommets quelconques (il y a alors un chemin simple). Si, de plus,
il y a unicit\'e du chemin simple, alors on dit que $G$ est un arbre
(ou graphe simplement connexe, graphe connexe sans cycle).
Remarquons qu'un arbre poss\`ede $\sharp E-1$ ar\^etes.

On se pose le probl\`eme suivant : supposant $G$ connexe, trouver un
sous-graphe couvrant $G'$ qui soit un arbre, et de poids minimal.
Evidemment, cela revient \`a chercher un sous-ensemble de $A$.
On identifie $F\subset A$ au sous-graphe $(E',F)$ contenant les sommets
extremit\'es d'ar\^etes de $F$.

\section{Algorithme de Kruskal}
On r\'eunit au fur et \`a mesure des composantes connexes.
\begin{algo}[Kruskal]
\
\begin{enumerate}
 \item Trier les ar\^etes par poids croissant $v(\alpha_1)\leq v(\alpha_2)\leq 
 \ldots$

 \item $F \leftarrow \emptyset$ (ensemble d'ar\^etes)

 \item Parcourir les ar\^etes et pour chacune, la rajouter \`a $F$ si
 elle relie deux composantes connexes distinctes du graphe d\'efini par $F$
\end{enumerate}
\end{algo}

Nous aurons besoin du lemme :
\begin{lemme}
Si $F_1$ et $F_2$ sont deux sous-arbres couvrants et si $\alpha
\in F_1, \alpha \notin F_2$, alors il existe une ar\^ete $\beta \in
F_2$ telle que $F_1 \backslash \{\alpha\} \cup \{\beta\}$ soit un
sous-arbre couvrant.
\end{lemme}
\begin{proof}
Notons $\alpha={x,y}$. $F_1 \backslash \{\alpha\}$ d\'efinit deux
composantes connexe simples (celle de $x$, celle de $y$). Dans le
chemin simple reliant $x$ \`a $y$ dans $F_2$, on peut choisir une
ar\^ete $\beta$ reliant un sommet de la composante connexe de $x$ \`a
un sommet de celle de $y$. On constate que $\beta$ convient.
\end{proof}

Il est clair que l'algorithme de Kruskal termine et fournit un
sous-arbre couvrant. Prouvons qu'il est minimal.
\begin{proof}
Soit $F$ le r\'esultat de l'algorithme et $U$ une solution minimale
ayant le plus d'ar\^etes communes avec $F$. $U$ et $F$ ont m\^eme
cardinal. Si $U \neq F$, on prend $\alpha \in U \backslash F$ de
telle sorte que $v(\alpha)$ soit minimal. Le lemme donne une ar\^ete
$\beta$ de $F$, $U'=U \backslash \{\alpha\} \cup \{\beta\}$ est un arbre
couvrant. Toutes les ar\^etes de $U$ moins lourdes que $\alpha$ sont
dans $F$ par d\'efinition de $\alpha$. La construction de
l'algorithme donne alors : $v(\beta)\leq v(\alpha)$ (sinon, $\alpha$
aurait \'et\'e trait\'ee avant $\beta$ et aurait \'et\'e accept\'ee). Ainsi
$U'$ est-il encore minimal, et moins diff\'erent de $F$ que $U$,
ce qui contredit sa d\'efinition.
\end{proof}

\section{Algorithme de Prim}
On construit ici un sous-graphe connexe que l'on fait cro\^itre.
\begin{algo}[Prim]
\
\begin{enumerate}
 \item $F \leftarrow \emptyset$ (ensemble d'ar\^etes, qui d\'efinit un
 sous-arbre)

 \item Tant que $F$ n'est pas couvrant, lui rajouter une des
 ar\^etes de poids minimal qui le relie \`a un sommet ext\'erieur.
\end{enumerate}
\end{algo}

Il est clair que l'algorithme de Prim termine et fournit un
sous-arbre couvrant. Prouvons qu'il est minimal.
\begin{proof}
Soit $U$ une solution minimale telle que le nombre d'\'etapes de l'algorithme pendant
lesquelles l'arbre en cours de construction est un sous-arbre de
$U$ soit maximale. Consid\'erons pr\'ecisement cette \'etape o\`u
l'algorithme rajoute \`a $F \subset U$ une ar\^ete $\alpha={x,y}$ qui n'est pas dans
$U$, $x$ est dans le graphe d\'efini par $F$ et non $y$. Il
existe un chemin reliant $x$ \`a $y$ dans $U$. Soit $\beta$ la
premi\`ere ar\^ete travers\'ee par ce chemin, qui sort de $F$. On
a $v(\alpha)\leq v(\beta)$ par d\'efinition de $\alpha$ dans
l'algorithme.
Rempla\c{c}ons $\beta$ par $\alpha$ dans $U$ pour obtenir $U'$. $U'$
est encore un arbre-couvrant minimal (supprimer $\beta$ s\'epare $U$ en deux
composantes connexes que $\alpha$ r\'eunit). Cela contredit la
d\'efinition de $U$.
\end{proof}

\end{document}