Gerichteter Graph: 2 Wege von < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:12 Mo 11.09.2006 | | Autor: | pheips |
| Aufgabe | Vorgegeben ist ein gerichteter Graph. Und folgendes soll realisiert werden:
Es sollen Kanten hinzugefügt werden können, allerdings nur, wenn dadurch nicht ein 2ter Weg von 2 beliebigen Knoten des Graphen entsteht. Sprich, sollte durch das Hinzufügen einer Kante von x nach y an irgendeiner Stelle im Graphen ein zweiter Pfad von 2 beliebigen Knoten A und B entstehen, dann darf die Kante nicht hinzugefügt werden. Also soll für alle Knoten A, B des gerichteten Graphen gelten, dass höchstens 1 Pfad von A nach B existiert. |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Das Ganze muss man sich als Art Gebilde aus gerichteten Pseudo-Bäumen vorstellen, wobei 2 Bäume durchaus selbe Knoten haben dürfen, aber es innerhalb eines dieser Bäume nicht 2 Wege zu ein und demselben Knoten geben darf.
Meine Überlegung war folgende:
Es gibt in diesem Graphen sogenannte Pseudo-Roots, die keine Vorgänger besitzen und Pseudo-Leafs, die keine Nachfolger besitzen. Will ich nun eine Kante von X nach Y hängen, so reicht es zu überprüfen, ob es nicht bereits einen Weg von einem Pseudoroot von X zu einem Pseudoleaf von Y gibt.
Dadurch muss ich schonmal nicht den Test für alle Knoten im Graph durchführen. Ich möchte das so effizient wie möglich lösen und frage mich daher, ob dieses bzw. eine ähnliches Problem bereits optimal gelöst existiert.
Vielen Dank im voraus!
mfg Philipp
P.S.:
Fall sie Aufgabenstellung nicht klar ist, dann würde ich eine kleine Zeichnung zur Verdeutlichung machen.
|
|
| |
|
Hallo,
der Standard-Ansatz, den Du ja selber implizit schon in Deiner Frage vorgibst, ist es, halt die Menge aller Pseudowurzeln und die aller
Pseudoblätter zu verwalten und
- entweder zu jedem Knoten X eine (günstigerweise sortierte) Liste oder besser noch einen Suchbaum von Pointern auf die jeweiligen Pseudo-Roots
und -Leafs zu halten, die dann bei Kanteneinfügeoperationen aktualisiert werden,
- oder speichereffizienter, aber laufzeitaufwendiger vorzugehen und jedesmal die Pfadsuchen durch diese Graphstruktur zu machen.
Ich würd ersteres präferieren.
Wenn Du zB sortierte Listen nimmst, so kannst Du zu gegebenen Knoten X,Y in Linearzeit in Länge der beiden Listen (nennen wir sie mal
ROOTS(X) und LEAFS(Y)) testen, ob die Kante (X,Y) noch legal ist, wenn Du für jedes Paar von Knoten die Information speicherst (woh oder übel in einer Matrix, die leider quadratischen Platz braucht), ob es einen ger. Pfad zw. diesen Knoten gibt.
Soviel vorerst,
Gruss,
Mathias
|
|
|
|
