Minimale Bäume < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Ein zusammenhängender Graph G = (V,E) habe paarweise verschiedene Gewichte auf den Kanten. Man zeige, dass G einen eindeutigen minimalen aufspannenden Baum besitzt. |
Hi,
bei dieser Aufgabe komme ich gerade nicht so weiter. Wir haben minimal aufspannende Bäume in Bezug mit dem Algorithmus von Kurskal von definiert, und zwar wie folgt:
Der durch das Verfahren von Kruskal zum zusammenhängenden Graphen G=(V,E) erzeugte Graph T'=(V,E') ist ein minimaler G aufspannender Baum.
In der Aufgabenstellung ist das eindeutig auch nochmal unterstrichen. Zu eindeutig habe ich was im folgenden Satz gefunden:
Sei G=(V,E) ein zusammenhängender Graph, f: E [mm] \to \IR [/mm] eine nicht-negative Kantenbewertung und x [mm] \in [/mm] V. Der Algorithmus von Dijkstra ergibt einen G aufspannenden Baum mit der Eigenschaft, dass für jedes y \ V der in T eindetige Weg von x nach y ein minimaler (x,y)-WEg mit d(x,y)=l(y) ist.
Also erstmal wissen wir ja, dass G zusammenhängend ist, daraus folgt aber noch nicht direkt, dass G auch ein Baum ist, oder?
Wie kann ich mit dieser Aufgabe jetzt anfangen??
Danke für Hilfe schon mal.
Grüße
|
|
| |
|
> Ein zusammenhängender Graph G = (V,E) habe paarweise
> verschiedene Gewichte auf den Kanten. Man zeige, dass G
> einen eindeutigen minimalen aufspannenden Baum besitzt.
> Hi,
>
> bei dieser Aufgabe komme ich gerade nicht so weiter. Wir
> haben minimal aufspannende Bäume in Bezug mit dem
> Algorithmus von Kurskal von definiert, und zwar wie folgt:
>
> Der durch das Verfahren von Kruskal zum zusammenhängenden
> Graphen G=(V,E) erzeugte Graph T'=(V,E') ist ein minimaler
> G aufspannender Baum.
>
> In der Aufgabenstellung ist das eindeutig auch nochmal
> unterstrichen. Zu eindeutig habe ich was im folgenden Satz
> gefunden:
>
> Sei G=(V,E) ein zusammenhängender Graph, f: E [mm]\to \IR[/mm] eine
> nicht-negative Kantenbewertung und x [mm]\in[/mm] V. Der Algorithmus
> von Dijkstra ergibt einen G aufspannenden Baum mit der
> Eigenschaft, dass für jedes y \ V der in T eindetige Weg
> von x nach y ein minimaler (x,y)-WEg mit d(x,y)=l(y) ist.
>
> Also erstmal wissen wir ja, dass G zusammenhängend ist,
> daraus folgt aber noch nicht direkt, dass G auch ein Baum
> ist, oder?
>
> Wie kann ich mit dieser Aufgabe jetzt anfangen??
>
> Danke für Hilfe schon mal.
>
> Grüße
Hallo Steve,
ich denke, dass da ein aufbauendes oder abbauendes Rezept
zur Bildung eines solchen Minimalbaums möglich sein sollte,
verbunden mit einem Beweis durch vollständige Induktion.
Z.B. fängt man mit dem vorliegenden Graph an und lässt
zuerst mal alle Schleifen weg, also Kanten mit identischem
Anfangs- und Endpunkt. Ferner lässt man zu jedem Paar
von Knoten, welche durch mehr als eine Kante verbunden
sind, alle dieser Kanten ausser der kürzesten weg. Dann
versucht man, "Kreise" nach der Reihe zu eliminieren, indem
man jeweils von ihren Kanten die längste herausnimmt.
Dabei sollte man wohl mit jenem Kreis beginnen, der die
längste noch vorhandene (überhaupt noch einem Kreis
angehörende) Kante besitzt.
So macht man weiter, bis man nur noch einen Baum hat.
Mach dir das zunächst an ein paar selber gebastelten Bei-
spielen klar, bis du in der Lage bist, den Algorithmus und
den zugehörigen Minimalitätsbeweis klar zu notieren.
LG Al-Chwarizmi
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:19 Fr 14.05.2010 | | Autor: | SEcki |
> ich denke, dass da ein aufbauendes oder abbauendes Rezept
> zur Bildung eines solchen Minimalbaums möglich sein
> sollte,
Ja, aber das ist nicht die Aufgabe. Die Aufgabe ist: unter den Bedingungen ist der minimale Spannbaum eindeutig. Alles, was du geschrieben hast, geht darauf nicht ein. Die Frage, die nämlich bleibt: warum ist der minimale Baum eindeutig? Bzw.: warum gibt es nur einen?
Daher habeich die Frage wieder auf unbeantwortet gestellt.
SEcki
|
|
|
| |
|
> > ich denke, dass da ein aufbauendes oder abbauendes Rezept
> > zur Bildung eines solchen Minimalbaums möglich sein
> > sollte,
>
> Ja, aber das ist nicht die Aufgabe. Die Aufgabe ist: unter
> den Bedingungen ist der minimale Spannbaum eindeutig.
> Alles, was du geschrieben hast, geht darauf nicht ein. ![[haee]](/images/smileys/haee.gif "[haee]") ![[kopfschuettel]](/images/smileys/kopfschuettel.gif "[kopfschuettel]")
Das stimmt so nicht ganz: ich habe von einem Beweis durch
vollständige Induktion geschrieben. Damit war genau der
Beweis der Minimalität und Eindeutigkeit gemeint, den man
auf meinem skizzierten Weg wohl führen kann.
Ich hatte jedoch nicht vor, einen solchen Beweis wirklich
vorzuführen - in der Meinung, dass meine Anregung wohl
genügen würde.
LG Al-Chw.
> Die Frage, die nämlich bleibt: warum ist der minimale Baum
> eindeutig? Bzw.: warum gibt es nur einen?
>
> Daher habeich die Frage wieder auf unbeantwortet gestellt.
>
> SEcki
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 12:18 Sa 15.05.2010 | | Autor: | SEcki |
> Wie kann ich mit dieser Aufgabe jetzt anfangen??
Die Kanten sind durch die Gewichte total geordnet. Nimm an, du hättest zwei minimale Spannbäume [m]T=e_1
SEcki
|
|
|
| |
|
HI,
> Die Kanten sind durch die Gewichte total geordnet. Nimm an, du hättest zwei minimale Spannbäume $ [mm] T=e_1
Aber erstmal muss ich doch irgendwie beweisen, dass dieser minimale Baum überhaupt besteht, oder nicht??
Ich glaube dein Denkansatz ist eher dafür gedacht, um die Eindeutigkeit zu zeigen, oder sehe ich das gerade falsch?
Und wieso definierst du dann einmal einen Spannbaum so: [mm] T=e_1
Und das mit dem Widerspruch habe ich auch leider noch nicht verstanden.
Vielleicht kommen ja noch paar tipps.
Grüße
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 01:12 Mo 17.05.2010 | | Autor: | SEcki |
> Aber erstmal muss ich doch irgendwie beweisen, dass dieser
> minimale Baum überhaupt besteht, oder nicht??
Kruskal liefert einen. Im Übrigen ist das Minimum über eine endliche Anzahl von Bäumen eh wohldefiniert und liefert die Existenz.
> Ich glaube dein Denkansatz ist eher dafür gedacht, um die
> Eindeutigkeit zu zeigen, oder sehe ich das gerade falsch?
Klar. Die Exisenz ist ja eh schon da.
> Und wieso definierst du dann einmal einen Spannbaum so:
> [mm]T=e_1
> T'=e'_1,e'_2,...
Durch die Kanten halt. Das sollte beim 2. auch < anstatt Kommata stehen.
SEcki
|
|
|
| |
|
Hallo,
eigentlich findet man ![[]](/images/popup.gif) da fast alles Nötige
für den verlangten Beweis. Für den Nachweis
der Eindeutigkeit des Kruskal-Spannbaums ist
dann die Voraussetzung der paarweise verschie-
denen Kantengewichte wesentlich.
LG Al-Chw.
|
|
|
| |
|
Hi nochmal,
also ich habe jetzt so begonnen:
Sei G=(V,E) ein zusammenhängender kantengewichteter Graph. Der Algorithmus von Kruskal liefert uns einen Teilgraphen T'=(V,E'), der zusammenhängend ist, keinen Kreis enthält, der ein spannender Treilgraph von G ist und letztendlich bezüglich G auch minimal ist.
[mm] \Rightarrow [/mm] T'=(V,E') ist ein minimaler Spannbaum bezüglich G.
Die Kanten eines minimalen Spannbaumes sind durch die Kantengewichte total geordenet. Wir nehmen an, wir hätten zwei minimale Spannbäume T'=e'_1 < e'_2 < .... und [mm] T=e_1 [/mm] < [mm] e_2 [/mm] < .... Dann existiert ein [mm] m\in \IN_0 [/mm] mit [mm] e_m \not=e'_m.
[/mm]
So jetzt weiß ich nicht, wie ich das widerlegen soll? Es reicht ja wohl nicht zu sagen, dass durch den Algo. von Kruskal nur ein Spannbaum exisiert oder? Ich glaube, dass ist sogar auch nicht richtig, nachdem was ich hier gelesen habe:
"Der Algorithmus von Kruskal arbeitet nicht-deterministisch, d.h. er liefert unter Umständen beim wiederholten Ausführen unterschiedliche Ergebnisse. Alle diese Ergebnisse sind minimale Spannbäume von G."
Kann mir da vielleicht jemand nochmal weiterhelfen?
Grüße
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 13:42 Mo 17.05.2010 | | Autor: | SEcki |
> So jetzt weiß ich nicht, wie ich das widerlegen soll? Es
> reicht ja wohl nicht zu sagen, dass durch den Algo. von
> Kruskal nur ein Spannbaum exisiert oder?
Per se nicht.
> Kann mir da vielleicht jemand nochmal weiterhelfen?
Wenn die Bedingung gegeben ist, dann ist Kruskal deterministisch.
Eine Analyse des Beweis warum Kruskal einen minimalen Spannbaum liefert, liefert dann (wäre auch meine Beweisidee gewesen) auch die Eindeutigkeit.
SEcki
|
|
|
| |
|
hmmmm,
dann weiß ich jetzt gerade immer noch nicht, wies weitergeht.
Den ersten Teil wie ich ihn oben zusammengefasst habe, kann ich dann aber so lassen, oder??
|
|
|
| |
|
> hmmmm,
>
> dann weiß ich jetzt gerade immer noch nicht, wies
> weitergeht.
Also wenn mal die Konstruktion eines minimalen Spannbaums
nach Kruskal klar ist: Wenn man zusätzlich weiß, dass alle
Kanten des gesamten Graphen unterschiedliche Längen
(bzw. "Gewichte") haben, dann kann man sich klar machen,
dass die Reihenfolge der Auswahl der Kanten, aus welchen
man den Minimalbaum schrittweise aufbaut, bei jedem
einzelnen Schritt eindeutig ist. Nur dann, wenn es irgendwann
beim Kruskal-Verfahren mehr als eine gleich kurze Kante
(die mit den schon gewählten Kanten keinen Kreis bildet)
zur Wahl gäbe, kann dieses "nicht-deterministisch" werden.
Unter der Voraussetzung über die allesamt verschiedenen
Kantenlängen gibt es bei keinem einzigen Kruskal-Schritt
eine solche "freie Wahl". Somit wird klar, dass für derartige
Graphen das Verfahren einen komplett eindeutig bestimmten
minimalen Spannbaum liefern muss. Wenn du diese Idee der
bei jedem einzelnen Schritt herrschenden eindeutigen Wahl
der nächsten Kante etwas formaler darstellst, kommst du
zu einer Darstellung in der Art, wie SEcki sie vorschlägt.
Wenn zwei unterschiedliche "Kruskominimalspannbäume"
für einen Graphen existieren würden, müsste es bei deren
schrittweisem Aufbau einen ersten Schritt geben, bei welchem
für die beiden Bäume verschiedene Kanten gewählt wurden.
Dies ist aber aus den besagten Gründen nicht möglich.
Die Reihenfolge der beim Kruskal-Verfahren nacheinander
gewählten Kanten muss natürlich keineswegs mit der
Größenreihenfolge dieser Kanten übereinstimmen.
Ein Induktionsbeweis sollte also nicht nach der Reihen-
folge der Kantengewichte gehen, sondern nach der Reihen-
folge beim Aufbau des Kruskalbaums.
(In diesem Punkt bin ich mir nicht ganz sicher, ob SEcki
dies wirklich auch bewusst war ...)
Man kann die Überlegungen eines solchen Beweises aber auch
sprachlich in aller nur gewünschten Präzision beschreiben,
ohne unbedingt eine "Kurzfassung" in mathematischer
Notation zu geben. Natürlich ist auch dies eine gute Übung,
aber klarer und verständlicher werden Beweise durch ihre
mathematisch notierte Kompaktifizierung oft gerade nicht ...
LG Al-Chwarizmi
|
|
|
| |
|
Also dann nochmal ein nächster Versuch:
Sei G=(V,E) ein zusammenhängender kantengewichteter Graph. Der Algorithmus von Kruskal liefert uns einen Teilgraphen T'=(V,E'), der zusammenhängend ist, keinen Kreis enthält, der ein spannender Treilgraph von G ist und letztendlich bezüglich G auch minimal ist.
$ [mm] \Rightarrow [/mm] $ T'=(V,E') ist ein minimaler Spannbaum bezüglich G.
Wir wollen jetzt die Eindeutigkeit dieses Baumes zeigen:
Die Kanten eines minimalen Spannbaumes sind durch die Kantengewichte total geordenet. Wir nehmen an, wir hätten zwei minimale Spannbäume T'=e'_1 < e'_2 < .... (T'=(V,E')) und $ [mm] T=e_1 [/mm] $ < $ [mm] e_2 [/mm] $ < .... (T^#=(V,E^#)) Dann existiert ein [mm] m\in \IN_0 [/mm] $ mit $ [mm] e_m \not=e'_m, [/mm] d.h. [mm] e_m [/mm] und e'_m haben unterschiedliche Kantengewichte.
Nach dem Alg. von Kruskal folgt jetzt auch, dass die Reihenfolge der Auswahl der Kanten, aus welchen man die Minimalbäume schrittweise aufbaut, bei jedem einzelnen Schritt eindeutig ist, da alle Kanten des gesamten Graphen unterschiedliche Kantengewichte haben.
Nur dann, wenn es irgendwann beim Kruskal-Verfahren mehr als eine gleich kurze Kante (die mit den schon gewählten Kanten keinen Kreis bildet) zur Wahl gäbe, kann dieses "nicht-deterministisch" werden.
Unter der Voraussetzung über die allesamt verschiedenen Kantenlängen gibt es bei keinem einzigen Kruskal-Schritt eine solche "freie Wahl". Somit wird klar, dass für derartige Graphen das Verfahren einen komplett eindeutig bestimmten minimalen Spannbaum liefern muss und somit [mm] e_m \not=e'_m [/mm] nicht gelten kann, sonder eher [mm] e_m=e'_m!!!.
[/mm]
Das müsste doch eigentlich so reichen, oder meint ihr nicht??
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:57 Mo 17.05.2010 | | Autor: | SEcki |
> Nach dem Alg. von Kruskal folgt jetzt auch, dass die
> Reihenfolge der Auswahl der Kanten, aus welchen man die
> Minimalbäume schrittweise aufbaut, bei jedem einzelnen
> Schritt eindeutig ist, da alle Kanten des gesamten Graphen
> unterschiedliche Kantengewichte haben.
Es ist per se noch nicht klar, dass es keinen anderen minimalen Spannbaum geben kann, auch wenn der Algo einen eindeutigen Baum liefert.
> Nur dann, wenn es irgendwann beim Kruskal-Verfahren mehr
> als eine gleich kurze Kante (die mit den schon gewählten
> Kanten keinen Kreis bildet) zur Wahl gäbe, kann dieses
> "nicht-deterministisch" werden.
Du musst imo aber noch die Folgen für jedne minimalen Baum mit angeben - zB per Induktion über die Kantenlänge (vgl. mal den Beweis, dass Kruskal wirklich einen minimalen Baum liefert)
> Das müsste doch eigentlich so reichen, oder meint ihr
> nicht??
Ich finde, da ist eine Lücke.
Ich mache mal den Beweis, wie ich ihn mir vorgestellt habe (man vergleiche mit der Wikipedia):
Seien [mm]T:e_1 < e_2 < ... < e_n[/mm] und [mm]T':e'_1 < e'_2 < ... < e'_n[/mm] minimale Spannbäume, wobei die Kanten geordnet sind durch die Gewichtsfunktion. Dann gibt es ein [m]1\le m \le n[/m] mit [m]e_m\neq e'_m[/m], OBdA [m]e_m
SEcki
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:33 Mo 17.05.2010 | | Autor: | jaruleking |
Hi also vielen Dank euch.
Auch wenn ich mir deinen Beweis noch paar mal durchlesen muss. Denn noch habe ich ihn noch nicht so verstanden.
Grüße
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:37 Mo 17.05.2010 | | Autor: | SEcki |
> Somit wird klar, dass für
> derartige
> Graphen das Verfahren einen komplett eindeutig bestimmten
> minimalen Spannbaum liefern muss.
Wieso ist das zwingend ohne Nähere Analyse des Algorithmus? So zeigst du doch nur, dass der Kruskal-Algo einen eindeutigen Spannbaum ausgibt, nicht aber, dass es überhaupt nur einen minimalen Spannbaum gibt.
Der Beweis (ja, der Beweis auf Wikipedia, nicht die Aussage!), dass der Kruskal-Algo einen minimalen Spannbaum liefert, liefert allerdings, wenn man ihn sich genauer anschaut, auch einen Beweis, dass irgendein minimaler Spannbaum durch entsprechende Wahlen im nicht-deterministischen fall durch einen Lauf des Kruskal-Algos erstellt werden kann.
> Wenn zwei unterschiedliche "Kruskominimalspannbäume"
> für einen Graphen existieren würden, müsste es bei
> deren
> schrittweisem Aufbau einen ersten Schritt geben, bei
> welchem
> für die beiden Bäume verschiedene Kanten gewählt
> wurden.
Ja, aber du musst noch zeigen, dass jeder minimale Spannbaum ein "Kruskominimalspannbaum" ist - davon steht in der Aufgabe ja nichts.
> Die Reihenfolge der beim Kruskal-Verfahren nacheinander
> gewählten Kanten muss natürlich keineswegs mit der
> Größenreihenfolge dieser Kanten übereinstimmen.
Wenn die Kanten paarweise verschiedene Gewichte haben, fällt dies aber zusammen.
> Ein Induktionsbeweis sollte also nicht nach der Reihen-
> folge der Kantengewichte gehen, sondern nach der Reihen-
> folge beim Aufbau des Kruskalbaums.
Was in unserem Fall das gleiche ist.
> (In diesem Punkt bin ich mir nicht ganz sicher, ob SEcki
> dies wirklich auch bewusst war ...)
Wenn ich mich irren sollte, bitte ich um Korrektur.
> Man kann die Überlegungen eines solchen Beweises aber auch
> sprachlich in aller nur gewünschten Präzision
> beschreiben,
> ohne unbedingt eine "Kurzfassung" in mathematischer
> Notation zu geben.
Ohne die richtige Notation, weiß niemand, wovon der andere redet.
> Natürlich ist auch dies eine gute
> Übung,
> aber klarer und verständlicher werden Beweise durch ihre
> mathematisch notierte Kompaktifizierung oft gerade nicht
> ...
Das ist ein Mythos. Man muss auf die richtige Menge achten - die moderne Formelsprache ist eher ein Segen, als ein Fluch. Euklid oder Vieta im (übersetzten) Original zu lesen, macht kaum etwas einfacher ...
SEcki
|
|
|
|
