Αλγόριθμοι και Συνδυαστική Βελτιστοποίηση — Ιούνιος 2020 (Σετ 3)¶
Η μεταγραφή προέρχεται από τη φωτογραφία aco-june20-set3.png.
aco-june20-set3.png¶
Ερώτηση 1 (Πολλαπλής Επιλογής (Μοναδική Απάντηση) — 0.60 βαθμοί)
Θεωρήστε το παρακάτω δίκτυο, στο οποίο οι αριθμοί που συσχετίζονται με τις ακμές του αναπαριστούν χωρητικότητα.
[Σχήμα: κατευθυνόμενο δίκτυο με κόμβους s, a, b, t. Χωρητικότητες ακμών: s→a 20, a→s 6· s→b 14, b→s 16· a→b 4, b→a 8· a→t 12, t→a 8· b→t 20, t→b 10]
(α) (6%) Ποιά είναι η τιμή της μέγιστης ροής ;
- [ ] A: 38
- [ ] B: 48
- [ ] Γ: 50
- [ ] Δ: 56
- [ ] E: 30
- [ ] ΣΤ: 32
- [ ] Z: 34
- [ ] Η: καμία από τις προηγούμενες
Ερώτηση 2 (Πολλαπλής Επιλογής (Μοναδική Απάντηση) — 0.60 βαθμοί)
(β) (6%) Ποιά είναι η χωρητικότητα της ελάχιστης s-t αποκοπής ;
- [ ] A: 38
- [ ] B: 48
- [ ] Γ: 50
- [ ] Δ: 56
- [ ] E: 30
- [ ] ΣΤ: 32
- [ ] Z: 34
- [ ] Η: καμία από τις προηγούμενες
[συμπληρώθηκε από 4.png]
Ερώτηση 3 (Ελεύθερου Κειμένου — 0.70 βαθμοί)
(γ) (7%) Ποιά είναι η ελάχιστη s-t αποκοπή ;
Απάντηση:
[κενό πλαίσιο απάντησης]
[συμπληρώθηκε από 4.png]
Ερώτηση 4 (Πολλαπλής Επιλογής (Μοναδική Απάντηση) — 0.60 βαθμοί)
(δ) (6%) Ποιό από τα παρακάτω είναι το υπολειπόμενο δίκτυο μετά την προώθηση 8 μονάδων ροής κατά μήκος της διαδρομής (s,b,a,t) ;
Απάντηση:
- [ ] A:
[Σχήμα Α: s→a 20, a→s 6· a→t 4, t→a 20· a→b 12· s→b 6, b→s 24· b→t 20, t→b 10]
- [ ] B:
[Σχήμα Β: s→a 20, a→s 6· a→t 4, t→a 20· a→b 14· s→b 6, b→s 24· b→t 20, t→b 10]
- [ ] Γ:
[Σχήμα Γ: s→a 20, a→s 6· a→t 4, t→a 8· a→b 4, b→a 0· s→b 6, b→s 16· b→t 20, t→b 10]
[Λείπει από τη φωτογραφία: οι επιλογές της Ερ.4 μετά την επιλογή Γ]
Επιπλέον πηγές χωρίς μεταγραφή εδώ (λύσεις →
2020-06-c.solutions.md, ή διπλότυπες φωτογραφίες της ίδιας σελίδας):4.png
Λύσεις (⚪ AI, μη επαληθευμένο)
Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (antigravity-gemini, deepseek-flash, gemini-3.7-flash), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο
Προσοχή
Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.
AI λύσεις — 2020-06-c¶
Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.
Ερώτηση 1¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
Η μέγιστη ροή είναι \(30\), δηλαδή η επιλογή E: 30. Πράγματι, για την αποκοπή \(S=\{s,a\}\), \(T=\{b,t\}\) οι ακμές \(S\to T\) είναι \(s\to b\), \(a\to b\), \(a\to t\) με χωρητικότητα \(14+4+12=30\), άρα κάθε ροή έχει τιμή \(\le 30\). Ροή τιμής \(30\) υπάρχει π.χ. με \(f_{sa}=16\), \(f_{sb}=14\), \(f_{ab}=4\), \(f_{at}=12\), \(f_{bt}=18\) και μηδέν στις υπόλοιπες.
Ερώτηση 2¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
Η χωρητικότητα της ελάχιστης \(s\)-\(t\) αποκοπής είναι \(30\), δηλαδή η επιλογή E: 30. Από το θεώρημα μέγιστης ροής-ελάχιστης αποκοπής, η ελάχιστη αποκοπή έχει την ίδια τιμή με τη μέγιστη ροή, η οποία βρέθηκε \(30\).
Ερώτηση 3¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
Οι δυνατές \(s\)-\(t\) αποκοπές έχουν χωρητικότητες: \(S=\{s\}\): \(34\), \(S=\{s,a\}\): \(14+4+12=30\), \(S=\{s,b\}\): \(20+8+20=48\), \(S=\{s,a,b\}\): \(12+20=32\).
Ελάχιστη είναι η αποκοπή \((S,T)=(\{s,a\},\{b,t\})\), με ακμές τομής \(s\to b\), \(a\to b\), \(a\to t\) και χωρητικότητα \(14+4+12=30\).
Ερώτηση 4¶
Αξιοπιστία: λύθηκε με βάση τις φωτογραφίες του θέματος· μία λύση AI
Στην εικόνα aco-june20-set3.png (και στο στιγμιότυπο 4.png) δίνεται το αρχικό δίκτυο με χωρητικότητες \(c(u, v)\):
- \(c(s, a) = 20\), \(c(a, s) = 6\)
- \(c(s, b) = 14\), \(c(b, s) = 16\)
- \(c(a, b) = 4\), \(c(b, a) = 8\)
- \(c(a, t) = 12\), \(c(t, a) = 8\)
- \(c(b, t) = 20\), \(c(t, b) = 10\)
Προωθούμε ροή \(f = 8\) μονάδων κατά μήκος της διαδρομής \(p = (s, b, a, t)\). Οι υπολειπόμενες χωρητικότητες \(c_f(u, v) = c(u, v) - f(u, v) + f(v, u)\) υπολογίζονται ως εξής: 1. Ακμή \((s, b)\): - Ευθεία: \(c_f(s, b) = 14 - 8 = 6\) - Αντίστροφη: \(c_f(b, s) = 16 + 8 = 24\) 2. Ακμή \((b, a)\): - Ευθεία: \(c_f(b, a) = 8 - 8 = 0\) (η ακμή \(b \to a\) μηδενίζεται και απαλείφεται) - Αντίστροφη: \(c_f(a, b) = 4 + 8 = 12\) 3. Ακμή \((a, t)\): - Ευθεία: \(c_f(a, t) = 12 - 8 = 4\) - Αντίστροφη: \(c_f(t, a) = c(t, a) + 8 = 8 + 8 = 16\) 4. Οι υπόλοιπες ακμές μένουν αμετάβλητες: - \(c_f(s, a) = 20\), \(c_f(a, s) = 6\) - \(c_f(b, t) = 20\), \(c_f(t, b) = 10\)
Σύγκριση με τις επιλογές:¶
- Επιλογή A: Έχει \(s \to b = 6\), \(b \to s = 24\), \(a \to b = 12\) (χωρίς \(b \to a\)), \(a \to t = 4\), \(s \to a = 20\), \(a \to s = 6\), \(b \to t = 20\), \(t \to b = 10\). Η μόνη διαφορά είναι ότι αναγράφει \(t \to a = 20\) αντί για \(16\). Αυτό προφανώς οφείλεται σε αριθμητικό/τυπογραφικό λάθος του διδάσκοντα, ο οποίος πρόσθεσε τη ροή 8 στην αρχική χωρητικότητα \(c(a, t) = 12\) (\(12 + 8 = 20\)) αντί της αντίστροφης \(c(t, a) = 8\) (\(8 + 8 = 16\)).
- Επιλογή B: Έχει \(a \to b = 14\) (λανθασμένο, καθώς \(4 + 8 = 12\)).
- Επιλογή Γ: Δεν ενημερώνει τις αντίστροφες ακμές (\(b \to s = 16\), \(t \to a = 8\)), άρα είναι εντελώς εσφαλμένη.
Συμπέρασμα: Αν η εξέταση περιείχε επιλογή «καμία από τις προηγούμενες» (όπως στις Ερωτήσεις 1 και 2) στις επιλογές που κόπηκαν από το στιγμιότυπο, αυτή θα ήταν η τυπικά αυστηρή απάντηση λόγω του \(t \to a = 16\). Αν όμως θεωρηθεί το προφανές τυπογραφικό λάθος του θέματος (\(12+8=20\) στο \(t \to a\)), η προτιμώμενη/προβλεπόμενη επιλογή είναι η A.