Übung 6 - H1 Verständnisproblem

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

Re: Übung 6 - H1 Verständnisproblem - Tippfehler

Beitrag von VersuchEs »

Hi,
ich muss mich bei euch für den Tippfehler entschuldigen.

jede leichte Kante hat 2 Eigenschaften :
1- Sie muss den Schnitt respektieren
2- Sie muss minimales Gewicht besitzen
Hinweis : Nach der Fragestellung wird die 2. Eigenschaft nicht erfüllt.

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

Re: Übung 6 - H1 Verständnisproblem

Beitrag von VersuchEs »

Hi,
ich muss mich bei euch für den Tippfehler entschuldigen.

jede leichte Kante hat 2 Eigenschaften :
1- Sie muss den Schnitt respektieren
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 »

Wenn die Kante den Schnitt respektiert, dann schneidet sie doch auch gar nicht den Schnitt...oder?

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

Re: Übung 6 - H1 Verständnisproblem

Beitrag von mantra »

Stumpf.Alex hat geschrieben: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.
Diese Folgerung kann ich nicht ganz nachvollziehen. Was meinst du mit minimal? Der erzeugte Spannbaum ist vielleicht nicht minimal im Sinne von "Es gibt keinen anderen Spannbaum mit geringerer Summe der Gewichte". Der erzeugte Spannbaum ist aber minimal im Sinne von "Für die verbundene Knotenmenge gibt es keinen anderen Spannbaum mit geringerer Summe der Gewichte".

Genau genommen sollte man auch nicht von Spannbäumen reden, bevor nicht alle Knoten verbunden sind. Insofern hat man als Zwischenergebnisse immer nur Teilgraphen von Spannbäumen. So gesehen ist es auch kein Problem, dass man zwischendurch keinen minimalen Spannbaum hat, sondern lediglich wichtig, dass man immer einen Teilgraphen des MST hat.

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

Re: Übung 6 - H1 Verständnisproblem

Beitrag von mantra »

VersuchEs hat geschrieben:Hi,
ich muss mich bei euch für den Tippfehler entschuldigen.

jede leichte Kante hat 2 Eigenschaften :
1- Sie muss den Schnitt respektieren
2- Sie muss minimales Gewicht besitzen
Hinweis : Nach der Fragestellung wird die 2. Eigenschaft nicht erfüllt.
Meinst du die Fragestellung des Themenerstellers oder die der Aufgabe?

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:
Stumpf.Alex hat geschrieben: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.
Diese Folgerung kann ich nicht ganz nachvollziehen. Was meinst du mit minimal? Der erzeugte Spannbaum ist vielleicht nicht minimal im Sinne von "Es gibt keinen anderen Spannbaum mit geringerer Summe der Gewichte". Der erzeugte Spannbaum ist aber minimal im Sinne von "Für die verbundene Knotenmenge gibt es keinen anderen Spannbaum mit geringerer Summe der Gewichte".
Achso...das minimal heißt hier minimale Anzahl an Kanten? Eigentlich ist ja der Spannbaum ja schon implizit so definiert. Deshalb ist das sehr verwirrend, wenn von minimalen Spannbäumen die rede ist, weil ich zumindest damit automatisch immer einen Spannbaum mit minimalen Gewicht verstehe.

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

Re: Übung 6 - H1 Verständnisproblem

Beitrag von mantra »

Natürlich ist ein minimaler Spannbaum über sein minimales Gewicht definiert.

Nur sind nicht alle Teilgraphen eines MST auch minimale Teilgraphen.

Benutzeravatar
Rinderhack
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 151
Registriert: 17. Okt 2005 20:13
Wohnort: Großostheim
Kontaktdaten:

Re: Übung 6 - H1 Verständnisproblem

Beitrag von Rinderhack »

Aufgabenstellung:
Sei (S, V-S) ein mit A verträglicher Schnitt
bedeutet das, das die Eigenschaften von (V,A) = ein Teilgraph eines MST zu sein, nach hinzufügen der Schnittüberquerenden Kante weiterhin erfüllt sein muss?
Aber eigentlich ist ja nur der fertige MST minimal, also was soll das "A-verträglich"?

reicht es hier ein Ausführungsschritt des Algorithmus von Prim anzugeben, nachdem die Eigenschaft (vorrübergehend) nicht erfüllt ist? So hab ich das inzwischen verstanden.

Am Ende des Algorithmus muss die Eigenschaft ja erfüllt sein, sonst wäre das Ergebnis ja kein MST. Ich denke, das ist was intuitiv anfangs verwirrt?

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 »

Rinderhack hat geschrieben:Aufgabenstellung:
Sei (S, V-S) ein mit A verträglicher Schnitt
bedeutet das, das die Eigenschaften von (V,A) = ein Teilgraph eines MST zu sein, nach hinzufügen der Schnittüberquerenden Kante weiterhin erfüllt sein muss?
Aber eigentlich ist ja nur der fertige MST minimal, also was soll das "A-verträglich"?

reicht es hier ein Ausführungsschritt des Algorithmus von Prim anzugeben, nachdem die Eigenschaft (vorrübergehend) nicht erfüllt ist? So hab ich das inzwischen verstanden.

Am Ende des Algorithmus muss die Eigenschaft ja erfüllt sein, sonst wäre das Ergebnis ja kein MST. Ich denke, das ist was intuitiv anfangs verwirrt?
Nach jedem Schleifendurchlauf muss die Bedingung erfüllt sein, dass der Teilgraph eines MST durch hinzufügen einer Kante zur Menge A wieder ein neuer Teilgraph des MST ist. Hierbei ändert sich aber der Schnitt, da der Schnitt beliebig gewählt werden kann, so dass auch die Bedingung wieder erfüllt ist.

secretmojo
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 124
Registriert: 31. Jan 2007 19:30

Re: Übung 6 - H1 Verständnisproblem

Beitrag von secretmojo »

Im Skript ist sicher kante auch so definiert:

"Das ist eine kante (u,v) mit der Eigenschaft, dass (V, A + (u,v)) ebenfalls Teilgraph eines MST ist."

und leichte kante:

"...eine kante von minimalem Gewicht, die den Schnitt überquert."

Nach dieser definition ist H1 einfach zu lösen...da man nur eine kante wählen muss, mit der man einen MST erhält, aber die nicht die minimale Kante für den schnitt ist.

P.S.: den Satz MST1 im skript halte ich persönlich für falsch...den beweis überlasse ich dem leser... :lol:

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 »

secretmojo hat geschrieben:Im Skript ist sicher kante auch so definiert:

"Das ist eine kante (u,v) mit der Eigenschaft, dass (V, A + (u,v)) ebenfalls Teilgraph eines MST ist."
Und was ist nun genau ein MST? Also nach meinem Wissensstand ein minimaler Spannbaum. Und das habe ich gerade im Corman nachgeschaut, wo explizit ausgedrückt wird, dass immer mit einem minimalen Spannbaum (MST) ein Spannbaum mit minimalen Kantengewicht gemeint ist. D.h. also, dass man jede Kante die man hinzufügt um einen MST zu erhalten auch leicht sein muss....

Benutzeravatar
Maeher
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 282
Registriert: 14. Okt 2007 23:02
Kontaktdaten:

Re: Übung 6 - H1 Verständnisproblem

Beitrag von Maeher »

Leicht ist immer in bezug auf einen Schnitt. Zu jeder sicheren Kante findet man irgendwann auch einen Schnitt, so dass sie eine leichte Kante ist. Aber du kann einfach einen Schnitt angeben, in dem es nicht stimmt.

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 ok...das hört sich schonmal plausibel an. Kannst du mir auch dazu ein Beispiel für einen Schnitt geben für die offensichtlich sichere Kante (f, d), wenn die schwarz makierten Kanten zur Menge A gehören, die den Schnitt respektieren soll und die Kantenmenge eines Teilgraphen eines MST ist?
Dateianhänge
graph.JPG
graph.JPG (17.33 KiB) 695 mal betrachtet

Benutzeravatar
Maeher
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 282
Registriert: 14. Okt 2007 23:02
Kontaktdaten:

Re: Übung 6 - H1 Verständnisproblem

Beitrag von Maeher »

öhm (f, d) ist keine sichere Kante. Aber (f,e) ist eine sichere Kante und überquert den eingezeichneten Schnitt, ist aber offensichtlich nicht leicht. (in Bezug auf den Schnitt)

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 »

hmmm.. und warum ist (f, d) keine sichere Kante? Weil sie nicht minimal ist? Aber wieso ist es dann (f, e)?
Bezieht sich sichere Kante vielleicht auf darauf, dass diejenige Kante (u, v) sicher ist, welche von allen anderen Kanten die den Schnitt überqueren und nach v gehen minimal ist?
Also das Beispiel: Zu d gehen die Kanten (f, d) und (c, d). Aber nur (c, d) ist sicher, weil diese minimal ist?

Und bedeutet das, dass eine leichte Kante dann die minimale aller sicheren Kanten ist?
also in dem Beispiel: Alle sicheren Kanten (h, a), (c, a), (c, d) und (f, e) und die leichte Kante ist (c, d) weil diese die minimalste von allen ist?

Hoffe ich habe es nun richtig verstanden...wenn nicht helft mir mal kurz mit diesem Beispiel auf die Sprünge....

EDIT:
Hmm... also sichere Kanten sind einfach alle den Schnitt kreuzenden Kanten, die bei hinzunahme wieder einen MST erzeugen.
Die leichte Kante ist einfach die minimale sichere Kante.

btw: (f, e) ist auch keine sichere Kante, weil der Spannbaum dann nicht minimal wäre.

Antworten

Zurück zu „Archiv“