Matrice d'adjacence ?

babsgueye
babsgueye
dans Combinatoire et Graphes
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

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

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

    Merci
  • Philippe Malot
    Philippe Malot
    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.
  • skilveg
    skilveg
    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.
  • babsgueye
    babsgueye
    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 ?
  • skilveg
    skilveg
    Tout dépend de ta définition de chaîne...
  • babsgueye
    babsgueye
    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.
  • babsgueye
    babsgueye
    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.

Bonjour!

Pour participer au forum, cliquer sur l'un des boutons :

Connexion S'inscrire

Catégories

In this Discussion

Qui est en ligne 4

Mathurinstfj +2 Invités