Introducción a la teoría de grafos: representar las conexiones

Abajo hay seis lugares. Las letras son solo nombres para identificarlos: $A$ es la casa y $E$ es la escuela. Una línea indica que hay un camino directo entre sus dos extremos. Ahora todos los caminos se pueden recorrer en ambos sentidos; la longitud con que se dibuja la línea no registra ninguna distancia.

Estos puntos que representan lugares se llaman vértices, y las líneas que representan conexiones directas se llaman aristas. Dos puntos sin línea no se alcanzan en un paso, aunque puede que sí rodeando por otros puntos. Así conservamos por separado la información de «si se puede llegar directamente».

Primero elige abajo un lugar y mira qué aristas lo conectan. Luego pulsa los botones de las aristas para añadir o quitar una conexión. La posición de los lugares nunca cambia, así que puedes ver con claridad qué relación ha cambiado.

Ahora volvemos a los siete caminos iniciales. Primero planteamos una pregunta muy pequeña: desde un lugar, ¿cuántos caminos se pueden tomar directamente? El número de aristas que tocan un vértice se llama grado de ese vértice. Aquí no hay aristas que vuelvan a un mismo punto ni varias aristas entre el mismo par de lugares.

Por ejemplo, $A$ toca las aristas $AB$ y $AC$, así que su grado es $2$. Cada vez que se pulsa «Siguiente» abajo se añade una arista y se cuenta una vez en cada uno de sus extremos. La línea dorada es la arista recién añadida; la tabla conserva los recuentos ya anotados.

¿Por qué el total de recuentos es siempre el doble del número de aristas? Porque cada arista tiene dos extremos. Sean cuales sean los dos lugares de sus extremos, contamos una vez en un extremo y otra vez en el otro. Por eso, cada arista añadida aumenta el total en $1+1=2$; al procesar todas las aristas se obtiene la igualdad de abajo.

A esto se le suele llamar lema del apretón de manos: cada apretón cuenta una vez por cada una de las dos personas que participan. Lo dedujimos contando los extremos de cada arista, así que se aplica a cualquier grafo no dirigido finito como el de esta página, no solo a nuestro ejemplo de las siete carreteras.

No basta con mirar los lugares conectados directamente: la escuela y la casa no están unidas de forma directa, pero podemos pasar por la tienda y la biblioteca. Recorrer las aristas contiguas una tras otra es una ruta. Aquí, la longitud de la ruta es el número de aristas recorridas: de $A$ a $B$ una arista, a $D$ otra y a $E$ otra, así que se recorren $1+1+1=3$ aristas.

Una ruta que no repite vértices se llama camino simple. Si se sale de un punto y se vuelve a él sin repetir otros vértices y pasando por al menos tres aristas, se obtiene un ciclo en un grafo simple no dirigido como el de esta página. Por ejemplo, $A,B,D,C,A$: la última $A$ solo vuelve al punto de partida y los demás lugares se recorren una vez cada uno.

Abajo solo puedes elegir el siguiente lugar que esté directamente conectado con el actual. Prueba a ir de la casa a la escuela; después de reiniciar, también puedes intentar ir de la escuela a la casa. Las etiquetas numéricas indican el orden en que se recorren los vértices; si pasas varias veces por el mismo punto, la ruta de abajo se conserva entera.

Si entre dos vértices cualesquiera se puede encontrar un camino, decimos que el grafo no dirigido es conexo. Si se quitan los caminos de ambos lados de la escuela, la escuela queda aislada de los demás lugares; aunque los otros cinco lugares sigan siendo alcanzables entre sí, el grafo en conjunto ya no es conexo.

También existen caminos de un solo sentido: poder ir de $A$ a $B$ no significa poder volver de $B$ a $A$. Registramos las direcciones permitidas con flechas y obtenemos un grafo dirigido. El proceso de búsqueda posterior también puede respetar las flechas, pero «poder llegar» exige especificar el punto de partida y la dirección.

Probar caminos al azar hace que se vuelva fácilmente al mismo lugar. Podemos poner en fila, en el orden en que se descubren, los lugares ya descubiertos cuyos caminos aún no se han revisado. Lo que se añade primero se procesa primero; ese registro de espera se llama cola. Abajo, el frente de la cola está a la izquierda y los lugares recién descubiertos se colocan a la derecha.

Al principio solo conocemos el punto de partida, así que lo marcamos con $0$ pasos y lo ponemos en la cola. Luego se saca el frente y se revisan una a una las conexiones por las que se puede salir. Si aparece un lugar aún no descubierto, se anota desde dónde se encontró y cuántos pasos cuesta llegar, y se añade al final de la cola. Si el lugar ya se había descubierto, no se vuelve a poner en la cola.

¿Por qué se suma $1$ al número de pasos del lugar nuevo? Ya conocemos una ruta hasta el lugar actual; si cruzamos la arista que acabamos de revisar, recorremos una arista más que en esa ruta. Por ejemplo, si el lugar actual tiene $2$ pasos, el nuevo lugar tiene $2+1=3$ pasos.

Este método de buscar capa por capa según la distancia se llama búsqueda en anchura; en inglés, BFS. Solo cuando termina la capa actual se pasa a la siguiente. Con «Siguiente» se revisan una a una la cola y los caminos; no avanza por sí solo. El gris indica lo aún no descubierto, el verde lo ya descubierto y la arista dorada es la conexión que se está revisando.

Ahora explicamos por qué los pasos anotados son realmente los mínimos. El punto de partida requiere $0$ pasos; todos los lugares directamente vecinos al punto de partida se descubren al procesarlo, así que requieren $1$ paso. La cola hace que estos lugares alcanzables en un paso queden todos delante de los lugares a dos pasos que se descubren después.

Seguimos aplicando el mismo razonamiento: cuando procesamos la capa $k$, es decir, los lugares alcanzables con al menos $k$ aristas, todas las capas más cercanas ya se han procesado. Un punto vecino aún no descubierto se alcanza en $k+1$ pasos, porque añadimos una arista a los $k$ pasos que ya tenemos.

¿Podría haber una ruta más corta? Si existiera, el penúltimo punto de esa ruta tendría un número mínimo de pasos menor que $k$. Ese punto ya se habría procesado y sus conexiones ya se habrían revisado, así que el objetivo debería haberse descubierto entonces. Esto contradice que «todavía no se haya descubierto». Por tanto, los $k+1$ pasos recién anotados son el mínimo.

Empezando por la capa $0$, este razonamiento garantiza que todas las capas son correctas. Cada punto recién descubierto entra en la cola una sola vez y el número total de vértices es finito, así que la cola termina vacía. En ese momento, los puntos aún no descubiertos son realmente inalcanzables: si existiera una ruta hacia uno de ellos, al buscar el primer punto no descubierto de la ruta, el punto anterior debería haberlo descubierto al revisar sus conexiones.

Aquí lo mínimo es el número de aristas. Si todos los caminos tardan lo mismo, el mínimo de aristas también da el tiempo mínimo; si los tiempos difieren, no se puede deducir así. Por ejemplo, si el camino directo tarda $10$ minutos y los dos tramos que pasan por una parada intermedia tardan $2$ minutos cada uno, los dos juntos suman $2+2=4$ minutos, más rápido que el directo. Registrar valores como el tiempo en las aristas se llama darles un peso; el número de capas de BFS no suma esos valores.

Intenta escribir tu respuesta. El contenido desplegable de abajo muestra el proceso de cálculo, que puedes usar para comprobarla. La respuesta usa las siete aristas iniciales de esta página; puedes volver al grafo de arriba y comprobarlo arista por arista.