3. Aplicación: Grafos y dígrafos

Definición:

1. Un grafo consiste de un conjunto finito de puntos llamados vértices y un conjunto finito de aristas, cada una de las cuales conecta dos vértices.
2. Se dice que dos vértices son adyacentes, si están conectados por una arista.
   

A lo largo de esa clase solamente vamos a considerar grafos tales que sus vértices están conectados a lo sumo por una arista.

Matriz de adyacencia: Dado un grafo $G$ que tiene $n$ vértices, su matriz de adyacencia es la matriz $A(G)$ de tamaño $n\times n$ definida por
$$a_{ij}= \begin{cases} 1 & \text{si existe una arista entre $i$ y $j$,}\\ 0 & \text{de lo contrario.} \end{cases}$$

Nota: La anterior definición es apropiada solamente para los grafos simples. Un grafo es simple si no existen múltiples aristas que conectan a una pareja de vértices.  En este curso solamente vamos a considerar ejemplos de grafos simples.

Ejemplo: Encontremos la matriz de adyacencia del siguiente grafo:

En este ejemplo tenemos que la matriz de adyacencia es: $$A=\left[ \begin{array}{c}0 & 1 & 1 & 1\\ 1 & 1 & 1 & 0\\ 1 & 1 & 0 & 0\\ 1 & 0 & 0 & 0 \end{array} \right].$$

Definición:

1. Una trayectoria en un grafo es una secuencia de aristas que permiten viajar de un vértice a otro de manera continua.
2. La longitud de una trayectoria es su número de aristas.
3. A una trayectoria de $k$ aristas se le llama $k$-trayectoria.
4. A una trayectoria que comienza y termina en el mismo vértice se le llama circuito.
5. A una trayectoria que no incluye la misma arista más de una vez se le llama simple.

Proposición: Si $A$ es la matriz de adyacencia de un grafo $G$, entonces la entrada $ij$ de $A^k$ es igual al número de $k$-trayectorias entre los vértices $i$ y $j$.

Ejemplo: Consideremos el grafo del ejemplo anterior.

Para este grafo tenemos que la tercera potencia de la matriz de adyacencia está dada por:
$$A^{3}=\left[ \begin{array}{c}3 & 6 & 5 & 3\\ 6 & 7 & 5 & 2\\ 5 & 5 & 3 & 1\\ 3 & 2 & 1 & 0 \end{array} \right].$$
Notemos en particular que la entrada $2,3$ de la matriz $A^{3}$ es $5$. Esto nos dice que existen en total $5$ maneras distintas de ir del vértice 2 al vértice 3 utilizando exactamente $3$ aristas, es decir, hay cinco $3$-trayectorias desde el vértice 2 al vértice 3. De manera similar, como la entrada $4,4$ de la matriz $A^{3}$ es $0$ esto significa que no es posible ir desde el vértice $4$ al mismo vértice por medio de $3$-trayectorias.

Nota: La matriz de adyacencia de un grafo siempre es una matriz simétrica.

Definición:

1. Un grafo con aristas dirigidas se llama dígrafo.
2. Si $G$ es un dígrafo con $n$ vértices, entonces su matriz de adyacencia es la matriz $A(G)$ $n\times n$ definida por $$a_{ij}= \begin{cases} 1 & \text{si existe una arista del vértice $i$ al $j$,}\\ 0 & \text{de lo contrario.} \end{cases}$$

Proposición: Si $A$ es la matriz de adyacencia de un digrafo $G$, entonces la entrada $ij$ de $A^k$ es igual al número de $k$-trayectorias dirigidas que van del vértice $i$ al $j$.

Ejemplo: Encontremos la matriz de adyacencia del siguiente dígrafo:

En este ejemplo tenemos que la matriz de adyacencia es: $$A=\left[ \begin{array}{c}0 & 1 & 1 & 0\\ 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 1\\ 1 & 0 & 0 & 0 \end{array} \right].$$
Adicionalmente, para este matriz tenemos que:
$$A^{2}=\left[ \begin{array}{c}0 & 1 & 0 & 1\\ 0 & 0 & 0 & 0\\ 1 & 0 & 0 & 0\\0 & 1 & 1 & 0 \end{array} \right].$$
Esto nos dice en particular que hay una $2$-trayectoria desde el vértice $1$ hasta el vértice $2$ ya que la entrada $1,2$ de la matriz $A^{2}$ es $1$.

Nota: La matriz de adyacencia de un dígrafo no tiene que ser simétrica.

Ejercicios de práctica

Te invitamos a practicar los conocimientos aprendidos en esta parte de la clase realizando los siguientes ejercicios.