On considère le graphe $ \G$ suivant donné par sa matrice booléenne. Ce graphe est composé de $ 4$ composantes connexes fortes. Déterminer chacune d'elle et donner la représentation matricielle et sagittale du graphe réduit. $$\begin{array}{c||ccccccccccccc} & x_{1} & x_{2} & x_{3} & x_{4} & x_{5} & x_{6} & x_{7} & x_{8} & x_{9} & x_{10} & x_{11} & x_{12} & x_{13} \\\hline\hline x_{1} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\ x_{2} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0\\ x_{3} & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ x_{4} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\ x_{5} & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\ x_{6} & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 0\\ x_{7} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\ x_{8} & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1\\ x_{9} & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ x_{10} & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\ x_{11} & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\ x_{12} & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ x_{13} & 0 & 0 & 0 & 0 & 0 & 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|*{13}{|c}}Sommet & {x_{1}} & {x_{2}} & {x_{3}} & {x_{4}} & {x_{5}} & {x_{6}} & {x_{7}} & {x_{8}} & {x_{9}} & {x_{10}} & {x_{11}} & {x_{12}} & {x_{13}} \\\hline \Gamma^+(x_{1}, \G) & \underline{\times} & & \underline{\times} & \underline{\times} & & & & & \underline{\times} & & \underline{\times} & & \underline{\times} \\\hline \Gamma^-(x_{1}, \G) & \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_{11}\}$
L'algorithme du marquage donne les descendants et ascendants du sommet $ x_{2}$ $$ \begin{array}{r|*{13}{|c}}Sommet & {x_{1}} & {x_{2}} & {x_{3}} & {x_{4}} & {x_{5}} & {x_{6}} & {x_{7}} & {x_{8}} & {x_{9}} & {x_{10}} & {x_{11}} & {x_{12}} & {x_{13}} \\\hline \Gamma^+(x_{2}, \G) & & \underline{\times} & \underline{\times} & \underline{\times} & & & \underline{\times} & & \underline{\times} & \underline{\times} & & \underline{\times} & \underline{\times} \\\hline \Gamma^-(x_{2}, \G) & & \underline{\times} & & & \underline{\times} & \underline{\times} & \underline{\times} & \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_{7}, x_{10}, x_{12}\}$
L'algorithme du marquage donne les descendants et ascendants du sommet $ x_{3}$ $$ \begin{array}{r|*{13}{|c}}Sommet & {x_{1}} & {x_{2}} & {x_{3}} & {x_{4}} & {x_{5}} & {x_{6}} & {x_{7}} & {x_{8}} & {x_{9}} & {x_{10}} & {x_{11}} & {x_{12}} & {x_{13}} \\\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} & \underline{\times} & \underline{\times} & \underline{\times} & \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_{4}, x_{9}, x_{13}\}$
L'algorithme du marquage donne les descendants et ascendants du sommet $ x_{5}$ $$ \begin{array}{r|*{13}{|c}}Sommet & {x_{1}} & {x_{2}} & {x_{3}} & {x_{4}} & {x_{5}} & {x_{6}} & {x_{7}} & {x_{8}} & {x_{9}} & {x_{10}} & {x_{11}} & {x_{12}} & {x_{13}} \\\hline \Gamma^+(x_{5}, \G) & \underline{\times} & \underline{\times} & \underline{\times} & \underline{\times} & \underline{\times} & \underline{\times} & \underline{\times} & \underline{\times} & \underline{\times} & \underline{\times} & \underline{\times} & \underline{\times} & \underline{\times} \\\hline \Gamma^-(x_{5}, \G) & & & & & \underline{\times} & \underline{\times} & & \underline{\times} & & & & & \end{array} $$
En fin de compte, $ CCF(x_5, \G)$ est le sous graphe engendré par $ \Gamma^+(x_{5}, \G)\cap \Gamma^-(x_{5}, \G)=\{ x_{5}, x_{6}, x_{8}\}$
Si l'on note chacune de ces composantes connexes respectivement de $ X_{1}$ à $ X_{4}$ alors le graphe réduit se représente par comme suit
$$\begin{array}{c||cccc} & X_{1} & X_{2} & X_{3} & X_{4} \\\hline\hline X_{1} & 1 & 0 & 1 & 0\\ X_{2} & 0 & 1 & 1 & 0\\ X_{3} & 0 & 0 & 1 & 0\\ X_{4} & 1 & 1 & 1 & 1\end{array}$$
$$
\xymatrix{
X_{1} \ar@(lu,ru)[]\ar@/^6.579pc/[rrdd] && X_{2} \ar@(lu,ru)[]\ar@/^0.579pc/[dd] \\
&&\\
X_{4} \ar@/^0.579pc/[uu]\ar@/^0.579pc/[rruu]\ar@/^0.579pc/[rr]\ar@(ld,rd)[] && X_{3} \ar@(ld,rd)[] \\
}
$$
