Costruire un dag da dati multipli topologici

Question

Ho bisogno di costruire un dag, dai suoi determinati ordini topologici (cioè il grafico $ G $ creato deve avere tutti gli ordini dati come i suoi ordini topologici). Per semplicità, i vertici sono etichettati come prima $ N $ numeri naturali. (Nota che una volta creata, il grafico $ G $ potrebbe avere altri ordini topologici a parte quelli dati.)
I seguenti vincoli dovrebbero essere soddisfatti:

.
1. Il outgezer massimo di ogni nodo dovrebbe essere 1
2. Il numero di nodi aventi l'indegresco 0 dovrebbe essere minimo.

Ci possono essere molteplici soluzioni, ognuna di esse dovrebbe funzionare.

Cosa ho provato. ( approccio 1 che è sbagliato in quanto fallisce un esempio indicato nella risposta. Scorri fino al secondo approccio, che non sono ancora in grado di trovare un errore.)

approccio 1
Da tutti gli ordini dati, in primo luogo, creare un grafico diretto creando un bordo diretto da ogni nodo al suo nodo successivo. Ciò significa se gli ordini sono:
$$ 1, 3, 2, 5, 4, 6 $$ $$ 3, 1, 5, 2, 4, 6 $$ $$ 1, 5, 3, 2, 4, 6 $$

Creerò un grafico diretto con un bordo diretto da $ 1 $ a $ 3, 3 $ a $ 2, 2 $ a $ 5 $ e così via.



Ciò garantisce che il numero di nodi con l'indegree 0 rimane minimo. Ora, rimuoverò tutti i cicli e assicurati che tutti gli ordini siano validi e infine, eliminano tutti i bordi aggiuntivi. Mentre lo faccio, farò in modo che se ci siano due nodi il cui bordo proviene dallo stesso nodo, rimuoverò il bordo dal nodo con un calendario più alto, in modo che la condizione 2 sia soddisfatta. Il grafico costruito quindi, dovrebbe apparire come:

Questo DAG ha creato, segue sia i vincoli, e IMO ha il numero minimo di nodi di indecortario come 0, sebbene, non è dimostrato.

Ho codificato l'approccio e sta dando risultati attesi per i casi di utilizzo che fornisco, ma so che è sbagliato. Cosa mi manca qui? Qualcuno può fornire un caso di uso alternativo, che fallisce l'approccio di cui sopra?

approccio 2
Creo un grafico diretto $ G $ creando un bordo da $ a_i $ a $ A_J $ per tutti $ j> I $ in tutti gli ordini forniti. Quindi, per gli ordini:
$$ 1, 2, 3, 4, 5 $$ $$ 2, 4, 1, 5, 3 $$

creerò il seguente grafico:
Il primo passo dopo questo è per convalidare tutti gli ordini. La rimozione dei cicli separatamente non è richiesta in quanto verranno rimossi da questo passaggio stesso.
Per qualsiasi ordine $$ A_1, A_2, A_3, A_4, ... A_N $$ Controllerò se esiste un vantaggio da $ a_j $ a $ a_i $ dove $ j> I $ , rimuoverò quel bordo.
Ciò, darà il seguente grafico:
L'ultimo passo è quello di rimuovere i bordi aggiuntivi da tutti i nodi poiché il massimo outstregree di qualsiasi nodo può essere $ 1 $ max. Rimuoverò i bordi in uscita in modo tale che il numero di nodi aventi un indegresco $ 0 $ è minimo. Per prima cosa calcolo dell'integreto di ogni nodo. Quindi per ciascun nodo che ha più di 1 bordi in uscita, rimuoverò tutti i bordi tranne quello con l'incongrego minimo.

Il grafico finale $ G $ sarà simile a:

Questo grafico soddisfa sia i vincoli. Ma so che questo approccio è sbagliato! Qualcuno può aiutare a trovare perché è sbagliato?

Answer 1

approccio 1

Ad esempio, considera i due ordini: 1, 2, 3, 4, 5 e 2, 4, 1, 5, 3.

Secondo il vostro approccio, otterremo un ciclo 1-> 2-> 3-> 4-> 1. Quindi rimuoviamo 3-> 4 e 4-> 1 e ottenere un grafico:

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

.

Ora 5-> 3 e 1-> 2 violare rispettivamente il primo e il secondo ordine, quindi li rimuoviamo e otteniamo

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

.

Ora il nodo 2 ha 2 bordi in uscita. La rimozione di uno è un grafico finale in cui 3 nodi (1, 2, 3 o 1, 2, 4) hanno in-grado 0.

Tuttavia, esiste un grafico

1->3 2->4->5

.

Dove entrambi gli ordini sono soddisfatti, ma solo 2 nodi hanno in-grado 0.

Quindi l'approccio 1 non è corretto.

approccio 2

Considera una soluzione ottimale. Ogni bordo in questa soluzione ottimale deve essere il modulo $ (a_i, a_j) $ dove $ i in ogni ordine. Ciò significa che tutti i bordi nella soluzione ottimale sono contenuti nel grafico intermedio. Quindi, se si rimuovono i bordi in uscita in modo tale che il numero di nodi aventi in-grado 0 è minimo, otterrai una soluzione ottimale corretta.

Tuttavia, il tuo approccio che cerca di rendere il numero di nodi con minimo in-grado 0 è errato.

Ad esempio, considera i tre ordini: \ Begin {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 {allinea}

Per prima cosa possiamo ottenere il seguente grafico intermedio:

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

.

Applicazione del tuo approccio, rimuoveremo 1-> 4, 2-> 4 e 3-> 4 (o 3-> 8), e ci sono 5 nodi con in-grado 0: 1, 2, 3, 4 (o 8), 5. Tuttavia, la soluzione ottimale sarebbe

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

.

Dove solo 4 nodi hanno in-grado 0: 1, 2, 3, 5.