Rutas y trayectorias 1: grafos dirigidos

Un grafo es una representación formada por puntos llamados vértices o nodos, unidos mediante líneas llamadas aristas.

Una ruta o camino es una sucesión de aristas que permite ir de un vértice a otro. Por ejemplo, para ir de $P$ a $S$ en la figura anterior, una ruta es $P-Q-R-S$ y otra es $P-R-S$.

Un tramo es cada arista que forma parte de una ruta. En la ruta $P-Q-R-S$, el tramo $Q-R$ es la arista que une $Q$ con $R$.

Grafos dirigidos y no dirigidos

Cuando una arista se puede recorrer en ambos sentidos, el grafo es no dirigido. Cuando el sentido está fijado por una flecha o por una regla del problema, el grafo es dirigido.

En este capítulo trabajamos exclusivamente con grafos dirigidos. Sus formas más comunes son:

• «solo hacia la derecha o hacia abajo»;
• «solo hacia arriba, hacia la izquierda y en diagonal hacia arriba»;
• «siguiendo las direcciones indicadas por las flechas»;
• «siempre avanzando, sin retroceder».

Todo el conteo de rutas dirigidas se apoya en dos principios básicos.

2.1. Principio de adición

Se aplica cuando se puede llegar a un mismo punto por una alternativa o por otra. En ese caso, el total de rutas se obtiene sumando las rutas de cada alternativa.

Ejemplo breve. Si a un punto $C$ se puede llegar desde $A$ por 3 rutas y desde $B$ por 5 rutas, entonces hay $3+5=8$ rutas distintas para llegar a $C$.

2.2. Principio de multiplicación

Se aplica cuando una ruta está formada por etapas sucesivas. Si para ir de $A$ a $B$ se debe pasar obligatoriamente por $M$, y hay $m$ rutas de $A$ a $M$ y $n$ rutas de $M$ a $B$, entonces hay $m\times n$ rutas de $A$ a $B$.

La palabra clave aquí es «y»: voy de $A$ a $M$ y luego de $M$ a $B$.

Es el método central de los grafos dirigidos. Consiste en anotar, en cada vértice, cuántas rutas distintas llegan hasta él.

3.1. La regla de la suma en cada nodo

1. Coloca el número $1$ en el punto de partida. Ese $1$ representa la ruta inicial: «ya estoy en $A$».
2. Avanza respetando el sentido de las flechas.
3. Para cada vértice, suma los números de todos los vértices que tienen una flecha directa hacia él.
4. El número que aparece en el punto final es el total de rutas.

¿Por qué funciona? Porque cualquier ruta que llega a un vértice $V$ debe haber pasado por uno de sus predecesores directos. Si desde un predecesor $P$ hay una arista dirigida hacia $V$, entonces cada ruta que llega a $P$ se prolonga de una única manera hasta $V$. Por eso sumamos las rutas de los predecesores.

Aplicando la regla:

• $A=1$.
• Los tres vértices de la primera fila reciben una única flecha desde la izquierda, por lo que valen $1,1,1$.
• Los dos vértices de la primera columna reciben una única flecha desde arriba, por lo que valen $1,1$.
• El vértice que está una fila debajo de $A$ y una columna a la derecha recibe dos flechas: desde arriba ($1$) y desde la izquierda ($1$). Por eso vale $2$.
• Seguimos así hasta que $B$ recibe $4$ desde arriba y $6$ desde la izquierda: $B=4+6=10$.

Hay $10$ rutas de $A$ a $B$.

3.2. Un error que debes evitar desde ya

No se suman las rutas de todos los vértices de la figura, sino únicamente las de los predecesores directos. Una ruta no puede saltar de un vértice a otro si no existe una arista que los conecte.

Cuando la figura es una cuadrícula rectangular y las únicas direcciones permitidas son derecha y abajo, existe un atajo poderoso.

Si para ir de $A$ a $B$ se necesitan $m$ pasos a la derecha y $n$ pasos hacia abajo, entonces cada ruta es un ordenamiento distinto de $m$ pasos $D$ y $n$ pasos $A$. El número de rutas es $$R=\frac{(m+n)!}{m!\, n!}.$$

Ejemplo. En la cuadrícula anterior, de $A$ a $B$ se requieren $3$ pasos a la derecha y $2$ abajo. Luego: $$R=\frac{(3+2)!}{3!\,2!} =\frac{5!}{3!\,2!} =\frac{120}{6\cdot 2} =10.$$

El atajo coincide con el llenado por nodos.

Pero solo es válido si:

• la cuadrícula es rectangular;
• no hay puntos prohibidos;
• no hay segmentos bloqueados;
• no hay diagonales;
• solo existen dos direcciones.

En cuanto aparece una restricción, es más seguro volver al método de acumulación o combinar por tramos.

Muchas preguntas piden ir de $A$ a $D$ pasando siempre por $B$ o por varios puntos.

Si la ruta debe pasar por $B$, se descompone el recorrido en dos etapas:

$$R_{AD} = (\text{rutas de } A \text{ a } B) \times (\text{rutas de } B \text{ a } D).$$

Si debe pasar por $B$ y luego por $C$, se descompone en tres tramos: $$R_{AD} = R_{AB} \times R_{BC} \times R_{CD}.$$

Cada tramo se calcula por acumulación o, si es una cuadrícula rectangular sin restricciones, por la fórmula de permutaciones.

Cuando se pide «sin pasar por el punto $M$» o «sin pasar por los puntos $M$ y $N$», la técnica más limpia es anular esos puntos.

6.1. Técnica de anulación

1. Identifica los puntos prohibidos.
2. Colócales el valor $0$ desde el inicio, o simplemente tájalos.
3. No utilices las aristas que salen de ellos, porque ninguna ruta válida puede pasar por allí.

Si un segmento está bloqueado, se procede como si esa arista no existiera: simplemente no se usa al sumar.

Cuando se agregan diagonales permitidas, el método de acumulación sigue siendo válido. Solo que ahora un vértice puede tener tres predecesores: desde la izquierda, desde arriba y desde la diagonal.

Por ejemplo, si las direcciones permitidas son derecha, abajo y diagonal ↘, para un vértice $V$:

• $(i-1,j)$ es el predecesor que está a la izquierda;
• $(i,j-1)$ es el predecesor que está arriba;
• $(i-1,j-1)$ es el predecesor que llega por la diagonal.

Entonces: $$V = (i-1,j) + (i,j-1) + (i-1,j-1).$$

En la figura, el vértice central $(1,1)$ recibe:

• $1$ desde la izquierda,
• $1$ desde arriba,
• $1$ desde la diagonal de $A$.

Por eso vale $3$. El vértice final $(2,2)$ recibe $5$ desde $(2,1)$, $5$ desde $(1,2)$ y $3$ desde $(1,1)$. En total, $5+5+3=13$ rutas.

No todas las redes son cuadrículas. A veces se presenta un grafo con flechas que van en distintos sentidos, sin formar un rectángulo.

El procedimiento es el mismo:

1. Colocar $1$ en el punto inicial.
2. Recorrer el grafo respetando las flechas.
3. Sumar en cada nodo los valores de todos los predecesores directos.
4. Anular puntos prohibidos si los hay.

Aplicando la regla:

• $A=1$.
• $P=1$, porque solo llega de $A$.
• $Q=1$, porque solo llega de $A$.
• $R=P+Q=1+1=2$.
• $S=P+R+Q=1+2+1=4$.
• $B=R+S=2+4=6$.

Por lo tanto, hay $6$ rutas de $A$ a $B$.

Algunas preguntas presentan cubos, prismas o estructuras de alambre en tres dimensiones. Las direcciones permitidas suelen ser, por ejemplo, «hacia la derecha, hacia abajo o hacia el frente».

El método de acumulación se extiende naturalmente: en cada vértice se suman los números de sus predecesores según las direcciones permitidas. Para no perderse, conviene trabajar por capas o planos.

Si la estructura es un prisma rectangular y las únicas direcciones son tres perpendiculares, se puede usar la fórmula: $$R=\frac{(m+n+p)!}{m!\, n!\, p!},$$ donde $m$, $n$ y $p$ son los pasos en cada una de las tres direcciones.

Antes de llenar números, sigue este orden:

1. Lee las direcciones permitidas. Determina si son derecha/abajo, flechas, diagonales o tridimensionales.
2. Marca las restricciones. Puntos obligados, puntos prohibidos o segmentos bloqueados.
3. Elige el método.
   • Cuadrícula rectangular sin restricciones y con dos direcciones: usa permutaciones con repetición.
   • Hay restricciones, diagonales o el grafo no es rectangular: usa acumulación en nodos.
   • Hay punto obligado: divide en tramos y multiplica.
   • Hay punto prohibido: anúlalo.
4. Verifica. Revisa que cada número provenga únicamente de sus predecesores directos.