15. Ciclos y circuitos

15.1 Introducción

Un recorrido es cerrado cuando comienza y termina en el mismo vértice. Dentro de esta familia encontramos circuitos y ciclos, que imponen restricciones sobre las aristas o vértices repetidos.

Detectar estas estructuras es importante para reconocer dependencias circulares, evitar bucles infinitos, estudiar circuitos físicos y encontrar recorridos que regresan al origen.

15.2 Terminología utilizada

Como ocurre con caminos y trayectorias, la terminología puede variar entre fuentes. En este curso utilizaremos:

15.3 Recorrido cerrado

Un recorrido cerrado es cualquier secuencia válida de longitud positiva cuyo primer y último vértice coinciden.

Puede repetir conexiones y vértices. Su única condición adicional respecto de un recorrido general es regresar al punto de partida.

15.4 Circuito y ciclo simple

Un circuito no repite aristas, aunque puede volver a visitar vértices internos. Un ciclo simple no repite ningún vértice salvo el que aparece al principio y al final.

Todo ciclo simple es un circuito, pero un circuito puede contener varios ciclos unidos por vértices comunes.

15.5 Simulación interactiva: cierra el recorrido

Selecciona vértices adyacentes y trata de regresar al nodo inicial. La aplicación clasificará la secuencia según las aristas y vértices repetidos.

Los dos triángulos comparten el vértice B. Puedes recorrer ambos sin repetir aristas para construir un circuito que no es un ciclo simple.

15.6 Longitud mínima de un ciclo

En un grafo simple no dirigido, un ciclo tiene al menos tres aristas.

En multigrafos pueden existir ciclos de longitud 2 mediante aristas paralelas, y si se admiten bucles puede considerarse un ciclo de longitud 1 según la convención.

15.7 Ciclos en grafos dirigidos

En un dígrafo, un ciclo debe respetar la orientación de todos los arcos y regresar al punto inicial.

Las dependencias circulares entre módulos o tareas forman ciclos dirigidos y pueden impedir un ordenamiento válido.

15.8 Grafos acíclicos

Un grafo que no contiene ciclos se denomina acíclico. Un grafo no dirigido conectado y acíclico es un árbol.

15.9 Importancia en programación

• Detectar dependencias circulares entre paquetes o módulos.
• Evitar recorridos infinitos al explorar grafos.
• Encontrar rutas que regresan al origen.
• Analizar circuitos eléctricos y redes de flujo.
• Reconocer estados repetidos en juegos y sistemas.
• Validar si es posible realizar un ordenamiento topológico.

15.10 Comprobar si una secuencia es un ciclo

function esCicloSimple(secuencia) {
  if (secuencia.length < 4) return false;
  if (secuencia[0] !== secuencia[secuencia.length - 1]) return false;

  const verticesInternos = secuencia.slice(0, -1);
  return new Set(verticesInternos).size === verticesInternos.length;
}

console.log(esCicloSimple(["A", "B", "C", "A"]));
console.log(esCicloSimple(["A", "B", "C", "B", "A"]));

15.11 Detectar ciclos durante DFS

En un grafo no dirigido, encontrar un vecino ya visitado que no sea el padre del vértice actual indica un ciclo.

function tieneCiclo(grafo, actual, padre, visitados = new Set()) {
  visitados.add(actual);

  for (const vecino of grafo[actual]) {
    if (!visitados.has(vecino)) {
      if (tieneCiclo(grafo, vecino, actual, visitados)) return true;
    } else if (vecino !== padre) {
      return true;
    }
  }
  return false;
}

const grafo = { A: ["B", "C"], B: ["A", "C"], C: ["A", "B"] };
console.log(tieneCiclo(grafo, "A", null));

15.12 Errores comunes

• Considerar ciclo cualquier recorrido que repita un vértice.
• Olvidar que el primer y último vértice deben coincidir.
• Contar dos veces el vértice inicial como repetición interna.
• Confundir circuito con ciclo simple.
• Ignorar la orientación de los arcos en ciclos dirigidos.
• Detectar falsos ciclos en DFS por no excluir la arista hacia el padre.

15.13 Qué debes recordar de este tema

• Un recorrido cerrado comienza y termina en el mismo vértice.
• Un circuito es una trayectoria cerrada sin aristas repetidas.
• Un ciclo simple no repite vértices salvo el inicial al final.
• Todo ciclo es un circuito, pero no todo circuito es un ciclo simple.
• Los grafos sin ciclos se denominan acíclicos.
• Los ciclos dirigidos representan dependencias circulares y estados recurrentes.

15.14 Conclusión

Los ciclos y circuitos describen formas de recorrer un grafo y volver al origen. Las restricciones sobre repeticiones permiten distinguir estructuras simples de recorridos cerrados más complejos.

En el próximo tema estudiaremos la conectividad y analizaremos cuándo todos los vértices pueden alcanzarse entre sí.