Konstruieren Sie einen DAG aus den jeweils mehrfach topologischen Bestellen

Question

Ich muss einen DAG erstellen, von seinen gegebenen topologischen Reihenfolge (d. H. In der Grafik $ g $ erstellt muss alle Bestellungen enthalten sind, die als topologische Reihenfolge angegeben sind). Zur Vereinfachung sind die Scheitelpunkte als erster $ n $ natürliche Zahlen gekennzeichnet. (Beachten Sie, dass das Diagramm $ G $ mehr topologische Reihenfolge aufweisen kann, abgesehen von den angegebenen.)
Die folgenden Einschränkungen sollten erfüllt sein:

.
1. Der maximale Überwachung jedes Knotens sollte 1
2. Die Anzahl der Knoten mit einem Indeye 0 sollte minimal sein.

Es kann mehrere Lösungen geben, deren von ihnen funktionieren sollte.

was ich versucht habe. ( Annäherung 1 was falsch ist, da es ein Beispiel fehlschlägt, das in der Antwort angegeben ist. Bitte blättern Sie zum zweiten Ansatz, den ich immer noch keinen Fehler finden kann.)

Annäherung 1

Erstellen Sie zunächst aus allen gegebenen Bestellungen ein entsprechendes Diagramm, indem er eine gerichtete Kante von jedem Knoten an seinen nächsten Knoten erstellt. Dies bedeutet, wenn die Bestellungen sind:
$$ 1, 3, 2, 5, 4, 6 $$ $$ 3, 1, 5, 2, 4, 6 $$ $$ 1, 5, 3, 2, 4, 6 $$

Ich erstellte einen gerichteten Diagramm mit einer gerichteten Kante von $ 1 $ bis 3, 3 $ bis $ 2, 2 $ bis $ 5 $ und so weiter.



Dies stellt sicher, dass die Anzahl der Knoten mit Indeygrale 0 minimal bleibt. Nun, ich werde alle Zyklen entfernen und sicherstellen, dass alle Bestellungen gültig sind und schließlich alle zusätzlichen Kanten beseitigen, die jeder Knoten hat. Ich werde dabei sicherstellen, dass, wenn es zwei Knoten gibt, deren Kante von demselben Knoten kommt, den Kanten vom Knoten mit einem höheren Indeye entfernen, so dass der Zustand 2 erfüllt ist. Die damals konstruierte Grafik sollte aussehen:

Diese DAG ergab, folgt sowohl den Einschränkungen, und IMO hat die Mindestanzahl von Indexknoten als 0, obwohl es nicht bewiesen ist.

Ich habe den Ansatz codiert und ergibt erwartete Ergebnisse für die Anwendungsfälle, die ich lieferte, aber ich weiß, dass es falsch ist. Was vermisse ich hier? Kann jemand einen alternativen Anwendungsfall bereitstellen, der den obigen Ansatz fehlschlägt?

Annäherung 2

Ich erstellte eine gerichtete Grafik $ g $ , indem Sie eine Kante von $ A_I $ bis $ a_j $ für alle $ j> i $ in allen angegebenen Bestellungen. Also für die Bestellungen:
$$ 1, 2, 3, 4, 5 $$ $$ 2, 4, 1, 5, 3 $$

Ich werde die folgende Grafik erstellen:

Der erste Schritt danach ist es, alle Bestellungen zu bestätigen. Die Entfernung von Zyklen ist separat nicht erforderlich, da sie von diesem Schritt selbst entfernt werden.
Für jede Bestellung $$ A_1, A_2, A_3, A_4, ... A_N $$ Ich werde prüfen, ob es einen Rand von $ A_J $ auf $ A_I $ , wo $ j> i $ , ich werde diesen Rand entfernen.
Dabei gibt es die folgende Grafik:

Der letzte Schritt besteht darin, zusätzliche Kanten von allen Knoten zu entfernen, da ein maximaler Überwachung von einem beliebigen Knoten $ 1 $ max ist. Ich werde die ausgehenden Kanten so entfernen, dass die Anzahl der Knoten mit Indeye $ 0 $ Minimum ist. Zuerst berechne ich den Indeye von jedem Knoten. Dann werde ich für jeden Knoten, der mehr als 1 ausgehende Kanten hat, alle Kanten außer dem mit dem minimalen Indeye entfernen.

Der letzte Diagramm $ g $ wird aussehen:

Dieses Graph erfüllt beide Einschränkungen. Aber ich weiß, dass dieser Ansatz falsch ist! Kann jemand helfen, zu finden, warum ist das falsch?

Answer 1

Annäherung 1

Betrachten Sie beispielsweise die beiden Ordnungen: 1, 2, 3, 4, 5 und 2, 4, 1, 5, 3.

Nach Ihrem Ansatz erhalten wir einen Zyklus 1-> 2-> 3-> 4-> 1. Dann entfernen wir 3-> 4 und 4-> 1 und erhalten einen Graphen:

generasacodicetagpre.

jetzt 5-> 3 und 1-> 2 verstoßen jeweils den ersten und den zweiten Bestellungen, also entfernen wir sie und erhalten

generasacodicetagpre.

Now NOW NODE 2 verfügt über 2 ausgehende Kanten. Entfernen von entweder eines macht eine endgültige Grafik, in der 3 Knoten (1, 2, 3 oder 1, 2, 4) in Grad 0 aufweisen.

Es gibt jedoch ein Diagramm

generasacodicetagpre.

wenn beide Bestellungen erfüllt sind, aber nur 2 Knoten haben in Grad 0.

, also ist Annäherung 1 falsch.

Annäherung 2

Betrachten Sie eine optimale Lösung. Jede Kante in dieser optimalen Lösung muss das Formular $ (A_I, A_J) $ sein, wo $ i in jeder Bestellung. Dies bedeutet, dass alle Kanten in der optimalen Lösung in der Zwischengrafik enthalten sind. Wenn Sie also die ausgehenden Kanten entfernen, so dass die Anzahl der Knoten mit In-Grad 0 minimal ist, erhalten Sie eine korrekte optimale Lösung.

Ihr Ansatz, der versucht, die Anzahl der Knoten mit einem Minimum von 0 von 0 zu erstellen, ist jedoch falsch.

Sehen Sie sich beispielsweise die drei Bestellungen an: \ beginnen {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}

Zuerst können wir das folgende Zwischengraph erhalten:

generasacodicetagpre.

Wenn Sie Ihren Ansatz anwenden, entfernen wir 1-> 4, 2-> 4 und 3-> 4 (oder 3-> 8), und es gibt 5 Knoten mit 0: 1, 2, 3, 4 in Grad (oder 8), 5. Die optimale Lösung wäre jedoch

generasacodicetagpre.

wo nur 4 Knoten in Grad 0: 1, 2, 3, 5 aufweisen.