Encontrar todos los ciclos (caras) de un gráfico

Question

Tengo un gráfico $G$ con una lista de aristas $E$ , todas las aristas pueden formar ciclos, como se muestra a continuación:

Todas las coordenadas del vértice $V$ son conocidos .

Wat es el algoritmo para encontrar todas las caras $F$ ? En el ejemplo anterior, hay 4 caras de este tipo, como indica la flecha en forma de bucle.

Actualización: ¿Por qué el algoritmo para encontrar la cara en el caso sin coordenadas es diferente del que tiene coordenadas? Simplemente porque al especificar las coordenadas hay un único conjunto de caras, y sin coordenadas podría haber conjuntos de caras que son topológicamente iguales. Véase el siguiente diagrama:

Actualización 2: Aclarar la terminología

Actualización 3: Se sugiere que construya una lista enlazada cíclicamente en cada vértice, ordenada según los ángulos realizados entre la arista entrante y la saliente. Entonces sólo habría que continuar a lo largo de la arista, pero me temo que este algoritmo no funciona con el llamado grafo mariposa. Consideremos este grafo:

Supongamos que empezamos en $e_1$ y la flecha indica la dirección del movimiento. Si tomamos como orientación el giro a la izquierda, entonces estaríamos visitando $v_1$ dos veces antes de completar un ciclo y el ciclo no es realmente un ciclo.

Answer 1

En su pregunta anterior Se ha hecho un mejor uso de la terminología de la teoría de grafos: se refiere al grafo como planar y a una base de ciclos.

Suponiendo que entiendas esos términos, quizás pueda señalar cómo la respuesta de Mariano se basa en el problema anterior. De hecho aquí preguntaste: "¿Por qué el algoritmo para encontrar la cara en el caso sin coordenadas es diferente al que tiene coordenadas?" Aunque probablemente esto sea retórico para explicar tu suposición "Se conocen todas las coordenadas de los [vértices]", es importante señalar que las "caras" que has pedido encontrar dependerán de dónde estén las aristas además de dónde estén los vértices.

Ilustremos con el gráfico completo de cuatro vértices $K_4$ . Definamos las coordenadas planas de los vértices como esquinas del cuadrado unitario {(0,0),(1,0),(1,1),(0,1)}. Habrá cuatro aristas, pero no podemos tomar todas ellas como segmentos de línea recta en el plano, ya que al hacerlo se produce una intersección (algo que una incrustación plana del grafo no permite).

De hecho, dependiendo de cómo conectes los vértices, obtendrás diferentes caras. Dibuja dos cuadrados (con cuatro aristas cada uno), y conecta un par de vértices "diagonales" dentro de un cuadrado y el otro par dentro del otro cuadrado. Ahora completa ambos gráficos con una arista exterior que conecte los pares diagonales restantes, haciendo un bucle por encima del cuadrado en un caso y por debajo del cuadrado en el otro. Dos (o más) casos con diferentes disposiciones de "caras".

La cuestión es que conocer una incrustación plana lo suficientemente bien como para que la base del ciclo de "caras" que buscas sea única requiere que "conozcas las coordenadas" de las aristas además de los vértices.

La respuesta de Mariano se centra en los bordes. Esto tiene el bonito efecto de permitirnos contar cada arista como perteneciente a exactamente dos ciclos o caras, una por cada dirección que recorre la arista. [No es posible hacer una afirmación tan sencilla para el número de caras en las que aparece un vértice]. Sin embargo, para que ese "dos ciclos por arista" funcione, debemos incluir la "cara no limitada" o el ciclo que recorre todo el exterior del grafo plano. En el caso más sencillo, un triángulo por ejemplo, tenemos un ciclo que lo rodea en el sentido de las agujas del reloj (siguiendo la dirección que has utilizado en tus diagramas de arriba). Para que cada arista aparezca dos veces, una en cada dirección, necesitamos obtener un ciclo en sentido contrario a las agujas del reloj. Puedes pensar que una es la cara "finita" delimitada por el triángulo, y la otra es la cara correspondiente a la región no delimitada fuera del triángulo.

Cuando le pides a Mariano que te diga cómo "ordenar las aristas cíclicamente", supongo que hay dos aspectos. Uno es entender lo que quiere decir con eso, y el otro es conectar esta tarea con la forma de "conocer las coordenadas" del gráfico incluyendo sus aristas.

Lo que Mariano quiere decir es que, cuando lleguemos a un vértice a lo largo de una "arista de entrada", ¿cuál será la "arista de salida" correcta que debemos tomar a continuación? Supongamos que se quiere construir todas las caras "finitas" que van en el en el sentido de las agujas del reloj dirección, como en sus diagramas. Entonces tendría que ordenar el bordes alrededor de cada vértice en una "lista" enlazada cíclicamente que recorre el vértice en el en sentido contrario a las agujas del reloj dirección. Esta "lista" se envuelve; no tiene un borde inicial o final específico. Tampoco distingue las direcciones de desplazamiento a lo largo de la arista. Sólo nos dice, para todas las aristas de un vértice dado, cuál sigue a cuál yendo en sentido contrario a las agujas del reloj alrededor del vértice.

Ahora podemos elaborar la solución de Mariano a tu pregunta. Para cada arista y cada sentido de la marcha a lo largo de esa arista, construye un ciclo mediante este algoritmo:

Algoritmo FollowYourNose
(1) Sigue la arista dada en la dirección dada hasta su vértice final.
(2) Consultar la lista enlazada cíclicamente de aristas en ese vértice para determinar la siguiente arista.
(3) Repita los pasos (1) y (2) hasta volver al borde original.
(4) Detente. Has construido un ciclo que utiliza la arista y la dirección dadas.

Cuando hayas hecho esto para cada arista y cada dirección, tendrás una lista de ciclos que contiene duplicados. Si un ciclo contiene $k$ bordes, habrás construido ese mismo ciclo $k$ tiempos. Descarta los duplicados, dejando sólo una copia de cada ciclo. [Si es importante por razones de rendimiento, podríamos llevar la cuenta de qué aristas han sido recorridas en qué direcciones y evitar preventivamente la creación de los duplicados].

Entonces te quedará una copia del ciclo que corresponde a la cara no limitada, el exterior del gráfico plano. Se quiere eliminar que también. Donde todos los ciclos que corresponden a las caras acotadas van en el sentido de las agujas del reloj, el ciclo que corresponde a la cara no acotada va en el sentido contrario. De hecho es algebraicamente menos la suma de todos los ciclos de la cara de las agujas del reloj/del límite.

Añadido: Una lista enlazada cíclicamente (o algunos escribirían, lista enlazada cíclica) es un caso especial de una lista enlazada . Significa que la lista enlazada da vueltas en ciclo o bucle. Aquí no se pretende confundir con los "ciclos" del grafo. Simplemente pedimos alguna forma concreta de determinar sistemáticamente cómo continuar un camino en el grafo con cada vértice al que llegamos. Una descripción informal sería decir "seguir a la derecha en cada intersección". Por supuesto, esto nos llevará a dar la vuelta a la manzana en términos de tráfico ordinario, y tiene un efecto similar en la navegación de un grafo plano.

Lo que Mariano propuso fue responder a la pregunta de "por dónde ir" ordenando las aristas que inciden en cada vértice en un orden correspondiente a los ángulos con los que llegan al vértice. Piensa que estás en una intersección (vértice) de dos o más calles (aristas). Enuméralas (las aristas o calles) en el orden en el que aparecen al girar en sentido contrario a las agujas del reloj durante una revolución, y utiliza esa lista/ordenación en el algoritmo esbozado por Mariano, de modo que cuando entres en una intersección (vértice) por una calle (arista), salgas por la siguiente de la lista (¡a la derecha!).

También hay que tener un poco de cuidado con el tipo de grafo planar al que se aplica el algoritmo. Si estás dispuesto a aceptar ciertas degeneraciones, entonces el grafo plano es suficiente. Pero consideremos el caso de una sola arista que conecta dos vértices. ¿Cuál es la cara?

Si desea evitar estas degeneraciones, suponga un grafo plano simple que esté conectado en 2 ocasiones. Lo que significa que el gráfico está conectado y permanece conectado incluso después de eliminar una arista. "Simple" significa que no hay "auto-borde" (arista que conecta un vértice consigo mismo) ni múltiples aristas que conecten un mismo par de vértices.

Respecto a la actualización 3: No se sugiere que ordene las aristas "según los ángulos formados entre la arista entrante y la saliente". Se te pide que hagas para cada vértice una lista de las aristas ordenadas en sentido contrario a las agujas del reloj alrededor de ese vértice (una lista circular si quieres), sin tener en cuenta las entrantes o salientes. En tu gráfico de mariposas sólo hay un vértice con más de dos aristas, por lo que sólo la lista de ese vértice requiere cuidado en la ordenación.

Ejemplos de trabajo con el gráfico de mariposa

Consideremos en primer lugar una incrustación planar del grafo de la mariposa similar a la que formaba parte de la Pregunta:

   v2    v3    +e1: (x,v1)  -e1: (v1,x)  
    |\   /|    +e2: (x,v2)  -e2: (v2,x)  
    | \ / |    +e3: (x,v3)  -e3: (v3,x)  
    |  X  |    +e4: (x,v4)  -e4: (v4,x)  
    | / \ |    +e5: (v1,v2) -e5: (v2,v1)  
    |/   \|    +e6: (v3,v4) -e6: (v4,v3)  
   v1    v4  

He utilizado los signos más y menos para asignar (arbitrariamente) las direcciones de cada una de las seis aristas. Sólo el vértice central x tiene más de dos aristas incidentes, por lo que seré explícito a la hora de ordenar las aristas (sin tener en cuenta la dirección de entrada o salida) en orden antihorario alrededor de x :

...e4,e3,e2,e1,e4,...

Debe quedar claro que se trata de un circular que se repite, recorriendo el mismo orden de aristas una y otra vez, lo que en estructuras de datos representaríamos como una lista enlazada cíclicamente. Para ello no hace falta nada más que el aparato estándar de las listas enlazadas. Simplemente se hace que el último nodo de la lista enlazada apunte de nuevo al primer nodo de la lista enlazada, y voilá, una lista enlazada cíclicamente. Pero no confundamos los detalles de la implementación con los detalles del algoritmo. Todo lo que el algoritmo requiere es cómo encontrar la siguiente arista en un vértice que está en sentido contrario a las agujas del reloj desde una arista dada en ese vértice. Una lista enlazada cíclicamente hace esa función, en el sentido de que buscaríamos en la lista linealmente la arista dada en el vértice dado, y luego tomaríamos la siguiente arista en la lista.

Como hay seis aristas, hay doce aristas dirigidas, por lo que aplicaremos el algoritmo SigueTuNariz doce veces (una por cada arista dirigida). Cada vez obtendremos un ciclo (un bucle en las aristas). Los ciclos pueden visitar un vértice más de una vez, pero nunca utilizarán una arista más de una vez (suponiendo que el grafo plano es simple y está conectado por 2). Sin embargo, los doce resultados contendrán duplicados. Una vez eliminados los duplicados, sólo quedan tres ciclos únicos:

[+e1,+e5,-e2]

[+e3,+e6,-e4]

[-e1,+e4,-e6,-e3,+e2,-e5]

De los diagramas proporcionados en la pregunta se desprende que las "caras" son las componentes acotadas del plano una vez eliminadas las aristas del grafo incrustado (desconectando así el plano en una componente no acotada y otras finamente acotadas). Por lo tanto, debemos eliminar de la lista de tres ciclos anterior el que corresponde a la frontera de la componente no acotada.

Esta distinción puede hacerse algorítmicamente sobre la orientación de los ciclos en el sentido de las agujas del reloj o en sentido contrario. Los ciclos que dan "caras" van en el sentido de las agujas del reloj alrededor de sus componentes acotados. Los ciclos que dan "caras" van en el sentido de las agujas del reloj alrededor de sus componentes acotados. En este caso es el tercer ciclo el que hay que descartar.

Para ilustrar cómo la distinción se hace sobre la base de la orientación de las agujas del reloj, y no sobre algún otro criterio como qué ciclo tiene mayor longitud, veamos otra incrustación del gráfico de mariposas:

           _ x _              +e1: (x,v1)  -e1: (v1,x)  
         _/ / \ \_            +e2: (x,v2)  -e2: (v2,x)  
       _/  /   \  \_          +e3: (x,v3)  -e3: (v3,x)  
     _/   v2___v1   \_        +e4: (x,v4)  -e4: (v4,x)  
    /                 \       +e5: (v1,v2) -e5: (v2,v1)  
   v4_________________v3      +e6: (v3,v4) -e6: (v4,v3)  

He tenido cuidado de que el etiquetado de las aristas con respecto a los vértices sea el mismo aquí, así como las orientaciones de los dos triciclos en el plano sean las mismas. El algoritmo producirá ahora un resultado diferente basado en el cambio en la forma en que las aristas inciden en el vértice x se ordenan en sentido contrario a las agujas del reloj alrededor de ese vértice:

...e4,e2,e1,e3,e4,...

De nuevo aplicaremos el algoritmo SigueTuNariz a cada una de las doce aristas dirigidas y obtener doce ciclos, incluyendo los duplicados. Después de eliminar los duplicados quedan los siguientes tres ciclos:

[+e1,+e5,-e2]

[+e3,+e6,-e4,+e2,-e5,-e1]

[+e4,-e6,-e3]

Se deja al lector que verifique cuál de ellos tiene orientación contraria a las agujas del reloj y que no es el más largo de los tres ciclos. El que tiene la orientación contraria a las agujas del reloj es el "más exterior" y, por tanto, el límite de la componente no limitada del plano \graph.

Answer 2

Considera que tu gráfica está incrustada en el plano. Y piensa que una arista no orientada es un par de arcos orientados en direcciones opuestas.

Elige un arco orientado $a$ . Hay una única cara cuyo límite, cuando se dibuja en sentido contrario a las agujas del reloj, "contiene" $a$ y en ese límite $a$ es seguido por un arco bien definido $b$ .

Para construir las caras, basta con poder decidir para cada $a$ lo que el correspondiente $b$ es. Esto puede hacerse fácilmente ordenando cíclicamente las aristas incidentes en cada vértice.

Answer 3

Este fue mi proyecto no hace mucho tiempo.

Lo resolví de más de una manera. Pero te presentaré el más fácil de los métodos que utilicé. Utilizar el relleno rápido dentro de una región. Luego encontrar las líneas que bordean la región.

Falla en ciertas situaciones, sin embargo, en la mayoría de los casos, esas situaciones no son tan graves de todos modos. Si este método falla para usted, vuelva a publicar y voy a compartir los otros métodos que he utilizado.