next up previous
suivant: La condition est nécessaire monter: Les conditions d'optimalité d'un précédent: Les conditions d'optimalité d'un

La condition d'optimalité de coupes

En préliminaire, il est important de préciser que l'on entend ici par coupe associée à un sous graphe $ H$ de $ G$ un couple $ [S, \, \overline{S}]$ sans arête de $ H$ entre $ S$ et $ \overline{S}$ tel que montré par la figure (6.1). Par analogie avec les graphes orientés, on parlera des arêtes d'une coupe : toutes les arêtes de $ G$ entre $ S$ et $ \overline{S}$, soit encore le cocycle de $ S$.

Figure 6.1: Illustration de la coupe pour l'ACM
\begin{figure}
\leavevmode
\begin{center}
\psfig{figure=arpm1.eps}
\end{center}
\end{figure}


\begin{theo}[Condition d'optimalité de coupes d'un ACM]
Soit $T^*$\ un arbre ...
...i,\,j)$\ est l'unique arête de $T^*$\ reliant $S$\ à $\overline{S}$.
\end{theo}


Sous-sections

Bruno Garcia 2000-12-17