Übung 6 - H1 Verständnisproblem

Eruptiv
Erstie
Erstie
Beiträge: 12
Registriert: 9. Apr 2008 11:44

Übung 6 - H1 Verständnisproblem

Beitrag von Eruptiv »

Tach allerseits!
Ich verstehe irgendwie die Aufgabe nicht. Und zwar ist es ja so, dass jede Kante eines MST (Minimal Spanning Tree) eine sichere Kante ist, aber es gibt im kompletten Graph nur eine leichte Kante, solange die Gewichte alle verschieden sind. Diese leichte Kante ist automatisch eine sichere Kante, sonst wäre der MST nicht minimal. Somit gibt es überhaupt nur einen Schnitt, für den die Aussage aus H1 stimmen würde, nämlich den, der durch die leichte Kante geht, und für alle anderen Schnitte wäre die Aussage falsch... somit würde es ausreichen, irgendeinen Schnitt an zu geben, der nichts mit der leichten Kante zu tun hat, und man hätte die Aufgabe gelöst! Allerdings verstehe ich dann nicht, was wir bei der Aufgabe lernen sollten, und was die mit Leichten Kanten zu tun hat?!
Sehe ich das richtig, oder steckt da mehr dahinter?! Bitte um Erleuchtung!

Benutzeravatar
Krümelmonster
Geek
Geek
Beiträge: 767
Registriert: 17. Okt 2007 13:58
Wohnort: Jossgrund

Re: Übung 6 - H1 Verständnisproblem

Beitrag von Krümelmonster »

Die sicheren Kanten sind diese, die im MST sind. Das siehst du richtig.

Die leichten Kanten können nur im Zusammenhang mit einem Schnitt angeben werden.
Du sollst nun widerlegen, dass eine sichere Kante, die den Schnitt verlässt automatisch eine
leichte Kante ist.
Schau dir mal den Graphen aus G1 an und überlege dir, welche Kante die Behauptung verletzt.
Stell deinen Fuß auf einen hohen Sockel
Mach dir ein Haar aus tausend Locken
Du bleibst doch immer, was du bist!

Stumpf.Alex
Nerd
Nerd
Beiträge: 647
Registriert: 1. Okt 2007 12:40
Wohnort: Darmstadt
Kontaktdaten:

Re: Übung 6 - H1 Verständnisproblem

Beitrag von Stumpf.Alex »

Es gilt folgendes:
leichte Kante => sichere Kante (in der Vorlesung bewiesen)
sichere Kante => leichte Kante (Nein! Genau dies soll man in der H1 zeigen)

tmx-master
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 253
Registriert: 25. Okt 2006 17:44

Re: Übung 6 - H1 Verständnisproblem

Beitrag von tmx-master »

Frage:

Ist "verträglich" gleich "respektiert" im Cormen? Ich denke mal ja, aber man weiß ja nie. Kann das jemand verbindlich beantworten?
Gruß TM

VersuchEs
Windoof-User
Windoof-User
Beiträge: 30
Registriert: 25. Mai 2008 11:21

Re: Übung 6 - H1 Verständnisproblem

Beitrag von VersuchEs »

Hi,
jede sichere Kante hat 2 Eigenschaften :
1- Sie muss den Schnitt überqueren
2- Sie muss minimales Gewicht besitzen
Hinweis : Nach der Fragestellung wird die 2. Eigenschaft nicht erfüllt. :!: :?:

Stumpf.Alex
Nerd
Nerd
Beiträge: 647
Registriert: 1. Okt 2007 12:40
Wohnort: Darmstadt
Kontaktdaten:

Re: Übung 6 - H1 Verständnisproblem

Beitrag von Stumpf.Alex »

tmx-master hat geschrieben:Frage:

Ist "verträglich" gleich "respektiert" im Cormen? Ich denke mal ja, aber man weiß ja nie. Kann das jemand verbindlich beantworten?
Diese Eigenschaften zeigen jeweils in eine andere Richtung:
respektiert: Keine Kante aus der Kantenmenge kreuzt den Schnitt
verträglich: Ein Schnitt ist verträglich mit der Kantenmenge, wenn keine Kante aus der Kantenmenge den Schnitt kreuzt.

An sich wird die gleichen Eigenschaft beschrieben. Der Unterschied ist, dass "respektiert" eine Eigenschaft der Kantenmenge und "verträglich" eine Eigenschaft des Schnittes ist.

CallForSanity
Windoof-User
Windoof-User
Beiträge: 27
Registriert: 17. Okt 2007 20:45

Re: Übung 6 - H1 Verständnisproblem

Beitrag von CallForSanity »

Code: Alles auswählen

GENERIC-MST(G,w)
1 A <- { }
2 while A does not form a spanning tree
3   do find an edge (u,v) that is safe for A
4     A <- A U {(u,v)}
5 return A
von VersuchEs am So Mai 25, 2008 10:29 am
Hi,
jede sichere Kante hat 2 Eigenschaften :
1- Sie muss den Schnitt überqueren
2- Sie muss minimales Gewicht besitzen
von Stumpf.Alex am Mi Mai 21, 2008 6:43 am
Es gilt folgendes:
leichte Kante => sichere Kante (in der Vorlesung bewiesen)
sichere Kante => leichte Kante (Nein! Genau dies soll man in der H1 zeigen)
Nach der Definition von VersuchEs würde der GENERIC-MST einwandfrei funktionieren, da in 2 gefordert wird, dass die sichere Kante auch minimales Gewicht haben muss und der Algorithmus eine sichere Kante fordert, was in Theorem 23.1 bestätigt wird.
Nach Alex' Definition muss das aber nicht der Fall sein.

Kann es also sein, dass der Ausdruck "sicher" hier mehrdeutig verwendet wird? Das wäre nämlich extrem uncool.
Wenn nicht, sagt mir bitte, wo der Denkfehler liegt.

Stumpf.Alex
Nerd
Nerd
Beiträge: 647
Registriert: 1. Okt 2007 12:40
Wohnort: Darmstadt
Kontaktdaten:

Re: Übung 6 - H1 Verständnisproblem

Beitrag von Stumpf.Alex »

Hmm..hast recht. Also "meine" Definition stammt aus der Vorlesung. Kann sein, dass ich was falsch gemacht habe. Ich muss nochmal im Corman nachschauen. Aber so steht das im Widerspruch zur GENERIC-MST, da dieser dann so keine minimalen Spannbäume erzeugt...hmm komisch.
Aber im Buchmann-Skript wird nicht gefordert, dass eine sichere Kante eine leichte Kante sein muss.

Benutzeravatar
s!mon
Computerversteher
Computerversteher
Beiträge: 373
Registriert: 20. Okt 2007 18:24
Wohnort: Höchst i. Odw

Re: Übung 6 - H1 Verständnisproblem

Beitrag von s!mon »

Wenn auf einer Seite des Schnittes nur Kanten des MST sind gilt sichere Kante -> leichte Kante würde ich sagen. Wenn man für den Schnitt aber nur sagt, dass die Kanten des MST respektiert werden müssen, können ja auch andere Kanten innerhalb des Schnittes liegen. Dann muss die Kante mit dem geringsten Gewicht die durch den Schnitt verläuft keine sichere Kante des MST sein (wie in der Hausübung). Die Eigenschaft "Sicher" kann man ja nur in Bezug auf eine Menge A treffen.

Ist ein bissl schwer zu erklären was ich jetzt gerade meine. Ein Beispiel kann ich ja auch nicht geben ohne die Lösung zu verraten :?

Benutzeravatar
mantra
Computerversteher
Computerversteher
Beiträge: 385
Registriert: 23. Okt 2005 23:56
Wohnort: Wiesbaden

Re: Übung 6 - H1 Verständnisproblem

Beitrag von mantra »

Ich sehe keinen Widerspruch zwischen
Stumpf.Alex hat geschrieben:Es gilt folgendes:
leichte Kante => sichere Kante (in der Vorlesung bewiesen)
sichere Kante => leichte Kante (Nein! Genau dies soll man in der H1 zeigen)
und

Code: Alles auswählen

GENERIC-MST(G,w)
1 A <- { }
2 while A does not form a spanning tree
3   do find an edge (u,v) that is safe for A
4     A <- A U {(u,v)}
5 return A
Beides halte ich für richtig, es sei denn jemand erklärt hier ganz genau, wo der Widerspruch liegen soll ;)

Stumpf.Alex
Nerd
Nerd
Beiträge: 647
Registriert: 1. Okt 2007 12:40
Wohnort: Darmstadt
Kontaktdaten:

Re: Übung 6 - H1 Verständnisproblem

Beitrag von Stumpf.Alex »

Das Problem ist halt, dass es heißt in Zeile 3 eine weitere sichere Kante zu finden und dem MST hinzuzufuegen. Aber da ja eine sichere Kante nicht impliziert, dass es eine leichte ist, bedeutet dass, das nach hinzufügen einer sicheren Kante zwar ein Spannbaum herauskommt, aber dieser nicht minimal sein muss, dass im Widerspruch zu GENERIC-MST steht, was dann eher GENERIC-ST heißen müsste.

CallForSanity
Windoof-User
Windoof-User
Beiträge: 27
Registriert: 17. Okt 2007 20:45

Re: Übung 6 - H1 Verständnisproblem

Beitrag von CallForSanity »

In "Introduction to Algorithms" hat eine "sichere" Kante auch minimales Gewicht, was auch zwingend nötig ist.
In der Vorlesung muss eine "sichere" Kante angeblich kein minimales Gewicht haben.

Wir haben es also offensichtlich mit zwei Definitionen von "sicher" zu tun.
Das ist so, als wenn man Kaffee bestellt, meint aber Espresso und beschwert sich dann, wenn die Bedienung normalen Milchkaffee bringt.
Espresso und Milchkaffee sind beide Kaffee, aber der Espresso ist eben noch etwas mehr.

Aber der eigentliche Haken an der Sache ist wohl der, den s!mon beschrieben hat. Die Sache mit den zwei Definitionen ist also in Bezug auf die Aufgabe gar nicht mehr relevant.

Stumpf.Alex
Nerd
Nerd
Beiträge: 647
Registriert: 1. Okt 2007 12:40
Wohnort: Darmstadt
Kontaktdaten:

Re: Übung 6 - H1 Verständnisproblem

Beitrag von Stumpf.Alex »

So.. im Corman ist sichere Kante so eingeführt und wenn man das Buchmann-Skript genauer liest, steht inhaltlich das gleiche (man muss nur mal den Absatz über und unter der Definition von sichere Kante lesen, denn dort wird die Definition eingeklemmt):
Corman hat geschrieben:...Invariante: Unmittelbar vor jeder Iteration ist A Teilmenge eines minimalen Spannbaums.

In jedem Schritt bestimmen wir eine Kante (u, v), die zu A hinzugefügt werden kann, ohne diese Invariante zu verletzen. Dass bedeutet, dass A vereinigt mit {(u, v)} ebenfalls eine Teilmenge eines minimalen Spannbaumes ist. Wir bezeichnen eine solche Kante als sichere Kante für A, da sie mit Sicherheit zu A hinzugefügt werden kann, ohne die Schleifeninvariante zu verletzen.
Der begriff sichere Kante wird in Zusammenhang von MST eingeführt, weshalb irgendwie so wieder sichere Kante => leichte Kante rauskommt. Aber ich vermute mal, dass hier der Begriff im Zusammenhang mit dem Algorithmus temporär eingeschränkt wurde, so dass nur innerhalb von GENERIC-MST gilt sichere Kante => leichte Kante, aber im allgemeinen gilt das halt nicht.

Benutzeravatar
mantra
Computerversteher
Computerversteher
Beiträge: 385
Registriert: 23. Okt 2005 23:56
Wohnort: Wiesbaden

Re: Übung 6 - H1 Verständnisproblem

Beitrag von mantra »

Vielleicht liegt es an der Uhrzeit, aber ich verstehe euer Problem nicht ganz.

Wenn ich mir zum Beispiel Ü6 G1 ansehe, gibt es dort drei sichere Kanten. Jede dieser Kanten könnte von GENERIC-MST als nächste genommen werden, aber nur eine davon hast minimales Gewicht.

Stumpf.Alex
Nerd
Nerd
Beiträge: 647
Registriert: 1. Okt 2007 12:40
Wohnort: Darmstadt
Kontaktdaten:

Re: Übung 6 - H1 Verständnisproblem

Beitrag von Stumpf.Alex »

mantra hat geschrieben:Vielleicht liegt es an der Uhrzeit, aber ich verstehe euer Problem nicht ganz.

Wenn ich mir zum Beispiel Ü6 G1 ansehe, gibt es dort drei sichere Kanten. Jede dieser Kanten könnte von GENERIC-MST als nächste genommen werden, aber nur eine davon hast minimales Gewicht.
Eben, eine davon ist minimal, also eine leichte Kante, und der Rest sind nur sichere Kanten. Da aber im Algorithmus nur von sicheren Kanten die Rede ist, steht da nirgends, dass die ausgewählte sichere Kante eine leichte sein muss => der erzeugte Spannbaum muss auch nicht minimal sein.
Im Buch und in der Vorlesung umgehen die das Problem, in dem sie sagen, dass eine sichere Kante gleich einer leichten Kante ist und somit sichere Kante => leichte Kante als Aussage benutzt wird. Das aber sorgt hier gerade für große Verwirrung, da zwei Widersprüchige Aussagen auftreten, da in der HÜ gerade gezeigt werden soll, dass eben nicht sichere Kante => leichte Kante gelten soll.

Antworten

Zurück zu „Archiv“