Übung 3, Aufgabe 4

[fl4$h g0rd0n]

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?

[MisterD123]

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.

[Stille]

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

[Render]

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.

[Stille]

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.

[Render]

Der Schnitt von T und H muss nicht leer sein.
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
  {}

1-2 4-5 ist nicht Teilmenge eines MSTs von H (weil es keinen MST gibt)

[Stille]

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.