Μετάβαση στο περιεχόμενο

Εισαγωγή στους Αλγόριθμους — Ιούνιος 2021 — Θέμα 5 (απόσπασμα)

Μεταγραφή από το PRIM.png· το 2021-06-08_141344.png είναι επιπλέον φωτογραφία του ίδιου σχήματος.

PRIM.png

ΘΕΜΑ 5

Θεωρήστε το μη κατευθυνόμενο γράφημα του παρακάτω σχήματος.

[Σχήμα: Μη κατευθυνόμενο γράφημα με κόμβους \(a, b, c, d, e, f, g, h, i, j\) και βάρη ακμών: \((a,h)=150\), \((a,i)=170\), \((a,b)=300\), \((h,i)=160\), \((i,b)=320\), \((h,g)=330\), \((g,i)=310\), \((i,j)=340\), \((j,b)=250\), \((b,c)=240\), \((g,j)=280\), \((j,c)=260\), \((g,f)=200\), \((g,e)=210\), \((j,e)=110\), \((j,d)=120\), \((c,d)=270\), \((f,e)=220\), \((e,d)=100\). Ορισμένες ακμές έχουν μαύρες κουκκίδες κατά μήκος τους.]

Επιπλέον πηγή χωρίς δική της ενότητα: 2021-06-08_141344.png — διπλότυπη φωτογραφία του ίδιου σχήματος (τα βάρη συμφωνούν με το PRIM.png). Το κάτω τμήμα της με τις χρωματισμένες λίστες ζευγών κορυφών δεν είναι μέρος της εκφώνησης και δεν μεταγράφεται εδώ (πιθανή λύση → για 2021-06.solutions.md).

Λύσεις (⚪ AI, μη επαληθευμένο)

Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (antigravity-gemini, sonnet), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο

Προσοχή

Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.

AI λύσεις — 2021-06

Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.

Θέμα 5

Αξιοπιστία: λύθηκε με βάση τις φωτογραφίες του θέματος· μία λύση AI

Από τις πρωτότυπες εικόνες PRIM.png και 2021-06-08_141344.png, καθώς και από τις συζητήσεις των φοιτητών την ημέρα της εξέτασης, το Θέμα 5 ζητά τον προσδιορισμό του Ελάχιστου Συνδετικού Δένδρου (Minimum Spanning Tree - MST) στο δοσμένο μη κατευθυνόμενο συνδεδεμένο γράφημα των 10 κορυφών (\(a, b, c, d, e, f, g, h, i, j\)) με χρήση των αλγορίθμων Prim και Kruskal.

Επειδή όλα τα βάρη των ακμών του γραφήματος είναι αυστηρά διακριτά μεταξύ τους, το Ελάχιστο Συνδετικό Δένδρο είναι μοναδικό. Για \(V = 10\) κορυφές, το MST περιλαμβάνει ακριβώς \(V - 1 = 9\) ακμές.

1. Πλήρης Πίνακας Ακμών και Βαρών του Γραφήματος

Ακμή Βάρος Ακμή Βάρος
\((e, d)\) 100 \((f, e)\) 220
\((j, e)\) 110 \((b, c)\) 240
\((j, d)\) 120 \((j, b)\) 250
\((a, h)\) 150 \((j, c)\) 260
\((h, i)\) 160 \((c, d)\) 270
\((a, i)\) 170 \((g, j)\) 280
\((g, f)\) 200 \((a, b)\) 300
\((g, e)\) 210 \((g, i)\) 310
\((i, b)\) 320 \((i, j)\) 340
\((h, g)\) 330

2. Επίλυση με τον Αλγόριθμο του Kruskal

Ταξινομούμε όλες τις ακμές κατά αύξουσα σειρά βάρους και εξετάζουμε διαδοχικά την εισαγωγή τους, απορρίπτοντας όσες δημιουργούν κύκλο:

  1. \((e, d) = 100\): Αποδοχή (συνδέει \(\{e\}, \{d\}\)).
  2. \((j, e) = 110\): Αποδοχή (συνδέει \(\{j\}, \{e, d\}\)).
  3. \((j, d) = 120\): Απόρριψη (κύκλος \(j-e-d-j\)).
  4. \((a, h) = 150\): Αποδοχή (συνδέει \(\{a\}, \{h\}\)).
  5. \((h, i) = 160\): Αποδοχή (συνδέει \(\{i\}, \{a, h\}\)).
  6. \((a, i) = 170\): Απόρριψη (κύκλος \(a-h-i-a\)).
  7. \((g, f) = 200\): Αποδοχή (συνδέει \(\{g\}, \{f\}\)).
  8. \((g, e) = 210\): Αποδοχή (συνδέει \(\{g, f\}\) με \(\{j, e, d\}\)).
  9. \((f, e) = 220\): Απόρριψη (κύκλος \(g-f-e-g\)).
  10. \((b, c) = 240\): Αποδοχή (συνδέει \(\{b\}, \{c\}\)).
  11. \((j, b) = 250\): Αποδοχή (συνδέει \(\{b, c\}\) με \(\{g, f, j, e, d\}\)).
  12. \((j, c) = 260\): Απόρριψη (κύκλος \(j-b-c-j\)).
  13. \((c, d) = 270\): Απόρριψη (κύκλος \(c-b-j-d-c\)).
  14. \((g, j) = 280\): Απόρριψη (κύκλος \(g-e-j-g\)).
  15. \((a, b) = 300\): Αποδοχή (συνδέει \(\{a, h, i\}\) με \(\{b, c, j, e, d, g, f\}\)).

Έχουν επιλεγεί 9 ακμές και όλες οι 10 κορυφές έχουν συνδεθεί. Ο αλγόριθμος τερματίζει.

3. Επίλυση με τον Αλγόριθμο του Prim (Εκκίνηση από την κορυφή \(a\))

  • Βήμα 1: Ξεκινώντας από \(V_{\text{tree}} = \{a\}\), οι διαθέσιμες ακμές είναι \((a,h)=150\), \((a,i)=170\), \((a,b)=300\). Επιλέγεται η \((a, h) = 150\) \(\to V_{\text{tree}} = \{a, h\}\).
  • Βήμα 2: Ακμές προς μη επισκεφθείσες: \((h,i)=160\), \((a,i)=170\), \((a,b)=300\), \((h,g)=330\). Επιλέγεται η \((h, i) = 160\) \(\to V_{\text{tree}} = \{a, h, i\}\).
  • Βήμα 3: Ακμές προς μη επισκεφθείσες: \((a,b)=300\), \((i,g)=310\), \((i,b)=320\), \((h,g)=330\), \((i,j)=340\). Επιλέγεται η \((a, b) = 300\) \(\to V_{\text{tree}} = \{a, h, i, b\}\).
  • Βήμα 4: Ακμές προς μη επισκεφθείσες: \((b,c)=240\), \((b,j)=250\), \((i,g)=310\), \((h,g)=330\), \((i,j)=340\). Επιλέγεται η \((b, c) = 240\) \(\to V_{\text{tree}} = \{a, h, i, b, c\}\).
  • Βήμα 5: Ακμές προς μη επισκεφθείσες: \((j,b)=250\), \((c,j)=260\), \((c,d)=270\), \((i,g)=310\), \((i,j)=340\). Επιλέγεται η \((j, b) = 250\) \(\to V_{\text{tree}} = \{a, h, i, b, c, j\}\).
  • Βήμα 6: Ακμές προς μη επισκεφθείσες: \((j,e)=110\), \((j,d)=120\), \((c,d)=270\), \((j,g)=280\), \((i,g)=310\). Επιλέγεται η \((j, e) = 110\) \(\to V_{\text{tree}} = \{a, h, i, b, c, j, e\}\).
  • Βήμα 7: Ακμές προς μη επισκεφθείσες: \((e,d)=100\), \((j,d)=120\), \((e,g)=210\), \((e,f)=220\), \((c,d)=270\). Επιλέγεται η \((e, d) = 100\) \(\to V_{\text{tree}} = \{a, h, i, b, c, j, e, d\}\).
  • Βήμα 8: Ακμές προς μη επισκεφθείσες: \((g,e)=210\), \((e,f)=220\), \((g,j)=280\), \((g,i)=310\). Επιλέγεται η \((g, e) = 210\) \(\to V_{\text{tree}} = \{a, h, i, b, c, j, e, d, g\}\).
  • Βήμα 9: Ακμές προς μη επισκεφθείσες: \((g,f)=200\), \((e,f)=220\). Επιλέγεται η \((g, f) = 200\) \(\to V_{\text{tree}} = \{a, h, i, b, c, j, e, d, g, f\}\).

4. Τελικό Αποτέλεσμα (Ακμές του MST και Συνολικό Βάρος)

Οι 9 ακμές του Ελάχιστου Συνδετικού Δένδρου (όπως επισημαίνονται με μαύρες κουκκίδες στο PRIM.png και με πράσινο χρώμα στο 2021-06-08_141344.png) είναι: 1. \((e, d)\) με βάρος \(100\) 2. \((j, e)\) με βάρος \(110\) 3. \((a, h)\) με βάρος \(150\) 4. \((h, i)\) με βάρος \(160\) 5. \((g, f)\) με βάρος \(200\) 6. \((g, e)\) με βάρος \(210\) 7. \((b, c)\) με βάρος \(240\) 8. \((j, b)\) με βάρος \(250\) 9. \((a, b)\) με βάρος \(300\)

Συνολικό Βάρος του MST: $\(W = 100 + 110 + 150 + 160 + 200 + 210 + 240 + 250 + 300 = \mathbf{1720}\)$

✔ Επιβεβαίωσε · ✖ Βρήκα λάθος

✖ Βρήκα λάθος στη μεταγραφή