Blatt 5 Aufgabe 5

Ich hab nicht ganz die constraints für die Anfangspartition bezüglich Balanciertheit verstanden:

Ist z.b. P={{1},{2,3,4,5,6,7,8}} als Anfangspartition möglich?

Was geschieht bei ungerader Anzahl von Knoten? Wird der letzte Knoten dann einfach nicht betrachtet?


felix

Hallo

In den Folien zur Vorlesung steht "bestimme eine „ungefähr gleichgroße“ Anfangsaufteilung". Wir beschränken uns aber üblicherweise auf eine gerade Anzahl Knoten und auf zwei Teilmengen, die genau gleich groß sind.

Wenn es eine ungerade Anzahl Knoten gibt, so hat eine Menge genau ein Element mehr als die andere; dieser Fall kommt aber bei uns nicht vor.

Grüße
Tobias Nopper

Wie wärs mal mit nem Tip? :)

Hi

Ok, Tip: Ich habe ein Beispiel mit acht Knoten konstruiert. Ich glaube nicht, daß es ein Beispiel mit sechs Knoten gibt, lasse mich notfalls aber überzeugen. ;)

Grüße
Tobias Nopper

Darf man negative Gewichte nehmen ?

Hi

Na, das macht ja keinen Sinn. Die Gewichtung einer Kante repräsentiert die Anzahl der Leitungen zwischen den beiden Knoten/Modulen; ich habe noch nie Module gesehen, die durch eine negative Anzahl Leitungen verbunden ist.

Die Gewichtungen müssen alle >=0 sein.

Grüße
Tobias Nopper

;D Lol ... negative Gewichte - der war gut!

haha,,
stimmt
ich hab gar nicht dran gedacht ( die Gewichte repraesentieren die # Leitungen )
:)))
Nur war es mir sehr einfach hier und da eine negaive Zahl zu haben um die Aufgabe zu loesen.

Aber jetzt habe ich es auch ohne neg.:))

:angry: was für eine gemeine Aufgabe, Tobi!!!! Ich saß stundenlang dran, aber ich hab's hingekriegt, hab den Kernighan Lin deswegen so oft angewandt, dass ich jetzt an nichts anders denken kann... werde bestimmt Albträume haben. :)