On considère le graphe \( \G\) suivant donné par sa matrice booléenne. Ce graphe est composé de \( 3\) composantes connexes fortes. Déterminer chacune d'elle et donner la représentation matricielle et sagittale du graphe réduit. \[\begin{array}{c||cccccccc} & x_{1} & x_{2} & x_{3} & x_{4} & x_{5} & x_{6} & x_{7} & x_{8} \\\hline\hline x_{1} & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0\\ x_{2} & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 1\\ x_{3} & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ x_{4} & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\ x_{5} & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\ x_{6} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\ x_{7} & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ x_{8} & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0\end{array}\]
L'algorithme du marquage donne les descendants et ascendants du sommet \( x_{1}\) \[ \begin{array}{r|*{8}{|c}}Sommet & {x_{1}} & {x_{2}} & {x_{3}} & {x_{4}} & {x_{5}} & {x_{6}} & {x_{7}} & {x_{8}} \\\hline \Gamma^+(x_{1}, \G) & \underline{\times} & & & & & & \underline{\times} & \\\hline \Gamma^-(x_{1}, \G) & \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_{7}\}\)
L'algorithme du marquage donne les descendants et ascendants du sommet \( x_{2}\) \[ \begin{array}{r|*{8}{|c}}Sommet & {x_{1}} & {x_{2}} & {x_{3}} & {x_{4}} & {x_{5}} & {x_{6}} & {x_{7}} & {x_{8}} \\\hline \Gamma^+(x_{2}, \G) & & \underline{\times} & \underline{\times} & \underline{\times} & \underline{\times} & \underline{\times} & & \underline{\times} \\\hline \Gamma^-(x_{2}, \G) & & \underline{\times} & \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_{3}, x_{5}\}\)
L'algorithme du marquage donne les descendants et ascendants du sommet \( x_{4}\) \[ \begin{array}{r|*{8}{|c}}Sommet & {x_{1}} & {x_{2}} & {x_{3}} & {x_{4}} & {x_{5}} & {x_{6}} & {x_{7}} & {x_{8}} \\\hline \Gamma^+(x_{4}, \G) & & & & \underline{\times} & & \underline{\times} & & \underline{\times} \\\hline \Gamma^-(x_{4}, \G) & & \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_{6}, x_{8}\}\)
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} & 0 & 1 & 1\\ X_{3} & 0 & 0 & 1\end{array}\]
\[
\xymatrix{
X_{1} \ar@(lu,ru)[] && X_{2} \ar@(lu,ru)[]\ar@/^0.79pc/[ldd] \\
&&\\
& X_{3} \ar@(ld,rd)[]&
}
\]
