Problèmes de chemins
113
Exemple : le graphe ci-dessous a deux composantes connexes.
Figure 7
La forte connexité, elle, s'applique au concept orienté : un graphe est fortement connexe
si pour tout couple de sommets et
, il existe un chemin reliant à et un chemin
reliant à .
Nous serons amenés à définir d'autres concepts relatifs aux graphes au fur et à mesure
que nous en analyserons les applications.
6.3. PROBLEMES DE CHEMINS
Problème 1
Soit un graphe
et deux sommets distincts et de ce graphe. Existe-t-il un
chemin entre et ?
Pour résoudre ce problème, nous allons introduire une notion nouvelle : la matrice
binaire associée à un graphe, ou matrice d'adjacence.
Les sommets du graphe étant numérotés de
, nous définirons la matrice binaire
associée
par ses éléments
tels que :
s'il existe un arc
s'il n'existe pas d'arc
Pour le graphe suivant :
Figure 8
113
Exemple : le graphe ci-dessous a deux composantes connexes.
Figure 7
La forte connexité, elle, s'applique au concept orienté : un graphe est fortement connexe
si pour tout couple de sommets et
, il existe un chemin reliant à et un chemin
reliant à .
Nous serons amenés à définir d'autres concepts relatifs aux graphes au fur et à mesure
que nous en analyserons les applications.
6.3. PROBLEMES DE CHEMINS
Problème 1
Soit un graphe
et deux sommets distincts et de ce graphe. Existe-t-il un
chemin entre et ?
Pour résoudre ce problème, nous allons introduire une notion nouvelle : la matrice
binaire associée à un graphe, ou matrice d'adjacence.
Les sommets du graphe étant numérotés de
, nous définirons la matrice binaire
associée
par ses éléments
tels que :
s'il existe un arc
s'il n'existe pas d'arc
Pour le graphe suivant :
Figure 8