Descendants et ascendants
Définition
Soit \( \G\) un graphe. Pour tout \( n\in \N_{{>}0}\) et tout \( x\in \Som(\G)\) on définit
\[\Gamma^{+n}(x,\G)=\left\{y\in \Som(\G)\Big|\exists \alpha\in \Chain_n(\G), \, or(\alpha)=x\wedge ab(\alpha)=y\right\}\]
\[\Gamma^{-n}(x,\G)=\left\{y\in \Som(\G)\Big|\exists \alpha\in \Chain_n(\G), \, or(\alpha)=y\wedge ab(\alpha)=x\right\}\]
On conviens que \( \Gamma^0(x,\G)=\{x\}\) .
On pose
\[\Gamma^+(x,\G)=\bigcup_{n\in \N}\Gamma^{+n}(x,\G),\qquad
\Gamma^-(x,\G)=\bigcup_{n\in \N}\Gamma^{-n}(x,\G)\]
Les éléments de \( \Gamma^{+n}(x,\G)\) correspondent aux sommets du graphe qui sont atteint par des chemins de longueur \( n\) d'origine \( x\) .
Les éléments de \( \Gamma^{-n}(x,\G)\) correspondent quand à eux aux sommets du graphe qui atteignent \( x\) par des chemins de longueur \( n\) .
Par exemple :
\[
\xymatrix@C=0.5cm@R=1.5cm{
&&a\ar@*{[red]}[lld]\ar@*{[red]}[rdd]&&\\
e\ar@*{[red]}[rrrr]&&&&{\color{red}{\boxed{b}}}\ar@(rd,ru)[]\ar[llu]\\
&{\color{red}{\boxed{d}}}\ar[ruu]\ar@/^1pc/[rr]&&c\ar@*{[red]}@/^1pc/[ll]&
}
\]
\[\color{red}{
\Gamma^{+2}(a,\G)=\{b,d\}
}
\]
\[
\xymatrix@C=0.5cm@R=1.5cm{
&&a\ar[lld]\ar[rdd]&&\\
{\color{red}{\boxed{e}}}\ar@*{[red]}[rrrr]&&&&{\color{red}{\boxed{b}}}\ar@*{[red]}@(rd,ru)[]\ar@*{[red]}[llu]\\
&d\ar@*{[red]}[ruu]\ar@/^1pc/[rr]&&{\color{red}{\boxed{c}}}\ar@*{[red]}@/^1pc/[ll]&
}
\]
\[\color{red}{
\Gamma^{-2}(a,\G)=\{b,c,e\}
}
\]
\[
\xymatrix@C=0.5cm@R=1.5cm{
&&{\color{red}{\boxed{a}}}\ar@{-}@*{[red]}[lld]\ar@{-}@*{[red]}[rdd]&&\\
{\color{red}{\boxed{e}}}\ar@{-}@*{[red]}[rrrr]&&&&{\color{red}{\boxed{b}}}\ar@{-}@*{[red]}[llu]\\
&{\color{red}{\boxed{d}}}\ar@{-}@*{[red]}[ruu]\ar@{-}@*{[red]}[rr]&&{\color{red}{\boxed{c}}}&
}
\]
\[\color{red}{
\Gamma^{-2}(a,\G)=\Gamma^{+2}(a,\G)=\{a,b,c,d,e\}
}
\]
Définition
Soit \( x\) un sommet d'un graphe \( \G\) .
- \( (i)\)
- Les éléments de \( \Gamma^{+1}(x,\G)\) sont appelés les successeurs de \( x\) .
- \( (ii)\)
- Les éléments de \( \Gamma^{-1}(x,\G)\) sont appelés les prédécesseurs de \( x\) .
- \( (iii)\)
- Les éléments de \( \Gamma^{+}(x,\G)\) sont appelés les descendants de \( x\) .
- \( (iv)\)
- Les éléments de \( \Gamma^{-}(x,\G)\) sont appelés les ascendants de \( x\) .
Lorsque le graphe est non orienté les notions de prédécesseurs et successeurs coïncident.
Proposition
Soit \( \G\) un graphe non orienté.
\[\forall n\in \N, \forall x\in \Som(\G),\qquad \Gamma^{+n}(x,\G)=\Gamma^{-n}(x,\G)\]
Démonstration
Triviale.
Définition
Soit \( \G\) un graphe non orienté. Les successeurs (et prédécesseurs) sont appelés les voisins ou sommets adjacents de \( x\) .
Proposition
Soient \( n\in \N\) et \( x\) un sommet d'un graphe \( \G\) .
\[\Gamma^{\pm (n+1)}(x,\G)=\left\{y\in \Som(\G)\Big|\exists z\in \Gamma^{\pm 1}(x,\G), y\in \Gamma^{\pm n}(z,\G)\right\}\]
Démonstration
Cela viens du fait que toute chaine de longueur \( n+1\) se décompose comme une chaine de longueur \( 1\) concaténée avec une chaine de longueur \( n\) .
De cette proposition on en déduit un algorithme pour déterminer les ensembles \( \Gamma^{\pm n}(x,n)\) .
§
Algorithme du marquage.
1. S = {x}
2. Pour une variable entière i allant de \( 1\) à \( n\)
On considère S\( {}_{\texttt{temp}}\) tous les
* successeurs (si l'on cherche à déterminer \( \Gamma^{+n}(x,\G)\) )
* prédécesseurs (si l'on cherche à déterminer \( \Gamma^{-n}(x,\G)\) )
des sommets de \( S\) .
S = S\( {}_{\texttt{temp}}\) .
Fin pour
3. \( \Gamma^{\pm n}(x,\G)=\) S.
Reprenons l'exemple précédent et déterminons \( \Gamma^{-3}(a,\G)\) avec l'algorithme.
On représente les différents états de la variable
S dans un tableau.
\[
\xymatrix@R=0.1cm{
&&a\ar[lld]\ar[rdd]&&\\
e\ar[rrrr]&&&&b\ar@(rd,ru)[]\ar[llu]\\
&d\ar[ruu]\ar@/^1pc/[rr]&&c\ar@/^1pc/[ll]&
}
\]
\[
\begin{array}{*{6}{|c}|}
\hline
&a&b&c&d&e\\\hline
\Gamma^0&&&&&\\\hline
\Gamma^{-1}&&&&&\\\hline
\Gamma^{-2}&&&&&\\\hline
\Gamma^{-3}&&&&&\\\hline
\end{array}
\]
La condition initial est
S\( =a\) . On marque à la ligne du \( \Gamma^0\) le sommet \( a\) :
\[
\begin{array}{*{6}{|c}|}
\hline
&a&b&c&d&e\\\hline
\Gamma^0&\times&&&&\\\hline
\Gamma^{-1}&&&&&\\\hline
\Gamma^{-2}&&&&&\\\hline
\Gamma^{-3}&&&&&\\\hline
\end{array}
\]
Pour la ligne suivante, on va marquer tous les prédécesseurs de \( a\) .
\[
\begin{array}{*{6}{|c}|}
\hline
&a&b&c&d&e\\\hline
\Gamma^0&\times&&&&\\\hline
\Gamma^{-1}&&\times&&\times&\\\hline
\Gamma^{-2}&&&&&\\\hline
\Gamma^{-3}&&&&&\\\hline
\end{array}
\]
Pour la ligne suivante, on va marquer tous les prédécesseurs de \( b\) et \( d\) .
\[
\begin{array}{*{6}{|c}|}
\hline
&a&b&c&d&e\\\hline
\Gamma^0&\times&&&&\\\hline
\Gamma^{-1}&&\times&&\times&\\\hline
\Gamma^{-2}&&\times&\times&&\times\\\hline
\Gamma^{-3}&&&&&\\\hline
\end{array}
\]
Pour finir on marque les prédécesseurs de \( b\) , \( c\) et \( e\)
\[
\begin{array}{*{6}{|c}|}
\hline
&a&b&c&d&e\\\hline
\Gamma^0&\times&&&&\\\hline
\Gamma^{-1}&&\times&&\times&\\\hline
\Gamma^{-2}&&\times&\times&&\times\\\hline
\Gamma^{-3}&\times&\times&&\times&\times\\\hline
\end{array}
\]
Finalement \( \Gamma^{-3}(a,\G)=\{a,b,d,e\}\) .
Pour déterminer \( \Gamma^{\pm}(x,\G)\) on améliore l'algorithme précédent.
§
Algorithme du marquage \( +\) .
1. On marque le sommet x
2. Tant qu'il existe des sommets marqués mais non sélectionnés
On sélectionne un sommet marqué y et non selectionné.
On marque tous les
* successeurs (si l'on cherche à déterminer \( \Gamma^{+}(x,\G)\) )
* prédécesseurs (si l'on cherche à déterminer \( \Gamma^{-}(x,\G)\) )
de \( y\) .
Fin tant que
3. \( \Gamma^{\pm}(x,\G)=\) les sommets marqués.
Calculons \( \Gamma^+(a,\G)\) pour le graphe non orienté \( \G\) suivant
\[\xymatrix@R=0.97cm@C=2cm{
&a\ar@{-}[dl]\ar@{-}[dd]\ar@{-}[dr]&b\ar@{-}@/^1pc/[dd]\ar@{-}[r]&c\ar@{-}[rd]&\\
j&&l\ar@{-}[r]&n&d\ar@{-}[dl]\\
i&k\ar@{-}[ur]&m&o&e\ar@{-}[dl]\\
&h\ar@{-}[ul]\ar@{-}[ur]&g\ar@{-}@/^1pc/[lluu]\ar@{-}[uur]&f\ar@{-}[ul]&
}\]
La première étape de l'algorithme reviens à marquer \( a\) :
\[
\begin{array}{*{16}{|c}|}
\hline
\Som(\G)&a&b&c&d&e&f&g&h&i&j&k&l&m&n&o\\\hline
\text{Marquage}&\times&&&&&&&&&&&&&&\\\hline
\end{array}
\]
On sélectionne le sommet \( a\) et on marque tous les sommets qui lui sont adjacents.
\[
\begin{array}{*{16}{|c}|}
\hline
\Som(\G)&\underline{a}&b&c&d&e&f&g&h&i&j&k&l&m&n&o\\\hline
\text{Marquage}&\times&&&&&&&&&\times&\times&\times&&&\\\hline
\end{array}
\]
on sélectionne le sommet \( j\) et on marque ses sommets adjacents. Et ainsi de proche en proche.
\[
\begin{array}{*{16}{|c}|}
\hline
\Som(\G)&\underline{a}&b&c&d&e&f&g&h&i&\underline{j}&k&l&m&n&o\\\hline
\text{Marquage}&\times&&&&&&\times&&&\times&\times&\times&&&\\\hline
\end{array}
\]
\[
\begin{array}{*{16}{|c}|}
\hline
\Som(\G)&\underline{a}&b&c&d&e&f&\underline{g}&h&i&\underline{j}&k&l&m&n&o\\\hline
\text{Marquage}&\times&&&&&&\times&&&\times&\times&\times&&\times&\\\hline
\end{array}
\]
\[
\begin{array}{*{16}{|c}|}
\hline
\Som(\G)&\underline{a}&b&c&d&e&f&\underline{g}&h&i&\underline{j}&\underline{k}&l&m&n&o\\\hline
\text{Marquage}&\times&&&&&&\times&&&\times&\times&\times&&\times&\\\hline
\end{array}
\]
\[
\begin{array}{*{16}{|c}|}
\hline
\Som(\G)&\underline{a}&b&c&d&e&f&\underline{g}&h&i&\underline{j}&\underline{k}&\underline{l}&m&n&o\\\hline
\text{Marquage}&\times&&&&&&\times&&&\times&\times&\times&&\times&\\\hline
\end{array}
\]
\[
\begin{array}{*{16}{|c}|}
\hline
\Som(\G)&\underline{a}&b&c&d&e&f&\underline{g}&h&i&\underline{j}&\underline{k}&\underline{l}&m&\underline{n}&o\\\hline
\text{Marquage}&\times&&&&&&\times&&&\times&\times&\times&&\times&\\\hline
\end{array}
\]
Le processus s'arrête ici puisque tous les sommets marqués sont sélectionnés ; finalement
\[\Gamma^+(a,\G)=\{a,g,j,k,l,n\}\]