Det är inte självklart att detta problem är ett flödesproblem, men om man ser det på följande sätt blir det lättare. Du har en startpunkt som du kopplar till vissa noder, nämligen de med kopplingsstift. Du ska sedan hitta vägar från dessa till vissa andra noder, nämligen de på kanten, och dessa kan du koppla till en slutpunkt. Då blir problemet att hitta så många skilda vägar som möjligt från startpunkten till slutpunkten. Om vi kunde sätta kapaciteten för varje nod till 1, skulle vi ha en vanlig flödesgraf.

Men kapacitet är en egenskap för varje båge, inte för noder. Därför måste du på något sätt göra om grafen så att varje punkt (nod) på plattan motsvaras av en båge med kapaciteten 1 i din flödesgraf. Ett sätt att åstadkomma detta är att låta varje punkt på plattan motsvaras av två noder i grafen:
*en in-nod som tar emot riktade bågar från de fyra omgivande punkternas ut-noder
*en ut-nod varifrån riktade bågar utgår till de fyra omgivande punkternas in-noder
*en extra riktad båge från in-noden till ut-noden
Detta får naturligtvis justeras vid kanterna och vid noderna med kopplingsstift, dessa kopplas till en slutpunkt resp. startpunkt enligt ovan. Alla kapaciteter kan sättas till 1, vilket gör att en något förenklad flödesalgoritm kan skrivas. w blir ju alltid 1, antalet möjliga kopplingar ökar därför med 1 för varje augmenting path. Efter avslutad algoritm får man återskapa kopplingsvägarna utifrån det flöde man har fått i sin graf.

Tillbaka