Qu'est-ce qu'un graphe ?
Un graphe est un ensemble de sommets, qui peuvent être reliés deux à deux par des arêtes.
Qu'est-ce que l'ordre d'un graphe ?
L'ordre d'un graphe désigne le nombre de ses sommets.
Qu'est-ce que le degré d'un sommet ?
Le degré d'un sommet désigne le nombre d'arêtes connectées à ce sommet.
Qu'est-ce que la matrice d'adjacence d'un graphe ?
La matrice d'adjacence d'un graphe est une matrice carrée où le terme a_{i,j} est égal au nombre d'arêtes reliant les sommets i et j.
Qu'est-ce qu'une chaîne ?
Une chaîne est une liste ordonnée de sommets où chaque sommet est adjacent au précédent et au suivant.
A quoi est égale la distance entre deux sommets ?
La distance entre deux sommets est égale à la longueur de la chaîne la plus courte reliant ces deux sommets.
Qu'est-ce qu'une chaîne eulérienne ?
Une chaîne eulérienne est une chaîne formée de toutes les arêtes d'un graphe, chacune n'apparaissant qu'une seule fois.
Qu'est-ce qu'un graphe étiqueté ?
Un graphe étiqueté est un graphe dont chacune des arêtes est associée à un texte ou à un nombre.
Qu'est-ce qu'un graphe pondéré ?
On appelle graphe pondéré un graphe étiqueté dont les étiquettes sont toutes des nombres positifs.
Qu'est-ce que le poids d'une chaîne d'un graphe pondéré ?
Le poids d'une chaîne d'un graphe pondéré est la somme des poids des arêtes qui forment cette chaîne.
Qu'appelle-t-on plus courte chaîne entre deux sommets d'un graphe pondéré ?
On appelle plus courte chaîne entre deux sommets une chaîne de poids minimum reliant ces deux sommets.
Qu'est-ce qu'un graphe orienté ?
Un graphe orienté est un graphe dont les arêtes ont un sens.
Qu'est-ce qu'un graphe probabiliste ?
Un graphe probabiliste est un graphe orienté pondéré où, pour chaque sommet, la somme des poids des arêtes sortantes est égale à 1.
Dans un graphe probabiliste, qu'est-ce qu'un état ?
Dans un graphe probabiliste, chaque sommet correspond à un état.
Qu'est-ce que la matrice de transition d'un graphe probabiliste d'ordre n ?
La matrice de transition d'un graphe probabiliste d'ordre n est une matrice à n lignes et n colonnes, où le terme a_{i,j} est égal au poids de l'arête d'origine i et d'extrémité j ou à 0 si cette arête n'existe pas.
A quoi est égal l’état probabiliste P_n à l'instant n d'un graphe probabiliste d'ordre n dont la matrice de transition est M et dont l'état initial est P_0 ?
P_n=P_0\times M^n
Qu'est-ce que l'état stable d'un graphe probabiliste ?
Si l’état P_n devient constant à partir d'un certain rang n, cet état est appelé état stable du graphe.