    
Spezi (Spezi)
Erfahrenes Mitglied
Benutzername: Spezi
Nummer des Beitrags: 246
Registriert: 10-2001
| | Veröffentlicht am Freitag, den 31. Oktober, 2003 - 21:18: | 
|
Hallo,
ich verstehe wieder zwei Aufgaben nicht, und bin wieder für jeden Hinweis (aber auch vollständige Lösungen) sehr dankbar!
Aufgabe 1)
a) Sei T ein nicht-leerer Binärbaum. Sei n0 die Anzahl der Blätter von T, und n2 die Anzahl der Knoten von T mit Grad 2. Beweisen Sie, dass n0 = n2 + 1 gilt. (Hinweis: Können Sie durch Induktion über Höhe von T zeigen).
Frage dazu: Heißt Grad 2, das ist die Wurzel und alle Knoten mit genau einem Kind??
b) Welche ist die kleinstmögliche Tiefe eines Blattes in einem Entscheidungsbaum, der in einem Vergleich-Sortierung-Algorithmus für n Elemente entstanden ist?
Kann die nicht einfach 1 sein??
Aufgabe 2)
Sei G = (V,E) ein endlicher gerichteter Graph ohne Zyklen. Eine topologische Sortierung für G ist eine Aufzählung v1, ..., vn der Knoten von G, so dass für alle i, j element {1, ..., n} gilt: Ist vi -> vj eine Kante in G, so ist i<j.
(i) Geben Sie ein Verfahren an, das als Eingabe einen endlichen, gerichteten, azyklischen Graphen hat und eine topologische Sortierung ermittelt. Was ist die Kosten ihres Verfahrens?
Die Aufgabe ist bestimmt einfach, wenn man weiß, wie ...
(ii) Verwenden Sie eine geeignete Darstellung des Graphen (keine Ahnung welches Graphen, ist nämlich keiner angegeben) mittels Adjazenzlisten und geben Sie einen Algorithmus an, der die obige Aufgabe in O(|V| + |E|) Schritten löst.
Wäre toll, wenn jemand mit den Aufgaben etwas anfangen kann...
Tamara
|
