graphentheorie, hilfe bei der aufgabe!!

Neue Frage »

charlie28 Auf diesen Beitrag antworten »
graphentheorie, hilfe bei der aufgabe!!
Netzwerkeigenschaften

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!!!
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 smile
charlie28 Auf diesen Beitrag antworten »

das hilft mir nicht sehr viel..könntest du ein paar beispiele angeben...
Abakus Auf diesen Beitrag antworten »
RE: graphentheorie, hilfe bei der aufgabe!!
Zitat:
Original von Abakus
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 ?


Die Fragen stehen noch.

Erste Beispiele findest du zB hier:

Flüsse und Schnitte (Wiki)

Ford-Fulkerson-Algorithmus (Wiki)

Grüße Abakus smile
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »