Hallo,
hier eine sehr blöde Frage:
Wenn ich den induzierten Subgraphen H ungeschickt wähle, dann ist dieser nicht zusammenhängend. In diesem Fall kann es meines Erachtens keinen
MST von H geben. Dann wäre aber die zu zeigende Aussage falsch. Der letzte Teil der Aussage ist nämliche eine implizite Existenzaussage über der Menge aller MSTs von H, die in diesem Fall leer ist.
Ist dies ein Fehler in der Aufgabenstellung oder in meinem Denken?
Übung 3, Aufgabe 4
Moderator: Effiziente Graphenalgorithmen
-
- BASIC-Programmierer
- Beiträge: 115
- Registriert: 1. Okt 2007 22:20
Übung 3, Aufgabe 4
"Education is the path from cocky ignorance to miserable uncertainty" -- Mark Twain
- MisterD123
- Geek
- Beiträge: 811
- Registriert: 31. Okt 2006 20:04
- Wohnort: Weiterstadt
Re: Übung 3, Aufgabe 4
ich glaub du hast recht. Ich würde behaupten wir sollen die subgraphen dann einfach mal als "nicht ungeschickt gewählt" annehmen, also so, dass H tatsächlich einen MST hat.
Re: Übung 3, Aufgabe 4
Hallo,
sorry für die späte Antwort. Eigentlich habe ich dieses Forum abonniert, was aber schon öfter nicht funktioniert hat.
Die leere Menge ist per Definition Teilmenge jeder Menge. Die "ungeschickte Wahl" führt daher zu einer trivialen Aussage
sorry für die späte Antwort. Eigentlich habe ich dieses Forum abonniert, was aber schon öfter nicht funktioniert hat.
Die leere Menge ist per Definition Teilmenge jeder Menge. Die "ungeschickte Wahl" führt daher zu einer trivialen Aussage

Re: Übung 3, Aufgabe 4
Hier in dem Fall bräuchte man "jede Menge ist Teilmenge der leeren Menge", was zum Glück aber nicht gilt
. Es soll doch einen MST des Subgraphen geben der den Schnitt von T und H enthält. Falls es keinen MST von H gibt kann der Schnitt auch nicht in einem MST von H enthalten sein und die Aussage der Aufgabe ist falsch.

Re: Übung 3, Aufgabe 4
Interessanter Aspekt. Der MST eines leeren Graphen kann nur ein leerer Graph sein. MST(H) ist in diesem Fall leer, der Schnitt von T und H jedoch auch. Passt also.
Re: Übung 3, Aufgabe 4
Der Schnitt von T und H muss nicht leer sein.
Beispiel:
1-2 4-5 ist nicht Teilmenge eines MSTs von H (weil es keinen MST gibt)
Beispiel:
Code: Alles auswählen
Graph (Zahlen = Knoten, - = Kanten):
G = 1-2-3-4-5
ein MST von G:
T = G = 1-2-3-4-5
ind. Subgraph ((3) entfernt)
H = 1-2 4-5
T geschnitten H
1-2 4-5
Menge der MSTs von H
{}
Re: Übung 3, Aufgabe 4
Dann wären die Kanten 1-2 und 4-5 aber im MST von H enthalten. Streng genommen ist das aber ein minimal aufspannender Wald, da ohne Zusammenhang von H natürlich kein Baum existiert. Es macht folglich wenig Sinn, nicht zusammenhängende Teilgraphen zu betrachten. Sollte ich diese Aufgabe ein weiteres Mal stellen, werde ich das Wörtchen "zusammenhängend" vor "Subgraphen" einfügen.