Graphes, puissances et suites matricielles · Terminale maths expertes

Avant de commencer5 questions pour vérifier tes bases

1. Le produit d’une matrice 2 × 3 par une matrice 3 × 2 a pour format…

2 × 23 × 3Il est impossible

2. Le produit matriciel est-il toujours commutatif ?

OuiNonOui pour toutes les matrices carrées

3. A⁰, pour une matrice carrée A, est…

la matrice nullela matrice identitéA

4. Si u₀ = 2 et uₙ₊₁ = 3uₙ, alors uₙ vaut…

2 + 3n2 × 3ⁿ3 × 2ⁿ

5. Une transformation X ↦ AX envoie le vecteur nul…

sur le vecteur nulsur n’importe quel vecteursur le premier vecteur colonne de A

Pourquoi ce chapitre ?

Le problème fondamental : compter les parcours d'un réseau

Un plan de transport montre les liaisons disponibles. Tu voudrais compter les parcours qui relient deux stations en exactement cinq étapes, en autorisant les retours. Une énumération à la main devient vite longue. Les matrices vont organiser les possibilités d'une étape, puis composer ces choix.

Prérequis. Produit matriciel, puissances, inverse, suites géométriques et démonstration par récurrence. Les termes propres aux graphes sont définis avant utilisation.

Le socle comprend graphes, matrices, dénombrement de chemins et suites matricielles. Les parcours eulériens et le problème sur Fibonacci sont des prolongements guidés. Une réduction $A=PDP^{-1}$ sera vérifiée directement, sans supposer un cours de diagonalisation.

L'idée avant la formule

Un sommet intermédiaire organise tous les cas

Pour aller de A à C en deux étapes, choisis d'abord le sommet intermédiaire B. Le nombre de possibilités via B est « nombre de liaisons de A à B » multiplié par « nombre de liaisons de B à C ». Additionne ensuite sur tous les intermédiaires. Tu reconnais le produit ligne-colonne.

Ce qu'on compte doit être annoncé

Deux étapes signifient deux arêtes parcourues, même si tu reviens à ton point de départ. Les puissances compteront ici des parcours avec répétitions possibles, pas nécessairement des chemins sans retour ni des trajets les plus courts. La convention sera précisée avant chaque utilisation.

Déplacer l'origine simplifie une évolution affine

Une suite réelle $u_{n+1}=au_n+b$ se simplifie en soustrayant une valeur fixe. L'idée reste vraie pour une colonne : si $$L=AL+C$$ , alors $U_{n+1}-L=A(U_n-L)$ . La quantité mesurée par rapport à L suit une récurrence homogène. Le chapitre construira cette formule et les puissances dont elle dépend.

Le cours formel

Graphes : objets et vocabulaire

Le degré d'un sommet est le nombre d'arêtes qui lui sont incidentes. Le graphe complet $$K_n$$ relie chaque paire de sommets distincts ; chaque degré vaut n-1, et son nombre d'arêtes vaut $$n(n-1)/2$$ .

Démonstration · Compter deux fois

Choisissons une arête reliant $$A$$ à $$B$$ . Elle ajoute 1 au degré de $$A$$ , et 1 au degré de $$B$$ : sa contribution totale est 2. Chaque arête possède exactement deux extrémités dans un graphe simple non orienté. Additionner tous les degrés compte donc chaque arête deux fois, d'où $\sum\deg(S)=2\times\text{nombre d'arêtes}$ .

Pour la conséquence sur la parité, écrivons chaque degré pair sous la forme $$2k$$ , et chaque degré impair sous la forme $2\ell+1$ . Si $$r$$ sommets ont un degré impair, leur somme totale s'écrit $$2K+r$$ pour un entier $$K$$ . Le premier résultat dit que cette somme est paire. Donc $$r$$ est pair. Le raisonnement ne dit pas que tous les degrés sont pairs : il dit que les degrés impairs viennent en nombre pair.

Schéma : Graphes : objets et vocabulaire

Le graphe représenté a quatre sommets et cinq arêtes. Les degrés, dans l'ordre A,B,C,D, valent 2,3,2,3 ; leur somme 10 correspond bien à deux fois cinq arêtes.

À toi d’essayer

Compter les extrémités sans dessiner tout le graphe

Un graphe simple a pour degrés 3,3,2,2. Combien possède-t-il d’arêtes ? Les degrés 3,2,2,2 seraient-ils possibles ?

Pour démarrer. Additionne les degrés avant de diviser par le nombre d’extrémités d’une arête.

Tu peux chercher, prendre un indice ou lire l’explication, à ton rythme.

Indice 1 · Une piste

La somme des degrés compte chaque arête deux fois.

Indice 2 · Un pas de plus

Le deuxième total est impair.

Voir l’explication

Pour les degrés $$3,3,2,2$$ , la somme vaut 10. Chaque arête est comptée deux fois, donc le nombre d'arêtes est $$10/2=5$$ . Pour la seconde liste, la somme est $$3+2+2+2=9$$ , impair. Elle ne peut pas être le double d'un nombre entier d'arêtes : cette liste est impossible. Une somme paire est nécessaire, mais ne suffit pas pour n'importe quelle liste : par exemple un degré ne peut pas dépasser le nombre des autres sommets dans un graphe simple.

Chaînes, connexité et orientation

Dans un graphe orienté, les liens sont des arcs portant un sens. Un chemin respecte ce sens. Un graphe peut aussi être pondéré : chaque lien porte un nombre (distance, coût ou probabilité selon le modèle).

Un parcours de longueur 0 reste sur son sommet initial. Dans un graphe simple, il n'y a pas de boucle ; une marche de longueur 2 peut pourtant revenir au départ en parcourant la même arête dans les deux sens.

À toi d’essayer

Une flèche change l’accessibilité

Un graphe orienté possède seulement les arcs A vers B et B vers C. Peut-on aller de A à C ? Et de C à A ?

Pour démarrer. Écris les déplacements autorisés dans le sens des flèches, puis examine ceux qui partent de $$C$$ .

Tu peux chercher, prendre un indice ou lire l’explication, à ton rythme.

Indice 1 · Une piste

Le sens de parcours doit suivre chaque flèche.

Indice 2 · Un pas de plus

Il n’existe aucun arc partant de C.

Voir l’explication

On dispose de l'arc $A\to B$ puis de l'arc $B\to C$ , donc $$A,B,C$$ est une marche orientée de longueur 2. Pour repartir de $$C$$ , il faudrait un arc dont $$C$$ est le départ. Il n'y en a aucun, donc on ne peut pas aller de $$C$$ à $$A$$ . Le segment dessiné entre $$B$$ et $$C$$ n'autorise pas automatiquement le retour $C\to B$ : le sens fait partie des données. Le trajet aller n'implique donc pas l'existence du trajet retour.

Matrice d'adjacence

Pour un graphe avec plusieurs arcs entre une paire de sommets, le coefficient peut compter les arcs. Pour un graphe pondéré, remplacer 1 par un poids change le sens du calcul : une puissance additionne des produits de poids ; elle ne donne pas automatiquement un nombre de trajets.

À toi d’essayer

Trois sommets en ligne

Écris la matrice du graphe A–B–C dans l'ordre A,B,C.

Pour démarrer. Construis une ligne par sommet, avec une colonne pour chaque arrivée possible.

Tu peux chercher, prendre un indice ou lire l’explication, à ton rythme.

Indice 1 · Une piste

Chaque ligne décrit les voisins d'un sommet.

Indice 2 · Un pas de plus

A et C ont un seul voisin ; B en a deux.

Voir l’explication

Dans l'ordre $$A,B,C$$ , depuis $$A$$ seul $$B$$ est voisin, donc la ligne est $$(0,1,0)$$ . Depuis $$B$$ , les voisins sont $$A,C$$ , donc $$(1,0,1)$$ . Depuis $$C$$ , seul $$B$$ est voisin, donc $$(0,1,0)$$ . Ainsi $M=\begin{pmatrix}0&1&0\\1&0&1\\0&1&0\end{pmatrix}$ . Les deux cases d'une même arête sont symétriques car le graphe est non orienté. Les zéros diagonaux correspondent à l'absence de boucle. Les sommes $$1,2,1$$ sont bien les degrés.

À toi d’essayer

Reconstruire le graphe à partir du tableau

Interprète $A=\begin{pmatrix}0&1&1\\1&0&0\\1&0&0\end{pmatrix}$ dans l’ordre U,V,W comme graphe non orienté simple.

Pour démarrer. Lis les cases $$(U,V)$$ , $$(U,W)$$ et $$(V,W)$$ , une seule fois par arête.

Tu peux chercher, prendre un indice ou lire l’explication, à ton rythme.

Indice 1 · Une piste

La matrice est symétrique et sa diagonale est nulle.

Indice 2 · Un pas de plus

Lis seulement les cases au-dessus de la diagonale pour ne pas compter chaque arête deux fois.

Voir l’explication

La case $$(U,V)$$ vaut 1, donc il y a l'arête $$UV$$ . La case $$(U,W)$$ vaut 1, donc il y a $$UW$$ . La case $$(V,W)$$ vaut 0, donc aucune arête $$VW$$ . Les cases symétriques ne sont pas de nouvelles arêtes : elles décrivent les mêmes liaisons dans l'autre sens. Les degrés sont les sommes des lignes, soit $$2,1,1$$ . Leur somme vaut 4, donnant $$4/2=2$$ arêtes, en accord avec la liste. La diagonale nulle indique aucune boucle.

Compter les chemins par des puissances

Démonstration · Preuve par récurrence

Ce que nous comptons. Une marche peut réutiliser sommets et arêtes. Pour une longueur $$k+1$$ , nous séparons ses $$k$$ premières étapes de sa toute dernière étape.

Initialisation, longueur 0. Sans aucune transition, il existe une marche de $$S_i$$ à lui-même, et aucune vers un autre sommet. La matrice de ces nombres est exactement $$I=M^0$$ : 1 sur la diagonale, 0 ailleurs.

Hypothèse. Supposons que $(M^k)_{i\ell}$ compte les marches de longueur $$k$$ de $$S_i$$ à $S_\ell$ , pour chaque paire de sommets.

Construire une marche de longueur $$k+1$$ . Fixons le sommet $S_\ell$ atteint juste avant la dernière étape. On dispose de $(M^k)_{i\ell}$ choix pour y arriver. Si $m_{\ell j}=0$ , aucune de ces marches ne peut être prolongée vers $$S_j$$ ; si $m_{\ell j}=1$ , chacune a exactement un prolongement. Le nombre correspondant est donc le produit $(M^k)_{i\ell}m_{\ell j}$ . Si plusieurs arcs sont autorisés, ce même produit compte les choix du dernier arc.

Chaque marche a un unique avant-dernier sommet. Les cas obtenus pour des $\ell$ différents ne se chevauchent donc pas, et tous les parcours sont couverts. On additionne leurs nombres : $\sum_\ell(M^k)_{i\ell}m_{\ell j}$ . Par la définition du produit ligne-colonne, c'est $(M^kM)_{ij}=(M^{k+1})_{ij}$ . La propriété est donc transmise du rang $$k$$ au rang $$k+1$$ , puis vraie pour toute longueur par récurrence.

Pour un graphe non orienté à n sommets, il est connexe exactement lorsque chaque paire distincte est reliée par une marche d'au plus n-1 étapes. On peut en effet retirer les boucles d'une marche jusqu'à obtenir un parcours sans sommet répété. Ainsi les coefficients hors diagonale de $I+M+\cdots+M^{n-1}$ permettent de vérifier la connexité.

À toi d’essayer

Décomposer par l’étape intermédiaire

Pour la matrice précédente, calcule $(A^2)_{VW}$ puis interprète-le.

Pour démarrer. Pour chaque intermédiaire $$U,V,W$$ , compte la possibilité d’aller de $$V$$ à cet intermédiaire puis à $$W$$ .

Tu peux chercher, prendre un indice ou lire l’explication, à ton rythme.

Indice 1 · Une piste

Multiplie la ligne V par la colonne W.

Indice 2 · Un pas de plus

Le seul intermédiaire possible est U.

Voir l’explication

La ligne $$V$$ est $$(1,0,0)$$ et la colonne $$W$$ est $$(1,0,0)^T$$ . Leur produit-somme vaut $1\times1+0\times0+0\times0=1$ . Le premier terme compte

\begin{aligned}V &\to U\\[.35em] &\to W,\end{aligned}

les deux autres sont nuls parce qu'il n'existe pas les étapes requises. Il y a donc exactement une marche de longueur 2 de $$V$$ à $$W$$ . La case directe $A_{VW}=0$ indiquait seulement l'absence d'arête en une étape, et n'interdisait pas ce trajet via $$U$$ .

Calculer des puissances sans multiplier n fois

Matrices diagonales et nilpotentes

Pour $D=\operatorname{diag}(a,b,c)$ , $D^n=\operatorname{diag}(a^n,b^n,c^n)$ . Les coefficients hors diagonale restent nuls.

Exemple · Un exemple d'ordre 3

Avec $N=\begin{pmatrix}0&1&0\\0&0&1\\0&0&0\end{pmatrix}$ , le produit $$N^2$$ a seulement la case $$(1,3)$$ égale à $0\times0+1\times1+0\times0=1$ . Toutes les autres sont nulles. Multiplier encore par $$N$$ donne zéro, car la troisième ligne de $$N$$ est nulle : $$N^3=0$$ .

Comme $$I$$ commute avec $$N$$ , le binôme est autorisé. Tous les termes contenant $$N^k$$ avec $k\ge3$ sont nuls. Il reste $I+nN+\binom n2N^2$ , où $\binom n2=n(n-1)/2$ ; pour $$n=0,1$$ , le dernier coefficient est nul.

On peut vérifier la transmission directement : multiplier $$I+nN+[n(n-1)/2]N^2$$ par $$I+N$$ donne $$I+(n+1)N+[n+n(n-1)/2]N^2$$ . Le nouveau coefficient vaut $$n(n+1)/2$$ , celui du rang $$n+1$$ . La matrice finale est $\begin{pmatrix}1&n&n(n-1)/2\\0&1&n\\0&0&1\end{pmatrix}$ .

Une factorisation vérifiée

Si tu as vérifié $A=PDP^{-1}$ , alors $A^n=PD^nP^{-1}$ pour tout n naturel. Les facteurs $P^{-1}P$ s'annulent entre deux copies successives ; au rang 0, $PI P^{-1}=I$ .

Exemple · Deux modes d'évolution

Pour $P=\begin{pmatrix}1&1\\1&-1\end{pmatrix}$ , calculons

P^2=\begin{pmatrix}2&0\\0&2\end{pmatrix}=2I.

Donc $P^{-1}=P/2$ . Pour $A=\begin{pmatrix}2&1\\1&2\end{pmatrix}$ , le produit $AP=\begin{pmatrix}3&1\\3&-1\end{pmatrix}$ . Avec $D=\operatorname{diag}(3,1)$ , $$PD$$ donne exactement cette même matrice. Donc $$AP=PD$$ , puis $A=PDP^{-1}$ en multipliant à droite par $P^{-1}$ .

Au rang 0,

\begin{aligned}PD^0P^{-1} &= PP^{-1}\\[.35em] &= I\\[.35em] &= A^0.\end{aligned}

Si $A^n=PD^nP^{-1}$ , alors

\begin{aligned}A^{n+1} &= PD^nP^{-1}PDP^{-1}\\[.35em] &= PD^{n+1}P^{-1},\end{aligned}

car les facteurs voisins $P^{-1}P$ valent $$I$$ . Ainsi la formule vaut à tout rang.

Comme $D^n=\operatorname{diag}(3^n,1)$ , $PD^n=\begin{pmatrix}3^n&1\\3^n&-1\end{pmatrix}$ . Le produit par $$P/2$$ donne $A^n=\frac12\begin{pmatrix}3^n+1&3^n-1\\3^n-1&3^n+1\end{pmatrix}$ . Chaque coefficient résulte d'une somme de deux produits ; aucune théorie supplémentaire n'a été supposée.

À toi d’essayer

Un carré ne suffit pas pour toutes les puissances

Pour $A=\begin{pmatrix}1&1\\0&1\end{pmatrix}$ , conjecture $$A^n$$ , puis explique l’étape de récurrence.

Pour démarrer. Calcule les quatre cases du produit de la formule supposée par $$A$$ .

Tu peux chercher, prendre un indice ou lire l’explication, à ton rythme.

Indice 1 · Une piste

Les premiers carrés donnent 2 puis 3 en haut à droite.

Indice 2 · Un pas de plus

Multiplie la formule supposée au rang n par A.

Voir l’explication

Les premiers produits donnent 2 puis 3 dans la case supérieure droite, suggérant $A^n=\begin{pmatrix}1&n\\0&1\end{pmatrix}$ . Au rang 0, cela donne l'identité. Supposons la formule au rang $$n$$ . Le produit par $$A$$ donne les cases $1\times1+n\times0=1$ , $1\times1+n\times1=n+1$ , $0\times1+1\times0=0$ , $0\times1+1\times1=1$ . C'est donc la même formule avec $$n+1$$ . La récurrence prouve tous les rangs ; les premiers calculs servaient à deviner, pas à prouver.

Suites de colonnes : cas homogène et affine

Exemple · Deux suites couplées

La première récurrence donne les coefficients $$(2,1)$$ et la seconde $$(1,2)$$ , donc $U_{n+1}=AU_n$ avec $$U_n=(x_n,y_n)^T$$ . Pour $$U_0=(1,0)^T$$ , multiplier $$A^n$$ par cette colonne sélectionne sa première colonne. On obtient $$x_n=(3^n+1)/2$$ et $$y_n=(3^n-1)/2$$ .

Retrouvons les mêmes résultats autrement. Posons $$s_n=x_n+y_n$$ : en additionnant les récurrences,

\begin{aligned}s_{n+1} &= 3x_n+3y_n\\[.35em] &= 3s_n,\end{aligned}

et $$s_0=1$$ , donc $$s_n=3^n$$ . Posons $$d_n=x_n-y_n$$ : soustraire donne

\begin{aligned}d_{n+1} &= x_n-y_n\\[.35em] &= d_n,\end{aligned}

donc $$d_n=1$$ . Enfin $$s_n+d_n=2x_n$$ et $$s_n-d_n=2y_n$$ , ce qui redonne les deux formules. Cette seconde méthode explique ce que représentent les deux puissances scalaires.

Démonstration · Deux méthodes

1. La somme des apports. Au rang 0, $$A^0U_0=U_0$$ et la somme vide vaut zéro, donc la formule est vraie. Supposons-la vraie au rang $$n$$ : $U_n=A^nU_0+\sum_{k=0}^{n-1}A^kC$ . Dans la récurrence,

\begin{aligned}U_{n+1}&=A\left(A^nU_0+\sum_{k=0}^{n-1}A^kC\right)+C\\[.35em]&=A^{n+1}U_0+\sum_{k=0}^{n-1}A^{k+1}C+C\\[.35em]&=A^{n+1}U_0+\sum_{j=1}^{n}A^jC+A^0C\\[.35em]&=A^{n+1}U_0+\sum_{j=0}^{n}A^jC.\end{aligned}

Dans la troisième ligne, nous avons posé $$j=k+1$$ et écrit

\begin{aligned}C &= IC\\[.35em] &= A^0C.\end{aligned}

Les exposants vont maintenant de 0 à $$n$$ : c'est la formule au rang suivant. La récurrence est établie.

2. Retirer un point fixe. Supposons $$L=AL+C$$ . En soustrayant cette égalité de $U_{n+1}=AU_n+C$ , les deux apports $$C$$ s'annulent : $U_{n+1}-L=A(U_n-L)$ . La suite $$V_n=U_n-L$$ vérifie donc $V_{n+1}=AV_n$ . Au rang 0, $$V_0=U_0-L$$ ; par récurrence, $$V_n=A^nV_0$$ . Rajouter $$L$$ donne $$U_n=L+A^n(U_0-L)$$ .

Pour trouver $$L$$ , l'équation équivaut à $$(I-A)L=C$$ . Si $$I-A$$ est inversible, multiplier à gauche par son inverse donne l'unique $L=(I-A)^{-1}C$ . Si cet inverse n'existe pas, on étudie directement le système ; on ne peut pas employer cette dernière formule automatiquement.

À toi d’essayer

Déplacer l'équilibre

Soit $U_{n+1}=\frac12U_n+(2,1)^T$ . Trouve L et exprime $$U_n-L$$ .

Pour démarrer. Isole $$L/2$$ dans l’équation du point fixe, puis soustrais cette équation à la récurrence.

Tu peux chercher, prendre un indice ou lire l’explication, à ton rythme.

Indice 1 · Une piste

Résous $L=\frac12 L+(2,1)^T$ .

Indice 2 · Un pas de plus

Soustrais ensuite cette relation à la récurrence.

Voir l’explication

$$L=L/2+(2,1)^T$$ équivaut à $$L/2=(2,1)^T$$ , donc $$L=(4,2)^T$$ . Soustraire cette égalité à la récurrence donne $U_{n+1}-L=(1/2)(U_n-L)$ . Au rang 0, l'écart est $$U_0-L$$ ; à chaque transition il est multiplié par $$1/2$$ . Par récurrence, $U_n-L=2^{-n}(U_0-L)$ . Chaque coordonnée de l'écart est une constante multipliée par une suite géométrique de raison $$1/2$$ , donc tend vers zéro. Ainsi $$U_n$$ tend vers $$L$$ , quelle que soit la colonne initiale.

À toi d’essayer

Pourquoi soustraire le point fixe ?

Soit $U_{n+1}=AU_n+C$ et $$L=AL+C$$ . Écris la récurrence satisfaite par $$V_n=U_n-L$$ et sa solution.

Pour démarrer. Écris les deux membres soustraits avec leurs parenthèses pour faire apparaître l’annulation de $$C$$ .

Tu peux chercher, prendre un indice ou lire l’explication, à ton rythme.

Indice 1 · Une piste

Soustrais les deux égalités.

Indice 2 · Un pas de plus

Les termes C se compensent.

Voir l’explication

\begin{aligned}V_{n+1} &= U_{n+1}-L\\[.35em] &= (AU_n+C)-(AL+C)\\[.35em] &= AU_n-AL\\[.35em] &= A(U_n-L)\\[.35em] &= AV_n.\end{aligned}

Nous avons utilisé la distributivité et la relation du point fixe. Au rang 0, $$V_0=U_0-L$$ . Si $$V_n=A^nV_0$$ , le rang suivant vaut $AV_n=A^{n+1}V_0$ ; avec le rang 0, cela prouve $$V_n=A^nV_0$$ . En revenant à $$U_n$$ , $$U_n=L+A^n(U_0-L)$$ . Une convergence vers $$L$$ exige encore que cette dernière colonne tende vers zéro ; le simple recentrement ne le prouve pas.

Parcours eulériens : un prolongement

Un parcours eulérien utilise chaque arête exactement une fois. Les sommets peuvent être visités plusieurs fois. Si le parcours est fermé, on parle de circuit eulérien. Dans un graphe non orienté connexe, un circuit eulérien existe si et seulement si tous les degrés sont pairs. Un parcours eulérien ouvert existe si et seulement si exactement deux degrés sont impairs : ce sont ses extrémités.

Démonstration · Comprendre le critère

Nécessité. Dans un parcours sans réutilisation d'arête, chaque arrivée à un sommet intermédiaire doit être suivie d'un départ par une autre arête. Les arêtes utilisées à ce sommet se groupent par paires. Pour un parcours fermé, cela vaut aussi au sommet de départ, donc tous les degrés sont pairs. Pour un parcours ouvert, le départ a un départ de plus que d'arrivées et l'arrivée a une arrivée de plus ; exactement ces deux sommets ont un degré impair.

Suffisance si tous les degrés sont pairs. Partons d'un sommet et suivons une arête encore inutilisée tant que possible. À un sommet différent du départ, arriver utilise une arête ; les utilisations précédentes y étaient appariées. Comme le degré total est pair, une arête inutilisée reste disponible pour repartir. On ne peut donc se bloquer qu'au point de départ, et le trajet obtenu est fermé. Les arêtes sont en nombre fini et chacune n'est prise qu'une fois, donc ce trajet se termine.

S'il reste des arêtes, la connexité garantit qu'un sommet du circuit déjà construit est incident à une arête inutilisée : sinon aucune arête ne pourrait relier les sommets déjà atteints à la partie restante. Retirer les arêtes du circuit enlève un nombre pair d'arêtes à chaque sommet. Les degrés restants sont donc encore pairs. Depuis le sommet choisi, le même argument construit un autre circuit avec les arêtes restantes. On l'insère dans le premier au moment où l'on passe par ce sommet. Chaque insertion utilise au moins une nouvelle arête ; le nombre total étant fini, on finit par toutes les utiliser.

Deux sommets impairs. Ajoutons temporairement une arête entre eux, même si cela crée deux arêtes parallèles ; on distingue alors ces deux arêtes. Les deux degrés deviennent pairs, et l'argument précédent reste valable. Il produit un circuit utilisant l'arête ajoutée. Couper ce circuit à cette arête puis la retirer laisse un parcours ouvert entre les deux sommets impairs, utilisant chaque arête originale exactement une fois.

Ce problème diffère du comptage par $$M^n$$ : la contrainte de ne pas réutiliser une arête n'est pas encodée dans la seule puissance d'adjacence.

Boîte à outils : relier réseau et évolution

Retrouver une matrice de transition de comptage

Exemple · Deux types de mots binaires

Pour $n\ge1$ , $$a_n$$ compte les mots valides finissant par 0 et $$b_n$$ ceux finissant par 1. Un mot de longueur $$n+1$$ finissant par 0 s'obtient en ajoutant 0 à n'importe quel mot valide de longueur $$n$$ : cela ne crée jamais deux 1 consécutifs. Il y en a donc $$a_n+b_n$$ . Pour finir par 1, le mot précédent doit finir par 0 ; il y en a $$a_n$$ . Retirer la dernière lettre inverse ces constructions, donc aucun mot n'est oublié ou compté deux fois.

Ainsi $a_{n+1}=a_n+b_n$ , $b_{n+1}=a_n$ , soit $U_{n+1}=\begin{pmatrix}1&1\\1&0\end{pmatrix}U_n$ . À longueur 1, les mots sont 0 et 1 : $$U_1=(1,1)^T$$ . Les étapes donnent $$U_2=(2,1)^T$$ , $$U_3=(3,2)^T$$ , $$U_4=(5,3)^T$$ , donc huit mots de longueur 4.

La formule générale est $U_n=A^{n-1}U_1$ : pour passer du rang 1 au rang $$n$$ , on applique $$n-1$$ transitions. Au rang 1, l'exposant zéro redonne bien la donnée initiale.

Une récurrence affine couplée complète

Soit $U_{n+1}=AU_n+C$ avec $A=\begin{pmatrix}1/2&1/4\\0&1/2\end{pmatrix}$ , $$C=(1,1)^T$$ . Le point fixe satisfait $$L_2=L_2/2+1$$ , donc $$L_2=2$$ , puis $$L_1=L_1/2+L_2/4+1$$ , donc $$L_1=3$$ .

Écris $$A=(1/2)(I+N)$$ avec $N=\begin{pmatrix}0&1/2\\0&0\end{pmatrix}$ et $N^{2}$ =0. Alors $A^n=2^{-n}\begin{pmatrix}1&n/2\\0&1\end{pmatrix}$ . Pour $$U_0=(0,0)^T$$ , on obtient

U_n=\begin{pmatrix}3-(n+3)2^{-n}\\2-2\times2^{-n}\end{pmatrix}.

Détaillons le produit : $$U_0-L=(-3,-2)^T$$ et $A^n(U_0-L)=2^{-n}(-3-n,-2)^T$ . Ajouter $$(3,2)^T$$ donne bien les deux coordonnées affichées. Au rang 0, elles valent $$3-3=0$$ et $$2-2=0$$ , comme la donnée initiale.

Pour la limite, il reste à justifier $n2^{-n}\to0$ , pas seulement $2^{-n}\to0$ . Posons $$v_n=n/2^n$$ pour $n\ge2$ . Ce nombre est positif, et $v_{n+1}/v_n=(n+1)/(2n)=1/2+1/(2n)\le3/4$ . Donc $v_{n+1}\le(3/4)v_n$ . En répétant de $$2$$ à $$n$$ , $0\le v_n\le v_2(3/4)^{n-2}$ . La borne supérieure est une suite géométrique de raison entre 0 et 1, donc tend vers zéro ; le théorème des gendarmes donne $v_n\to0$ . Alors

\begin{aligned}(n+3)2^{-n} &= n2^{-n}+3\times2^{-n}\\[.35em] &\to 0.\end{aligned}

Les deux coordonnées convergent ainsi vers 3 et 2.

Sommer des puissances avec le bon ordre

Posons $S=I+A+\cdots+A^{n-1}$ pour $n\ge1$ . Le produit $AS=A+A^2+\cdots+A^n$ décale chaque exposant. Dans $$S-AS$$ , les termes $$A$$ à $A^{n-1}$ se compensent, laissant $$I-A^n$$ . Ainsi $$(I-A)S=I-A^n$$ . Si $$I-A$$ est inversible, multiplier à gauche par son inverse donne $S=(I-A)^{-1}(I-A^n)$ . Puis $SC=\sum_{k=0}^{n-1}A^kC$ représente les apports successifs de la récurrence affine. Cette preuve explique le sens de la multiplication et les deux termes qui restent après compensation.

Lorsque I-A n'est pas inversible, l'identité de compensation demeure vraie, mais on ne peut pas la résoudre en multipliant par un inverse inexistant. La somme finie reste alors une expression valide et souvent utile.

À toi d’essayer

Ne pas décaler une suite

Si $$U_2=V$$ et $U_{n+1}=AU_n$ pour n $\ge$ 2, exprime $U_{n}$ en fonction de V.

Pour démarrer. Compte combien de transitions séparent le rang 2 du rang $$n$$ .

Tu peux chercher, prendre un indice ou lire l’explication, à ton rythme.

Indice 1 · Une piste

Calcule d'abord $U_{3}$ et $U_{4}$ .

Indice 2 · Un pas de plus

À n=2, l'exposant doit valoir zéro.

Voir l’explication

Au rang 2, $$U_2=V$$ . Puis $$U_3=AV$$ et

\begin{aligned}U_4 &= A(AV)\\[.35em] &= A^2V.\end{aligned}

On conjecture donc $U_n=A^{n-2}V$ . Au rang 2,

\begin{aligned}A^0V &= IV\\[.35em] &= V,\end{aligned}

donc la formule est vraie. Si elle vaut à $n\ge2$ ,

\begin{aligned}U_{n+1} &= AA^{n-2}V\\[.35em] &= A^{n-1}V,\end{aligned}

qui est bien l'exposant $$(n+1)-2$$ . La récurrence conclut. Écrire $$A^nV$$ aurait effectué deux transitions supplémentaires et ne redonnerait pas forcément la donnée au rang 2.

À toi d’essayer

Un zéro ne suffit pas

Dans le graphe A–B–C, le coefficient (A,C) de M est nul. Les sommets sont-ils pourtant reliés ?

Pour démarrer. Cherche d’abord un trajet concret à deux étapes, puis retrouve-le dans $$M^2$$ .

Tu peux chercher, prendre un indice ou lire l’explication, à ton rythme.

Indice 1 · Une piste

Cherche une marche passant par B.

Indice 2 · Un pas de plus

Examine le coefficient (A,C) de $M^{2}$ .

Voir l’explication

Le graphe a les arêtes $$AB$$ et $$BC$$ , donc la marche $$A,B,C$$ relie $$A$$ à $$C$$ en deux étapes. Sa matrice dans l'ordre $$A,B,C$$ a première ligne $$(0,1,0)$$ et troisième colonne $$(0,1,0)^T$$ . La case $$(A,C)$$ de $$M^2$$ vaut $0\times0+1\times1+0\times0=1$ . Il y a exactement cette marche de longueur 2. Le zéro dans $$M$$ signifie absence de liaison directe ; il ne permet pas de conclure à une absence de connexion à toute longueur.

Exercices progressifs

Les exercices 1 à 5 consolident les bases, 6 à 10 relient les notions et 11 à 15 demandent davantage d'initiative. Cherche d'abord, puis utilise un indice si tu en as besoin.

Exercice 1 : Ordre et degrés ★☆☆

Un graphe possède les sommets A,B,C,D et les arêtes AB,AC,BC,CD. Donne son ordre, les degrés et vérifie leur somme.

Exercice 2 : Graphe complet ★☆☆

Combien d’arêtes possède $$K_6$$ ? Quel est le degré de chaque sommet ?

Exercice 3 : Matrice d’un triangle ★☆☆

Écris la matrice d’adjacence du triangle A,B,C dans cet ordre.

Exercice 4 : Chemins de longueur deux ★☆☆

Calcule $$M^2$$ pour le triangle de l’exercice 3. Combien de marches de longueur deux vont de A à B ?

Exercice 5 : Connexité ★☆☆

Le graphe d’arêtes AB et CD sur quatre sommets est-il connexe ? Peut-il exister une marche de A à D ?

Exercice 6 : Graphe orienté ★★☆

Les arcs sont A vers B, B vers C et C vers A. Écris M puis $$M^3$$ .

Exercice 7 : Puissance diagonale ★★☆

Pour $D=\begin{pmatrix}2&0&0\\0&-1&0\\0&0&1/2\end{pmatrix}$ , donne $$D^n$$ et le comportement des trois coordonnées de $$D^n(1,1,1)^T$$ .

Exercice 8 : Une matrice triangulaire ★★☆

Pour $A=\begin{pmatrix}1&3\\0&1\end{pmatrix}$ , conjecture puis démontre $$A^n$$ .

Exercice 9 : Puissance d’ordre trois ★★☆

Pour $A=\begin{pmatrix}1&1&0\\0&1&1\\0&0&1\end{pmatrix}$ , calcule $$A^5$$ .

Exercice 10 : Suite couplée ★★☆

Soit $x_{n+1}=2x_n+y_n$ , $y_{n+1}=x_n+2y_n$ avec $$x_0=2,y_0=0$$ . Donne $x_{n}$ et $y_{n}$ .

Exercice 11 : Récurrence affine ★★★

Soit $U_{n+1}=\begin{pmatrix}1/2&0\\0&1/3\end{pmatrix}U_n+\begin{pmatrix}1\\2\end{pmatrix}$ , $$U_0=(0,0)^T$$ . Calcule $U_{n}$ et sa limite.

Exercice 12 : Sans point fixe ★★★

Soit $U_{n+1}=U_n+C$ avec $C\ne0$ . Exprime $U_{n}$ et explique pourquoi la méthode du point fixe échoue.

Exercice 13 : Compter les retours ★★★

Pour le triangle de l’exercice 3, calcule le nombre de marches de longueur trois de A à A, puis de A à B.

Exercice 14 : Parcours eulérien, prolongement ★★★

Le graphe de l’exercice 1 possède-t-il un parcours utilisant chaque arête une fois ? Donne-en un.

Exercice 15 : Une formule de puissances ★★★

Soit $A=\begin{pmatrix}2&1\\1&2\end{pmatrix}$ . Démontre sans calculer P que $A^n=\frac12\begin{pmatrix}3^n+1&3^n-1\\3^n-1&3^n+1\end{pmatrix}$ .

Problème : Pour aller plus loin

Ce prolongement est accessible à partir du cours : les résultats supplémentaires sont guidés, et leur mémorisation n'est pas un préalable. Tu peux répartir la recherche sur plusieurs séances.

Fibonacci, pavages et matrice de transition

On définit $$F_0=0$$ , $$F_1=1$$ et $F_{n+2}=F_{n+1}+F_n$ . Le but est de relier cette suite au nombre de pavages d'une bande et de démontrer une identité de produits. Durée indicative : 90 minutes.

Partie I : Une récurrence à deux coordonnées

Pose $U_n=(F_{n+1},F_n)^T$ . Montre $U_{n+1}=AU_n$ avec $A=\begin{pmatrix}1&1\\1&0\end{pmatrix}$ .
Calcule $$A^2,A^3$$ et les six premiers termes de la suite.
Démontre pour $n\ge1$ : $A^n=\begin{pmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{pmatrix}$ .

Partie II : Une formule d'addition

Utilise $A^{m+n}=A^mA^n$ pour démontrer, pour $m,n\ge1$ , $F_{m+n}=F_{m+1}F_n+F_mF_{n-1}$ .
Déduis une expression de $F_{2n}$ puis calcule $F_{10}$ à partir de $$F_4,F_5,F_6$$ .

Partie III : Un invariant alterné et des pavages

Pose $D_n=F_{n+1}F_{n-1}-F_n^2$ . Montre $D_{n+1}=-D_n$ puis déduis $$D_n=(-1)^n$$ pour $n\ge1$ .
On pave une bande de n cases avec des tuiles de longueur 1 ou 2. Si $T_{n}$ est le nombre de pavages et $$T_0=1$$ , justifie $$T_1=1$$ et $T_n=T_{n-1}+T_{n-2}$ pour $n\ge2$ .
Déduis $T_n=F_{n+1}$ et calcule le nombre de pavages d'une bande de 9 cases.

Pistes

Multiplie les matrices dans I. Dans II, lis un seul coefficient du produit. Dans III, remplace $F_{n+1}$ par $F_n+F_{n-1}$ et classe les pavages selon la longueur de leur première tuile.

Corrigés détaillés

Corrigé 1

Corrigé 2

Corrigé 3

Corrigé 4

Corrigé 5

Corrigé 6

Corrigé 7

Corrigé 8

Corrigé 9

Corrigé 10

Corrigé 11

Corrigé 12

Corrigé 13

Corrigé 14

Corrigé 15

Corrigé du problème

Partie I : Mettre deux rangs dans une colonne

1. La colonne $$U_n$$ contient $F_{n+1}$ en haut et $$F_n$$ en bas. Le produit par $$A$$ donne $(F_{n+1}+F_n,F_{n+1})^T$ . La relation de Fibonacci identifie le premier terme à $F_{n+2}$ ; le produit est donc $(F_{n+2},F_{n+1})^T=U_{n+1}$ . La deuxième ligne copie l'ancien premier terme pour conserver les deux rangs consécutifs.

2. Le carré de $$A$$ a pour cases $$1+1=2$$ , $$1+0=1$$ , $$1+0=1$$ , $$1+0=1$$ , donc $A^2=\begin{pmatrix}2&1\\1&1\end{pmatrix}$ . Multiplier encore par $$A$$ donne $A^3=\begin{pmatrix}3&2\\2&1\end{pmatrix}$ . Les six premiers termes sont $$F_0=0$$ , $$F_1=1$$ ,

\begin{aligned}F_2 &= 1+0\\[.35em] &= 1,\end{aligned}

\begin{aligned}F_3 &= 1+1\\[.35em] &= 2,\end{aligned}

\begin{aligned}F_4 &= 2+1\\[.35em] &= 3,\end{aligned}

\begin{aligned}F_5 &= 3+2\\[.35em] &= 5.\end{aligned}

3. Au rang $$n=1$$ , la matrice annoncée est $\begin{pmatrix}F_2&F_1\\F_1&F_0\end{pmatrix}=A$ . Supposons la formule vraie à un rang $n\ge1$ . Alors

A^{n+1}=\begin{pmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{pmatrix}\begin{pmatrix}1&1\\1&0\end{pmatrix} =\begin{pmatrix}F_{n+1}+F_n&F_{n+1}\\F_n+F_{n-1}&F_n\end{pmatrix}.

Les deux sommes sont $F_{n+2}$ et $F_{n+1}$ . C'est la formule au rang $$n+1$$ , donc elle est vraie pour tous les rangs $n\ge1$ par récurrence. Le départ à 1 évite d'utiliser un terme $F_{-1}$ non défini.

Partie II : Lire un coefficient utile

1. Dans $A^{m+n}$ , la case $$(1,2)$$ est $F_{m+n}$ . Dans $$A^mA^n$$ , elle est le produit de la ligne $(F_{m+1},F_m)$ par la colonne $(F_n,F_{n-1})^T$ , donc $F_{m+1}F_n+F_mF_{n-1}$ . Les matrices sont égales parce que les puissances d'une même matrice vérifient $A^{m+n}=A^mA^n$ . Leurs cases correspondantes sont donc égales, ce qui démontre l'identité demandée.

2. Prenons $$m=n$$ . On obtient

\begin{aligned}F_{2n} &= F_{n+1}F_n+F_nF_{n-1}\\[.35em] &= F_n(F_{n+1}+F_{n-1}).\end{aligned}

Pour $$n=5$$ , les valeurs sont $$F_4=3,F_5=5,F_6=5+3=8$$ , donc

\begin{aligned}F_{10} &= 5(8+3)\\[.35em] &= 5\times11\\[.35em] &= 55.\end{aligned}

Partie III : Justifier l'alternance puis les pavages

1. Partons de $D_{n+1}=F_{n+2}F_n-F_{n+1}^2$ . Remplaçons $F_{n+2}$ par $F_{n+1}+F_n$ :

\begin{aligned}D_{n+1}&=F_{n+1}F_n+F_n^2-F_{n+1}^2\\[.35em]&=F_n^2-F_{n+1}(F_{n+1}-F_n)\\[.35em]&= F_n^2-F_{n+1}F_{n-1}\\[.35em]&= -D_n.\end{aligned}

La deuxième ligne met $F_{n+1}$ en facteur ; la troisième utilise $F_{n+1}-F_n=F_{n-1}$ . Au rang 1,

\begin{aligned}D_1 &= F_2F_0-F_1^2\\[.35em] &= 1\times0-1\\[.35em] &= -1.\end{aligned}

Chaque pas change le signe : par récurrence, $$D_n=(-1)^n$$ .

2. La bande vide possède un pavage vide, donc $$T_0=1$$ . Une bande d'une case accepte uniquement une tuile de longueur 1, donc $$T_1=1$$ . Pour $n\ge2$ , séparons les pavages selon leur première tuile. Si elle a longueur 1, il reste une bande de $$n-1$$ cases, pavable de $T_{n-1}$ façons. Si elle a longueur 2, il reste $$n-2$$ cases, pavables de $T_{n-2}$ façons. Retirer puis remettre la première tuile établit une correspondance exacte dans chaque cas. Les deux cas sont distincts et couvrent toutes les possibilités, donc $T_n=T_{n-1}+T_{n-2}$ .

3. La suite $G_n=F_{n+1}$ a

\begin{aligned}G_0 &= F_1\\[.35em] &= 1\end{aligned}

\begin{aligned}\text{et }G_1 &= F_2\\[.35em] &= 1,\end{aligned}

comme $$T$$ . Si $T_{n-1}=F_n$ et $T_{n-2}=F_{n-1}$ , leur récurrence donne

\begin{aligned}T_n &= F_n+F_{n-1}\\[.35em] &= F_{n+1}.\end{aligned}

Les deux valeurs initiales et cette transmission prouvent $T_n=F_{n+1}$ à tous les rangs. Pour neuf cases,

\begin{aligned}T_9 &= F_{10}\\[.35em] &= 55\end{aligned}

pavages.

Faire le point par une variante autonome

Essaie cette variante sans relire le corrigé précédent. Explique le choix de ta méthode, puis utilise les contrôles pour décider quelle notion retravailler.

À toi d’essayer

De l’affine à une formule explicite

Soit $U_{n+1}=\frac12U_n+(1,2)^T$ et $$U_0=(0,0)^T$$ . Détermine un point fixe, puis $$U_n$$ et sa limite.

Pour démarrer. Trouve $$L$$ , calcule l’écart initial, puis remets le point fixe à la fin.

Tu peux chercher, prendre un indice ou lire l’explication, à ton rythme.

Indice 1 · Une piste

Résous $L=\frac12L+(1,2)^T$ .

Indice 2 · Un pas de plus

Soustrais L avant de chercher la puissance.

Voir l’explication

$$L=L/2+(1,2)^T$$ donne $$L/2=(1,2)^T$$ , donc $$L=(2,4)^T$$ . Après soustraction,

\begin{aligned}U_n-L &= 2^{-n}(U_0-L)\\[.35em] &= 2^{-n}(-2,-4)^T.\end{aligned}

Donc $U_n=(2-2\times2^{-n},4-4\times2^{-n})^T$ , soit $(2-2^{1-n},4-2^{2-n})^T$ . Au rang 0, les deux coordonnées valent zéro ; au rang 1, elles valent 1 et 2, conformément à la récurrence. Comme $2^{-n}\to0$ , la limite est $$(2,4)^T$$ . La limite a été obtenue à partir de l'écart, pas seulement devinée en résolvant le point fixe.

Fiche-mémoire

Ordre : nombre de sommets ; degré : nombre d'arêtes incidentes ; longueur : nombre de transitions.
Fixe l'ordre des sommets avant de construire une matrice d'adjacence.
$(M^n)_{ij}$ compte les marches de longueur n, avec répétitions autorisées.
$U_{n+1}=AU_n$ donne $$U_n=A^nU_0$$ .
Si $U_{n+1}=AU_n+C$ et $$L=AL+C$$ , alors $$U_n=L+A^n(U_0-L)$$ .
Si $A=PDP^{-1}$ , alors $A^n=PD^nP^{-1}$ ; les facteurs doivent être vérifiés.

Contrôle. Ai-je confondu un nombre de parcours avec une distance ? Les répétitions sont-elles autorisées ? Ai-je vérifié le premier rang ? Une convergence est-elle effectivement prouvée, au-delà de l'existence d'un point fixe ?

Maîtrise du chapitre

Validation contrôlée

Réponds aux QCM, sélectionne les bonnes propositions ou remets les étapes dans l'ordre. Le site vérifie chaque réponse avant d'ouvrir la balise suivante.

Avant le cours, vérifie tes bases

Pourquoi ce chapitre ?

Le problème fondamental : compter les parcours d'un réseau

L'idée avant la formule

Un sommet intermédiaire organise tous les cas

Ce qu'on compte doit être annoncé

Déplacer l'origine simplifie une évolution affine

Le cours formel

Graphes : objets et vocabulaire

Chaînes, connexité et orientation

Matrice d'adjacence

Compter les chemins par des puissances

Calculer des puissances sans multiplier n fois

Matrices diagonales et nilpotentes

Une factorisation vérifiée

Suites de colonnes : cas homogène et affine

Parcours eulériens : un prolongement

Boîte à outils : relier réseau et évolution

Retrouver une matrice de transition de comptage

Une récurrence affine couplée complète

Sommer des puissances avec le bon ordre

Exercices progressifs

Exercice 1 : Ordre et degrés ★☆☆

Exercice 2 : Graphe complet ★☆☆

Exercice 3 : Matrice d’un triangle ★☆☆

Exercice 4 : Chemins de longueur deux ★☆☆

Exercice 5 : Connexité ★☆☆

Exercice 6 : Graphe orienté ★★☆

Exercice 7 : Puissance diagonale ★★☆

Exercice 8 : Une matrice triangulaire ★★☆

Exercice 9 : Puissance d’ordre trois ★★☆

Exercice 10 : Suite couplée ★★☆

Exercice 11 : Récurrence affine ★★★

Exercice 12 : Sans point fixe ★★★

Exercice 13 : Compter les retours ★★★

Exercice 14 : Parcours eulérien, prolongement ★★★

Exercice 15 : Une formule de puissances ★★★

Problème : Pour aller plus loin

Fibonacci, pavages et matrice de transition

Partie I : Une récurrence à deux coordonnées

Partie II : Une formule d'addition

Partie III : Un invariant alterné et des pavages

Pistes

Corrigés détaillés

Corrigé 1

Corrigé 2

Corrigé 3

Corrigé 4

Corrigé 5

Corrigé 6

Corrigé 7

Corrigé 8

Corrigé 9

Corrigé 10

Corrigé 11

Corrigé 12

Corrigé 13

Corrigé 14

Corrigé 15

Corrigé du problème

Partie I : Mettre deux rangs dans une colonne

Partie II : Lire un coefficient utile

Partie III : Justifier l'alternance puis les pavages

Faire le point par une variante autonome

Fiche-mémoire

Maîtrise du chapitre

Pour relier les notions