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
Un paseo euleriano de
es un paseo de que pasa por todas las aristas.Un circuito euleriano de
es un circuito de 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
Proposición. Si
Demostración. Con el fin de encontrar una contradicción, supongamos que
Hay otra observación crucial sobre una propiedad que debe cumplir una gráfica para poder tener un circuito euleriano.
Proposición. Si
Demostración. Supogamos que
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
tiene a lo más una componente conexa de al menos dos vértices.Todos los grados de los vértices de
son pares.
Demostración. Las dos proposiciones anteriores demuestran «la ida» del teorema: si
El primer caso es
Supongamos que el resultado es cierto para cuando tenemos menos de
Si
Ser una
de un sólo vértice. Aquí declaramos al único vértice.Ser una
de al menos dos vértices, todos ellos con grado par y entonces por hipótesis inductiva tiene un circuito euleriano
Como
Ciclos Hamiltonianos#
En la sección anterior estudiamos cuándo hay circuitos eulerianos.
Definición. Sea
Una trayectoria hamiltoniana de
es una trayectoria de que pasa por todos los vértices.Un ciclo hamiltoniano de
es un ciclo de 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.
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
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
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
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
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.