Non sei se agora se estuda algo de teoría de grafos no grao de Matemáticas. Na miña época non se tocaba ese tema, por iso eu non teño nin idea sobre o asunto. Con todo, como son algo atolondrado, non é esta a primeira entrada do blogue que leva a etiqueta "grafos". Ao meu favor teño que todas esas entradas son moi básicas pois nada hai que saber de teoría de grafos para poder seguilas sen dificultade. Velaquí un novo exemplo no que verificar esta afirmación.
Vou poñer como referencia un texto de divulgación, En busca del grafo perdido (Ariel, 2021), escrito por Clara Grima. Nun dos seus capítulos, para explicar o que é a matriz de adxacencia dun grafo, recolle unha escena da película do 1997 O indomable Will Hunting (Good Will Hunting) na que un profesor do mítico MIT (Massachusetts Institute of Technology) propón o seguinte problema:
A matriz de adxacencia deste grafo será: $$ A=\begin{pmatrix}
0 & 1& 0& 1\\
1& 0 &2 & 1 \\
0 &2 & 0 & 0 \\
1& 1& 0 & 0
\end{pmatrix} $$
Onde cada elemento $a_{ij}$ indica o número de arestas que conectan o vértice $i$ co vértice $j$. A propia matriz describe o número de camiño de lonxitude $1$ entre os vértices. Que pasa cos camiños de lonxitude $2$, isto é, os formados por dúas arestas?
O vértice $1$ pode conectarse consigo mesmo por medio de dúas arestas de dúas formas: $(1,2,1)$ e $(1,4,1)$.
Ese mesmo vértice pode conectarse co vértice $2$ mediante un único camiño de lonxitude $2$: $(1,4,2)$.
O vértice $1$ pode conectarse mediante dous camiños de lonxitude $2$ co vértice $3$: $(1,2,3)$ seguindo a aresta superior, e outro seguindo a aresta inferior.
Finalmente o vértice $1$ pode conectarse co vértice $4$ mediante un único camiño de dúas arestas, o camiño $(1,2,4)$
Resumindo, o número de camiños cos que o vértice $1$ pode conectarse con todos os vértices do grafo virá dado polos elementos da fila $\begin{pmatrix}
2 & 1 & 2 &1
\end{pmatrix}$. Se fixeramos o mesmo co resto dos vértices obteriamos a seguinte matriz:$$A^{2}=\begin{pmatrix} 0 & 1& 0& 1\\ 1& 0 &2 & 1 \\ 0 &2 & 0 & 0 \\ 1& 1& 0 & 0 \end{pmatrix} \begin{pmatrix} 0 & 1& 0& 1\\ 1& 0 &2 & 1 \\ 0 &2 & 0 & 0 \\ 1& 1& 0 & 0 \end{pmatrix} =\begin{pmatrix} 2 & 1& 2& 1\\ 1& 6 &0 & 1 \\ 2 &0 & 4 & 2 \\ 1& 1& 2 & 2 \end{pmatrix} $$
Efectivamente, os camiños de lonxitude $2$ virán indicados polos coeficientes da matriz $A^{2}$. En xeral os coeficientes de $A^{n}$ resolven o problema de determinar a cantidade de camiños de lonxitude $n$. Daquela, a solución da segunda pregunta do problema da película obtense así:
$$A^{3}=A^{2}A=\begin{pmatrix} 2 & 1& 2& 1\\ 1& 6 &0 & 1 \\ 2 &0 & 4 & 2 \\ 1& 1& 2 & 2 \end{pmatrix} \begin{pmatrix} 0 & 1& 0& 1\\ 1& 0 &2 & 1 \\ 0 &2 & 0 & 0 \\ 1& 1& 0 & 0 \end{pmatrix}=\begin{pmatrix} 2 & 7& 2& 3\\ 7& 2 &12 & 7 \\ 2 &12 & 0 & 2 \\ 3& 7& 2 & 2 \end{pmatrix}$$
Ben, ata aquí temos todos os vimbios para propoñer, e resolver, un problemiña.
Un problema simple
De entre todos os tipos de grafos, podemos concordar en que os máis simples son os denominados grafos camiño ou grafos lineares. O grafo linear de lonxitude $n$ denótase $P_{n}$. Ilustraremos a idea co grafo linear $P_{4}$:
Camiños nun grafo linear. Cantos camiños de lonxitude $k$ hai entre os vértices de $P_{4}$?
Trátase de determinar a matriz dos camiños de lonxitude $k$ de $P_{4}$. Para saborear o problema podemos abordar primeiro algúns casos máis simples. Poderiamos comezar estudando os camiños de $P_{2}$:
A matriz de adxacencia deste grafo será $A=\begin{pmatrix}
0 & 1 \\
1 & 0
\end{pmatrix}$; como $A^{2}=\begin{pmatrix}
1 & 0 \\
0 & 1
\end{pmatrix}=I$ teremos que :
$A^{k}=\begin{pmatrix}
0 & 1\\
1 & 0
\end{pmatrix}=A$ se $k$ é impar e $A^{k}=\begin{pmatrix}
1 & 0 \\
0 & 1
\end{pmatrix}=I$ se $k$ é par.
Que sucede no caso de $P_{3}$? Mirando o grafo
Vemos que a súa matriz de adxacencia é $A=\begin{pmatrix}
0 &1 & 0 \\
1&0 & 1 \\
0 & 1 & 0
\end{pmatrix}$ polo que
$A^{2}=\begin{pmatrix}
1 &0 & 1 \\
0&2 & 0 \\
1 & 0 & 1
\end{pmatrix}$ ; $A^{3}=\begin{pmatrix}
0 &2 & 0 \\
2&0 & 2 \\
0 & 2 & 0
\end{pmatrix}=2\begin{pmatrix}
0 &1 & 0 \\
1&0 & 1 \\
0 & 1 & 0
\end{pmatrix}$; $A^{4}=\begin{pmatrix}
2 &0 & 2 \\
0&2 & 0 \\
2& 0 & 2
\end{pmatrix}=2\begin{pmatrix}
1 &0 & 1 \\
0&2 & 0 \\
1 & 0 & 1
\end{pmatrix}$ ; $A^{5}=\begin{pmatrix}
0 &4 & 0 \\
4&0 & 4 \\
0 & 4 & 0
\end{pmatrix}=4\begin{pmatrix}
0 &1 & 0 \\
1&0 & 1 \\
0 & 1 & 0
\end{pmatrix}$; $A^{6}=\begin{pmatrix}
4 &0 & 4 \\
0&8 & 0 \\
4& 0 & 4
\end{pmatrix}=4\begin{pmatrix}
1 &0 & 1 \\
0&2 & 0 \\
1 & 0 & 1
\end{pmatrix}$
Xa se ve como vai continuar.
Agora é o momento de abordar o problema orixinal, o dos camiños de $P_{4}$. É o teu turno. Prométoche que ten premio. Nunha
próxima entrada, darei a solución.
