Connexité
Définition
Soit \( x\) un sommet d'un graphe \( \G\) . La composante connexe de \( x\) est le sous-graphe de \( \G\) engendré par \( \Gamma^+(x,\nonor{\G})=\Gamma^-(x,\nonor{\G})\) . On le note \( CC(x,\G)\) .
Autrement dis : la composante connexe d'un sommet est le sous-graphe engendré par tous les ascendants ou descendants de ce sommet.
\[\G\]
\[
\xymatrix@R=0.5cm{
&a\ar[rrd]&&\\
b\ar@/^1pc/[rr]\ar@/_1pc/[rd]&&c\ar@/^1pc/[dl]&d\ar@/_1pc/[ddl]\ar@(dr,ur)[]\\
&e\ar@/_1pc/[ul]\ar@/_1pc/[rr]\ar@(dl,dr)[]&&f\ar@(dr,ur)[]\\
&&g\ar@/_5pc/[ruu]\ar@/^3pc/[uuul]&
}
\]
\[CC(d,\G)\]
\[
\xymatrix@R=0.5cm{
&a\ar[rrd]&&\\
&&&d\ar@/_1pc/[ddl]\ar@(dr,ur)[]\\
&&&\\
&&g\ar@/_5pc/[ruu]\ar@/^3pc/[uuul]&
}
\]
\[ \xymatrix@C=1.5cm@R=0.5cm{
a\ar@{-}@/^1pc/[rr]\ar@{-}[rrd]&b\ar@{-}[d]&c\ar@{-}[d]\\
f&e&d\ar@{-}@/^1pc/[ll]
}
\]
\[ \xymatrix@C=1.5cm@R=0.5cm{
a\ar@{-}@/^1pc/[rr]\ar@{-}[rrd]&&c\ar@{-}[d]\\
f&&d\ar@{-}@/^1pc/[ll]
}
\]
Remarque
L'algorithme du marquage permet donc de déterminer les composantes connexes d'un graphe. Avec l'exemple développé au paragraphe précédent la composante connexe de \( a\) est le sous-graphe engendré par les sommets \( \{a,g,j,k,l,n\}\) . De la même manière la composante connexe de \( b\) est le sous-graphe engendré par les sommets \( \{b,c,d,e,f,h,i,m,o\}\)
\[\xymatrix@R=0.25cm@C=1cm{
&a\ar@{-}[dl]\ar@{-}[dd]\ar@{-}[dr]&&&\\
j&&l\ar@{-}[r]&n&\\
&k\ar@{-}[ur]&&&\\
&&g\ar@{-}@/^1pc/[lluu]\ar@{-}[uur]&&
}\qquad
\xymatrix@R=0.25cm@C=1cm{
&&b\ar@{-}@/^1pc/[dd]\ar@{-}[r]&c\ar@{-}[rd]&\\
&&&&d\ar@{-}[dl]\\
i&&m&o&e\ar@{-}[dl]\\
&h\ar@{-}[ul]\ar@{-}[ur]&&f\ar@{-}[ul]&
}\]
Proposition
Soient \( x\) et \( y\) deux sommets d'un graphe \( \G\) .
\[CC(x,\G) = CC(y,\G)\qquad \Longleftrightarrow\qquad \Big(\exists \alpha \in \Chain(\nonor{\G}),\quad \big(or(\alpha)=x\wedge ab(\alpha)=y\big)\Big)\]
Démonstration
Exercice.
Définition
On dira qu'un graphe est connexe s'il ne possède qu'une seul composante connexe.
\[
\xymatrix@C=2cm@R=1cm{
a\ar@{-}[d]\ar@{-}[dr]\ar@{-}[drr]\ar@{-}@/^1pc/[rr]&b\ar@{-}[d]\ar@{-}[r]&c\ar@{-}[dll]\\
f&e&d
}
\]
Ce graphe est connexe.
Définition
Soit \( x\) un sommet d'un graphe orienté \( \G\) . La composante connexe forte de \( x\) est le sous-graphe de \( \G\) engendré par \( \Gamma^+(x,\G)\cap\Gamma^-(x,\G)\) . On le note \( CCF(x,\G)\) .
\[\G\]
\[
\xymatrix@R=0.5cm{
&a\ar[rrd]&&\\
b\ar@/^1pc/[rr]\ar@/_1pc/[rd]&&c\ar@/^1pc/[dl]&d\ar@/_1pc/[ddl]\ar@(dr,ur)[]\\
&e\ar@/_1pc/[ul]\ar@/_1pc/[rr]\ar@(dl,dr)[]&&f\ar@(dr,ur)[]\\
&&g\ar@/_5pc/[ruu]\ar@/^3pc/[uuul]&
}
\]
\[CCF(a,\G)\]
\[
\xymatrix@R=0.5cm{
&a\ar[rrd]&&\\
&&&d\ar@/_1pc/[ddl]\ar@(dr,ur)[]\\
&&&\\
&&g\ar@/_5pc/[ruu]\ar@/^3pc/[uuul]&
}
\]
Définition
Soit \( \G\) un graphe orienté. On définit le graphe réduit de \( \G\) , noté \( \G_{red}\) par :
\[\Som(\G_{red})=\left\{CCF(x,\G)\Big|x\in \Som(\G)\right\}\]
\[\Arc(\G_{red})=\left\{(I,J)\in \Som(\G_{red})\Big|\Arc(\G)\cap(I\times J)\neq\varnothing\right\}\]
\[\G\]
\[
\xymatrix@R=0.5cm{
&a\ar[rrd]&&\\
b\ar@/^1pc/[rr]\ar@/_1pc/[rd]&&c\ar@/^1pc/[dl]&d\ar@/_1pc/[ddl]\ar@(dr,ur)[]\\
&e\ar@/_1pc/[ul]\ar@/_1pc/[rr]\ar@(dl,dr)[]&&f\ar@(dr,ur)[]\\
&&g\ar@/_5pc/[ruu]\ar@/^3pc/[uuul]&
}
\]
\[\G_{red}\]
\[
\xymatrix{
\underset{\{a,d,g\}}{CCF(a,\G)}\ar@(ul,ur)[]&&{\underset{\{b,c,e\}}{CCF(b,\G})}\ar@(ul,ur)[]\\
&{\underset{\{f\}}{CCF(f,\G)}}\ar@{{<}-}[ru]\ar@(lu,ru)[]&
}
\]
Proposition
Un graphe orienté est connexe si et seulement si son graphe réduit est connexe.
Démonstration
Exercice.
