From: Jan Johannsen (jjohanns@informatik.uni-muenchen.de)
Date: Tue Jul 08 2003 - 17:09:35 CEST
Jan Hoffmann schreibt:
> Das Corollar ist glaube ich falsch. Gegenbeispiel: G = (V,E) mit V
> = {a,b,c}, alle verbunden und w( {a,b} ) = w( {a,c} ) = 1, w( {b,c}
> ) = 100, A := leere Menge Dann ist A Teilmenge eines
> min. Spannbaums und e = {b,c} eine Kante minimalen Gewichts die die
> Zusammenhangskomponenten {b} und {c} verbindet. Dann ist nach dem
> Corollar e sicher für A. Das ist offensichtlich ein Widerspruch.
> Oder nicht?
Sie haben recht, so wie es dasteht, ist es falsch.
Man koennte es (mit gutem Willen) so lesen, dass gemeint
ist: eine Kante $e$, die minimales Gewicht hat unter ALLEN
Kanten, die irgendwelche zwei Zus.komponenten von A verbinden, ist
sicher fuer A.
Das reicht fuer die Korrektheit von Kruskal, ist aber wohl
zugegebenermassen nicht, was ich im Sinne hatte, als ich das
schrieb.
> Der Beweis für dasselbe Corollar im Buch ist falsch und beweist
> ungefähr das folgende: Ist v noch nicht verbunden mit A und ist e =
> {u,v} eine Kante minimalen Gewichts in der Adjazenzliste von v,
> dann ist e sicher für A.
> Dieses Corollar wäre aber für die Beweise der Korrektheit von
> Kruskal und Prim schon ausreichend.
Diese Version reicht nur aus fuer die Korrektheit von Prim.
Was im Buch (2. Aufl.) steht, ist aber korrekt, und nicht
das Gleiche wie auf meiner Folie, naemlich:
"Sei C eine Zus.komponente von A, und e eine Kante min. Gewichts,
die C mit (irgend-) einer anderen Zus.komponente verbindet, dann
ist e sicher fuer A."
Dies ist korrekt, und reicht fuer die Korrektheit beider Algorithmen
aus.
Vielen Dank fuer das aufmerksame Lesen
Jan Johannsen
This archive was generated by hypermail 2.1.5 : Tue Aug 05 2003 - 20:25:00 CEST