[informatik-bonn] Re: Blatt 13 3b

  • From: Philipp Kirchner <mail@xxxxxxxxxxxxxxxxxx>
  • To: informatik-bonn@xxxxxxxxxxxxx
  • Date: Sun, 26 Jan 2003 15:12:10 +0100

Philipp Kirchner wrote:

Lutz Oberst wrote:

On Fri, Jan 24, 2003 at 08:31:15PM +0100, Philipp Kirchner wrote:

Moin,


Ich denke schon. Im Grunde ist das doch die Frage ob gilt:
a+b < c+d => a*b < c*d   \forall a,b,c,d \in N


Hab schon ein Gegenbeispiel ;-)

a=b=4, c=2, d=7.... Schade



Hmmm, stimmt.


Anderer Ansatz: Das Produkt ist minimal, wenn die einzelnen
Faktoren minimal sind. Damit treffen wir immer die
richtige Entscheidung, wenn wir 2 ZHK mit der
minimalen Kante verbinden, da wir ja beim Hinzufügen
einer anderen Kante einen nicht minimalen Faktor in
das Produkt einbauen würden.

Das sehe ich auch so....


Spiele ich später noch mal durch, melde mich dann

Philipp


Damit wäre Kruskal ok. (?)
Das habe ich jetzt auch auch so raus, die Kanten sind ja nach Gewicht sortiert, also werden immer die minimalen Faktoren rausgesucht, das Produkt wird minimal.
Also ist Kruskal doch ok, hätte man sich denken können, gibt ja nur einen Punkt (Dafür habe ich mich aber jetzt mit dem Algorithmus von Kruskal auseinandergesetzt und kann vielleicht bald was zur 2 sagen..


Gruß Philipp


Gruß Philipp


Bye, Lutz








Other related posts: