Min. Durchmesser-Spannbäume < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 13:49 Mo 05.01.2009 | | Autor: | jno |
| Aufgabe | Sei [mm]G:=(V,E)[/mm] ein ungerichteter zusammenhängender Graph mit einer auf den Kanten induzierten Distanzfunktion [mm]d: E \to \mathbb{R}_+[/mm] und [mm] \Pi[/mm] ein Algorithmus, der einen Spannbaum [mm]S:=(V,E')[/mm] bestimmt, so dass dieser unter allen Spannbäumen von [mm]G[/mm] den kleinsten Durchmesser besitzt.
Sei nun [mm]e \in E[/mm] eine Kante und [mm]G'[/mm] der Graph der ensteht, wenn in [mm]G[/mm] die Kante [mm]e[/mm] kontrahiert wird. Falls die beiden Endknoten der Kante [mm]e[/mm] gemeinsame Nachbarn besitzen, wird das Minimum der beiden alten Kantengewichte als Kantengewicht vom Nachbarn zum neuen Knoten gewählt.
Zu zeigen:
Wird der Algorithmus [mm]\Pi[/mm] auf den Graphen [mm]G'[/mm] angewandt und anschließend im entstandenen Spannbaum [mm]S'[/mm] die Kontraktion wieder rückgängig gemacht, so ist der entstandene Graph ein Spannbaum von [mm]G[/mm], der minimalen Durchmesser unter allen Spannbäumen von [mm]G[/mm], die die Kante [mm]e[/mm] enthalten, hat. |
Diesen Beweis muss ich für eine Studienarbeit führen und habe die Frage in keinem anderen Forum gestellt. Genauergesagt weiss ich noch gar nicht, ob die Behauptung wirklich stimmt, aber ich bin mir ziemlich sicher, dass es klappt. Wenn jemand ein Gegenbeispiel dafür hat, bin ich auch glücklich, dann muss ich mir nämlich was anderes ausdenken 
Mein erster Ansatz war, anzunehmen, dass der Algorithmus einen Spannbaum s geliefert hat, der kontrahierte Spannbaum heißt s' und ich nehme an, dass ein Spannbaum s2 existiert, der einen kleineren Durchmesser als s hat und die Kante e enthält.
Für den Fall, dass sowohl bei s, alsauch bei s2 die Kante e auf dem Durchmesserpfad liegt, habe ich argumentiert:
d(s2)<d(s) => d(s2) - d(e) < d(s) - d(e) => d(s2') < d(s')
Die letzte Aussage wäre nun ein Widerspruch zur Minimalität von s', allerdings hab ich dann - viel zu spät - gemerkt, dass die letzte Implikation Blödsinn ist, da ja durch die Kantenkontraktion nicht zwangsläufig der neue Durchmesser gleich der Differenz des alten und des Kantengewichtes sein muss, der Durchmesserpfad kann ja ganz anders aussehen jetzt..
Jetzt bin ich etwas ratlos. Hatte mir überlegt, dass ich vielleicht mal den Zusammenhang zwischen dem Durchmesserpfad im Spannbaum und dem im kontrahierten Spannbaum untersuche. Ich glaube komplett disjunkt können die nämlich nicht sein. Aber ich weiss auch noch nicht, ob mir das was bringt...?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:07 Mo 05.01.2009 | | Autor: | SEcki |
> d(s2)<d(s) => d(s2) - d(e) < d(s) - d(e) => d(s2') < d(s')
Imo schon sehr richtig, fehlt bloß eine Betrachtung wenn man andere Kanten als e schluckt.
> Die letzte Aussage wäre nun ein Widerspruch zur Minimalität
> von s', allerdings hab ich dann - viel zu spät - gemerkt,
> dass die letzte Implikation Blödsinn ist, da ja durch die
> Kantenkontraktion nicht zwangsläufig der neue Durchmesser
> gleich der Differenz des alten und des Kantengewichtes sein
> muss, der Durchmesserpfad kann ja ganz anders aussehen
> jetzt..
Könntest du hierzu ein Beispiel machen? Ich sehe das Problem hier nicht. Imo ist das ein schneller Widerspruch zur Minimalität im kontrahierten Baum (da man im Kollisionsfall ja die Kante mit dem kleinsten Gewicht nimmt).
SEcki
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:58 Mi 07.01.2009 | | Autor: | jno |
Hallo, danke für deine Antwort.
> > d(s2)<d(s) => d(s2) - d(e) < d(s) - d(e) => d(s2') < d(s')
>
> Imo schon sehr richtig, fehlt bloß eine Betrachtung wenn
> man andere Kanten als e schluckt.
Verstehe nicht ganz, was du meinst. Ich will ja nur eine ganz bestimmte Kante e kontrahieren. Wieso andere schlucken?
>
> > Die letzte Aussage wäre nun ein Widerspruch zur Minimalität
> > von s', allerdings hab ich dann - viel zu spät - gemerkt,
> > dass die letzte Implikation Blödsinn ist, da ja durch die
> > Kantenkontraktion nicht zwangsläufig der neue Durchmesser
> > gleich der Differenz des alten und des Kantengewichtes sein
> > muss, der Durchmesserpfad kann ja ganz anders aussehen
> > jetzt..
>
> Könntest du hierzu ein Beispiel machen? Ich sehe das
> Problem hier nicht. Imo ist das ein schneller Widerspruch
> zur Minimalität im kontrahierten Baum (da man im
> Kollisionsfall ja die Kante mit dem kleinsten Gewicht
> nimmt).
Mein Problem ist, dass ich in der letzten Implikation ja eigentlich annehme, dass d(s2)-d(e) = d(s2') sowie d(s)-d(e) = d(s'), was ja nicht unbedingt stimmt, wenn man zB den Graph:
1 2 1
2 3 10 Kante e
3 4 1
4 5 1
4 6 4
5 7 4
betrachtet (die ersten beiden Spalten sind Knotennamen, zwischen denen eine Kante existiert, die 3. gibt die Kantengewichte an... oder gibts hier irgendein tolles TeX-Graphenpaket? =)), dann hat der Durchmesser 17, aber der kontrahierte Graph hat nicht Durchmesser 17-10 = 7, sondern 9. Der Durchmesserpfad sieht jetzt ganz anders aus.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:44 Mi 07.01.2009 | | Autor: | SEcki |
> > Imo schon sehr richtig, fehlt bloß eine Betrachtung wenn
> > man andere Kanten als e schluckt.
> Verstehe nicht ganz, was du meinst. Ich will ja nur eine
> ganz bestimmte Kante e kontrahieren. Wieso andere
> schlucken?
Ich meinte die Kollisionen, wo man die kleinere schluckt. Aber jetzt versteh ich erst dein Problem wirklich ...
> Mein Problem ist, dass ich in der letzten Implikation ja
> eigentlich annehme, dass d(s2)-d(e) = d(s2') sowie
> d(s)-d(e) = d(s'), was ja nicht unbedingt stimmt, wenn man
> zB den Graph:
>
> 1 2 1
> 2 3 10 Kante e
> 3 4 1
> 4 5 1
> 4 6 4
> 5 7 4
Gar nicht so übel, hab ich mir aufgeziechnet. Vielleicht Knotennamen a, b usw verwenden - ich kam mit den Ziffern durcheinander ...
> betrachtet (die ersten beiden Spalten sind Knotennamen,
> zwischen denen eine Kante existiert, die 3. gibt die
> Kantengewichte an... oder gibts hier irgendein tolles
> TeX-Graphenpaket? =)), dann hat der Durchmesser 17, aber
> der kontrahierte Graph hat nicht Durchmesser 17-10 = 7,
> sondern 9. Der Durchmesserpfad sieht jetzt ganz anders aus.
Du hast völlig recht. Es ist sogar so, dass der Durchmesser nicht sinken braucht, oder aber um genau das Kantengewicht abfällt - oder alles dazwischen. Ich bin mir nicht mehr sicher, ob die Behauptung stimmt oder nicht. Also überhaupt nicht sicher. Vielleicht fällt mir noch mehr ein - hast du schon rumexperimentiert?
SEcki
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:28 Mo 12.01.2009 | | Autor: | jno |
Hi,
etwas rumexperimentiert hab ich schon, allerdings nur mit dem Ergebnis, dass die Behauptung in allen Beispielen gestimmt hat... *g*
Ich versuche gerade einen neuen, direkten Beweisansatz:
Sei wieder s der Spannbaum, der die Kante e = (r1,r2) enthält und s' der Spannbaum mit der kontrahierten Kante e und d = (v1,...,v2) der Durchmesserpfad von s'.
Fall 1: Die zu dem Knoten r1r2 kontrahierte Kante liegt auf d. Dann sind alle Pfade, die in s' durch r1r2 verlaufen, in s genau um die Kantenlänge von e länger. Also ist d2 = (v1,...,r1,r2,...v2) der längste Pfad in s.
Fall 2: Die zu dem Knoten r1r2 kontrahierte Kante liegt nicht auf d.
Wir betrachten nun wieder den Durchmesserpfad d2 von s. Liegt die Kante e nicht in d2, so kann das Wiederaufheben der Kontraktion auch keinen Einfluss gehabt haben und d ist nach wie vor der längste Pfad.
Also nehmen wir an, e liegt auf d2. d2 hat mit d nun mindestens einen Endknoten gemeinsam. (Beweis hierfür lasse ich mal aus.)
...
Soweit bin ich im Moment, irgendwie läuft es denke ich darauf hinaus zu argumentieren, dass Zyklen im Baum existieren, falls (v1,...,r1,r2,...v2) und der Durchmesserpfad in s nicht gleich sind. Also wenn d1 zB v1 und v2 beide als Endknoten hat und nicht identisch mit dem erweiterten Durchmesserpfad ist, dann existiert ja offenbar ein Zyklus.
Außerdem habe ich hier noch einen Satz zur Verfügung der sagt:
Sei T ein beliebiger Baum und v1 ein Blatt von T. Bestimme nun den längsten Weg von v1 im Baum. Sei jetzt v2 der andere Endknoten dieses Weges.
Dann ist v2 ein Endknoten des Durchmesserpfades.
Weiss noch nicht genau, ob ich etwas damit anfangen kann, klingt aber irgendwie danach finde ich 
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:21 Fr 06.02.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
