Graphische Darstellung von Algorithmus zur Spiel-Knoten

Question

Bei einem gerichteten Graphen, was ist ein Algorithmus, die ich verwenden kann eine zufällige Teilmenge der Kanten zu finden, so dass jeder Knoten genau eine eingehende und genau eine ausgehende Kante?

Zum Beispiel dies der Graph sein könnte mir gegeben wird:

Und dies würde ein gültiger Ausgang Graph:

Dies gilt, weil:

• Sie enthält alle Knoten auf dem Eingabegraphen
• Alle seine Ränder sind auch auf dem Eingang Graph
• Jeder Knoten genau eine Kante hat und eine Kante verlassen, um es kommt (und das kann nicht die gleiche Kante sein, sind keine Schleifen erlaubt, hat jeder Knoten mit mindestens einem anderen Knoten verbinden).

Wenn es keine mögliche Lösung, die erkannt werden soll.

Gibt es einen effizienten Algorithmus, dies zu lösen?

Danke!

Answer 1

Es ist ein Knoten Zyklen Abdeckung Problem. Es kann als gelöst werden Maximum Matchings in bipartiten Graphen .

Kurz gesagt:

1. Split jeden Knoten in zwei, jeweils in einer Partition eines Graphen, so dass alle Kanten von Partition P1 zu Partition P2 gehen. In Ihrem Beispiel sind die Knoten A und D in Knoten A1, D1 in Partition P1 und A2, D2 in P2 drehen wird. Edge-A-D werden sich in A1-D2 und D-A -. D1-A2
2. Sie dann eine maximale Übereinstimmung finden, gibt es einige Algorithmen.
3. verschmelzen dann die verschiedenen Knoten zurück, und Sie haben einen Zyklus Abdeckung.

Answer 2

Sie versuchen, eine Grafik in eine Reihe von Zyklen zu zersetzen.

diesen Link Punkte, die Sie Tarjan-Algorithmus für die Zyklen in einem Graphen zu finden.

Danach werden Sie einige Suchstrategie müssen (einige Entscheidungen von Zyklen nicht zu einer Lösung gegeben, um Ihre Zwänge führen).