Sommaire : Sous-graphe – Matrice associée à un graphe simple – Matrice associée à un graphe orienté
1. Sous-graphe
On appelle sous-graphe G’ d’un graphe G, le graphe composé d’une partie des sommets de G et des arêtes qui les relient.
Le graphe, composé des sommets (A, C, D, E) et des arêtes a, b, c et d, est un sous-graphe de (A, B, C, D, E).
2. Matrice associée à un graphe simple
Soit G un graphe comprenant n sommets (n entier non nul).
On appelle matrice de transition ou adjacente de G, la matrice carrée de dimension n x n, où le terme à l’intersection de la ième ligne avec la jième colonne vaut :
• 1
...