Recorrer toda una gráfica#
Introducción#
Un acertijo clásico es determinar si se puede hacer un cierto dibujo sin levantar el lápiz del papel, y sin repetir segmentos. Por ejemplo, ¿se puede hacer esto en la siguiente figura?
Una pregunta parecida es si en la figura anterior podemos comenzar en algún vértice y, sin levantar el lápiz, pasar por todos los vértices, sin repetir vértices (no importa si no se recorren todas las aristas).
Los dos problemas anteriores, así como otros más, se pueden poner en términos de los conceptos de caminos, circuitos, ciclos, trayectorias, etc. que hemos definido con anterioridad. Los dos problemas de arriba son simplemente juegos, pero en las aplicaciones nos interesa encontrar recorridos como estos, por ejemplo para resolver problemas de transporte. En esta sección hablaremos de algunos resultados teóricos que ayudan a determinar cuándo existen estos recorridos.
Paseos y circuitos eulerianos#
En los recorridos que estamos hablando nos interesa cubrir toda la gráfica de algún modo, y evitando ciertas repeticiones. Lo primero que estudiaremos es cuándo podemos pasar por todas las aristas, sin repetir. Nos interesará tanto el caso de los paseos, como el de los circuitos. Recuerda que un paseo es un camino en el que no se repiten aristas y un circuito es un camino cerrado en el que no se repiten aristas.
Definición. Sea \(G\) una gráfica.
Un paseo euleriano de \(G\) es un paseo de \(G\) que pasa por todas las aristas.
Un circuito euleriano de \(G\) es un circuito de \(G\) que pasa por todas las aristas.
El término euleriano viene del matemático Leonhard Euler, quien estudió este tipo de problemas en el siglo XVIII. Euler se dio cuenta de ciertas condiciones sencillas de verificar que debe tener una gráfica para que tenga un paseo o un circuito euleriano. A continuación exploraremos estas condiciones. Primero supondremos que una gráfica tiene un circuito euleriano y de ahí veremos que tiene que cumplir algunas propiedades sencillas. Después, veremos que estas propiedades sencillas de hecho son suficientes para que la gráfica tenga un circuito euleriano.
Observación. Si \(G\) es una gráfica con vértices aislados, entonces a esos vértices no llega ninguna arista. Por lo tanto, para fines de encontrar un circuito euleriano, podemos ignorar los vértices aislados.
Proposición. Si \(G\) es una gráfica con un circuito euleriano, entonces su cantidad de componentes conexas con al menos dos vértices es menor o igual a uno.
Demostración. Con el fin de encontrar una contradicción, supongamos que \(G\) tiene dos componentes conexas \(C_1\) y \(C_2\) con al menos dos vértices cada una. Como \(C_1\) tiene al menos dos vértices, entonces hay por lo menos una arista \(e_1=v_1w_1\) en \(C_1\), y análogamente hay por lo menos una arista \(e_2=v_2w_2\) en \(C_2\). El circuito euleriano que suponemos que existe, pasa por la arista \(e_1\) (y por lo tanto por el vértice \(v_1\)) y por la arista \(e_2\) (y por lo tanto por el vértice \(v_2\)). Esto nos da un camino del vértice \(v_1\) al vértice \(v_2\), pero eso es imposible, pues están en componentes conexas distintas. Concluimos entonces que no puede haber dos componentes conexas con al menos dos vértices cada una. \(\square\)
Hay otra observación crucial sobre una propiedad que debe cumplir una gráfica para poder tener un circuito euleriano.
Proposición. Si \(G\) es una gráfica que tiene un circuito euleriano, entonces no puede tener vértices de grado impar.
Demostración. Supogamos que \(v\) es un vértice de \(G\). Como la gráfica tiene un circuito euleriano, podemos pensar que dicho circuito no comienza en \(v\). Entonces, las aristas de \(v\) quedan emparejadas de la siguiente manera: cada vez que llegamos a \(v\) se llega por cierta arista que emparejamos con la arista con la cual salimos. Este emparejamiento muestra que la cantidad de aristas que llega a \(v\) debe ser par. \(\square\)
Un resultado sorprendente es que las dos condiciones anteriores, por muy sencillas que sean, caracterizan por completo a aquellas gráficas que tienen un circuito euleriano.
Teorema. Una gráfica \(G\) con al menos una arista tiene un circuito euleriano si y sólo si suceden las siguientes dos condiciones simultáneamente:
\(G\) tiene a lo más una componente conexa de al menos dos vértices.
Todos los grados de los vértices de \(G\) son pares.
Demostración. Las dos proposiciones anteriores demuestran «la ida» del teorema: si \(G\) tiene circuito euleriano, entonces \(G\) tiene a lo más una componente conexa de al menos dos vérties, y todos los grados de \(G\) son pares. El regreso del teorema es más elaborado. Procederemos por inducción fuerte sobre el número de aristas de una gráfica \(G\) para mostrar que si es conexa, si tiene cierta cantidad \(m\) de aristas y todos los grados de \(G\) son pares, entonces \(G\) tiene un circuito euleriano. El resultado para gráficas no conexas con algunos vértices aislados es una consecuencia inmediata de demostrar esto.
El primer caso es \(m=1\). Aquí no hay gráficas que cumplan las hipótesis, así que resultado es cierto por vacuidad. Para \(m=2\) pasa lo mismo. Para \(m=3\), las únicas gráficas que cumplen las hipótesis son ciclos de longitud \(3\) a los que se han agregado algunos vértices independientes, que sí tienen un circuito euleriano.
Supongamos que el resultado es cierto para cuando tenemos menos de \(m\) aristas y tomemos una gráfica \(G\) con \(m\) aristas, \(n\) vértices y que cumple con las hipótesis. Tomemos cualquier vértice \(u\) de \(G\) y a partir de ahí comencemos a hacer una trayectoria paso a paso (sin repetir aristas). Al llegar a un vértice distinto de \(u\), siempre podemos salir por otra arista pues el grado de dicho vértice es par. Así, la única razón por la cual no podríamos salir de un vértice es si regresamos a \(u\). Esto muestra que \(G\) tiene circuito \(C\). Si \(C\) pasó por todas las aristas, entonces hemos encontrado nuestro circuito euleriano.
Si \(C\) no pasó por todas las aristas, consideremos la gráfica \(G^\ast\) obtenida de quitarle a \(G\) las aristas de \(C\). Como el circuito usa una cantidad par de aristas de cada vértice, entonces \(G^\ast\) también cumple que todos sus vértices son de grado par. Además, \(G^\ast\) tiene menos aristas que \(G\). Ahora, no necesariamente \(G^\ast\) cumple con ser conexa, pero cada una de sus componentes conexas \(H_1,H_2,\ldots,H_k\) cumple:
Ser una \(H_i\) de un sólo vértice. Aquí declaramos \(C_i\) al único vértice.
Ser una \(H_i\) de al menos dos vértices, todos ellos con grado par y entonces por hipótesis inductiva tiene un circuito euleriano \(C_i\)
Como \(G\) es conexa, el circuito \(C\) debe pasar por lo menos por un vértice \(v_i\) de cada componente conexa \(H_i\). Para encontrar el circuito euleriano de \(G\) podemos entonces recorrer \(C\) y cada que encontremos un \(v_i\), recorremos todo \(C_i\). Esto nos regresa a \(v_i\), de donde podemos seguir recorriendo \(C\). Esto garantiza pasar por todas las aristas de \(C\), y por todas las aristas de cada \(C_i\) una y sólo una vez. En otras palabras, hemos encontrado un circuito euleriano para \(G\). \(\square\)
Ciclos Hamiltonianos#
En la sección anterior estudiamos cuándo hay circuitos eulerianos.
Definición. Sea \(G\) una gráfica.
Una trayectoria hamiltoniana de \(G\) es una trayectoria de \(G\) que pasa por todos los vértices.
Un ciclo hamiltoniano de \(G\) es un ciclo de \(G\) que pasa por todos los vértices.
Recuerda que en las palabras «trayectoria» y «ciclo» viene implícito que no se repiten vértices. Estas definiciones no nos dicen nada acerca de pasar por todas las aristas.
Ejemplo. En la siguiente figura, la gráfica de la izquierda tiene un ciclo hamiltoniano, que marcamos en rojo a la derecha.
\(\square\)
Los ciclos hamiltonianos son mucho más difíciles de estudiar que los circuitos eulerianos. De hecho, no se conoce una condición sencilla que caracterice a las gráficas que tienen ciclos hamiltonianos, lo cual a su vez está muy relacionado con un problema algorítmico que estudiaremos más adelante. Lo que sí existen son algunos resultados parciales que garantizan que las gráficas sí tengan un ciclo hamiltoniano. Un ejemplo es el siguiente resultado de Ore.
Teorema (de Ore). Sea \(G\) una gráfica de orden \(n\geq 3\). Supongamos que para cualesquiera dos vértices \(u\) y \(v\) no adyacentes se cumple que \(\deg(u)+\deg(v)\geq n\). Entonces, \(G\) tiene un ciclo hamiltoniano.
Aunque este resultado sea una condición suficiente para la existencia de un ciclo hamiltoniano, esta no es una condición necesaria. Por ejemplo, la gráfica ejemplo tiene un vértice de grado \(2\) y otro de grado \(3\), para los cuales claramente no se cumple que la suma sea mayor o igual a \(10\). Sin embargo, sí tiene un ciclo hamiltoniano.
Tarea moral#
Los siguientes problemas te ayudarán a practicar lo visto en esta entrada. Para resolverlos, necesitarás usar herramientas matemáticas, computacionales o ambas.
De acuerdo al teorema de Euler, la siguiente gráfica sí tiene un circuito euleriano. Encuéntralo. Como sugerencia, puedes usar las ideas de la demostración del teorema de circuitos eulerianos.
Una hormiga comienza en un vértice de un dodecahedro. Puede caminar sobre las aristas del dodecaedro para moverse de un vértice a otro. Muestar que la hormiga puede hacer un recorrido que pase una y sólo una vez por cada uno de los vértices del dodecaedro.
La gráfica completa \(K_8\) tiene puros vértices de grado impar, así que está «muy lejos» de tener un circuito euleriano. ¿Cuál es el circuito más largo que tiene?
Ya estudiamos cuándo una gráfica tiene un circuito euleriano. También dimos la definición de paseo euleriano. Pero, ¿cuándo tiene una gráfica un paseo euleriano? Esto puede obtenerse como corolario de lo que sabemos de circuitos eulerianos. Demuestra que una gráfica conexa \(G\) tiene un paseo euleriano si y sólo si tiene exactamente dos vértices de grado impar.
Encuenta ejemplos de lo siguiente:
Una gráfica con ciclo hamiltoniano pero sin circuito euleriano.
Una gráfica con circuito euleriano pero sin ciclo hamiltoniano.
Una gráfica con circuito euleriano y con ciclo hamiltoniano.
Una gráfica sin circuito euleriano ni ciclo hamiltoniano.
Demuestra el teorema de Ore. Como sugerencia, primero usa principio extremo para mostrar que existe una trayectoria hamiltoniana (considera la trayectoria de mayor longitud). Luego, realiza los ajustes necesarios para justificar cómo obtener un ciclo hamiltoniano a partir de esa trayectoria.