Matrici di percorso

Lo schema seguente mostra una parte della piantina di una città, con alcuni punti di riferimento importanti (P è un parco, M un monumento, T un teatro e G sono dei giardini) e i sensi unici delle strade (il senso unico è  indicato con la freccia, altrimenti la strada è da intendersi a doppio senso):

La tabella qui sotto riportata mostra il numero dei collegamenti a un tratto, cioè il numero dei collegamenti diretti possibili tra un luogo e l'altro, rispettando i sensi unici:

       P     G      T     M

P     1      2       1       0

G     1      0       1       1

T     1      0       0       0

M     1      1       0       0

La tabella precedente si può indicare brevemente con la notazione:

e si dice anche matrice 4 x 4 (quattro righe e quattro colonne) dei percorsi a un tratto.

Ci si può chiedere adesso: quanti sono i collegamenti a due tratti, vale a dire, i collegamenti possibili tra un luogo e l'altro con una tappa intermedia?

Con uno schema del tipo seguente (che mette in comunicazione, per esempio, P con T tramite percorsi a due tratti)

si riesce subito a capire che i percorsi (a due tratti) che conducono da P a T sono 3.
Controllate sulla piantina seguendo il disegno e individuando tali percorsi.

In base alle indicazioni precedenti compilate la matrice dei percorsi a due tratti, completando la seguente:

       P       G       T       M

P     4                3

G

T                                0

M     2

Si può ottenere rapidamente quanto richiesto utilizzando la sola matrice a un tratto, ma ripetendola due volte e moltiplicando le righe della prima per le corrispondenti colonne della seconda:

Il risultato è, come ci si aspetta, il seguente

Spiegate come è stato ottenuto ogni numero di quest'ultima matrice, prodotto delle precedenti (righe per colonne).