Übung 3, Aufgabe 4

Moderator: Effiziente Graphenalgorithmen

fl4$h g0rd0n
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 115
Registriert: 1. Okt 2007 22:20

Übung 3, Aufgabe 4

Beitrag von 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?
"Education is the path from cocky ignorance to miserable uncertainty" -- Mark Twain

Benutzeravatar
MisterD123
Geek
Geek
Beiträge: 811
Registriert: 31. Okt 2006 20:04
Wohnort: Weiterstadt

Re: Übung 3, Aufgabe 4

Beitrag von 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.

Benutzeravatar
Stille
Moderator
Moderator
Beiträge: 195
Registriert: 3. Jul 2008 10:11

Re: Übung 3, Aufgabe 4

Beitrag von 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 :)
Wolfgang Stille
UKP Lab - FB Informatik
http://www.ukp.informatik.tu-darmstadt.de

Benutzeravatar
Render
Windoof-User
Windoof-User
Beiträge: 32
Registriert: 12. Okt 2008 17:21

Re: Übung 3, Aufgabe 4

Beitrag von Render »

Hier in dem Fall bräuchte man "jede Menge ist Teilmenge der leeren Menge", was zum Glück aber nicht gilt :D. 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.

Benutzeravatar
Stille
Moderator
Moderator
Beiträge: 195
Registriert: 3. Jul 2008 10:11

Re: Übung 3, Aufgabe 4

Beitrag von 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.
Wolfgang Stille
UKP Lab - FB Informatik
http://www.ukp.informatik.tu-darmstadt.de

Benutzeravatar
Render
Windoof-User
Windoof-User
Beiträge: 32
Registriert: 12. Okt 2008 17:21

Re: Übung 3, Aufgabe 4

Beitrag von 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)

Benutzeravatar
Stille
Moderator
Moderator
Beiträge: 195
Registriert: 3. Jul 2008 10:11

Re: Übung 3, Aufgabe 4

Beitrag von 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.
Wolfgang Stille
UKP Lab - FB Informatik
http://www.ukp.informatik.tu-darmstadt.de

Antworten

Zurück zu „Effiziente Graphenalgorithmen“