Αλγόριθμοι για εύρεση της μέγιστης ροής σε ένα δίκτυο ροής

Abstract

Το πρόβλημα μέγιστης ροής είναι να βρεθεί μία εφικτή ροή μέσω ενός δικτύου ροής μονής-πηγής, μονού-βυθού που να είναι μέγιστη. Η απλούστερη μορφή που η δήλωση μπορεί να πάρει θα ήταν κατά μήκος των γραμμών του: «Δίνεται μία λίστα σωλήνων, με διαφορετικές χωρητικότητες ροής. Αυτοί οι σωλήνες ενώνονται στα καταληκτικά σημεία τους. Ποια είναι η μέγιστη ποσότητα νερού που μπορείτε να κατευθύνετε από ένα δεδομένο σημείο εκκίνησης σε ένα δεδομένο σημείο κατάληξης;» ή ισοδύναμα «Μία εταιρεία έχει ένα εργοστάσιο που βρίσκεται στην πόλη X όπου κατασκευάζονται προϊόντα που χρειάζεται να μεταφερθούν σε ένα κέντρο διανομής στην πόλη Y. Σας δίνονται οι μονόδρομες οδοί που ενώνουν τα ζευγάρια πόλεων της χώρας, και ο μέγιστος αριθμός φορτηγών που μπορούν να κινηθούν κατά μήκος κάθε οδού. Ποιος είναι ο μέγιστος αριθμός φορτηγών που η εταιρεία μπορεί να στείλει στο κέντρο διανομής;» Δίνεται ένα κατευθυνόμενο γράφημα G = (V, E) με ακέραιες χωρητικότητες, c : E, και έναν κόμβο πηγής s και έναν κόμβο βυθού t στο V. Σκοπός η εύρεση μίας συνάρτησης ροής στα τόξα που υπόκεινται σε «περιορισμούς διατήρησης» και «περιορισμούς χωρητικότητας». Ο περιορισμός διατήρησης για έναν κόμβο είναι ότι το άθροισμα της ροής των εισερχόμενων τόξων ισούται με το άθροισμα των εξερχόμενων τόξων για όλους τους κόμβους εκτός από την πηγή και το βυθό. Ο περιορισμός χωρητικότητας για ένα τόξο είναι ότι η ροή δεν είναι μεγαλύτερη από τη χωρητικότητα. Ζητούμενο είναι η μεγιστοποίηση της ροής από την πηγή (στο βυθό).