Problèmes de chemins
117
On peut donc avoir par :
En fait, on peut calculer d'une autre façon encore : il est facile de voir que
En effet , cette expression est vraie pour
Supposons qu'elle le soit pour
Mais comme
, alors
On en conclut :
Dans la pratique, pour calculer , on prendra
; on calculera
, puis
, en s'arrêtant au premier entier tel que :
Sur le graphe de la figure 7, il suffit de calculer
On
trouve
Par l'intermédiaire de cette matrice, on pourrait isoler les sous-graphes fortement
connexes d'un graphe donné, en repérant dans
des matrices carrées remplies
uniquement de 1 et dont les lignes et les colonnes correspondent aux mêmes sommets.
Sur l'exemple choisi, on constate que cette opération n'est pas possible.
Problème 2 : Le problème du plus court chemin.
Soit
, un graphe dans lequel chaque arc est valué, c'est à dire qu'à chaque arc
u est associé un nombre entier
.Trouver un chemin µ allant d'un sommet donné à
un sommet donné tel que la valeur totale de ce chemin
soit minimale