winbgim realizar programacion miniwin hacer graficos graficas graficar funciones ejemplos dev como circulo c++ xcode cocoa loops graph

c++ - realizar - winbgim ejemplos



Cómo encontrar bucles cerrados en redes de gráficos (2)

Tengo una red de gráficos no dirigida hecha de calles y cruces, y me gustaría saber si hay algún algoritmo que me ayude a encontrar bucles cerrados, es decir, lugares donde puedo colocar edificios. Cualquier ayuda apreciada, gracias!

Basado en los comentarios a mi respuesta anterior:

Parece que los gráficos son todos no dirigidos y planar, es decir, se pueden incrustar en un plano 2D sin cruzar bordes, y se da una incrustación. Esta incrustación dividirá el avión. Por ejemplo, una figura 8 divide el avión en tres: dos áreas "internas" y un área exterior infinita. Una vista alternativa es que todos los bordes de un nodo se ordenan cíclicamente. (Esta es la parte esencial que nos permite aplicar la teoría de grafos)

Una partición está necesariamente encerrada por un ciclo, pero no todos los ciclos pueden particionar un área individual. En el caso trivial de una figura 8, sin embargo, las tres áreas están directamente asociadas con un ciclo distinto.

El gráfico de entrada generalmente se puede simplificar. Algunos nodos pueden tener solo un borde; no pueden contribuir a la partición y pueden eliminarse junto con el borde. Otros nodos tienen dos bordes que conectan distintos nodos. Aquí, el nodo y los dos bordes se pueden reemplazar por un borde directo que conecta los vecinos. Es decir, un gráfico de la figura 8 se puede simplificar a dos nodos y tres bordes entre ellos. (Esto no es un paso necesario pero ayuda al cálculo).

Ahora, cada vértice tendrá dos áreas en cada lado (ya que no están dirigidas, "izquierda y derecha" no son distinciones obvias). Entonces, para |V| vértices, tenemos que considerar 2 * |V| lados. En general no son distintos. Dos bordes adyacentes (conectados al mismo nodo) pueden bordear la misma área, si también son adyacentes en el orden cíclico de los bordes de ese nodo. Obviamente, para los nodos con solo dos bordes, los dos bordes comparten ambas áreas (por eso los eliminamos en el paso anterior). Para nodos con tres bordes, dos bordes comparten al menos un área.

Entonces, aquí está cómo enumerar esas áreas: Asigne un número secuencial a todos los bordes y vértices. Asigna una dirección a cada borde para que se ejecute desde el borde de menor numeración hasta el más alto. Comience con el vértice 1, lado derecho, y numere esta área 1. Rastree los bordes de los límites de esta área, asignando el mismo número 1 a los lados apropiados de los bordes de los bordes. Para ello, toma en cada nodo el siguiente borde adyacente en orden contracíclico. Cuando regrese a su punto de partida, sabrá todos los bordes que delimitan el área 1.

Luego verifica el borde izquierdo del primer vértice. Si no es parte del área 1, entonces es el área 2, y aplica el mismo algoritmo. Luego, verifique el vértice 2, el lado derecho y el lado izquierdo, etc. Cada vez que encuentre un borde y un lado que aún no estén numerados, asigne el siguiente número de área y trace los bordes del área recién fundada.

Hay un pequeño problema para determinar qué número de área corresponde al infinito. Para ver esto, tome un gráfico simple (): dos bordes, dos nodos y dos áreas (interior y exterior). Debido a la numeración aleatoria de los bordes y vértices, afuera puede terminar como 1 o 2. Eso es inevitable; en teoría de grafos no hay distinción entre adentro y afuera.