>Die findet so nicht einen Knotenmenge, die immer höchstens doppelt so >groß wie die minimal überdeckende Menge ist... >Warum nehmen wir nicht einfach die Knoten als überdeckende Menge, die >rausgeschmissen werden, das ist IMHO sogar die minimal überdeckende, >kanns nur nicht Beweisen... >Weiß irgendjemand ein paar Eigenschaften dieser Minimal überdeckenden Menge? natürlich bilden die rausgeschmissenen Knoten die Überdeckung, habs halt nur vergessen aufzuschreiben. Da es ein Greedy ist, findet er nicht die minimale, stelle dir einen Stern mit drei Strahlen a 2 Kanten vor, der algo nimmt den zentralknoten und die drei mittleren Knoten der Strahlen. eine Minimale währen aber nur die Drei Knoten in der Mitte der Strahlen. Die eigenschaften der minimalen Überdeckung stehen doch in der Aufgabe. So verbessere jetzt gleich die 4 und schreibe die 3 auf. Jochen