Graphes et matrices
Fiche de révision · Mathématiques · Term
L'essentiel du cours
Chapitre 1 : Qu'est-ce qu'un graphe ?
Un graphe transforme une relation binaire en un dessin lisible et exploitable mathématiquement.
Chapitre 2 : La matrice d'adjacence
La matrice d'adjacence code toutes les connexions d'un graphe sous forme de 0 et de 1.
Chapitre 3 : Compter les chaînes avec M^k
La puissance k-ième de la matrice d'adjacence compte les chaînes de longueur k.
Chapitre 4 : Graphes orientés et matrices de transition
Une matrice de transition permet de prévoir l'évolution d'un système probabiliste étape par étape.
Teste-toi · 8 questions
1.Que vaut le coefficient m_{ij} de la matrice d'adjacence d'un graphe non orienté si les sommets i et j ne sont pas reliés ?
Voir la réponseMasquer la réponse
Réponse : 0
Par définition, m_{ij}=0 lorsqu'il n'y a pas d'arête entre i et j.
2.La matrice d'adjacence d'un graphe non orienté est toujours...
Voir la réponseMasquer la réponse
Réponse : symétrique
Si i est relié à j, alors j est relié à i, donc m_{ij}=m_{ji}.
3.Que représente le coefficient (i,j) de M^2 ?
Voir la réponseMasquer la réponse
Réponse : Le nombre de chaînes de longueur 2 entre i et j
M^2 compte les chaînes de longueur 2, c'est-à-dire les chemins en deux arêtes.
4.Dans une matrice de transition, que vaut la somme des coefficients de chaque colonne ?
Voir la réponseMasquer la réponse
Réponse : 1
Chaque colonne décrit les probabilités de transition depuis un état donné, leur somme vaut 1.
5.Un graphe possède 4 sommets. Quelle est la taille de sa matrice d'adjacence ?
Voir la réponseMasquer la réponse
Réponse : 4×4
La matrice d'adjacence est carrée d'ordre n, donc 4×4.
6.Si M = [[0,1],[1,0]], que vaut M^2 ?
Voir la réponseMasquer la réponse
Réponse : [[1,0],[0,1]]
M^2 = M×M = [[0×0+1×1, 0×1+1×0],[1×0+0×1,1×1+0×0]] = [[1,0],[0,1]].
7.Dans un graphe orienté, les liaisons sont appelées...
Voir la réponseMasquer la réponse
Réponse : des arcs
Un graphe orienté utilise des arcs, qui ont un sens de parcours.
8.Si P_{n+1} = T P_n, que représente T ?
Voir la réponseMasquer la réponse
Réponse : La matrice de transition
T est la matrice de transition qui fait évoluer l'état probabiliste d'une étape à la suivante.