Arbres couvrant de poids minimum
Définition
Soit \( (\G,\lambda)\) un graphe métrique non orienté.
- \( \bullet\)
- Un arbre couvrant de \( \G\) est un sous graphe \( \G'\) de \( \G\) tel que \( \G'\) soit un arbre et \( \Som(\G')=\Som(\G)\) .
- \( \bullet\)
- Soit \( \G'\) un arbre couvrant de \( \G\) . Le poids de \( \G'\) est la somme des valuations de ses arêtes. On le note \( P(\G')\) .
\[P(\G')=\sum_{\{x,y\}\in \Ar(\G')}\lambda(\{x,y\})\]
Considérons 8 villes dont certaines sont reliées entre elles par de petites routes de terre
\[
\xymatrix@R=2cm@C=2cm{
a\ar@{-}[r]^4\ar@{-}[d]_8\ar@{-}@/^2pc/[rr]^6&b\ar@{-}[r]^1\ar@{-}[d]^2\ar@{-}[dl]_2&c\ar@{-}[r]^4\ar@{-}[d]^6\ar@{-}[dl]_4&d\ar@{-}[d]^3\ar@{-}@/^1pc/[lld]^1\ar@{-}[dl]^3\\
e\ar@{-}[r]_1&f\ar@{-}[r]_2&g\ar@{-}[r]_1&h
}
\]
où la métrique représente la distance en kilomètre qui sépare les villes.
Le gouvernement souhaite construire des routes entre ces villes en goudronnant les chemins de terre. Ce projet est soumis à deux contraintes :
- Chaque ville doit avoir au moins une route goudronnée.
- Minimiser le prix de construction sachant qu'un kilomètre de goudronnage coute \( 10000\) €.
Le premier point sera satisfait, si on parvient à trouver un arbre couvrant. Pour satisfaire le second point il faudra que cet arbre soit de poids minimum.
Algorithme de Kruskal
Cet algorithme permet de déterminer un arbre couvrant en parcourant le graphe par ses arêtes.
§
Algorithme de Kruskal (on ne décrit les graphes que par leur arêtes).
\( A\) = l'ensemble des arêtes de \( \G\)
\( F\) = \( \varnothing\)
Tant que \( A\neq\varnothing\)
\( a\) = élément de \( A\) tel que \( \lambda(a)\) soit minimal.
\( A = A -\{a\}\) .
Si \( F\cup\{a\}\) est sans circuit
\( F=F\cup\{a\}\)
Fin si
Fin tant que
Solution = \( F\) .
Appliquons cette méthode avec le graphe de l'exemple.
- \( \bullet\)
- Arête \( \{b,c\}\)
\(
\xymatrix@R=2cm@C=2cm{
a\ar@{-}@{..}[r]^4\ar@{-}@{..}[d]_8\ar@{-}@{..}@/^2pc/[rr]^6&
b\ar@{-}[r]^1\ar@{-}@{..}[d]^2\ar@{-}@{..}[dl]_2&
c\ar@{-}@{..}[r]^4\ar@{-}@{..}[d]^6\ar@{-}@{..}[dl]_4&
d\ar@{-}@{..}[d]^3\ar@{-}@{..}@/^1pc/[lld]^1\ar@{-}@{..}[dl]^3\\
e\ar@{-}@{..}[r]_1&
f\ar@{-}@{..}[r]_2&
g\ar@{-}@{..}[r]_1&
h
}
\)
- \( \bullet\)
- Arête \( \{d,f\}\)
\(
\xymatrix@R=2cm@C=2cm{
a\ar@{-}@{..}[r]^4\ar@{-}@{..}[d]_8\ar@{-}@{..}@/^2pc/[rr]^6&
b\ar@{-}[r]^1\ar@{-}@{..}[d]^2\ar@{-}@{..}[dl]_2&
c\ar@{-}@{..}[r]^4\ar@{-}@{..}[d]^6\ar@{-}@{..}[dl]_4&
d\ar@{-}@{..}[d]^3\ar@{-}@/^1pc/[lld]^1\ar@{-}@{..}[dl]^3\\
e\ar@{-}@{..}[r]_1&
f\ar@{-}@{..}[r]_2&
g\ar@{-}@{..}[r]_1&
h
}
\)
- \( \bullet\)
- Arête \( \{e,f\}\)
\(
\xymatrix@R=2cm@C=2cm{
a\ar@{-}@{..}[r]^4\ar@{-}@{..}[d]_8\ar@{-}@{..}@/^2pc/[rr]^6&
b\ar@{-}[r]^1\ar@{-}@{..}[d]^2\ar@{-}@{..}[dl]_2&
c\ar@{-}@{..}[r]^4\ar@{-}@{..}[d]^6\ar@{-}@{..}[dl]_4&
d\ar@{-}@{..}[d]^3\ar@{-}@/^1pc/[lld]^1\ar@{-}@{..}[dl]^3\\
e\ar@{-}[r]_1&
f\ar@{-}@{..}[r]_2&
g\ar@{-}@{..}[r]_1&
h
}
\)
- \( \bullet\)
- Arête \( \{g,h\}\)
\(
\xymatrix@R=2cm@C=2cm{
a\ar@{-}@{..}[r]^4\ar@{-}@{..}[d]_8\ar@{-}@{..}@/^2pc/[rr]^6&
b\ar@{-}[r]^1\ar@{-}@{..}[d]^2\ar@{-}@{..}[dl]_2&
c\ar@{-}@{..}[r]^4\ar@{-}@{..}[d]^6\ar@{-}@{..}[dl]_4&
d\ar@{-}@{..}[d]^3\ar@{-}@/^1pc/[lld]^1\ar@{-}@{..}[dl]^3\\
e\ar@{-}[r]_1&
f\ar@{-}@{..}[r]_2&
g\ar@{-}[r]_1&
h
}
\)
- \( \bullet\)
- Arête \( \{b,e\}\)
\(
\xymatrix@R=2cm@C=2cm{
a\ar@{-}@{..}[r]^4\ar@{-}@{..}[d]_8\ar@{-}@{..}@/^2pc/[rr]^6&
b\ar@{-}[r]^1\ar@{-}@{..}[d]^2\ar@{-}[dl]_2&
c\ar@{-}@{..}[r]^4\ar@{-}@{..}[d]^6\ar@{-}@{..}[dl]_4&
d\ar@{-}@{..}[d]^3\ar@{-}@/^1pc/[lld]^1\ar@{-}@{..}[dl]^3\\
e\ar@{-}[r]_1&
f\ar@{-}@{..}[r]_2&
g\ar@{-}[r]_1&
h
}
\)
- \( \bullet\)
- Arête \( \{b,f\}\) . Fait apparaitre un circuit.
\(
\xymatrix@R=2cm@C=2cm{
a\ar@{-}@{..}[r]^4\ar@{-}@{..}[d]_8\ar@{-}@{..}@/^2pc/[rr]^6&
b\ar@{-}[r]^1\ar@{-}@[red][d]^2\ar@{-}[dl]_2&
c\ar@{-}@{..}[r]^4\ar@{-}@{..}[d]^6\ar@{-}@{..}[dl]_4&
d\ar@{-}@{..}[d]^3\ar@{-}@/^1pc/[lld]^1\ar@{-}@{..}[dl]^3\\
e\ar@{-}[r]_1&
f\ar@{-}@{..}[r]_2&
g\ar@{-}[r]_1&
h
}
\)
- \( \bullet\)
- Arête \( \{f,g\}\) .
\(
\xymatrix@R=2cm@C=2cm{
a\ar@{-}@{..}[r]^4\ar@{-}@{..}[d]_8\ar@{-}@{..}@/^2pc/[rr]^6&
b\ar@{-}[r]^1\ar@{-}@[red][d]^2\ar@{-}[dl]_2&
c\ar@{-}@{..}[r]^4\ar@{-}@{..}[d]^6\ar@{-}@{..}[dl]_4&
d\ar@{-}@{..}[d]^3\ar@{-}@/^1pc/[lld]^1\ar@{-}@{..}[dl]^3\\
e\ar@{-}[r]_1&
f\ar@{-}[r]_2&
g\ar@{-}[r]_1&
h
}
\)
- \( \bullet\)
- Arête \( \{d,g\}\) . Fait apparaitre un circuit.
\(
\xymatrix@R=2cm@C=2cm{
a\ar@{-}@{..}[r]^4\ar@{-}@{..}[d]_8\ar@{-}@{..}@/^2pc/[rr]^6&
b\ar@{-}[r]^1\ar@{-}@[red][d]^2\ar@{-}[dl]_2&
c\ar@{-}@{..}[r]^4\ar@{-}@{..}[d]^6\ar@{-}@{..}[dl]_4&
d\ar@{-}@{..}[d]^3\ar@{-}@/^1pc/[lld]^1\ar@{-}@[red][dl]^3\\
e\ar@{-}[r]_1&
f\ar@{-}[r]_2&
g\ar@{-}[r]_1&
h
}
\)
- \( \bullet\)
- Arête \( \{d,h\}\) . Fait apparaitre un circuit.
\(
\xymatrix@R=2cm@C=2cm{
a\ar@{-}@{..}[r]^4\ar@{-}@{..}[d]_8\ar@{-}@{..}@/^2pc/[rr]^6&
b\ar@{-}[r]^1\ar@{-}@[red][d]^2\ar@{-}[dl]_2&
c\ar@{-}@{..}[r]^4\ar@{-}@{..}[d]^6\ar@{-}@{..}[dl]_4&
d\ar@{-}@[red][d]^3\ar@{-}@/^1pc/[lld]^1\ar@{-}@[red][dl]^3\\
e\ar@{-}[r]_1&
f\ar@{-}[r]_2&
g\ar@{-}[r]_1&
h
}
\)
- \( \bullet\)
- Arête \( \{a,b\}\) .
\(
\xymatrix@R=2cm@C=2cm{
a\ar@{-}[r]^4\ar@{-}@{..}[d]_8\ar@{-}@{..}@/^2pc/[rr]^6&
b\ar@{-}[r]^1\ar@{-}@[red][d]^2\ar@{-}[dl]_2&
c\ar@{-}@{..}[r]^4\ar@{-}@{..}[d]^6\ar@{-}@{..}[dl]_4&
d\ar@{-}@[red][d]^3\ar@{-}@/^1pc/[lld]^1\ar@{-}@[red][dl]^3\\
e\ar@{-}[r]_1&
f\ar@{-}[r]_2&
g\ar@{-}[r]_1&
h
}
\)
- \( \bullet\)
- Arête \( \{c,d\}\) . Fait apparaitre un circuit.
\(
\xymatrix@R=2cm@C=2cm{
a\ar@{-}[r]^4\ar@{-}@{..}[d]_8\ar@{-}@{..}@/^2pc/[rr]^6&
b\ar@{-}[r]^1\ar@{-}@[red][d]^2\ar@{-}[dl]_2&
c\ar@{-}@[red][r]^4\ar@{-}@{..}[d]^6\ar@{-}@{..}[dl]_4&
d\ar@{-}@[red][d]^3\ar@{-}@/^1pc/[lld]^1\ar@{-}@[red][dl]^3\\
e\ar@{-}[r]_1&
f\ar@{-}[r]_2&
g\ar@{-}[r]_1&
h
}
\)
- \( \bullet\)
- Arête \( \{c,f\}\) . Fait apparaitre un circuit.
\(
\xymatrix@R=2cm@C=2cm{
a\ar@{-}[r]^4\ar@{-}@{..}[d]_8\ar@{-}@{..}@/^2pc/[rr]^6&
b\ar@{-}[r]^1\ar@{-}@[red][d]^2\ar@{-}[dl]_2&
c\ar@{-}@[red][r]^4\ar@{-}@{..}[d]^6\ar@{-}@[red][dl]_4&
d\ar@{-}@[red][d]^3\ar@{-}@/^1pc/[lld]^1\ar@{-}@[red][dl]^3\\
e\ar@{-}[r]_1&
f\ar@{-}[r]_2&
g\ar@{-}[r]_1&
h
}
\)
- \( \bullet\)
- Arête \( \{a,c\}\) . Fait apparaitre un circuit.
\(
\xymatrix@R=2cm@C=2cm{
a\ar@{-}[r]^4\ar@{-}@{..}[d]_8\ar@{-}@[red]@/^2pc/[rr]^6&
b\ar@{-}[r]^1\ar@{-}@[red][d]^2\ar@{-}[dl]_2&
c\ar@{-}@[red][r]^4\ar@{-}@{..}[d]^6\ar@{-}@[red][dl]_4&
d\ar@{-}@[red][d]^3\ar@{-}@/^1pc/[lld]^1\ar@{-}@[red][dl]^3\\
e\ar@{-}[r]_1&
f\ar@{-}[r]_2&
g\ar@{-}[r]_1&
h
}
\)
- \( \bullet\)
- Arête \( \{c,g\}\) . Fait apparaitre un circuit.
\(
\xymatrix@R=2cm@C=2cm{
a\ar@{-}[r]^4\ar@{-}@{..}[d]_8\ar@{-}@[red]@/^2pc/[rr]^6&
b\ar@{-}[r]^1\ar@{-}@[red][d]^2\ar@{-}[dl]_2&
c\ar@{-}@[red][r]^4\ar@{-}@[red][d]^6\ar@{-}@[red][dl]_4&
d\ar@{-}@[red][d]^3\ar@{-}@/^1pc/[lld]^1\ar@{-}@[red][dl]^3\\
e\ar@{-}[r]_1&
f\ar@{-}[r]_2&
g\ar@{-}[r]_1&
h
}
\)
- \( \bullet\)
- Arête \( \{a,e\}\) . Fait apparaitre un circuit.
\(
\xymatrix@R=2cm@C=2cm{
a\ar@{-}[r]^4\ar@{-}@[red][d]_8\ar@{-}@[red]@/^2pc/[rr]^6&
b\ar@{-}[r]^1\ar@{-}@[red][d]^2\ar@{-}[dl]_2&
c\ar@{-}@[red][r]^4\ar@{-}@[red][d]^6\ar@{-}@[red][dl]_4&
d\ar@{-}@[red][d]^3\ar@{-}@/^1pc/[lld]^1\ar@{-}@[red][dl]^3\\
e\ar@{-}[r]_1&
f\ar@{-}[r]_2&
g\ar@{-}[r]_1&
h
}
\)
- \( \bullet\) Conclusion
-
\(
\xymatrix@R=2cm@C=2cm{
a\ar@{-}[r]&
b\ar@{-}[r]\ar@{-}[dl]&
c&
d\ar@{-}@/^1pc/[lld]\\
e\ar@{-}[r]&
f\ar@{-}[r]&
g\ar@{-}[r]&
h
}
\)
Algorithme de Prim
Le problème de l'algorithme de Kruskal est d'observer un cycle. Une alternative : l'algorithme de Prim
§ On choisi un sommet \( x\) .
1. Initialisation
d_min(x)=0;
sommet_proche(x)={};
Pour tous les sommets y différent de x
d_min(y)=\( +\infty\) ; sommet_proche(y)={};
Fin pour
2.
Tant qu'il existe des sommets non marqués
On marque un sommet y non marqué tel que d_min(y)
soit le plus petit possible.
Pour tout sommet z non marqué et successeur/voisin à y
Si d_min(z) > \( \lambda\) ({y,z})
d_min(z) = \( \lambda\) ({y,z}); sommet_proche(z) = y;
Fin si
Fin pour
Fin tant que
Cet algorithme est très proche de celui de Djikstra. Historiquement, il fut trouvé dans les années 30 par Vojtěch Jarník, un mathématicien tchèque puis redécouvert et publié par Prim et Dijkstra en 1959. Il est parfois appelé algorithme DJP.
A noter qu'il suffit de partir de n'importe quelle sommet. L'arbre ne sera peut-être pas le même mais le poids sera minimal.
Faisons tourner cet algorithme sur le même graphe. On utilise le même tableau que celui de Dijkstra.
Initialisons les variables :
\[
\begin{array}{|c|*{8}{|c}|}
\hline
&a&b&c&d&e&f&g&h\\\hline\hline
\texttt{Init}&0&&&&&&&\\\hline
&&&&&&&&\\\hline
&&&&&&&&\\\hline
&&&&&&&&\\\hline
&&&&&&&&\\\hline
&&&&&&&&\\\hline
&&&&&&&&\\\hline
&&&&&&&&\\\hline
\end{array}
\]
Le sommet au
d_min minimal est \( a\) . On le marque. Ses sommets adjacents sont \( b\) , \( c\) et \( e\) .
- \( \bullet\)
- Puisque d_min(\( b\) ) > \( \lambda(\{a,b\})\) soit \( +\infty{>}4\) on modifie la colonne du sommet \( b\) .
- \( \bullet\)
- Puisque d_min(\( c\) ) > \( \lambda(\{a,c\})\) soit \( +\infty{>}6\) on modifie la colonne du sommet \( c\) .
- \( \bullet\)
- Puisque d_min(\( e\) ) > \( \lambda(\{a,e\})\) soit \( +\infty{>}8\) on modifie la colonne du sommet \( e\) .
\[
\begin{array}{|c|*{8}{|c}|}
\hline
&a&b&c&d&e&f&g&h\\\hline\hline
\texttt{Init}&\boxed{0}&&&&&&&\\\hline
a&X&4&6&&8&&&\\\hline
&X&&&&&&&\\\hline
&X&&&&&&&\\\hline
&X&&&&&&&\\\hline
&X&&&&&&&\\\hline
&X&&&&&&&\\\hline
&X&&&&&&&\\\hline
\end{array}
\]
Le sommet au
d_min minimal non marqué est \( b\) . On le marque. Ses sommets adjacents non marqués sont \( c\) , \( e\) et \( f\) .
- \( \bullet\)
- Puisque d_min(\( f\) ) > \( \lambda(\{b,f\})\) soit \( +\infty{>}2\) on modifie la colonne du sommet \( f\) .
- \( \bullet\)
- Puisque d_min(\( e\) ) > \( \lambda(\{b,e\})\) soit \( 8{>}2\) on modifie la colonne du sommet \( e\) .
- \( \bullet\)
- Puisque d_min(\( c\) ) > \( \lambda(\{b,c\})\) soit \( 6{>}1\) on modifie la colonne du sommet \( c\) .
\[
\begin{array}{|c|*{8}{|c}|}
\hline
&a&b&c&d&e&f&g&h\\\hline\hline
\texttt{Init}&\boxed{0}&&&&&&&\\\hline
a&X&\boxed{4}&6&&8&&&\\\hline
b&X&X&1&&2&2&&\\\hline
&X&X&&&&&&\\\hline
&X&X&&&&&&\\\hline
&X&X&&&&&&\\\hline
&X&X&&&&&&\\\hline
&X&X&&&&&&\\\hline
\end{array}
\]
Le sommet au
d_min minimal non marqué est \( c\) . On le marque. Ses sommets adjacents non marqués sont \( d\) , \( f\) et \( g\) .
- \( \bullet\)
- Puisque d_min(\( d\) ) > \( \lambda(\{c,d\})\) soit \( +\infty{>}4\) on modifie la colonne du sommet \( d\) .
- \( \bullet\)
- Puisque d_min(\( f\) ) \( \leqslant\) \( \lambda(\{c,f\})\) soit \( 2\leqslant 4\) on ne modifie pas la colonne du sommet \( f\) .
- \( \bullet\)
- Puisque d_min(\( g\) ) > \( \lambda(\{c,g\})\) soit \( +\infty{>}6\) on modifie la colonne du sommet \( g\) .
\[
\begin{array}{|c|*{8}{|c}|}
\hline
&a&b&c&d&e&f&g&h\\\hline\hline
\texttt{Init}&\boxed{0}&&&&&&&\\\hline
a&X&\boxed{4}&6&&8&&&\\\hline
b&X&X&\boxed{1}&&2&2&&\\\hline
c&X&X&X&4&2&2&6&\\\hline
&X&X&X&&&&&\\\hline
&X&X&X&&&&&\\\hline
&X&X&X&&&&&\\\hline
&X&X&X&&&&&\\\hline
\end{array}
\]
Le sommet au
d_min minimal non marqué est \( e\) . Le seul sommet adjacent non marqué est \( f\) .
- \( \bullet\)
- Puisque d_min(\( f\) ) > \( \lambda(\{e,f\})\) soit \( 2{>}1\) on modifie la colonne du sommet \( f\) .
\[
\begin{array}{|c|*{8}{|c}|}
\hline
&a&b&c&d&e&f&g&h\\\hline\hline
\texttt{Init}&\boxed{0}&&&&&&&\\\hline
a&X&\boxed{4}&6&&8&&&\\\hline
b&X&X&\boxed{1}&&\boxed{2}&2&&\\\hline
c&X&X&X&4&2&2&6&\\\hline
e&X&X&X&4&X&1&6&\\\hline
&X&X&X&&X&&&\\\hline
&X&X&X&&X&&&\\\hline
&X&X&X&&X&&&\\\hline
\end{array}
\]
Le sommet au
d_min minimal non marqué est \( f\) . Les sommets adjacents non marqués sont \( d\) et \( g\) .
- \( \bullet\)
- Puisque d_min(\( d\) ) > \( \lambda(\{f,d\})\) soit \( 4{>}1\) on modifie la colonne du sommet \( f\) .
- \( \bullet\)
- Puisque d_min(\( g\) ) > \( \lambda(\{f,g\})\) soit \( 6{>}2\) on modifie la colonne du sommet \( g\) .
\[
\begin{array}{|c|*{8}{|c}|}
\hline
&a&b&c&d&e&f&g&h\\\hline\hline
\texttt{Init}&\boxed{0}&&&&&&&\\\hline
a&X&\boxed{4}&6&&8&&&\\\hline
b&X&X&\boxed{1}&&\boxed{2}&2&&\\\hline
c&X&X&X&4&2&2&6&\\\hline
e&X&X&X&4&X&\boxed{1}&6&\\\hline
f&X&X&X&1&X&X&2&\\\hline
&X&X&X&&X&X&&\\\hline
&X&X&X&&X&X&&\\\hline
\end{array}
\]
Le sommet au
d_min minimal non marqué est \( d\) . Les sommets adjacents non marqués sont \( g\) et \( h\) .
- \( \bullet\)
- Puisque d_min(\( g\) ) \( \leqslant\) \( \lambda(\{d,g\})\) soit \( 2\leqslant 3\) on ne modifie pas la colonne du sommet \( g\) .
- \( \bullet\)
- Puisque d_min(\( h\) ) > \( \lambda(\{d,h\})\) soit \( +\infty{>}3\) on modifie la colonne du sommet \( h\) .
\[
\begin{array}{|c|*{8}{|c}|}
\hline
&a&b&c&d&e&f&g&h\\\hline\hline
\texttt{Init}&\boxed{0}&&&&&&&\\\hline
a&X&\boxed{4}&6&&8&&&\\\hline
b&X&X&\boxed{1}&&\boxed{2}&2&&\\\hline
c&X&X&X&4&2&2&6&\\\hline
e&X&X&X&4&X&\boxed{1}&6&\\\hline
f&X&X&X&\boxed{1}&X&X&2&\\\hline
d&X&X&X&X&X&X&2&3\\\hline
&X&X&X&X&X&X&&\\\hline
\end{array}
\]
Le sommet au
d_min minimal non marqué est \( g\) . Le seul sommet adjacent non marqué est \( h\)
- \( \bullet\)
- Puisque d_min(\( h\) ) > \( \lambda(\{g,h\})\) soit \( 3{>}1\) on modifie la colonne du sommet \( h\) .
\[
\begin{array}{|c|*{8}{|c}|}
\hline
&a&b&c&d&e&f&g&h\\\hline\hline
\texttt{Init}&\boxed{0}&&&&&&&\\\hline
a&X&\boxed{4}&6&&8&&&\\\hline
b&X&X&\boxed{1}&&\boxed{2}&2&&\\\hline
c&X&X&X&4&2&2&6&\\\hline
e&X&X&X&4&X&\boxed{1}&6&\\\hline
f&X&X&X&\boxed{1}&X&X&\boxed{2}&\\\hline
d&X&X&X&X&X&X&2&3\\\hline
g&X&X&X&X&X&X&X&1\\\hline
\end{array}
\]
\[
\begin{array}{|c|*{8}{|c}|}
\hline
&a&b&c&d&e&f&g&h\\\hline\hline
\texttt{Init}&\boxed{0}&&&&&&&\\\hline
a&X&\boxed{4}&6&&8&&&\\\hline
b&X&X&\boxed{1}&&\boxed{2}&2&&\\\hline
c&X&X&X&4&2&2&6&\\\hline
e&X&X&X&4&X&\boxed{1}&6&\\\hline
f&X&X&X&\boxed{1}&X&X&\boxed{2}&\\\hline
d&X&X&X&X&X&X&2&3\\\hline
g&X&X&X&X&X&X&X&\boxed{1}\\\hline
\end{array}
\]
Pour finir il suffit de lire les arêtes a mettre en avant pour déterminer l'arbre couvrant.
Pour \( b\) c'est l'arête \( \{b,a\}\) .
Pour \( c\) c'est l'arête \( \{c,b\}\) .
Pour \( d\) c'est l'arête \( \{d,f\}\) .
Pour \( e\) c'est l'arête \( \{e,b\}\) .
Pour \( f\) c'est l'arête \( \{f,e\}\) .
Pour \( g\) c'est l'arête \( \{g,f\}\) .
Pour \( h\) c'est l'arête \( \{h,g\}\) .
\(
\xymatrix@R=2cm@C=2cm{
a\ar@{-}[r]&
b\ar@{-}[r]\ar@{-}[dl]&
c&
d\ar@{-}@/^1pc/[lld]\\
e\ar@{-}[r]&
f\ar@{-}[r]&
g\ar@{-}[r]&
h
}
\)
