Gut nicht gerade nee Mathefrage sondern eher eine Informatikerfrage, aber ein Mathematiker sollte sie im Grunde auch beantworten können:
Sei G=(V,E) ungerichteter Graph und c:E->N Gewichtsfunktion, die sagt wie viele Kanten sich zwischen zwei Knoten befinden.
Folgendes: Es gibt nen randomisierten MinCut-Algorithmus. Der zwar nicht 100% das richtige Ergebnis liefert, aber zumindest >50%.
Grob gesagt: Man nimmt jedes mal nee zufällige Kante und verschmilzt die dazugehörigen Knoten. Wenn zwischen 2 Knoten eine höhere Anzahl an Kanten ist, ist es leicht zu erkennen, das die Kante eine höhere Chance hat gewählt zu werden.
Jetzt stellt sich mir die Frage warum man nicht das MaxCut Problem auf das MinCut Problem reduzieren kann indem man sagt C(E(p)) := max[i=1..|E|](c(E(i)))-c(E(p)) + 1. Also die Kante mit dem größten Gewicht nimmt und alle anderen von ihr abzieht. Damit ist die Wahrscheinlichkeit doch umgedreht worden und man kann genauso den Algorithmus für MinCut anwenden um MaxCut zu berechnen...
Ich glaub ich überseh da irgendwas...