Inscription / Connexion Nouveau Sujet
Matrices carrées et graphes
Bonjour,
Voici un exercice qui me pose des difficultés:
Considérons la matrice A=[2 1 1
1 2 1
1 1 2]
dont le coefficient aij représente le nombre d'arêtes reliant les sommets i et j d'un graphe.
1.Démontrez que pour tout entier p:
A^p=[4^p+2 4^p-1 4^p-1
4^p-1 4^p+2 4^p-1
4^p-1 4^p-1 4^p+2].
2.n est un naturel non nul.
Déduidez de la question 1. que le nombre de chaînesde longueur au plus n reliant les sommets 1 et 2 de ce graphe est:
(4^(n+1)-4-3n)/9.
1. Je voulais commencer une récurrence avec comme valeur de p dans l'initialisation p=1 mais je ne retrouve pas la matrice A.
2. Je ne vois pas ce qu'on me demande ...
Merci pour votre aide !
Bonjour
Il faut sans doute savoir (ce n'est pas évident...) que le coefficient i,j de A^n est le nombre de chaînes de longueur n reliant les sommets i et j. À partir de là, la récurrence est aisée.
P.S.: On fait de la théorie des graphes en terminale, maintenant ? Comme quoi, tout n'est pas à jeter dans les programmes actuels...
Je dois donc faire une récurrence pour la 2e question ?
On voit juste ça en exercice en devoir à la maison 
Puisque le coefficient i,j de A^n est le nombre de chaînes de longeur n reliant les sommets i et j, le nombre de chaînes de longueur au plus n et la somme du coefficient i,j des A^k pour k allant de 1 à n. Elle est évidente pour n = 1, et ensuite oui, faire une récurrence.
Évidemment qu'on n'est pas strictement obligé de faire une récurrence. Si on te donne un résultat, tu peux l'utiliser...
Annuler
connectez vous