[informatik-bonn] Re: CVS-Log: Uni Projekte

  • From: Candle Jack <Candlejack@xxxxxxxxxxxxx>
  • To: <informatik-bonn@xxxxxxxxxxxxx>
  • Date: Sun, 12 Jan 2003 22:02:16 +0100

>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


Other related posts: