¿Referencia para el algoritmo de prueba de aciclicidad de gráfico mixto?

16

Un gráfico mixto es un gráfico que puede tener bordes tanto dirigidos como no dirigidos. Su gráfico subyacente no dirigido se obtiene olvidando las orientaciones de los bordes dirigidos, y en la otra dirección se obtiene una orientación de un gráfico mixto al asignar una dirección a cada borde no dirigido. Un conjunto de aristas forma un ciclo en un gráfico mixto si puede orientarse para formar un ciclo dirigido. Un gráfico mixto es acíclico si y solo si no tiene ciclos.

Todo esto es estándar y hay muchos artículos publicados que mencionan gráficos mixtos acíclicos. Por lo tanto, se debe conocer el siguiente algoritmo para probar la aciclicidad de gráficos mixtos:

Repita los siguientes pasos:

  • Elimine cualquier vértice que no tenga bordes dirigidos entrantes y sin bordes incidentes no dirigidos, ya que no puede ser parte de ningún ciclo.
  • Si algún vértice no tiene bordes dirigidos entrantes pero tiene exactamente un borde incidente no dirigido, entonces cualquier ciclo que use el borde no dirigido debe entrar en ese borde. Reemplace el borde no dirigido por un borde dirigido entrante.

Deténgase cuando no se puedan realizar más pasos. Si el resultado es un gráfico vacío, entonces el gráfico original necesariamente debe haber sido acíclico. De lo contrario, comenzando desde cualquier vértice que quede, uno puede retroceder a través del gráfico, en cada paso siguiendo hacia atrás a través de un borde entrante o siguiendo un borde no dirigido que no es el utilizado para alcanzar el vértice actual, hasta ver un vértice repetido. La secuencia de aristas seguida entre la primera y la segunda repetición de este vértice (en orden inverso) forma un ciclo en el gráfico mixto.

El artículo de Wikipedia sobre gráficos mixtos menciona gráficos mixtos acíclicos, pero no menciona cómo probarlos, por lo que me gustaría agregarle algo sobre este algoritmo, pero para eso necesito una referencia publicada. ¿Alguien puede decirme dónde aparece (o cualquier otro algoritmo para probar la aciclicidad) aparece en la literatura?

ds.algorithms reference-request graph-theory graph-algorithms directed-acyclic-graph David Eppstein
fuente
¿Qué sucede cuando un vértice tiene dos bordes incidentes no dirigidos y ningún otro borde? Por ejemplo en un triángulo no dirigido. Quiero decir, ¿las reglas anteriores cubren este caso?
Mateus de Oliveira Oliveira
No puede hacer nada acerca de tal vértice hasta que otro vértice diferente aplique la regla que orienta uno de los bordes. Si te quedas atascado en una situación en la que existen tales vértices y no puedes aplicar más reglas, entonces tu gráfico contiene un ciclo.
David Eppstein
Tal vez sería más claro considerar lo que sucede en el caso de que su gráfico no esté dirigido. Una forma de probar si se trata de un bosque es eliminar las hojas (vértices de grado uno) y los vértices aislados hasta obtener un gráfico vacío (es un bosque) o un núcleo no trivial de 2 núcleos (un subgrafo en el que todos los vértices tienen un grado ≥ 2, que necesariamente contiene un ciclo). El algoritmo de gráfico mixto degenera a esto en el caso no dirigido (excepto que orienta las hojas en lugar de eliminarlas inmediatamente), así como degenera a un algoritmo de clasificación topológica estándar en el caso dirigido.
David Eppstein
No estoy seguro si lo has visto: hay una publicación en cs.stackexchange que hace una pregunta similar ref . El respondedor da un algoritmo para encontrar un ciclo en un gráfico mixto orientando los bordes no dirigidos, rechazando el gráfico si no existe. También hay documentos sobre la determinación de si un gráfico mixto es fuertemente orientable ref pero, extrañamente, no pudo encontrar nada sobre encontrar componentes conectados en gráficos mixtos.
Quanquan Liu
Gracias, no, no había visto eso. La pregunta "encontrar una orientación para hacer que el gráfico contenga un ciclo dirigido" es definitivamente la misma, y ​​el algoritmo en la respuesta parece correcto. Pero a diferencia del que describo, no es tiempo lineal.
David Eppstein

Respuestas:

1

Encontrar ciclos mixtos en un gráfico mixto es equivalente a encontrar ciclos dirigidos elementales (de longitud> = 3) en el gráfico dirigido correspondiente. El gráfico dirigido correspondiente se obtiene del gráfico mixto reemplazando cada borde no dirigido por dos bordes dirigidos que apuntan en direcciones opuestas. Prueba: (1) Cada ciclo dirigido elemental (de longitud> = 3) en el dígrafo corresponde directamente a un ciclo mixto en el gráfico mixto. (2) Cada ciclo mixto en el gráfico mixto contiene un ciclo mixto elemental de longitud> = 3, y cada ciclo corresponde directamente a un ciclo dirigido elemental (de longitud> = 3) en el gráfico dirigido. (1) y (2) juntos prueban ambas direcciones de la declaración, qed. Por lo tanto, estamos buscando referencias sobre cómo calcular (¿todo?) Ciclos elementales (de longitud> = 3) en un gráfico dirigido.

Los comentarios indican que cs.stackexchange contiene algunas respuestas a esta pregunta, pero no está claro cómo organizar los resultados en una respuesta concisa. Esta publicación de blog parece resumir muy bien las (¿más?) Referencias importantes:

Algoritmo de R. Tarjan

El primer algoritmo que incluí fue publicado por R. Tarjan en 1973.

Enumeration of the elementary circuits of a directed graph
R. Tarjan, SIAM Journal on Computing, 2 (1973), pp. 211-216
http://dx.doi.org/10.1137/0202017

Algoritmo de DB Johnson

El algoritmo de DB Johnson de 1975 mejora el algoritmo de Tarjan por su complejidad.

Finding all the elementary circuits of a directed graph.
D. B. Johnson, SIAM Journal on Computing 4, no. 1, 77-84, 1975.
http://dx.doi.org/10.1137/0204007

En el peor de los casos, el algoritmo de Tarjan tiene una complejidad temporal de O (n⋅e (c + 1)) mientras que el algoritmo de Johnson supuestamente logra permanecer en O ((n + e) ​​(c + 1)) donde n es el número de vértices, e es el número de aristas yc es el número de ciclos en el gráfico.

Algoritmo de KA Hawick y HA James

El algoritmo de KA Hawick y HA James de 2008 mejora aún más el algoritmo de Johnson y elimina sus limitaciones.

Enumerating Circuits and Loops in Graphs with Self-Arcs and Multiple-Arcs.
Hawick and H.A. James, In Proceedings of FCS. 2008, 14-20
www.massey.ac.nz/~kahawick/cstn/013/cstn-013.pdf
http://complexity.massey.ac.nz/cstn/013/cstn-013.pdf

A diferencia del algoritmo de Johnson, el algoritmo de KA Hawick y HA James es capaz de manejar gráficos que contienen bordes que comienzan y terminan en el mismo vértice, así como múltiples bordes que conectan los mismos dos vértices.

La prueba de aciclicidad en sí misma parece ser fácil: calcule los componentes fuertemente conectados del gráfico. Cualquier ciclo (elemental) está completamente contenido en un componente fuertemente conectado. Un componente fuertemente conectado contiene un ciclo elemental si no es un árbol no dirigido.

El algoritmo propuesto por David Eppstein calcula adicionalmente un ciclo elemental como evidencia, y los algoritmos anteriores enumeran todos los ciclos elementales. Cualquier vértice o borde no contenido en un ciclo elemental podría eliminarse como un paso de preprocesamiento para mejorar la velocidad de los algoritmos anteriores. El algoritmo de David Eppstein podría usarse para ese propósito, pero incluso si solo se usa en los componentes fuertemente conectados, no eliminará todos los vértices o bordes posibles que se pueden eliminar. Pero incluso si se pudiera extender para hacerlo (calcular el árbol de corte de bloque al menos permite eliminar todos los vértices posibles que se pueden eliminar), no está claro si esto realmente mejoraría la velocidad de los algoritmos anteriores.

Thomas Klimpel
fuente
¿Alguna de esas referencias menciona gráficos mezclados? Sé sobre encontrar ciclos en gráficos dirigidos. Mi pregunta fue sobre extensiones de esos algoritmos a gráficos mixtos.
David Eppstein
@DavidEppstein Encontrar ciclos mixtos en un gráfico mixto es equivalente a encontrar ciclos elementales (de longitud> = 3) en el gráfico dirigido correspondiente. Encontrar una referencia para esa afirmación puede ser un desafío, pero probar esta afirmación es sencillo. Ahora agregué la declaración y su prueba a la respuesta. (También se agregó una observación sin pruebas de que calcular el árbol cortado en bloque permite eliminar todos los vértices posibles que se pueden eliminar sin afectar los ciclos elementales).
Thomas Klimpel,
Ok, pero tampoco son de tiempo lineal.
David Eppstein
@DavidEppstein La prueba de aciclicidad se realiza en tiempo lineal. Pero tiene razón, el tiempo que cualquiera de esos algoritmos necesita para encontrar el primer circuito elemental (de longitud> = 3) no es lineal (en el peor de los casos). Peor aún, la mayoría de las implementaciones disponibles del algoritmo de Johnson parecen usar más del tiempo O ((n + e) ​​(c + 1)), cuando se aplican a un solo círculo dirigido (con n vértices, e = n aristas y c = 1 elemental ciclos). Aún así, se suponía que era una respuesta correcta, porque el artículo de Johnson parece ser la referencia más citada para "encontrar circuitos elementales".
Thomas Klimpel