Graphes et matrices
Ce que tu dois retenir
Un graphe transforme une relation binaire en un dessin lisible et exploitable mathématiquement.
La matrice d'adjacence code toutes les connexions d'un graphe sous forme de 0 et de 1.
La puissance k-ième de la matrice d'adjacence compte les chaînes de longueur k.
Une matrice de transition permet de prévoir l'évolution d'un système probabiliste étape par étape.
Teste-toi
◆ Teste-toi
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
Réponse : A — 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
Réponse : A — 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
Réponse : A — 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
Réponse : A — 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
Réponse : A — 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
Réponse : A — [[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
Réponse : A — 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
Réponse : A — La matrice de transition
T est la matrice de transition qui fait évoluer l'état probabiliste d'une étape à la suivante.