Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

maximaler Durchfluss in Graph

Werbeanzeige

birdfreeyahoo

Alter Hase

  • »birdfreeyahoo« ist der Autor dieses Themas

Beiträge: 756

Wohnort: Schorndorf

Beruf: Junior Software Engineer

  • Private Nachricht senden

1

17.06.2015, 23:05

maximaler Durchfluss in Graph

Hallo, ich habe eine Frage bezüglich Graphen.

Wenn ich mit dem Ford-Fulkerson Algorithmus den Fluss des Graphen bestimme, habe ich ja den Graphen mit den Flussinformationen und einen Residualgraphen an dem ich sehe welche Restkapazität noch vorhanden ist.

Wenn ich nun aber den maximalen Fluss bestimmen soll, was ist dann verlangt?
Ich würde aus Intuition einfach mal sagen, von allen Flüssen (Pfaden) die ich bei der Berechnung berücksichtigt habe, derjenige, der die höchste Flusskapazität hat?

Ich hoffe jemand kann mir da helfen

mfg

Tobiking

1x Rätselkönig

Beiträge: 1 231

  • Private Nachricht senden

2

17.06.2015, 23:48

Zitat von »birdfreeyahoo«

Wenn ich nun aber den maximalen Fluss bestimmen soll, was ist dann verlangt?
Ich würde aus Intuition einfach mal sagen, von allen Flüssen (Pfaden) die ich bei der Berechnung berücksichtigt habe, derjenige, der die höchste Flusskapazität hat?

Dem Wikipedia Artikel nach steckt in der Definition eines Flusses kein Pfad. Es geht (grob und unvollständig formuliert) nur um eine Belegung der Kanten, so dass die Kapazitätsgrenzen der Kanten eingehalten werden und in jedem Knoten in der Summe genau so viel rein fließt wie raus. Ein maximaler Fluss zwischen 2 Knoten ist eine Belegung, bei der die Summe der Belegungen der ausgehenden Kanten des Startknoten (und damit auch das was in den Endknoten geht, da unterwegs nichts verloren gehen kann) maximal ist.

birdfreeyahoo

Alter Hase

  • »birdfreeyahoo« ist der Autor dieses Themas

Beiträge: 756

Wohnort: Schorndorf

Beruf: Junior Software Engineer

  • Private Nachricht senden

3

18.06.2015, 00:16

Ich hatte das falsch verstanden, also mein maximaler Durchfluss ist die Zuordnung einer Zahl zu jeder Kante, die den Fluss durch diese angibt?

Wie finde ich den Wert des maximalen Durchflusses dann?

birdfreeyahoo

Alter Hase

  • »birdfreeyahoo« ist der Autor dieses Themas

Beiträge: 756

Wohnort: Schorndorf

Beruf: Junior Software Engineer

  • Private Nachricht senden

4

18.06.2015, 01:10

Ok danke für das beispiel noch. Jetzt habe ich das verstanden.
Wir hatten das im studium und ich hatte es nicht so ganz verstanden.

Werbeanzeige

Ähnliche Themen