Matrice d'adjacence ? — Les-mathematiques.net The most powerful custom community solution in the world

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.

Réponses

  • C'est vrai. Démonstration facile par récurrence. Et $k<n$ ne sert à rien.
  • Bonsoir Babacar,

    Le résultat que tu énonces est vrai pour des graphes quelconques (pas forcément simples).
  • Salut
    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 ?
  • @b.b, peux tu me décrire les 8 chaines reliant le sommet $4$ au sommet $2$, dont il parle ?

    Merci
  • Il y a 4-1-3-2, 4-3-1-2, 4-2-3-2, 4-2-1-2, 4-1-4-2, 4-2-4-2, 4-3-4-2 et 4-5-4-2.
  • Cela peut même se voir sans récurrence avec une grosse expression : on a toujours
    \[
    (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.
  • Merci @Philipe Malot.

    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 ?
  • Tout dépend de ta définition de chaîne...
  • Je viens de voir qu'on fait la différence en parlant de chaîne simple (qui ne passe pas 2 fois par le même arc) et de chaîne élémentaire (qui ne passe pas 2 fois par le même sommet).
    [Je me mets à la théorie des graphes !]

    Merci.
  • Salut.

    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.
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!