Bonsoir,
Soit A la matrice d'adjacence d'un graphe d'ordre n.
Le terme aij à l'intersection de la i-ième ligne et j-ième colonne de la matrice A^k est le nombre de chaînes de longueur k reliant le sommet i au sommet j.
Ce théorème est-il encore valable dans le cas d'un graphe orienté ?
Merci beaucoup.
C.
autre question graphe orienté ou non orienté ?
-
SoS-Math(31)
- Messages : 1360
- Enregistré le : lun. 12 oct. 2015 10:33
Re: autre question graphe orienté ou non orienté ?
Effectivement Cédric,
A est la matrice d’adjacence associée à un graphe orienté dont les sommets sont numérotés. k désigne un nombre entier naturel. Le terme \(a_{ij}\)
de la matrice \(A^{k}\) donne le nombre de chaînes de longueur k reliant i à j
A est la matrice d’adjacence associée à un graphe orienté dont les sommets sont numérotés. k désigne un nombre entier naturel. Le terme \(a_{ij}\)
de la matrice \(A^{k}\) donne le nombre de chaînes de longueur k reliant i à j
-
sos-math(21)
- Messages : 10401
- Enregistré le : lun. 30 août 2010 11:15
Re: autre question graphe orienté ou non orienté ?
Bonsoir,
ce théorème est encore valable pour les graphes orientés : le coefficient d'indice \((i,j)\) de la matrice \(A^k\) est le nombre de chaînes orientées de longueur \(k\) allant du sommet \(i\) au sommet \(j\).
Bonne continuation
ce théorème est encore valable pour les graphes orientés : le coefficient d'indice \((i,j)\) de la matrice \(A^k\) est le nombre de chaînes orientées de longueur \(k\) allant du sommet \(i\) au sommet \(j\).
Bonne continuation