Construir un DAG de dados múltiples ordenamientos topológicos

Question

Necesito construir un DAG, de sus ordenamientos topológicos dados (es decir, el gráfico $ G $ creado debe tener todos los ordenamientos dados como sus ordenamientos topológicos). Para simplificar, los vértices se etiquetan como el primer $ n $ Natural Number. (Tenga en cuenta que, una vez creado, el gráfico $ g $ puede tener más pedidos topológicos aparte de los que se dan). Se deben cumplir las siguientes restricciones:

1. El máximo superado de cada nodo debe ser 1
2. El número de nodos que tienen un indicigre de 0 debe ser mínimo.

Puede haber múltiples soluciones, cualquiera de ellos debería funcionar.

lo que he intentado. ( se aproxima 1 que está mal, ya que falla un ejemplo dado en la respuesta. Por favor, desplácese hasta el segundo enfoque, que aún no puedo encontrar un error).

acercamiento 1
De todos los pedidos dados, primero, cree un gráfico dirigido creando un borde dirigido de cada nodo a su siguiente nodo. Esto significa que si los ordenamientos son:

$$ 1, 3, 2, 5, 4, 6 $$ $$ 3, 1, 5, 2, 4, 6 $$ $$ 1, 5, 3, 2, 4, 6 $$

Crearé un gráfico dirigido con un borde dirigido de $ 1 $ a $ 3, 3 $ a $ 2, 2 $ a $ 5 $ y así sucesivamente.



Esto asegura que el número de nodos con nombre de entregadura 0 permanezca mínimo. Ahora, voy a eliminar todos los ciclos y asegurarme de que todos los ordenamientos sean válidos y, finalmente, eliminen todos los bordes adicionales que tenga ningún nodo. Mientras lo hace, me aseguraré de que si hay dos nodos cuyo borde viene del mismo nodo, eliminaré el borde del nodo que tiene un indigriado más alto, de modo que se cumpla con la condición 2. La gráfica construida entonces debería parecer:

Este DAG creado, sigue ambas restricciones, e IMO tiene el número mínimo de nodos de indepeje como 0, aunque, no está probado.

He codificado el enfoque y está dando resultados esperados para los casos de uso que proporciono, pero sé que está mal. ¿Que me estoy perdiendo aqui? ¿Alguien puede proporcionar un caso de uso alternativo, lo que falla el enfoque anterior?

acercamiento 2
Creo un gráfico dirigido $ g $ creando una ventaja de $ a_i $ a $ A_J $ para todos $ j> i $ en todos los ordenamientos dados. Entonces, para los pedidos:

$$ 1, 2, 3, 4, 5 $$ $$ 2, 4, 1, 5, 3 $$

Voy a crear el siguiente gráfico:
El primer paso después de esto es validar todos los pedidos. Eliminación de ciclos por separado no se requiere, ya que se eliminarán por este paso en sí.
Para cualquier orden $$ A_1, A_2, A_3, A_4, ... A_N $$ Voy a comprobar si existe cualquier ventaja de $ a_j $ a $ a_i $ donde $ J> i $ , quitaré ese borde.
Hacerlo, dará el siguiente gráfico:
El último paso es eliminar los bordes adicionales de todos los nodos, ya que la máxima ventaja de cualquier nodo puede ser $ 1 $ max. Eliminaré los bordes salientes, de modo que el número de nodos que tenga un nombre de identificador $ 0 $ es mínimo. Primero calculo el indigriado de cada nodo. Luego, para cada nodo, que tiene más de 1 bordes salientes, eliminaré todos los bordes, excepto el que tiene el mínimo de indigrie.

El gráfico final $ g $ se verá como:

Este gráfico satisface ambas restricciones. ¡Pero sé que este enfoque está mal! ¿Alguien puede ayudar a encontrar por qué está mal?

Answer 1

Enfoque 1

Por ejemplo, considere los dos pedidos: 1, 2, 3, 4, 5 y 2, 4, 1, 5, 3.

De acuerdo con su enfoque, obtendremos un ciclo 1-> 2-> 3-> 4-> 1. Luego eliminamos 3-> 4 y 4-> 1, y obtenemos un gráfico:

     ______
    /      \
1->2->4->5->3
 \______/

ahora 5-> 3 y 1-> 2, respectivamente, violan la primera y la segunda órdenes, por lo que los eliminamos, y obtengamos

     ______
    /      \
1  2->4->5  3
 \______/

Ahora el nodo 2 tiene 2 bordes salientes. La eliminación de uno hace un gráfico final donde 3 nodos (1, 2, 3 o 1, 2, 4) tienen en grado 0.

Sin embargo, existe un gráfico

1->3 2->4->5

donde se cumplen ambos pedidos, sino que solo 2 nodos tienen en grado 0.

así que el enfoque 1 es incorrecto.

Enfoque 2

Considerar una solución óptima. Cada ventaja en esta solución óptima debe ser el formulario $ (A_I, A_J) $ donde $ i En cada pedido. Esto significa que todos los bordes en la solución óptima están contenidos en el gráfico intermedio. Entonces, si luego, elimina los bordes salientes, de manera que el número de nodos que tenga en grado 0 sea mínimo, obtendrá una solución óptima correcta.

Sin embargo, su enfoque que intenta hacer que el número de nodos que tenga en grado 0 mínimo sea incorrecto.

Por ejemplo, considere los tres pedidos: \ comienzan {align} 1, 2, 3, 4, 5, 6, 7, 8 \\ 5, 1, 6, 3, 8, 2, 4, 7 \\ 2, 7, 3, 8, 1, 4, 5, 6 \ End {align}

Primero podemos obtener el siguiente gráfico intermedio:

    _____
   / ____\__
  / / ____\_\__
 / / /     \ \ \
1 2 3->4 5->6 7 8
 \ \__/
  \__/

Aplicando su enfoque, eliminaremos 1-> 4, 2-> 4 y 3-> 4 (o 3-> 8), y hay 5 nodos con en grado 0: 1, 2, 3, 4 (u 8), 5. Sin embargo, la solución óptima sería

     _______
    / ____ _\__
   / /       \ \
1 2 3 4 5->6 7 8
 \___/

donde solo 4 nodos tienen en grado 0: 1, 2, 3, 5.