Fragen zu Graphen und Algo'n < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) für Interessierte  | | Datum: | 13:46 Sa 23.07.2005 | | Autor: | svenb |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Hallo zusammen,
ich sitze gerade an ein paar Fragen, die ich mir nicht beantworten kann und deshalb hoffe ich auf eure Hilfe.
a) Skizzieren Sie einen Algorithmus, der für einen gerichteten Graphen G und zwei Knoten u, v entscheidet, ob v erreichbar von u ist.
b) Geben Sie zwei verschiedene Algorithmen an, um für einen gegebenen Graphen G zu entscheiden, ob G ein Baum ist.
c) Beweisen Sie: wenn G ein Baum ist und Depth-First-Search an seiner Wurzel startet, dann werden alle Kanten von G als Baumkanten klassifziert.
d) Beweisen Sie: wenn Depth-First-Search für einen Graphen G alle Kanten als Baumkanten klassifziert, dann ist G ein Baum.
e) Welche Ungleichungskette erfüllen die Discovery- und Finish Zeitstempel bei einer Baumkante (u; v)?
f) Die Korrektheit von Dijkstras Algorithmus kann nur bei nicht-negativen
Kantengewichten garantiert werden. Geben Sie ein Beispiel für einen gewichteten Graphen G mit mindestens einer negativ gewichteten Kante, aber ohne negativen Zyklus, sodaß Dijkstras Algorithmus ein falsches Ergebnis liefert.
Die Algorithmen die behandelt wurden sind:
BFS, DFS, Bellman-Ford, Single-Source-Path, All Pairs-Shortest, Floyd-Warshall, Dijkstra, topologische Sortierung
zu a) funktioniert das mit DFS oder Topologische Sortierung?
zu b) DFS und BFS?
zu c) keine Ahnung :-(
zu d) siehe c :-(
zu e) kann mit dem Begriff Ungleichungskette nix anfangen.
zu f) wenn ich 3 Knoten habe und von 2 zu 3 eine negative Kante, dann laufe ich wieder zurück zu 2 und die Zahl wird immer kleiner oder wie muss ich das realisieren?
Vielen Dank schonmal für die Hilfe!!!
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:54 Sa 23.07.2005 | | Autor: | Karl_Pech |
Hallo Sven,
Deine Frage wurde ja bereits ![[]](/images/popup.gif) im Usenet beantwortet. Ich nehme also an, daß Du an einer Antwort hier nicht mehr interessiert bist.
Wenn Du eine Frage zusätzlich zu diesem Forum noch irgendwo anders stellst, so gib bitte auch den entsprechenden Link zur dortigen Frage an, damit man sich hier nicht umsonst die Mühe macht, wenn die Frage im anderen Forum beantwortet wird.
Viele Grüße
Karl
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:20 Sa 23.07.2005 | | Autor: | svenb |
ok, danke für die Info: Ich wusste jetzt nicht, wie ich das mit dem Usenet angeben sollte.
Allerdings wär ich trotzdem dankbar, wenn ich noch weitere Antworten bekommen würde, da noch einige Fragen etwas unklar sind z.B b), e), f)
Danke nochmal!
|
|
|
|
