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} & \underline{\times} & \underline{\times} & \underline{\times} & \underline{\times} \\\hline \Gamma^-(x_{1}, \G) & \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_{2}, x_{5}\}\)
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} \\\hline \Gamma^-(x_{3}, \G) & \underline{\times} & \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_{6}\}\)
L'algorithme du marquage donne les descendants et ascendants du sommet \( x_{4}\) \[ \begin{array}{r|*{7}{|c}}Sommet & {x_{1}} & {x_{2}} & {x_{3}} & {x_{4}} & {x_{5}} & {x_{6}} & {x_{7}} \\\hline \Gamma^+(x_{4}, \G) & & & & \underline{\times} & & & \underline{\times} \\\hline \Gamma^-(x_{4}, \G) & \underline{\times} & \underline{\times} & \underline{\times} & \underline{\times} & \underline{\times} & \underline{\times} & \underline{\times} \end{array} \]
En fin de compte, \( CCF(x_4, \G)\) est le sous graphe engendré par \( \Gamma^+(x_{4}, \G)\cap \Gamma^-(x_{4}, \G)=\{ x_{4}, 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 & 1 & 1\\ X_{2} & 0 & 1 & 1\\ X_{3} & 0 & 0 & 1\end{array}\]
\[
\xymatrix{
X_{1} \ar@(lu,ru)[]\ar@/^0.79pc/[rr]\ar@/^0.79pc/[rdd] && X_{2} \ar@(lu,ru)[]\ar@/^0.79pc/[ldd] \\
&&\\
& X_{3} \ar@(ld,rd)[]&
}
\]
