algoritmo de gráfico para detectar ciclos pares

Tengo un gráfico no dirigido. Un borde en ese gráfico es especial. Quiero encontrar todos los otros bordes que son parte de un ciclo par que contiene el primer borde.algoritmo de gráfico para detectar ciclos pares

No necesito enumerar todos los ciclos, eso sería inherentemente NP, creo. Solo necesito saber, para cada borde, si cumple las condiciones anteriores.

Una búsqueda de fuerza bruta funciona, por supuesto, pero es demasiado lenta y estoy luchando por encontrar algo mejor. Cualquier ayuda apreciada.

Fuente

2012-08-26 john

No hay información suficiente aquí para proporcionar una respuesta de la calidad que está buscando. ¿Qué tan adelantado sabe usted qué borde es especial? ¿Se le permite preprocesar los datos? ¿Cuánto toca los datos de antemano (por ejemplo, cargarlos) y puede modificar la forma en que preprocesa los datos? – ninjagecko

Además, posiblemente debas consultar todos los ciclos ** si ** no puedes abusar del preprocesamiento, aunque no puedo pensar en una prueba de esa afirmación de una forma u otra. – ninjagecko

@ninjagecko El gráfico representa una estructura química, es decir, los vértices son átomos y los bordes son enlaces químicos entre esos átomos. La estructura química está siendo continuamente editada por el usuario y se espera que este algoritmo se ejecute en tiempo real a medida que el usuario realiza ediciones. Usamos una estructura de lista de adyacencia simple para el gráfico, aunque también mantenemos algunas otras estructuras (por ejemplo, sabemos en todo momento si un borde es parte de un ciclo o no). Si entiendo bien, el preprocesamiento no es una opción, ya que el gráfico (y el borde especial) siempre cambian. – john

Creo que tenemos una respuesta (debo darle crédito a mi colega con la idea). Básicamente, su idea es hacer un algoritmo de llenado de inundación a través del espacio de pares de ciclos. Esto funciona porque si tiene un gran ciclo par formado por la fusión de dos ciclos más pequeños, entonces los ciclos más pequeños deben haber sido pares o ambos impares. De manera similar, la fusión de un ciclo impar y par siempre forma un ciclo impar más grande.

Esta es una opción práctica solo porque puedo imaginar casos patológicos que consisten en alternar ciclos pares e impares. En este caso, nunca encontraríamos dos ciclos pares adyacentes, por lo que el algoritmo sería lento. Pero estoy seguro de que tales casos no surgen en la química real. Al menos en química, como se sabe actualmente, hace 30 años que nunca habíamos oído hablar de fullerenos.

Fuente

2012-08-30 08:47:43 john

-1

Si el gráfico tiene un pequeño grado de nodo, es posible considerar el uso de una representación gráfica diferente:

Vamos a tres átomos de u,v,w y dos enlaces químicos e=(u,v) y k=(v,w). Una forma típica de representar dichos datos es almacenar u,v,w como nodos y e,k como bordes en un gráfico.

Sin embargo, uno puede representar e y k como nodos en el gráfico, que tiene bordes como f=(e,k) donde f representa un enlace 2-paso u-w, f=(e,k) o f=(u,v,w). Ejecutar cualquier algoritmo para encontrar ciclos en dicho gráfico devolverá todos los ciclos pares en el gráfico original.

Por supuesto, esto es eficiente solo si el gráfico original tiene un pequeño grado de nodo. Cuando un usuario realiza una edición, puede editar fácilmente en consecuencia la representación alternativa.

Fuente

2013-03-14 23:53:38 michai

algoritmo de gráfico para detectar ciclos pares

Respuesta

Cuestiones relacionadas