DFS Baum & Graphentheorie

[FoSAP] Formale Systeme, Automaten, Prozesse
[BuK] Berechenbarkeit und Komplexität
[MaLo] Mathematische Logik

DFS Baum & Graphentheorie

Beitragvon wil89 » 24.08.14 13:33

Hallo, ich brauche etwa kreative Idee gegenüber diesen Aufgaben:
Ich weiss nicht,ob hier solch 1 Frage auszustellen,
frag ich einfach:
"(a) Kann es sein, dass bei der Tiefensuche in einem gerichteten Graphen ein Knoten u mit Ingrad und Ausgrad jeweils > 0 zum Schluss im DFS–Wald selbst ein Baum (bestehend aus einem einzigen Knoten) ist? Begr¨undung!
(b) Finden Sie mittels dfs eine topologische Sortierung der Knoten des dag Graphen in der Abbildung.
1:2,6
2:4,5
3:5
4:5
5:-
6:2,4,7
7:4,5
8:3,5
Beschreiben Sie einen Algorithmus, der gleichzeitig f¨ur einen gerichteten Eingabegraphen pr¨uft, ob dieser ein dag ist (d.h. eine Sortierung m¨oglich ist).
(c) Eine totale Senke in einem gerichteten Graphen G = (V,E) ohne Loops und Mehrfachkanten ist ein Knoten mit Ingrad|V|−1 und Ausgrad 0. Der Graph sei in Adjazenzmatrixdarstellung (also mit|V|2 Eintr¨agen) gegeben. Argumentieren Sie, dass man weniger als 3|V| viele Anfragen an Matrixeintr¨age stellen muss, um zu entscheiden, ob G eine totale Senke besitzt.
"

Idee zu a.
Natuerlich gibt es nie 1 Baum ohne Nachfolgeknoten, falls es degIn u. deg out > 1 hat,oder ?
Bei anderen 2 habe ich nicht Ahnung, ausser dass , man kann mittels dfs or depth first search testen,ob da im Graph Kreis vorhanden ist, falls ja, keine topSort ist moeglich.
Besonders am c. der Satz "dass man weniger als 3|V| viele Anfragen an Matrixeintr¨age stellen muss, um zu entscheiden, ob G eine totale Senke besitzt." bin ich ja ahnungslos, woher 3 als Konstante zu diesem Problem kommt.
Hat jmd Vorschlag ?
Waere super, wenn jmd . mir Beistand geben könnte.
Danke, Leute.
wil89
 
Beiträge: 1
Registriert: 24.08.14 13:12
Anwendungsfach: Bio

Zurück zu Theoretische Informatik