Graphalgorithmus finden < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:36 Do 04.09.2014 | | Autor: | loggeli |
| Aufgabe | | Es sei ein binärer Baum als Graph (V,E) gegeben. Der Wurzelknoten sei w. Es ist ein Algorithmus gesucht, der einen Knoten k des Binärbaums bestimmt, sodass nach Entferen von k der Baum in zwei Teilbäume zerfällt, wobei jeder der Teilbäume maximal 2/3|V| Knoten haben kann. |
Hallo,
meine Idee zu dieser Aufgabe ist es einfach immer den Wurzelknoten zu suchen und diesen entsprechend zu löschen. Eine Skizze davon habe ich hier erstellt skizze. Leider bin ich mir nicht sicher, ob das wirklich die richtige Strategie ist.
Ich würde mich über Ideen von euch freuen.
Beste Grüße
loggeli
Dateianhänge:
Anhang Nr. 1 (Typ: jpg) [nicht öffentlich]
|
|
| |
|
Hallo loggeli,
> Es sei ein binärer Baum als Graph (V,E) gegeben. Der
> Wurzelknoten sei w. Es ist ein Algorithmus gesucht, der
> einen Knoten k des Binärbaums bestimmt, sodass nach
> Entferen von k der Baum in zwei Teilbäume zerfällt, wobei
> jeder der Teilbäume maximal 2/3|V| Knoten haben kann.
> Hallo,
>
> meine Idee zu dieser Aufgabe ist es einfach immer den
> Wurzelknoten zu suchen und diesen entsprechend zu löschen.
> Eine Skizze davon habe ich hier erstellt skizze. Leider bin
> ich mir nicht sicher, ob das wirklich die richtige
> Strategie ist.
Bestimmt nicht. Woher weißt Du denn, dass nicht z.B. der linke Teilbaum nur zwei Knoten enthält, der rechte aber 937?
Grüße
reverend
|
|
|
|
