Graphe et nombre de chemins de longueur K

[touff]

bonjour à tous,

je suis en présence d'un graphe, dont la matrice est la suivante :

| 1 2 1 2 |
| 3 0 1 2 |
| 1 4 1 0 |
| 1 1 3 1 |

soit Nk le nombre de chemin de longueur k reliant le sommet 1 à lui-même.

il me faut montrer que :

ß*6^k(1+C/3^k) ? Nk ? ß*6^k(1+C'/3^k)

avec ß, C et C' réels indépendants de k. On ne cherche pas C et C'

où j'en suis :

- je pense que 6^k est égal à la somme des élément de la première ligne de la matrice à la puissance k, à savoir le nombre de chemin de longueur k partant du sommet 1.

- ß est un réel strictement positif


par contre :

- les C et C' j'en ai aucune idée

- le 3^k je ne vois pas non plus ce qu'il représente.


je vous remercie par avance de me communiquer quelques tuyaux pour essayer de m'en sortir.