graphentheorie, hilfe bei der aufgabe!! |
17.06.2008, 20:13 | charlie28 | Auf diesen Beitrag antworten » | ||
graphentheorie, hilfe bei der aufgabe!! Sei N=(D=(V,A),c) ein Netzwerk. Welche der folgenden aussagen sind wahr? Die antwort sollte entweder durch einen beweis oder ein gegenbeispiel bestätigt werden. a) Wenn f: A ->R ein maximaler Fluss für N ist, dann gilt entweder f(u,v)=0 oder f(u,v)=c(u,v) für jeden Bogen (u,v) /in A. b) N besitzt einen maximalen Fluß für den gilt, dass entweder f(u,v)=0 oder f(u,v)=c(u,v) für jeden Bogen (u,v) /in A. c) Wenn alle Kapazitäten verschieden sind dann ist der minimale schnitt eindeutig. d) Wenn jede Kapazität mit einer positiven Zahl /lambda /in R multipliziert wird, dann bleibt jeder minimale Schnitt ein minimaler Schnitt des geänderten Netzwerkes. e) Wenn zu jeder Kapazität mit einer positiven Zahl /lambda /in R addiert wird, dann bleibt jeder minimale Schnitt ein minimaler Schnitt des geänderten Netzwerkes. Bitte hilft mir!!! |
||||
17.06.2008, 20:53 | Abakus | Auf diesen Beitrag antworten » | ||
RE: graphentheorie, hilfe bei der aufgabe!! Also das c gibt die Maximalkapazität eines Pfeils an und ein Bogen ist dasselbe wie ein Pfeil ? Die Minimalkapazität soll immer 0 sein ? So wie die Aufgabe gestellt ist, würde ich ein paar einfache Netzwerke zeichnen und zunächst versuchen, die Eigenschaften zu widerlegen. Wie weit kommst du dabei ? Grüße Abakus |
||||
17.06.2008, 21:35 | charlie28 | Auf diesen Beitrag antworten » | ||
das hilft mir nicht sehr viel..könntest du ein paar beispiele angeben... |
||||
17.06.2008, 23:26 | Abakus | Auf diesen Beitrag antworten » | ||
RE: graphentheorie, hilfe bei der aufgabe!!
Die Fragen stehen noch. Erste Beispiele findest du zB hier: Flüsse und Schnitte (Wiki) Ford-Fulkerson-Algorithmus (Wiki) Grüße Abakus |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|