danjou

Ja ich möchte einen schleifenlosen Graphen. Aber ich möchte nicht sofort alle Rückwärtszweige löschen, da es sich in Wahrheit um einen Signalflussgraphen handelt. Daher müssen die gelöschten Kanten später durch andere Elemente ersetzt werden. Aber das ist hier weitestgehend unwichtig. Tatsache ist, dass so wenig Kanten wie möglich gelöscht werden sollen. Sieh dir mal das angehängte triviale Beispiel an. Hier kann man natürlich die Rückwärtszeige 5 und 3 löschen. Dann wären die Schleifen weg. Man kann aber auch, und so ist es am effiziensten nur die Kante 2 löschen. Dann sind sofort alle Zyklen eliminiert. Sowohl der äußere als auch der innere. Ein Ansatz ist über die Schnittmenge der beiden Zyklen zu gehen. Also {2,3} und {1,2,4,5}. Die Schnittmenge ist dabei 2 --> Kante 2 löschen. Das unangenehme dabei ist, dass die Zeitkomplexität O(exp) ist, wächst also exponentiell. Daher bin ich auch der Suche nach einem effizienteren Algorithmus. Lg

Hallo zusammen, folgende Problemstellung: Ich habe einen (beliebigen) gerichteten, zyklischen Graphen. Mittels der topologischen Sortierung und Tiefensuche (DFS) ist es möglich diese Zyklen zu detektieren (Zyklus genau dann, wenn Rückwärtszweig gefunden). Nun bin ich auf der Suche nach einem effizienten Algorithmus zum Auflösen der Schleifen. Dabei sollen durch das Aufbrechen einer Kante möglichst viele Schleifen beseitigt werden. Optimal wäre ein Algorithmus, dessen Zeitkomplexität proportional zur Knotenanzahl n wächst ( O(n) ). Hat irgendjemand vielleicht von einem Algorithmus gehört, der diese Aufgabe erfüllt oder hat möglicherweise sogar eine eigene, gute Idee, wie man die Kanten am effiziensten aufbrechen kann? Ich bin über jeden Vorschlag dankbar. Lg danjou