Intro: Estoy trabajando en una ingeniería del mundo real problema que puede ser traducido a un grafo no dirigido. Soy un ingeniero aeroespacial, así que quizás yo no sé/el uso correcto de los términos matemáticos para describir mi problema, lo siento por eso :)
Problema: En este gráfico necesito para detectar todos 'el más pequeño de los ciclos", es decir, todos los ciclos que no contienen otros ciclos. Mi aplicación no es de tiempo crítico, o más específicamente en el gráfico la voy a cargar en son pequeños (<1000 nodos con ~4 bordes por nodo), y se analizan sólo una vez, así que el tiempo de procesamiento no es un problema real. Tengo dos preguntas.
1 - En el ciclo de detección
He encontrado ya cómo detectar todos los ciclos en un gráfico, haciendo un DFS para encontrar el ciclo de base para la gráfica, a partir de la cual todos los demás ciclos se pueden encontrar por XOR-ción de la incidencia de los vectores.
En esta imagen he de empezar con el gráfico 1. Quiero que mi algoritmo para volver finalmente subdiagramas (ciclos) 2 y 3, pero no de 4.
Aquí está una foto, no estoy permitido a publicar como una imagen sin embargo, debido a que yo sea un usuario nuevo :( https://www.dropbox.com/s/xwwpve2j1tncwy4/graph_question.jpg
Si ese enlace no funciona: http://s9.postimage.org/6o0idbt27/graph_question.jpg
Creo que necesitan esencialmente una forma de detectar si un nodo está contenida en una región que se describen por un ciclo, por ejemplo, que el centro de nodo " en mi dibujo está contenida en el ciclo 4 ¿algún consejo?
Edit: estoy buscando Circuitos aparentemente, la cual me enteré gracias a Hans Engler la respuesta!
2 - Bono: borde intersecciones
En los modelos que voy a analizar es improbable pero posible que el borde de las intersecciones que existen. Me di cuenta de que al escribir el anterior, y no tengo idea pero si esto representa un problema para la descomposición de la gráfica en los ciclos. ¿No es así?
