Exercice
L'algorithme du marquage donne les descendants et ascendants du sommet \( x_{1}\) \[ \begin{array}{r|*{7}{|c}}Sommet & {x_{1}} & {x_{2}} & {x_{3}} & {x_{4}} & {x_{5}} & {x_{6}} & {x_{7}} \\\hline \Gamma^+(x_{1}, \G) & \underline{\times} & & & & \underline{\times} & \underline{\times} & \\\hline \Gamma^-(x_{1}, \G) & \underline{\times} & \underline{\times} & \underline{\times} & \underline{\times} & \underline{\times} & \underline{\times} & \underline{\times} \end{array} \]
En fin de compte, \( CCF(x_1, \G)\) est le sous graphe engendré par \( \Gamma^+(x_{1}, \G)\cap \Gamma^-(x_{1}, \G)=\{ x_{1}, x_{5}, x_{6}\}\)
L'algorithme du marquage donne les descendants et ascendants du sommet \( x_{2}\) \[ \begin{array}{r|*{7}{|c}}Sommet & {x_{1}} & {x_{2}} & {x_{3}} & {x_{4}} & {x_{5}} & {x_{6}} & {x_{7}} \\\hline \Gamma^+(x_{2}, \G) & \underline{\times} & \underline{\times} & \underline{\times} & \underline{\times} & \underline{\times} & \underline{\times} & \underline{\times} \\\hline \Gamma^-(x_{2}, \G) & & \underline{\times} & & \underline{\times} & & & \end{array} \]
En fin de compte, \( CCF(x_2, \G)\) est le sous graphe engendré par \( \Gamma^+(x_{2}, \G)\cap \Gamma^-(x_{2}, \G)=\{ x_{2}, x_{4}\}\)
L'algorithme du marquage donne les descendants et ascendants du sommet \( x_{3}\) \[ \begin{array}{r|*{7}{|c}}Sommet & {x_{1}} & {x_{2}} & {x_{3}} & {x_{4}} & {x_{5}} & {x_{6}} & {x_{7}} \\\hline \Gamma^+(x_{3}, \G) & \underline{\times} & & \underline{\times} & & \underline{\times} & \underline{\times} & \underline{\times} \\\hline \Gamma^-(x_{3}, \G) & & \underline{\times} & \underline{\times} & \underline{\times} & & & \underline{\times} \end{array} \]
En fin de compte, \( CCF(x_3, \G)\) est le sous graphe engendré par \( \Gamma^+(x_{3}, \G)\cap \Gamma^-(x_{3}, \G)=\{ x_{3}, x_{7}\}\)
Si l'on note chacune de ces composantes connexes respectivement de \( X_{1}\) à \( X_{3}\) alors le graphe réduit se représente par comme suit
\[\begin{array}{c||ccc} & X_{1} & X_{2} & X_{3} \\\hline\hline X_{1} & 1 & 0 & 0\\ X_{2} & 1 & 1 & 1\\ X_{3} & 1 & 0 & 1\end{array}\]
\[
\xymatrix{
X_{1} \ar@(lu,ru)[] && X_{2} \ar@/^0.79pc/[ll]\ar@(lu,ru)[]\ar@/^0.79pc/[ldd] \\
&&\\
& X_{3} \ar@/^0.79pc/[luu]\ar@(ld,rd)[]&
}
\]
