¿ Cuántos caminos de tres tramos ... ? ( Artículo escrito en catalán )

Enunciat:
El graf de la figura 1 representa un conjunt de pobles (nodes del graf) comunicats per carreteres (arestes del graf) de dos sentits (graf no orientat). Fent ús de les propietats de la matriu d'adjacència del graf, resoleu la següent qüestió:

    Quants trajectes (camins) de 3 trams (arestes) permeten anar del node "4" al node "2" ?

Resolució:
La matriu $A$ d'adjacència d'un graf no orientat, de $n$ nodes, és la matriu quadrada, els coeficients $(a_{ij})_{n \times n}$ on ( $i=1,2,\ldots,n$ i $j=1,2,\ldots,n$ ) de la qual prenen els següents valors:
$a_{ij}=\left\{\begin{matrix}1 \;\; \text{si els nodes}\; i \;\text{i} \;j\; \text{estan directament connectats} \\ \;\;\; 0 \;\;\text{si els nodes}\; i \;\text{i} \;j\; \text{no estan directament connectats} \end{matrix}\right.$

Llavors, la matriu d'adjacència del graf és

        $A=\begin{pmatrix} 0&0 &0 &1 &0 \\ 0&0 &1 &0 &1 \\ 0&1 &0 &1 &0 \\ 1&1 &1 &0 &0 \\ 0&1 &0 &0 &0 \end{pmatrix}$

I, d'acord amb la següent propietat:

    La matriu $C(k)$ [que dóna el nombre de camins de $k$ trams (arestes) ( $k=1,2,\ldots $) per anar d'un vèrtex $i$ ( $i=1,2,\ldots,n$ ) a qualsevol altre vèrtex $j$ ( $j=1,2,\ldots,n$ ) ] és igual a la potència $A^k$

podem calcular (fent servir MAXIMA per comoditat i rapidesa en fer el càlcul dels productes de matrius ) que, essent $k=3$, la matriu $C(3)=A^3$ és igual a

        $C(3)=\begin{pmatrix} 0&1 &1 &2 &1 \\ 1&1 &3 &0 &2 \\ 0&3 &1 &3 &1 \\ 2&4 &3 &1 &1 \\ 0&2 &0 &1 &0 \end{pmatrix}$

I, d'aquí, deduïm que el nombre de camins de tres trams (arestes) per anar del node "4" al node "2" és igual a
    $c_{4\,2}=4$

$\blacksquare$

Observació:
Per bé que la matriu d'adjacència $A$ d'un graf no orientat és una matriu simètrica, les matrius $C(k)$, en general, no ho són; és a dir, no es compleix que $c_{i\,j} \ne c_{j\,i} \; \forall i,j \in \{1,2,\ldots,n\} $. Per exemple, $c_{4\,2}$ (que, com acabem de veure, és igual a $4$ ) no és igual al nombre de camins de tres trams $c_{2\,4}$ per anar del vèrtex "2" al vèrtex "4" (que, com es pot llegir a la matriu $C(3)$, és igual a $0$ ).

En l'estudi de les relacions entre un conjunt de persones (aplicació a les xarxes socials), això també es posa de manifest, a primer cop d'ull, d'una manera ben clara (sense fer càlculs, vull dir); canviant "camins" per "lligams de relació" entre dues persones, és evident que si una persona A es relaciona indirectament, de $k$ modes diferents amb una altra persona B, per mitjà de, per exemple, 3 contactes o persones intermediàries ( $k=3$ ), no necessàriament es compleix que B es relaciona amb A, amb el mateix nombre de modes (camins) indirectes ( $k=3$, en aquest cas) que involucrin també a tres persones com a contactes intermedis, atès que cada persona té un grau d'aïllament diferent, en general.

[nota del autor]