From: Jan Hoffmann (hoffmann@informatik.uni-muenchen.de)
Date: Mon Jul 07 2003 - 16:20:42 CEST
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?
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.
Gruß Jan
This archive was generated by hypermail 2.1.5 : Tue Jul 08 2003 - 17:15:01 CEST