Τι είναι το υπολειμματικό δίκτυο και η διαδρομή αύξησης;

Ας ορίσουμε τόσο τα υπολειπόμενα δίκτυα όσο και τις διαδρομές αύξησης, ιδιαίτερα στο πλαίσιο των αλγορίθμων ροής δικτύου όπως η μέθοδος Ford-Fulkerson.

1. Υπολειμματικό δίκτυο:

Φανταστείτε ότι έχετε ένα δίκτυο με πηγή (ες), νεροχύτη (t) και άκρες με χωρητικότητες που αντιπροσωπεύουν τη μέγιστη ροή που επιτρέπεται μέσω κάθε άκρου. Ένα υπολειμματικό δίκτυο * είναι μια αναπαράσταση της υπόλοιπης χωρητικότητας στο δίκτυο * Μετά από * μια ορισμένη ποσότητα ροής έχει ήδη ωθηθεί μέσω αυτού.

Δείτε πώς λειτουργεί:

* Προώθηση άκρων: Για κάθε άκρη (U, V) στο αρχικό δίκτυο με χωρητικότητα C (U, V) και ροή ρεύματος F (U, V), το υπολειπόμενο δίκτυο περιλαμβάνει ένα αντίστοιχο * Forward Edge * (U, V) με χωρητικότητα C F (U, V) =C (U, V) - F (U, V). Αυτό αντιπροσωπεύει την υπόλοιπη χωρητικότητα που είναι διαθέσιμη στην άκρη.

* Πίσω άκρα: Το κρίσιμο μέρος είναι ότι το υπολειπόμενο δίκτυο *επίσης *περιλαμβάνει *προς τα πίσω άκρα *. Για κάθε άκρη (U, V) στο αρχικό δίκτυο με τρέχουσα ροή F (U, V), το υπολειπόμενο δίκτυο περιέχει μια οπίσθια άκρη (V, U) με χωρητικότητα C F (V, U) =F (U, V). Αυτό αντιπροσωπεύει τη δυνατότητα * ώθησης της ροής πίσω * κατά μήκος της άκρης, ακυρώνοντας αποτελεσματικά κάποια από τη ροή που έχει ήδη αποσταλεί. Η χωρητικότητα της οπίσθιας άκρης είναι ίση με τη ροή που βρίσκεται επί του παρόντος στην εμπρόσθια άκρη, επειδή μπορείτε να σπρώξετε μόνο την ποσότητα ροής που είναι ήδη εκεί.

Στην ουσία, το υπολειπόμενο δίκτυο παρουσιάζει τη διαθέσιμη χωρητικότητα για αλλαγές στη ροή. Προσαρμόζεται δυναμικά καθώς η ροή ωθείται μέσω του δικτύου. Η εύρεση μιας διαδρομής αύξησης (που εξηγείται παρακάτω) στο υπολειμματικό δίκτυο σημαίνει ότι εξακολουθεί να υπάρχει δυνατότητα αύξησης της συνολικής ροής από την πηγή στο νεροχύτη.

2. Διαδρομή αύξησης:

Μια * διαδρομή αύξησης * είναι μια απλή διαδρομή (χωρίς επαναλαμβανόμενες κορυφές) στο υπολειπόμενο δίκτυο που οδηγεί από τις πηγές (ες) στο νεροχύτη (t). Βασικά, αντιπροσωπεύει έναν τρόπο αύξησης της συνολικής ροής μέσω του δικτύου.

Η ποσότητα με την οποία η ροή μπορεί να αυξηθεί κατά μήκος της διαδρομής αύξησης καθορίζεται από την ικανότητα *BottleNeck *. Αυτή είναι η ελάχιστη υπολειμματική χωρητικότητα μεταξύ όλων των άκρων στη διαδρομή αύξησης.

Για παράδειγμα:

Εάν μια διαδρομή αύξησης έχει άκρα με υπολειμματικές ικανότητες των 5, 3 και 7, η χωρητικότητα της συμφόρησης είναι 3. Στη συνέχεια, μπορούμε να αυξήσουμε τη ροή κατά μήκος αυτής της διαδρομής κατά 3 μονάδες. Αυτή η διαδικασία ενημερώνει τη ροή στο αρχικό δίκτυο και στη συνέχεια τροποποιεί το υπολειπόμενο δίκτυο.

Σχέση μεταξύ υπολειμματικών δικτύων και διαδρομών αύξησης:

Ο πυρήνας πολλών αλγορίθμων μέγιστης ροής (όπως το Ford-Fulkerson) είναι επαναληπτικά:

1. Βρείτε μια διαδρομή αύξησης Στο τρέχον υπολειμματικό δίκτυο.

2. Αύξηση της ροής κατά μήκος αυτής της διαδρομής από την ικανότητα συμφόρησης.

3. Ενημερώστε το υπολειμματικό δίκτυο για να αντικατοπτρίζει τη μεταβολή της ροής.

Αυτή η διαδικασία συνεχίζεται έως ότου δεν υπάρχουν πλέον διαδρομές αύξησης στο υπολειπόμενο δίκτυο, οπότε έχει επιτευχθεί η μέγιστη ροή. Το θεώρημα Max-Flow Min-Cut εγγυάται αυτό.