Ik heb mijzelf laatst bezig gehouden met de theorie over stromen in netwerken. Een van de eerste dingen die je daar leert is de methode van Ford en Fulkerson om een maximale stroom in een netwerk te vinden: Je zoekt steeds naar een groeipad in het netwerk, en je kijkt wat de minimale hoeveelheid stroom is die je toe kan voegen. Die voeg je toe aan voorwaartse paden en trek je van achterwaartse paden af. Dit blijf je doen totdat er geen groeipad meer te vinden is, en dan heb je de maximale stroom gevonden.
Wat ik mij dus af vraag is het volgende:
Is het mogelijk om een algoritme op te stellen, en zoja hoe, dat een tak in het netwerk vind met de eigenschap dat als je zijn capaciteit verhoogt, dat dan de waarde van de maximale stroom ook verandert.
Een mogelijke manier zou zijn om te kijken naar de minimale snede die je verkrijgt uit het algoritme. In die snede kijk je dan naar de takken waarvoor geldt dat als je de capaciteit verhoogt, de snede nog steeds minimaal blijft. Maar het probleem hierbij is dat je moet zien te bepalen wanneer de snede nog steeds minimaal is. Hiervoor zou je dus ook de andere sneden moeten weten.
Een andere manier zou zijn om bij elke iteratie allereerst te kijken welke tak nu eigenlijk de volgende iteratie beinvloed. Daarna kun je kijken hoe je de capaciteit van deze tak verandert, zonder dat de gerichte grafen in de volgende iteraties ook veranderen. Als dit mogelijk is sla je bijvoorbeeld deze tak op in een andere verzameling samen met de maximale waarde die toegevoegd kan worden aan de stroom. Bij elke volgende iteratie doe je hetzelfde. Uiteindelijk heb je waarschijnlijk een lijst gevonden met een aantal takken, en mischien ook meerdere keren dezelfde tak. Als een tak meerdere keren voorkomt neem je de tak met de minimale toegevoegde capaciteit om problemen te voorkomen
Die tak is dan een tak waarvoor onze gewenste eigenschap geldt.
Ik ben zelf nog niet echt overtuigd van mijn ideeen
Ik ben benieuwd of jullie nog enige goede suggesties hebben voor het probleem en/of kritiek op mijn methode(s)!
Wat ik mij dus af vraag is het volgende:
Is het mogelijk om een algoritme op te stellen, en zoja hoe, dat een tak in het netwerk vind met de eigenschap dat als je zijn capaciteit verhoogt, dat dan de waarde van de maximale stroom ook verandert.
Een mogelijke manier zou zijn om te kijken naar de minimale snede die je verkrijgt uit het algoritme. In die snede kijk je dan naar de takken waarvoor geldt dat als je de capaciteit verhoogt, de snede nog steeds minimaal blijft. Maar het probleem hierbij is dat je moet zien te bepalen wanneer de snede nog steeds minimaal is. Hiervoor zou je dus ook de andere sneden moeten weten.
Een andere manier zou zijn om bij elke iteratie allereerst te kijken welke tak nu eigenlijk de volgende iteratie beinvloed. Daarna kun je kijken hoe je de capaciteit van deze tak verandert, zonder dat de gerichte grafen in de volgende iteraties ook veranderen. Als dit mogelijk is sla je bijvoorbeeld deze tak op in een andere verzameling samen met de maximale waarde die toegevoegd kan worden aan de stroom. Bij elke volgende iteratie doe je hetzelfde. Uiteindelijk heb je waarschijnlijk een lijst gevonden met een aantal takken, en mischien ook meerdere keren dezelfde tak. Als een tak meerdere keren voorkomt neem je de tak met de minimale toegevoegde capaciteit om problemen te voorkomen
Die tak is dan een tak waarvoor onze gewenste eigenschap geldt.Ik ben zelf nog niet echt overtuigd van mijn ideeen
Ik ben benieuwd of jullie nog enige goede suggesties hebben voor het probleem en/of kritiek op mijn methode(s)!
/u/27299/hoofd.png?f=community)
Dus in feite kan je dus de capaciteiten van het netwerk blijven verhogen en zo een steeds grotere stroom krijgen!
:strip_exif()/u/63575/killbill_additionalproductimage_001_small.gif?f=community)