Azykische Graphen < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:33 Mi 06.02.2008 | | Autor: | Dadalino |
| Aufgabe | Ein gerichteter Zyklus in einem gerichteten Graphen ist ein (gerichteter) Pfad, der mindestens eine Kante enthlt und dessen Anfangs- und Endknoten übereinstimmen. Ein gerichteter Graph heißt azyklisch, wenn es in dem Graphen keinen gerichteten Zyklus gibt.
Ein gerichteter Graph G = (V , E) mit n Knoten heißt topologisch sortierbar, wenn es eine Anordnung der Knotenmenge V in v1 , . . . , vn gibt, sodass für jede Kante [vi , vj
⟩ ∈ E gilt, dass i < j . Diese Anordnung nennt man dann auch topologische Sortierung.
Ein nicht allzu schwer zu beweisender Satz sagt, dass ein Graph G genau dann azyklisch ist, wenn G topologisch sortierbar ist.
Entwerfen Sie einen Algorithmus, der in O(|V | + |E|) Zeit testet, ob ein gegebener gerichteter Graph azyklisch ist.
Hinweis: Versuchen Sie ein topologische Sortierung zu berechnen. |
Hi!
Hoffe ihr könnt mir helfen!
Leider hilft mir nur im Moment alles nicht so wirklich weiter. Wäre über einen guten Ansatz ganz dankbar. Schlage mich nun schon ein paar Tage damit rum.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt. Und auch googlen hat mir nicht weiterhelfen können
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 08:43 Do 07.02.2008 | | Autor: | bazzzty |
Hallo Dadalino,
der erste, vielleicht wenig hilfreiche Tipp: Du suchst gerade zweimal dasselbe. Die Lösung zu diesem Problem wie auch zu dem Problem, bipartite Graphen in O(V+E) zu färben (erkennen), ist (fast) dieselbe. Etwas leichter zu verstehen sind allerdings die bipartiten Graphen.
Jetzt fällt es mir allerdings schwer, einen Tipp zu geben, ohne das Problem vollständig zu lösen, allerdings ist ja die Fälligkeit ohnehin schon abgelaufen -- sagt Dir Breitensuche etwas?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:28 Fr 08.02.2008 | | Autor: | Dadalino |
Ja, Bin irgendwann auch selber in diese Richtung gekommen. Deine Erklärung hat mir meine Idee nochmal übersichtlich klar gemacht. Dankesehr
|
|
|
|
