Matrice d'adjacence ?
Je voulais mettre un lien venant de ''you tube'', apparemment ça n’apparaît pas.
En fait ça parle d'une propriété de la matrice d'adjacence. En gros, il dit que si j'ai un graphe (simple) d'ordre $n$ ($n\gt 3$ par exemple) de matrice d'adjacence $M$, alors le coefficient $a_{ij}$ de la matrice $M^k\;$,($k\lt n$, par précaution) est le nombre de chaines de longueur $k$ allant du sommet $i$ au sommet $j$.
Je pense que c'est faux.
Merci d'éclairer.
En fait ça parle d'une propriété de la matrice d'adjacence. En gros, il dit que si j'ai un graphe (simple) d'ordre $n$ ($n\gt 3$ par exemple) de matrice d'adjacence $M$, alors le coefficient $a_{ij}$ de la matrice $M^k\;$,($k\lt n$, par précaution) est le nombre de chaines de longueur $k$ allant du sommet $i$ au sommet $j$.
Je pense que c'est faux.
Merci d'éclairer.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Le résultat que tu énonces est vrai pour des graphes quelconques (pas forcément simples).
C'est ce qui est dit dans la vidéo que je voulais passer (je vais réessayer). Y a alors quelque chose qui m'échappe. Peux-tu me donner un exemple stp @b.b ?
Merci
\[
(M^k)_{i,j} = \sum_{k_1,\ldots,k_n}a_{i,k_1}\,a_{k_1,k_2}\cdots a_{k_n,j}
\]
et on voit qu'on a compté tous les chemins reliant $i$ à $j$ en les décomposant en pas élémentaires.
Mais je ne prenais pas 4-2-3-2 comme une chaîne reliant 4 à 2, parce qu'on passe deux fois sur l’arête 2-3 ?
[Je me mets à la théorie des graphes !]
Merci.
Je viens de voir que: si $M = (a_{i,j})_{i=1..n, j=1..n}$ est la matrice d'adjacence d'un graphe $G$ d'ordre $n$ alors;
$G$ contient un cycle hamiltonien $\iff\; a_{1,2} = a_{2,3} =\cdots= a_{n-1,n} = a_{n,1} = 1$ ou il existe une permutation des sommets de $G$
de matrice d'adjacence $M' = (a'_{i,j})_{i=1..n, j=1..n}$ telle que $a'_{1,2} = a'_{2,3} =\cdots= a'_{n-1,n} = a'_{n,1} = 1$.
Cordialement.