Αλγόριθμοι και Συνδυαστική Βελτιστοποίηση — Ιούνιος 2020 (Σετ 1)¶
Η μεταγραφή προέρχεται από τη φωτογραφία aco-june20-set1.png.
aco-june20-set1.png¶
Ερώτηση 1 (Ελεύθερου Κειμένου — 1.20 βαθμοί)
(12%) Θεωρήστε το δίκτυο του παρακάτω σχήματος, στο οποίο οι αριθμοί που συσχετίζονται με τις ακμές του αναπαριστούν χωρητικότητα.
[Σχήμα: δίκτυο με κορυφές s, x, y, t σε σειρά· ακμές s → x με χωρητικότητα 40, x → y με 20, y → t με 30]
Θεωρήστε την εκτέλεση του αλγορίθμου προροής-προώθησης (preflow-push) με τον κανόνα υψηλότερου επιπέδου στο παραπάνω δίκτυο. Ποιά είναι η τελική ετικέτα \(d(x)\) της κορυφής \(x\) μετά το τέλος της εκτέλεσης του αλγορίθμου ;
[κενό πεδίο απάντησης]
Ερώτηση 2 (Ελεύθερου Κειμένου — 1.30 βαθμοί)
(13%) Θεωρήστε ένα δίκτυο \(G = (V, E)\) με χωρητικότητες στις ακμές του και δύο διακεκριμένες κορυφές \(s \in V\) (πηγή) και \(t \in V\) (απόληξη). Έστω ότι σας δίνετε μια \(s\)-\(t\) ροή \(f\) στο \(G\), η τιμή \(|f|\) της οποίας ισούται με την χωρητικότητα \(c[A, A']\) μιας \(s\)-\(t\) αποκοπής \([A, A']\). Αποδείξτε ότι η \(f\) είναι η μέγιστη ροή στο \(G\).
Απάντηση:
[κενό πεδίο απάντησης]
Επιπλέον πηγές χωρίς μεταγραφή εδώ (λύσεις →
2020-06-a.solutions.md, ή διπλότυπες φωτογραφίες της ίδιας σελίδας):image0.jpg
Λύσεις (🟡 community)
Κατάσταση: 🟡 community Πηγή: χειρόγραφη λύση φοιτητή της Ερώτησης 1 (φωτογραφία image0.jpg)
Προσοχή
Η λύση είναι ημιτελής και σε μεγάλο μέρος δυσανάγνωστη· η τελική ετικέτα d(x) δεν διακρίνεται στη φωτογραφία, άρα δεν μπορεί να συγκριθεί με την απάντηση της Ερώτησης 1. Η Ερώτηση 2 του σετ δεν έχει λύση σε καμία από τις πηγές του σετ.
Λύσεις — Αλγόριθμοι και Συνδυαστική Βελτιστοποίηση — Ιούνιος 2020 (Σετ 1)¶
Μεταγραφή χειρόγραφης λύσης φοιτητή για την Ερώτηση 1 (preflow-push, δίκτυο s→x (40), x→y (20), y→t (30)). Η φωτογραφία είναι περιστραμμένη και σε μεγάλο μέρος δυσανάγνωστη· η μεταγραφή είναι ατελής.
image0.jpg¶
[Η φωτογραφία είναι περιστραμμένη κατά 90 μοίρες. Όλο το κείμενο είναι χειρόγραφο και πολλά τμήματα είναι δυσανάγνωστα.]
Preflow - Push.
Ερώτηση 1.
[Σχήμα: δίκτυο s → x (40), x → y (20), y → t (30) με ετικέτες 3, 2, 1, 0 δίπλα στις κορυφές s, x, y, t]
- Δημιουργούμε n(=4) επίπεδα
- Εκτελούμε αναδρομικά BFS (με κορυφή εκκίνησης την t)
1ο
(1) [δυσανάγνωστο] max δυνατόν ροή από τον S (S = −40 / x = 40)
(2) Η κορυφή x έχει την πλεονάζουσα ροή ([δυσανάγνωστο] ενεργ.)
(3) Η κορυφή x [δυσανάγνωστο] να προωθήσει ροή κάτω στις ακμής x → y
[Σχήμα: δεύτερο δίκτυο s, x, y, t με χειρόγραφες ετικέτες· οι αριθμοί δεν διακρίνονται με βεβαιότητα]
2ο
(1) Η κορυφή y έχει την πλεονάζουσα ροή ([δυσανάγνωστο] ενεργ.)
(2) Η y [δυσανάγνωστο] να προωθήσει ροή κάτω στις ακμής y → t
3ο
(1) Η κορυφή t έχει την πλεονάζουσα ροή ([δυσανάγνωστο] ενεργ.)
[δυσανάγνωστο: διαγραμμένο χειρόγραφο κείμενο στο κάτω μέρος της σελίδας, με μερικό τμήμα (β) που δεν διακρίνεται]
Σημείωση: η φωτογραφία περιέχει χειρόγραφες απαντήσεις φοιτητή.