Caminos cerrados, circuitos y ciclos#
Introducción#
Anteriormente hablamos de caminos, paseos y trayectorias. Estos conceptos indicaban distintas formas en las que podemos ir de un vértice a otro en una gráfica a través de aristas. En ocasiones, nos interesará estudiar lo que sucede no sólo cuando vamos de un vértice a otro distinto, sino también cuando comenzamos en un vértice, paseamos por otros y finalmente regresamos al inicial. Este tipo de recorridos se llaman caminos cerrados, circuitos o ciclos, dependiendo de las propiedades que cumplen.
En las aplicaciones hay situaciones en las que nos interesan estos conceptos. Un ejemplo de esto sería un camión que comienza en un punto de distribución, que tiene que repartir mercancía a distintas tiendas y que al final de la repartición debe regresar al punto original. Otro posible ejemplo es tomar una gráfica en donde los vértices son personas y las aristas indican que son amigos. Un ciclo en esta gráfica indica que podemos sentar a esas personas alrededor de una mesa redonda de modo que cada quien sea amigo de su vecino.
Caminos cerrados, circuitos y ciclos#
De manera informal, los caminos cerrados, los circuitos y los ciclos nos ayudan a saber «cómo se puede comenzar y terminar en un mismo vértice de una gráfica» ya sea sin restricciones, o con algunas restricciones.
Definición. Sea \(G\) una gráfica y \(n\geq 3\) un número entero. Un camino cerrado es una sucesión \(v_1,v_2,\ldots, v_n, v_{n+1}\) en donde \(v_iv_{i+1}\) es una arista de \(G\) para cada \(i\in\{1,\ldots,n\}\), y además \(v_1=v_{n+1}\). A \(n\) le llamamos la longitud del camino cerrado.
En otras palabras, un camino cerrado es un camino de longitud al menos \(3\) que empieza y termina en el mismo vértice. De hecho, al vértices \(v_1\) y al \(v_{n+1}\) los pensaremos como «la misma aparición del vértice», de modo que en un camino cerrado de longitud \(n\) aparecen \(n\) vértices y se tiene una estructura cíclica.
Así como en el caso de los caminos, también tenemos nociones más restrictivas que impiden que se repitan aristas o vértices.
Definición. Sea \(G\) una gráfica.
Un circuito es un camino cerrado con todas sus aristas distintas.
Un ciclo es un camino cerrado con todos sus vértices distintos.
Recordemos que estamos identificando la primera y la última aparición del primer vértice, así que esta repetición no entra en conflicto con la definición de ciclo.
Ejemplo. Consideremos la siguiente gráfica:
Un posible camino cerrado es el \(a,i,d,c,a\), el cual mostramos a continuación:
Sus vértices son \(a,i,d,c\), sus aristas son \(ai, id, dc, ca\). El camino cerrado tiene longitud \(4\). Como no repite vértices (salvo el primero y el último), entonces es ciclo. Como no repite aristas, entonces es circuito. Hay un poco de abigüedad, pues también pudimos haberle llamado el camino cerrado \(i,d,c,a,i\) o incluso recorrerlo en sentido contrario para escribir \(c,d,i,a,c\). Casi siempre pensaremos a todos estos como el mismo camino cerrado, aunque la notación escrita sea diferente.
Otro posible camino cerrado es \(a,i,d,g,a,i,h,a\). Empieza y termina en el mismo vértice y tiene longitud 7. Sin embargo, tiene repeticiones. El vértice \(a\) se repite más allá del principio y el final. Se pasa dos veces por la arista \(ai\). Entonces este camino cerrado no es ni ciclo, ni circuito. Si intentamos hacer una figura, obtenemos un resultado algo confuso, en el cual se pierde la información del orden en el que estamos recorriendo los vértices.
Hay que tener cuidado con hacer dibujos de caminos cerrados que no sean ciclos.
¿Podrás encontrar en esta misma gráfica un camino cerrado que sí sea un circuito, pero que no sea un ciclo? \(\square\)
Una vez más, si un camino cerrado repite aristas, entonces debe repetir vértices. De este modo, si no repite vértices entonces no repite aristas. Concluimos lo siguiente.
Proposición. Todo ciclo es un circuito.
Así, cualquier ciclo es circuito y cualquier circuito es un camino cerrado. ¿Qué podemos concluir de la existencia de un camino cerrado? Si no suponemos algo más, en realidad no podemos obtener mucho. Considera, por ejemplo, la siguiente gráfica.
En esta gráfica tenemos el camino cerrado \(j,c,g,d,g,c,f,c,j\), sin embargo, en la gráfica no hay ni un solo ciclo. En los ejercicios se da una condición que sí nos permite encontrar un ciclo.
Ciclos inducidos y cuello#
En algunas ocasiones nos interesará encontrar en una gráfica ciclos que no puedan acortarse «tomando como atajo» la arista entre dos vértices.
Definición. Un ciclo inducido en una gráfica es un ciclo tal que las únicas aristas de \(G\) entre los vértices que conforman al ciclo son exactamente las aristas del ciclo.
Así mismo, en alguanas ocasiones nos interesará encontrar el ciclo más chico posible en una gráfica.
Definición. El cuello de una gráfica es la longitud de un ciclo de la menor longitud posible.
Ejemplo. Consideremos la gráfica de la izquierda en la siguiente figura. En ella hemos indicado un ciclo verde y un ciclo azul. El ciclo verde sí es un ciclo inducido, pues no existe ninguna arista que una vértices del ciclo verde. Sin embargo, el ciclo azul no es un ciclo inducido, pues a la derecha podemos ver que la artista roja une dos vértices del ciclo azul.
Nota que la arista roja y las dos aristas azules con las que completa un triángulo conforman un ciclo de longitud \(3\). Así, esta es una gráfica con cuello \(3\). Si quitáramos la arista roja, ¿cuál sería el cuello de la gráfica?
\(\square\)
Los ciclos inducidos y el cuello están muy relacionados entre sí mediante la siguiente proposición.
Proposición. Sea \(G\) una gráfica de cuello \(k\). Si \(C\) es un ciclo de \(G\) de longitud \(k\), entonces \(G\) es un ciclo inducido.
Demostración. Supongamos que el ciclo \(C\) es \(v_1,v_2,\ldots,v_k,v_1\). Para buscar una contradicción, suponemos que \(C\) no es inducido. Así, existe una arista de \(G\) entre dos vértices \(v_i\) y \(v_j\) con \(i\geq 1\) y \(i+2\leq j \leq k\). Pero en ese caso, \(v_1,v_2,\ldots,v_i,v_j,v_{j+1},\ldots,v_k,v_1\) es un ciclo de \(G\) de longitud \(k-(j-i+1)\leq k-1\), lo cual es una contradicción a que el cuello de la gráfica sea \(k\). \(\square\)
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.
Considera la siguiente gráfica
¿Puedes encontrar un ciclo que pase por todos los vértices? Si no, intenta encontrar uno que pase por la mayor cantidad posible.
¿Puedes encontrar un circuito que pase por todas las aristas? Si no, intenta encontrar uno que pase por la mayor cantidad posible.
Determina el cuello de la gráfica.
La siguiente gráfica muestra las amistades entre \(12\) personas: cada vértice es una persona y hay una arista entre dos personas si son amigas. Se quiere sentar a estas personas en tres mesas circulares. Cada mesa tendrá cuatro personas. Encuentra una manera de hacer esto de forma que cada persona quede sentada al lado de alguno de sus amigos.
Demuestra que si una gráfica tiene un camino cerrado de orden impar, entonces también tiene un ciclo de orden impar. ¿Es cierta esta afirmación cuando el orden del ciclo es par? ¿Se puede garantizar aunque sea la existencia de un ciclo?
Retomemos la gráfica \(G\) de la sección anterior, cuyos vértices son los números de \(50\) a \(100\) y hay arista entre dos números si hay un número primo que divide a ambos. Encuentra un ciclo lo más grande posible en \(G\).
En una gráfica se sabe que hay un camino cerrado de longitud \(5\) y un camino cerrado de longitud \(7\). Se sabe que, además, estos caminos tienen un vértice en común. Demuestra que en esta gráfica es posible encontrar caminos cerrados de longitud \(n\) para toda \(n\geq 24\). ¿Y para longitudes menores puedes garantizar que existen siempre? ¿Para cuáles longitudes sí existen y para cuáles no?