nicht angemeldet
Hi
Sorry, aber das ist mir zu konfus!
Das allgemeine Problem ist äquivalent dazu n Männer und Frauen (Knotenmenge A und B) miteinander zu verheiraten, wobei die Kanten ausdrücken, wer mit wem könnte.
Deswegen spricht die deutsche Mathematik bei Bipartiten Graphen auch vom "Heiratssatz" um die existenz einer vollständigen Lösung zu beschreiben.
Optimierst du nun zusätzlich über gerichete und gewichtete Kanten, dann ist das in unserem Bild vergleichbar mit Brautpreis in der einen und Mitgift in der anderen Richtung.
Da du aber nur in eine Richtung optimieren willst, reicht es auf einen ungerichteten Graphen zu vereinfachen. Alles andere macht keinen Sinn.
Na und dafür hast du ja angeblich schon nen Algorithmus!
tschau
LanX