Ataraxy

\( %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Mes commandes %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newcommand{\multirows}[3]{\multirow{#1}{#2}{$#3$}}%pour rester en mode math \renewcommand{\arraystretch}{1.3}%pour augmenter la taille des case \newcommand{\point}[1]{\marginnote{\small\vspace*{-1em} #1}}%pour indiquer les points ou le temps \newcommand{\dpl}[1]{\displaystyle{#1}}%megamode \newcommand{\A}{\mathscr{A}} \newcommand{\LN}{\mathscr{N}} \newcommand{\LL}{\mathscr{L}} \newcommand{\K}{\mathbb{K}} \newcommand{\N}{\mathbb{N}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\R}{\mathbb{R}} \newcommand{\C}{\mathbb{C}} \newcommand{\M}{\mathcal{M}} \newcommand{\D}{\mathbb{D}} \newcommand{\E}{\mathcal{E}} \renewcommand{\P}{\mathcal{P}} \newcommand{\G}{\mathcal{G}} \newcommand{\Kk}{\mathcal{K}} \newcommand{\Cc}{\mathcal{C}} \newcommand{\Zz}{\mathcal{Z}} \newcommand{\Ss}{\mathcal{S}} \newcommand{\B}{\mathbb{B}} \newcommand{\inde}{\bot\!\!\!\bot} \newcommand{\Proba}{\mathbb{P}} \newcommand{\Esp}[1]{\dpl{\mathbb{E}\left(#1\right)}} \newcommand{\Var}[1]{\dpl{\mathbb{V}\left(#1\right)}} \newcommand{\Cov}[1]{\dpl{Cov\left(#1\right)}} \newcommand{\base}{\mathcal{B}} \newcommand{\Som}{\textbf{Som}} \newcommand{\Chain}{\textbf{Chain}} \newcommand{\Ar}{\textbf{Ar}} \newcommand{\Arc}{\textbf{Arc}} \newcommand{\Min}{\text{Min}} \newcommand{\Max}{\text{Max}} \newcommand{\Ker}{\text{Ker}} \renewcommand{\Im}{\text{Im}} \newcommand{\Sup}{\text{Sup}} \newcommand{\Inf}{\text{Inf}} \renewcommand{\det}{\texttt{det}} \newcommand{\GL}{\text{GL}} \newcommand{\crossmark}{\text{\ding{55}}} \renewcommand{\checkmark}{\text{\ding{51}}} \newcommand{\Card}{\sharp} \newcommand{\Surligne}[2]{\text{\colorbox{#1}{ #2 }}} \newcommand{\SurligneMM}[2]{\text{\colorbox{#1}{ #2 }}} \newcommand{\norm}[1]{\left\lVert#1\right\rVert} \renewcommand{\lim}[1]{\underset{#1}{lim}\,} \newcommand{\nonor}[1]{\left|#1\right|} \newcommand{\Un}{1\!\!1} \newcommand{\sepon}{\setlength{\columnseprule}{0.5pt}} \newcommand{\sepoff}{\setlength{\columnseprule}{0pt}} \newcommand{\flux}{Flux} \newcommand{\Cpp}{\texttt{C++\ }} \newcommand{\Python}{\texttt{Python\ }} %\newcommand{\comb}[2]{\begin{pmatrix} #1\\ #2\end{pmatrix}} \newcommand{\comb}[2]{C_{#1}^{#2}} \newcommand{\arrang}[2]{A_{#1}^{#2}} \newcommand{\supp}[1]{Supp\left(#1\right)} \newcommand{\BB}{\mathcal{B}} \newcommand{\arc}[1]{\overset{\rotatebox{90}{)}}{#1}} \newcommand{\modpi}{\equiv_{2\pi}} \renewcommand{\Re}{Re} \renewcommand{\Im}{Im} \renewcommand{\bar}[1]{\overline{#1}} \newcommand{\mat}{\mathcal{M}} \newcommand{\und}[1]{{\mathbf{\color{red}\underline{#1}}}} \newcommand{\rdots}{\text{\reflectbox{$\ddots$}}} \newcommand{\Compa}{Compa} \newcommand{\dint}{\dpl{\int}} \newcommand{\intEFF}[2]{\left[\!\left[#1 ; #2\right]\!\right]} \newcommand{\intEFO}[2]{\left[\!\left[#1 ; #2\right[\!\right[} \newcommand{\intEOF}[2]{\left]\!\left]#1 ; #2\right]\!\right]} \newcommand{\intEOO}[2]{\left]\!\left]#1 ; #2\right[\!\right[} \newcommand{\ou}{\vee} \newcommand{\et}{\wedge} \newcommand{\non}{\neg} \newcommand{\implique}{\Rightarrow} \newcommand{\equivalent}{\Leftrightarrow} \newcommand{\Ab}{\overline{A}} \newcommand{\Bb}{\overline{B}} \newcommand{\Cb}{\overline{C}} \newcommand{\Cl}{\texttt{Cl}} \newcommand{\ab}{\overline{a}} \newcommand{\bb}{\overline{b}} \newcommand{\cb}{\overline{c}} \newcommand{\Rel}{\mathcal{R}} \newcommand{\superepsilon}{\varepsilon\!\!\varepsilon} \newcommand{\supere}{e\!\!e} \makeatletter \newenvironment{console}{\noindent\color{white}\begin{lrbox}{\@tempboxa}\begin{minipage}{\columnwidth} \ttfamily \bfseries\vspace*{0.5cm}} {\vspace*{0.5cm}\end{minipage}\end{lrbox}\colorbox{black}{\usebox{\@tempboxa}} } \makeatother \def\ie{\textit{i.e. }} \def\cf{\textit{c.f. }} \def\vide{ { $ {\text{ }} $ } } %Commande pour les vecteurs \newcommand{\grad}{\overrightarrow{Grad}} \newcommand{\Vv}{\overrightarrow{v}} \newcommand{\Vu}{\overrightarrow{u}} \newcommand{\Vw}{\overrightarrow{w}} \newcommand{\Vup}{\overrightarrow{u'}} \newcommand{\Zero}{\overrightarrow{0}} \newcommand{\Vx}{\overrightarrow{x}} \newcommand{\Vy}{\overrightarrow{y}} \newcommand{\Vz}{\overrightarrow{z}} \newcommand{\Vt}{\overrightarrow{t}} \newcommand{\Va}{\overrightarrow{a}} \newcommand{\Vb}{\overrightarrow{b}} \newcommand{\Vc}{\overrightarrow{c}} \newcommand{\Vd}{\overrightarrow{d}} \newcommand{\Ve}[1]{\overrightarrow{e_{#1}}} \newcommand{\Vf}[1]{\overrightarrow{f_{#1}}} \newcommand{\Vn}{\overrightarrow{0}} \newcommand{\Mat}{Mat} \newcommand{\Pass}{Pass} \newcommand{\mkF}{\mathfrak{F}} \renewcommand{\sp}{Sp} \newcommand{\Co}{Co} \newcommand{\vect}[1]{\texttt{Vect}\dpl{\left( #1\right)}} \newcommand{\prodscal}[2]{\dpl{\left\langle #1\left|\vphantom{#1 #2}\right. #2\right\rangle}} \newcommand{\trans}[1]{{\vphantom{#1}}^{t}{#1}} \newcommand{\ortho}[1]{{#1}^{\bot}} \newcommand{\oplusbot}{\overset{\bot}{\oplus}} \SelectTips{cm}{12}%Change le bout des flèches dans un xymatrix \newcommand{\pourDES}[8]{ \begin{itemize} \item Pour la ligne : le premier et dernier caractère forment $#1#2$ soit $#4$ en base 10. \item Pour la colonne : les autres caractères du bloc forment $#3$ soit $#5$ en base 10. \item A l'intersection de la ligne $#4+1$ et de la colonne $#5+1$ de $S_{#8}$ se trouve l'entier $#6$ qui, codé sur $4$ bits, est \textbf{\texttt{$#7$}}. \end{itemize} } \)

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\}\]