Αλγόριθμοι και Συνδυαστική Βελτιστοποίηση — Σεπτέμβριος 2020¶
20200924_092340.jpg¶
Σημείωση: η φωτογραφία είναι χειρόγραφη σε χαρτί με γραμμές (τετράδιο)· η μεταγραφή καλύπτει μόνο το κείμενο της ερώτησης και τα σχήματα, χωρίς απαντήσεις.
Ποιό από τα παρακάτω είναι το υπολειπόμενο δίκτυο μετά την πραίσωση 4 μονάδων ροής κατά μήκος της διαδρομής \((S, b, a, t)\)?
A:
[Σχήμα A: δίκτυο με κόμβους S, a, b, t. Ετικέτες ακμών ανά ζεύγος κόμβων: S–a: 3 και 10· S–b: 8 και 3· a–b: 2 και 6· a–t: 4 και 2· b–t: 10 και 5.]
B:
[Σχήμα B: δίκτυο με κόμβους S, a, b, t. Ετικέτες ακμών ανά ζεύγος κόμβων: S–a: 3 και 10· S–b: 12 και 3· a–b: 8· a–t: 8 και 2· b–t: 10 και 5.]
Γ:
[Σχήμα Γ: δίκτυο με κόμβους S, a, b, t. Ετικέτες ακμών ανά ζεύγος κόμβων: S–a: 3 και 10· S–b: 12 και 3· a–b: 6· a–t: 8 και 2· b–t: 10 και 5.]
20200924_092409.jpg¶
Σημείωση: όλο το κείμενο είναι χειρόγραφο και όχι τυπωμένο. Δεν είναι σαφές αν πρόκειται για αντιγραφή θέματος εξέτασης.
(1)
[Σχήμα: κατευθυνόμενο δίκτυο με κόμβους s, a, b, t. Βάρη ακμών: s–a 3 και 10, a–b 2 και 4, a–t 6, t–a 4, s–b 7 και 8, b–t 10 και 5. Οι κατευθύνσεις των βελών φαίνονται στην εικόνα.]
- Ποια η μέγιστη ροή [δυσανάγνωστο];
- [ ] a) 15
- [ ] b) 16
- [ ] c) 14
- [ ] d) 19
- [ ] e) 24
- [ ] f) 25
- [ ] g) 28
-
[ ] h) καμία από αυτές
-
Ποια η χωρητικότητα της ελάχιστης s-t τομής;
- [ ] 15
- [ ] 16
- [ ] 17
- [ ] 19
- [ ] 24
- [ ] 25
- [ ] 28
- [ ] καμία από αυτές
[Πλαισιωμένο τμήμα:] Ποια η ελάχιστη s-t τομή; (Να αιτιολογ[δυσανάγνωστο].)
Λύσεις (⚪ AI, μη επαληθευμένο)
Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (deepseek-flash, gemini-3.7-flash), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο
Προσοχή
Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.
AI λύσεις — 2020-09¶
Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.
Θέμα 20200924_092340.jpg¶
Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή
Σωστή επιλογή είναι η Γ.
Αιτιολόγηση: Σπρώχνοντας \(4\) μονάδες κατά μήκος της διαδρομής \((S,b,a,t)\): - στην \(S\to b\) η υπολειπόμενη χωρητικότητα μειώνεται κατά \(4\) και η αντίστροφη αυξάνεται κατά \(4\), άρα προκύπτει το ζεύγος \(12\) και \(3\) (ανάλογα με τη φορά)· - στην \(b\to a\) χρησιμοποιούνται \(4\) μονάδες· μένει μόνο η αντίστροφη \(a\to b\) με χωρητικότητα \(6\)· - στην \(a\to t\) η ευθεία μειώνεται κατά \(4\) και η αντίστροφη αυξάνεται κατά \(4\), άρα προκύπτει \(8\) και \(2\)· - οι υπόλοιπες ακμές μένουν ως έχουν.
Αυτά συμφωνούν με το δίκτυο της επιλογής Γ.
Θέμα 20200924_092409.jpg (1) — Μέγιστη ροή¶
Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή
Θεωρώ τις κατευθύνσεις/χωρητικότητες όπως προκύπτουν από το σχήμα και το σωστό υπολειπόμενο δίκτυο: \(s\to a:10\), \(a\to s:3\), \(s\to b:7\), \(b\to s:8\), \(a\to b:2\), \(b\to a:4\), \(a\to t:6\), \(t\to a:4\), \(b\to t:10\), \(t\to b:5\).
Μια ροή \(15\) είναι: [ 7 \text{ κατά } s\to b\to t,\quad 6 \text{ κατά } s\to a\to t,\quad 2 \text{ κατά } s\to a\to b\to t. ] Έλεγχος χωρητικοτήτων: \(s\to b:7\), \(s\to a:8\le10\), \(a\to t:6\), \(a\to b:2\), \(b\to t:9\le10\).
Άρα μέγιστη ροή \(=15\). Επιλογή: a) 15.
Θέμα 20200924_092409.jpg (1) — Χωρητικότητα ελάχιστης \(s\)-\(t\) τομής¶
Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή
Η τομή [ S={s,a},\qquad T={b,t} ] έχει χωρητικότητα [ c(S,T)=c(s\to b)+c(a\to b)+c(a\to t)=7+2+6=15. ] Εφόσον η μέγιστη ροή είναι \(15\), από max-flow min-cut η χωρητικότητα της ελάχιστης τομής είναι επίσης \(15\). Επιλογή: 15.
Θέμα 20200924_092409.jpg (1) — Ελάχιστη \(s\)-\(t\) τομή¶
Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή
Ελάχιστη \(s\)-\(t\) τομή είναι η [ ({s,a},{b,t}) ] με χωρητικότητα [ 7+2+6=15, ] όπου οι ακμές που τη διασχίζουν από το \(S\) προς το \(T\) είναι \(s\to b\), \(a\to b\) και \(a\to t\).