Chaines
Définition
Soient \( \G\) un graphe non orienté (resp. orienté) et \( n\in \N\) . Une chaine ou un chemin de longueur \( n\) sur \( \G\) est un mot \( a=a_0\dots a_n\) du langage \( \Chain_n(\G)\subset (\Som(\G))^{n+1}\) sur l'alphabet \( \Som(\G)\) défini par la règle :
\begin{eqnarray*}
&&\forall 0\leqslant k {<} n, \qquad \{a_i,a_{i+1}\}\in \Ar(\G)\\
\text{(resp.}&&\forall 0\leqslant k {<} n, \qquad (a_i,a_{i+1})\in \Arc(\G)\text{)}
\end{eqnarray*}
La première lettre de la chaine est appelé l'origine et la dernière l'aboutissement.
On note \( \norm{a}_\G=n\) et \( \Chain(\G)=\dpl{\bigcup_{n\in \N}\Chain_n(\G)}\) .
Remarque
Dans la pratique le mot chaine est réservé au graphe non orienté. Dans le cas orienté, on parle plus de chemin. Dans ce cours, pour simplifier les notations, nous ne ferons pas la distinction.
Remarque
On prendra garde : malgré le fait qu'une arête est non orienté c'est à dire que \( \{a,b\}=\{b,a\}\) , il y a une différence entre la chaine \( ab\) et la chaine \( ba\) , qui sont par définition des éléments du produit cartésien \( \Som(\G)\times\Som(\G)\) .
\[
\xymatrix@C=2cm@R=2cm{
a\ar@{-}[d]\ar@{-}[dr]\ar@{-}[drr]\ar@{-}@/^2pc/[rr]&b\ar@{-}[d]\ar@{-}[r]&c\ar@{-}[dll]\\
f&e&d
}
\]
Par exemple \( acbead\) est une chaine de ce graphe de longueur 5 (et pas 6 ; on compte en fait le nombre d'arête) et \( acbeda\) n'est pas une chaine car \( \{e,d\}\) n'est pas une arête.
Proposition
Tout sous-mot d'une chaine est une chaine.
Démonstration
Triviale.
Définition
Une chaine est dite élémentaire si elle ne passe pas deux fois par le même sommet.
Dans l'exemple précédent, \( acbead\) n'est pas une chaine élémentaire puisqu'elle passe deux fois par le somment \( a\) .
Proposition
Soit \( \G\) un graphe.
- \( (i)\)
- Si il existe une chaine entre deux sommets du graphe alors il existe une chaine élémentaire entre ces deux sommets.
- \( (ii)\)
- Soit \( \alpha\) une chaine élémentaire de \( \G\) ,
\[\norm{\alpha}_\G\leqslant \Card(\Som(\G))-1\]
Démonstration
Le second point est évident : si la longueur de la chaine est strictement supérieur à \( \Card(\Som(\G))-1\) c'est à dire supérieur ou égale à \( \Card(\Som(\G))\) alors la chaine passe forcement deux fois
par le même sommet et ne peut donc pas être élémentaire.
Pour le premier point il suffit d'observer qu'une si une chaine est non élémentaire alors elle passe deux fois par le même sommet et donc elle "boucle". Si on enlève cette boucle on obtient une nouvelle chaine avec la même origine
et le même aboutissement mais de longueur strictement inférieur. Si la nouvelle chaine n'est pas élémentaire on recommence le processus. Ces itérations prennent nécessairement fin puisque les longueurs décroissent strictement.
La concaténation des chaines se réalise comme celle des mots en "fusionnant" aboutissement et origine. Plus précisément :
Définition
Soit \( \G\) un graphe. On définit
\[
or : \Chain(\G)\longrightarrow\Som(\G)\qquad\qquad
ab : \Chain(\G)\longrightarrow\Som(\G)
\]
les fonctions qui associent respectivement l'origine et l'aboutissement d'une chaine.
Par exemple \( ab(abcetgbed)=d\) et \( or(abcetgbed)=a\) .
Définition
Soient \( \alpha\) et \( \beta\) deux chaines sur un graphe \( \G\) de longueur respectives \( n\) et \( m\) .
On dira que \( \alpha\) et \( \beta\) sont concatenables si \( ab(\alpha)=or(\beta)\) . Dans ce cas on définit la concaténation de \( \alpha\) et de \( \beta\) par la règle :
\[\forall 1\leqslant k\leqslant n+m-1,\qquad (\alpha\beta)_k=\left\{
\begin{array}{rl}
\alpha_k&\text{si } k{<} n\text{,}\\
\beta_{k-n}& \text{sinon.}
\end{array}
\right.\]
On prendra garde : l'inégalité est stricte ! Par exemple avec le graphe précédent : \( acbe\circ eafc=acbeafc\) (on ne réécrit pas deux fois le sommet \( e\) ).
Proposition
Soient \( \G\) un graphe non orienté, \( \alpha\) , \( \beta\) et \( \gamma\) des chaines de \( \G\) tel que \( \alpha\) soit concaténable à \( \beta\) lui même concaténable à \( \gamma\) . Alors \( \alpha\beta\) est concaténable a \( \gamma\)
et \( \alpha\) est concaténable à \( \beta\gamma\) . De plus
- (Associativité)
- \( (\alpha\beta)\gamma=\alpha(\beta\gamma)\) .
- (Elément neutre)
- \( \alpha\varepsilon=\varepsilon\alpha=\alpha\) .
- (Longueur)
- \( \norm{\alpha\beta}_\G=\norm{\alpha}_\G+\norm{\beta}_\G\) .
Démonstration
Le raisonnement est le même que celui sur les mots.
Théorème
Soient \( n\in \N\) , \( \G\) un graphe et \( M\) sa matrice booléenne.
\[\left(\exists \alpha\in \Chain_n(\G),\quad or(\alpha)=a_i\;\wedge\; ab(\alpha)=a_j\right) \Longleftrightarrow
M_{i,j}^n=1\]
Autrement dit : il existe une chaine de longueur \( n\) entre deux sommets \( a_i\) et \( a_j\) si et seulement si \( M_{i,j}^n=1\) .
Démonstration
Raisonnons par récurrence sur \( n\in \N\) , le cas initial étant triviale. Supposons que pour un \( n\) quelconque fixé la propriété du théorème soit satisfaite et vérifions la au rang \( n+1\) .
On commence par observer que \( M^{n+1}=M\times M^{n}\) , ce produit de matrice se réalisant avec des coefficients dans l'algèbre de Boole \( \B\) . En particulier, par définition du produit matricielle et par définition des règles de calcul dans \( \B\) ,
\begin{eqnarray*}
M_{i,j}^{n+1}=\sum_{k=1}^nM_{i,k}\times M_{k,j}^n=1
&\Longleftrightarrow& \exists k_0,\quad M_{i,k_0}\times M_{k_0,j}^n=1\\
&\Longleftrightarrow& \exists k_0,\quad M_{i,k_0}=1 \wedge M_{k_0,j}^n=1
\end{eqnarray*}
Par définition de la matrice booléenne \( M_{i,k_0}=1\) si et seulement si il existe un arc \( (a_i,a_{k_0})\) (ou une arête \( \{a_i,a_{k_0}\}\) dans le cas non orienté) et par hypothèse de récurrence \( M_{k_0,j}^n=1\) si et seulement si il existe une chaine de longueur \( n\) d'origine \( a_{k_0}\) et d'aboutissement \( a_j\) . La concaténation permet d'achever cette récurrence.
