Rutas y trayectorias 2

1.1. ¿Qué es un grafo no dirigido?

Un grafo no dirigido es una figura formada por puntos llamados vértices, unidos por líneas llamadas aristas. Decimos que es no dirigido porque cada arista puede recorrerse en ambos sentidos, a diferencia de lo que ocurría en algunas cuadrículas con flechas del tema anterior.

Por ejemplo, una estructura de alambre formada por un cuadrado y sus dos diagonales es un grafo no dirigido. Allí, cada varilla puede ser recorrida de izquierda a derecha o de derecha a izquierda.

1.2. Grado de un punto: la idea clave

El grado de un vértice es el número de aristas que concurren en él.

En la figura del cuadrado con dos diagonales:

• $A$ está unido a $B$, $D$ y $C$; por lo tanto, su grado es $3$.
• $B$ está unido a $A$, $C$ y $D$; su grado es $3$.
• $C$ está unido a $B$, $D$ y $A$; su grado es $3$.
• $D$ está unido a $A$, $C$ y $B$; su grado es $3$.

A un punto de grado par se le llama punto par; a uno de grado impar, punto impar.

Este concepto de paridad es lo que permite saber si una figura se puede trazar sin repetir líneas, y cuándo hay que repetir tramos.

Usa siempre la paridad. En grafos no dirigidos, la clave casi nunca es memorizar una figura, sino preguntarte: ¿este punto es par o impar?

1.3. Ruta, trayectoria y recorrido

En los problemas de admisión se usan varias palabras que debes distinguir:

• Ruta: camino que sigue una persona, animal u objeto desde un punto inicial hasta un punto final. Según el problema, puede repetir o no puntos o tramos.
• Trayectoria sin repetir punto: recorrido que no pasa dos veces por el mismo vértice. En teoría de grafos se llama camino simple.
• Recorrido sin repetir tramo: recorrido que no usa dos veces la misma arista, aunque puede repetir vértices. En teoría de grafos se llama recorrido euleriano cuando recorre todas las aristas una sola vez.

Muchos errores en el examen provienen de no leer bien cuál de estas restricciones se pide.

Este es uno de los tipos de pregunta más característicos del tema. El enunciado típico es:

“¿De cuántas rutas distintas dispone la hormiga para ir desde $M$ hasta $N$, recorriendo solo por el alambre, sin repetir punto?”

La restricción “sin repetir punto” significa que una ruta no puede visitar dos veces el mismo vértice. Por tanto, cada ruta es lo que llamamos una trayectoria simple.

2.1. Método del árbol de posibilidades

El método más seguro para contar estas rutas es elaborar un diagrama de árbol desde el punto de partida.

Los pasos son:

1. Desde el punto inicial $M$, ramifica hacia cada punto vecino.
2. Al pasar a un nuevo punto, márcalo como ya usado; no podrás volver a él.
3. Desde cada nuevo punto, vuelve a ramificar hacia los puntos vecinos que aún no hayan sido usados.
4. Continúa hasta llegar a $N$. Cada rama que termina en $N$ es una ruta válida.
5. Suma todas las ramas que llegaron a $N$.

La ventaja del árbol es que evita olvidar rutas y también evita contarlas dos veces.

2.2. Ejemplo breve

Consideremos el cuadrado $ABCD$ con sus dos diagonales $AC$ y $BD$. Queremos ir desde $A$ hasta $C$ sin repetir punto.

Desde $A$ podemos ir a $C$, $B$ o $D$.

• Si salimos hacia $C$: llegamos directamente; ruta $A \to C$.
• Si salimos hacia $B$:
  • desde $B$ podemos ir a $C$ (ruta $A \to B \to C$);
  • o ir a $D$ y luego a $C$ (ruta $A \to B \to D \to C$).
• Si salimos hacia $D$:
  • desde $D$ podemos ir a $C$ (ruta $A \to D \to C$);
  • o ir a $B$ y luego a $C$ (ruta $A \to D \to B \to C$).

Total: $5$ rutas.

Observa que una ruta como $A \to B \to D \to C$ es válida porque no repite puntos. Una ruta como $A \to B \to D \to B \to C$ sería inválida porque repetiría $B$.

2.3. Atajos con simetrías

En figuras simétricas, no siempre es necesario contar todas las ramas una por una. Si la figura es simétrica respecto de un eje, puedes contar las rutas que salen por un lado y multiplicar por la cantidad de lados simétricos, siempre que tengas cuidado con las rutas centrales o directas.

Por ejemplo, en el cuadrado con dos diagonales, la ruta directa $A \to C$ es central, y las rutas por $B$ y por $D$ son simétricas. Contamos un lado y duplicamos si corresponde, añadiendo la central.

Pero en un primer aprendizaje, lo más seguro es usar el árbol completo. Los atajos se vuelven útiles cuando ya tienes práctica.

Un problema ligeramente distinto pide contar rutas sin repetir tramo o sin pasar dos veces por el mismo tramo.

Aquí la restricción es sobre las aristas, no sobre los vértices. Por lo tanto, una ruta puede pasar dos veces por el mismo punto si lo hace por líneas diferentes.

Por ejemplo, en un cuadrado con una diagonal $AC$, consideremos ir de $A$ a $C$ sin repetir tramo.

Rutas:

• $A \to C$ por la diagonal.
• $A \to B \to C$ por dos lados.
• $A \to D \to C$ por dos lados.

En este caso coinciden con las rutas sin repetir punto, porque la figura es pequeña. Pero en figuras más complejas pueden aparecer rutas adicionales que repiten algún vértice usando aristas distintas.

Este tipo de restricción se conecta con el problema de trazar figuras sin levantar el lápiz, que estudiamos enseguida: si un recorrido debe pasar por todas las aristas exactamente una vez, estamos ante un recorrido euleriano.

Uno de los resultados clásicos de este tema es el criterio que permite saber si una figura se puede dibujar de un solo trazo, sin levantar el lápiz y sin repetir líneas.

4.1. Criterio de Euler

Para que una figura pueda recorrerse de un solo trazo sin repetir tramos, debe cumplir una de estas dos condiciones:

1. Todos los puntos son pares.
   Entonces se puede comenzar en cualquier punto y terminar en el mismo punto. El recorrido es cerrado.

2. Hay exactamente dos puntos impares.
   Entonces se debe comenzar en uno de los puntos impares y terminar en el otro. El recorrido es abierto.

Si hay más de dos puntos impares, no es posible recorrer toda la figura sin repetir tramos.

4.2. ¿Por qué funciona esta regla?

La lógica es simple. En un recorrido por una figura:

• Si un punto no es el inicio ni el final, cada vez que llegas a él debes salir de él. Por lo tanto, sus líneas se consumen de dos en dos: una para entrar y otra para salir. Luego, su grado debe ser par.
• El punto inicial solo necesita una línea de salida si el recorrido es abierto, o una de salida y otra de entrada final si es cerrado. Por eso, en un recorrido abierto los únicos puntos impares pueden ser el inicio y el final.

Esta explicación permite recordar la regla sin memorizarla.

4.3. Ejemplo

La figura $ABCD$ es un rectángulo de $6$ cm × $8$ cm con sus dos diagonales $AC$ y $BD$.

Cada vértice tiene grado $3$: está unido a dos lados y a una diagonal. Por lo tanto, hay cuatro puntos impares. Según el criterio de Euler, esta figura no se puede trazar de un solo trazo sin repetir tramos.

Para poder trazarla, habrá que repetir algunas líneas, y de eso trata el siguiente apartado.

Cuando una figura tiene más de dos puntos impares, no se puede recorrer completamente sin repetir tramos. En los problemas de admisión se pide, entonces, hallar la mínima longitud que se debe recorrer.

5.1. La idea central: repetir tramos para corregir la paridad

Repetir una arista cambia la paridad de sus dos extremos:

• si un punto era par, al repetir una línea que sale de él se vuelve impar;
• si era impar, se vuelve par.

Por lo tanto, si repetimos una arista que une dos puntos impares, ambos se convierten en pares. Así reducimos el número de puntos impares de dos en dos.

La longitud total mínima de un recorrido es:

$$L_{\text{mín}} = L_{\text{figura}} + L_{\text{repeticiones}}$$

donde:

• $L_{\text{figura}}$ es la suma de las longitudes de todas las aristas originales;
• $L_{\text{repeticiones}}$ es la suma mínima de las longitudes de los tramos que se deben repetir.

5.2. Número mínimo de tramos a repetir

Si la figura tiene $I$ puntos impares:

• Para un recorrido abierto (inicio y fin distintos), el número mínimo de tramos a repetir es

$$r = \frac{I-2}{2}$$

porque debemos dejar exactamente dos puntos impares.

• Para un recorrido cerrado (inicio y fin iguales), el número mínimo de tramos a repetir es

$$r = \frac{I}{2}$$

porque debemos dejar cero puntos impares.

Estas fórmulas indican cuántos tramos repetir, pero no dicen cuáles. Para minimizar la longitud, se deben elegir los tramos más cortos entre los puntos impares que se necesitan corregir.

5.3. Casos según el inicio y el final

Los problemas de admisión varían según qué se sepa del inicio y del final.

Caso 1: no se fija inicio ni final

Solo se pide recorrer toda la figura de un solo trazo continuo. Entonces puedes elegir el recorrido abierto que resulte más conveniente, dejando dos puntos impares al final.

Caso 2: inicio y final fijos, distintos

Si el problema dice que se debe empezar en $M$ y terminar en $N$, con $M \neq N$, entonces, después de repetir tramos, los únicos puntos impares deben ser $M$ y $N$.

Para lograr esto, debes repetir tramos que conviertan en pares a todos los demás puntos impares, sin alterar la paridad de $M$ y $N$.

Caso 3: inicio y final fijos, iguales

Si se debe empezar y terminar en el mismo punto $M$, entonces, al final, todos los puntos deben ser pares, incluido $M$. Se deben repetir tramos hasta eliminar todos los puntos impares.

Caso 4: solo se conoce el inicio

Si se fija el inicio $M$ pero no se dice dónde termina, hay que analizar dos posibilidades:

• que el recorrido sea abierto y termine en otro punto; o
• que sea cerrado y termine en $M$.

Se calcula la longitud mínima en ambos casos y se elige la menor.

5.4. Ejemplo breve de aplicación

Tomemos nuevamente el rectángulo de $6$ cm × $8$ cm con sus dos diagonales. Ya vimos que tiene $4$ puntos impares: sus cuatro vértices.

Las longitudes de sus líneas son:

• lados: $6+8+6+8 = 28$ cm;
• diagonales: $10+10 = 20$ cm;
• total: $48$ cm.

Si no se fija inicio ni final, elegimos un recorrido abierto. El número de tramos a repetir es

$$r = \frac{4-2}{2} = 1.$$

Para minimizar la longitud, repetimos un lado corto de $6$ cm. Entonces:

$$L_{\text{mín}} = 48 + 6 = 54 \text{ cm}.$$

Al repetir el lado $AB$, los puntos $A$ y $B$ se vuelven pares, y quedan como impares $C$ y $D$, que serán el inicio y el final del recorrido.