Brauch wieder mathe hilfe :(

[[VK]]

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...

[Ramkhamhaeng]

Ich denke das scheitert an dem „+1“ in deiner neuen Kantengewichtungsfunktion. Damit können dann immer Graphen so konstruiert werden, dass die Lösung deines MinCut-Ersatztproblems beliebig weit von der Lösung des MaxCut-Problems entfernt ist.

[[VK]]

Naja, das +1 Ist ja nur dazu da damit die maximale Kante nicht automatisch auf 0 Geht und damit nie ausgewählt wird :grubel:

[Ramkhamhaeng]

Wie schon geschrieben: „Nur“ ist eine Untertreibung. Wenn man sich einen Graphen vorstellt, bei dem es eine Kante mit sehr hohem Gewicht gibt und dem Gegenüber ein Netz aus sehr vielen Kanten mit Gewicht 1 (so dass die Durchscheidung dieser zwei Strukturen gleich teuer ist, so wird dieses Gleichgewicht zerstört, wenn man bei der Invertierung 1 addiert. Und diese Eins kann man nat. auch nicht weglassen. Ergo ist es nicht so einfach die Probleme aufeinander abzubilden.
Ich gebe aber zu, dass ich selber nicht weiß ob man damit ein Gegenbeispiel konstruieren kann. Sollte aber deine Bedenken gegenüber deiner Konstruktion bestärken.

[Tzu Iop]

Ist da gesichert, dass zur Basis 2 jede beliebige Folge auftreten kann oder ist das nur vermutet?

[Simato]

Ich muss heute mal anfangen, mir Mathe anzuschauen

[v33l3dn3M]

Also, wenn ich eine Gleichung der Form x²+px+q>0 habe... Kann ich das dann zu x1/2>p/2+-Wurzel aus bla umformen, oder muss das Zeichen vielleicht doch < sein oder wie macht man das?

[Ramkhamhaeng]

Skizziere dir doch mal den Kurvenverlauf. Daran sieht man es ohne zu rechnen.

[Der Kantelberg]

Also, wenn ich eine Gleichung der Form x²+px+q>0 habe... Kann ich das dann zu x1/2>p/2+-Wurzel aus bla umformen, oder muss das Zeichen vielleicht doch < sein oder wie macht man das?

Plus und Minus verändern das Ungleichzeichen nicht.
Mal und Geteilt drehen es, falls der Faktor oder Dividend kleiner als Null ist.
http://de.wikipedia.org/wiki/Ungleic...notoniegesetze

[E-Feld]

Plus und Minus verändern das Ungleichzeichen nicht.
Mal und Geteilt drehen es, falls der Faktor oder Dividend kleiner als Null ist.
http://de.wikipedia.org/wiki/Ungleic...notoniegesetze

Und was ist, wenn er gleich Null ist? :o

[Der Kantelberg]

Du willst mich wohl kantelisieren.

[v33l3dn3M]

Also, die Gesetze kenne ich auch, das Problem liegt eher darin, dass ich die Herleitung der PQ-Formel 1.längst vergessen habe, da für mich nur die Anwendung zählt und 2. gerade keinen Nerv dafür habe, sie mir selber noch mal herzuleiten.

[Nycan]

http://www.re-wi.de/quadgleich.pdf

[Nycan]

Ich soll in Numerik mit der Definition der Lipschitz-Bedingung die kleinste Lipschitz-Konstante L berechnen. Ich habe schon so weit vereinfacht, komme aber nicht auf die Lsg ( L = 1)

[math] (sin(y1)-sin(y2))/|(y1-y2)| \le L [/math]

y1, y2 sind aus R

[Peregrin_Tooc]

Taylorentwicklung von sinus verwenden tät ich sagen.