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.
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). -
Voilà ! revisionsbac
-
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. -
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.
Bonjour!
Catégories
- 163.1K Toutes les catégories
- 8 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 53 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 62 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 312 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 772 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres