Estoy buscando un algoritmo para convertir un dígrafo (gráfico dirigido) en un gráfico no dirigido de manera reversible, es decir, el dígrafo debe ser reconstruible si se nos da el gráfico no dirigido. Entiendo que esto vendrá a expensas del gráfico no dirigido que tiene más vértices, pero no me importa.
¿Se sabe cómo hacer esto o se puede sugerir alguna referencia? Gracias por adelantado.
Actualización: Respecto a la respuesta de AdrianN a continuación. Puede ser un buen punto de partida, pero no creo que funcione en su forma actual. Aquí hay una imagen de por qué creo que no:
Actualización después del comentario de DW: considero que los vértices de los gráficos no están etiquetados. Si una solución implica etiquetar los vértices (como lo hace AdrianN), entonces debería dar el mismo gráfico (isomorfo) no dirigido, sin importar cómo se realice el etiquetado. Mi definición de "isomorfo" para gráficos con vértices etiquetados es que hay una permutación del etiquetado que relaciona los dos gráficos, pero no estoy seguro de la definición exacta de gráficos sin etiquetar ...
fuente
Respuestas:
fuente
La respuesta de David Richerby (que fue aceptada) es buena.
Seguí sus instrucciones en un ejemplo simple de dígrafo y espero que ayude a alguien.
(Hubiera publicado esto como un comentario sobre la respuesta de David, pero no tengo los puntos de reputación requeridos).
fuente
Al hacer la unión disjunta, uno debe tener cuidado para que sea reversible.
fuente
¿Qué pasa con la función de identidad? Es decir, cada dígrafo puede verse como un gráfico bipartito no dirigido con particiones de igual tamaño y viceversa.
fuente
Aquí hay una puñalada en esto:
Reemplace la información de dirección con vértices adicionales en el gráfico no dirigido. En otras palabras, use los vértices adicionales en el gráfico no dirigido para "codificar" la información de dirección. Por ejemplo, para cada vértice dirigido con al menos un borde, agregue un número de vértices no dirigidos igual a 1 + el número de bordes "entrantes". Los vértices con bordes cero permanecen sin cambios.
Para realizar la dirección inversa, cree un vértice dirigido para cada vértice que tenga 0 o más de 1 borde. (Los vértices con exactamente un borde son los vértices de "codificación de dirección"). Cada borde que conecta otro vértice de bordes múltiples es una conexión en el gráfico dirigido. Ahora es la parte difícil para la que no puedo explicar un algoritmo (pero creo que existe): debe deducir la dirección de las flechas dado solo el número de flechas entrantes para cada vértice.
Creo que la parte difícil es algo así como jugar al buscaminas :-) Averigua dónde se les da a las bombas (bordes entrantes) el número de bombas adyacentes para cada cuadrado (vértice).
fuente