Knotenüberdeckung eines Baums |
| 05.04.2008, 12:02 | n! | Auf diesen Beitrag antworten » |
| Knotenüberdeckung eines Baums Ich habe folgende Aufgabe: Sei der vollständige Baum der Tiefe n. Zeigen Sie, dass für alle ungeraden keine optimale Lösung des minimalen Knotenüberdeckungsproblems die Wurzel des Baums enthält Mein Problem: In der Aufgabe zuvor habe ich einen Algorithmus angegeben, der eine minimale Knotenüberdeckung ausgibt. Nach diesem Algorithmus wäre aber die Wurzel enthalten in der optimalen Lösung und die Aussage, die ich zu beweisen habe, müsste genau umgekehrt gelten. Ist die Aussage in der Aufgabe richtig? 
Gruß, n! |
||
| 05.04.2008, 13:20 | papahuhn | Auf diesen Beitrag antworten » |
| RE: Knotenüberdeckung eines Baums Welcher Verzweigungsgrad? |
||
| 05.04.2008, 14:13 | n! | Auf diesen Beitrag antworten » |
Also das ist leider nichts weiter angegeben
|
||
| 05.04.2008, 15:55 | papahuhn | Auf diesen Beitrag antworten » |
Hm komisch, in einem Baum der Tiefe 3 ist die Wurzel zusammen mit den Ecken der Tiefe 2 eine minimale Eckenüberdeckung. Verstehe gerade auch nicht, wie die Aufgabe stimmen soll. |
||
| 05.04.2008, 15:58 | n! | Auf diesen Beitrag antworten » |
Ja genau, das ist auch genau das Beispiel was ich gemacht habe. Da besteht die minimale Knotenüberdeckung genau aus den Ecken, die du gemeint hast merkwürdig... |
||
| 06.04.2008, 15:44 | n! | Auf diesen Beitrag antworten » |
Hat vielleicht noch jemand eine Idee diesbezüglich? Zumindest wäre es mal interessant zu wissen, ob die Aufgabe vielleicht falsch gestellt ist, worauf der Verdacht ja fällt Gruß |
||
| Anzeige | ||
|
|
||
| 14.04.2012, 17:40 | bechte | Auf diesen Beitrag antworten » |
Zwar etwas spät, aber vielleicht benötigt die Antwort ja noch jemand anderes: Kommt drauf an, wie man Tiefe eines Baums definiert. Wenn die Wurzel dazu zählt, dann ist es in meinen Augen korrekt, denn für T=3 gilt: - 0 / - 0 - 0 / 0 \ - 0 - 0 \ - 0 In dieser Lösung ist es optimal die beiden Knoten der Ebene 1 zu wählen und nicht die Wurzel. So verstehe ich es und so macht das auch Sinn. Eine optimale Belegung findet man am einfachsten, wenn man von den Blättern aus immer dann den Vaterknoten wählt, wenn man selbst nicht bereits von einem seiner Kinder gewählt wurde. (Beachte, es gibt Möglichkeiten, bei denen Vater und Kind beide gewählt werden!) |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
