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

Εισαγωγή στους Αλγόριθμους — Ιούνιος 2024

Μεταγραφή από τις πέντε φωτογραφίες του Ιουνίου 2024 με τη σειρά των θεμάτων (1, 2, 3, 5, 6).

466751839_1075117040681556_6452575663150212523_n.jpg.png

ΘΕΜΑ 1 (2 μονάδες). Δίνεται το παρακάτω μη κατευθυνόμενο γράφημα με κόστη στις ακμές του.

[Σχήμα: Μη κατευθυνόμενο γράφημα με κορυφές a, h, i, j, k, u, b, c, d, e, f, g. Ακμές και βάρη: (a,h)=110, (a,g)=105 (g,h)=100, (g,f)=180 (h,f)=185, (h,i)=175 (f,i)=130, (f,e)=50, (f,d)=60 (e,d)=55 (d,i)=160, (d,c)=155 (i,j)=140, (i,k)=125, (i,c)=150 (j,k)=135 (k,u)=75, (k,b)=80, (k,c)=190 (u,b)=85 (c,b)=200]

(α) [0.8] Να βρείτε το Ελάχιστο Γεννητικό Δένδρο (ΕΓΔ) εφαρμόζοντας τον αλγόριθμο Prim και θεωρώντας ως αρχική κορυφή την a. Το ΕΓΔ να δοθεί σαν μια ακολουθία ακμών του γραφήματος με τη σειρά κατά την οποία προστίθενται οι ακμές σε αυτό κατά την εκτέλεση του αλγορίθμου. (β) [0.8] Να βρείτε το ΕΓΔ εφαρμόζοντας τον αλγόριθμο Kruskal. Το ΕΓΔ να δοθεί σαν μια ακολουθία ακμών του γραφήματος με τη σειρά κατά την οποία προστίθενται οι ακμές σε αυτό κατά την εκτέλεση του αλγορίθμου. (γ) [0.4] Αν το κόστος της ακμής (f,d) αλλάξει από 60 σε 52, τότε απαντήστε αν θα μεταβληθεί το ΕΓΔ που βρήκατε στα δύο προηγούμενα ερωτήματα αιτιολογώντας την απάντησή σας χωρίς να εκτελέσετε κάποιον από τους αλγορίθμους.

Απάντηση:

462564175_1259454968537901_626935897197143348_n.jpg.png

ΘΕΜΑ 2 (1 μονάδα). Θεωρήστε το παρακάτω κατευθυνόμενο γράφημα, στο οποίο οι αριθμοί που συσχετίζονται με τις ακμές του αναπαριστούν κόστος, και θεωρήστε την εκτέλεση του αλγορίθμου Dijkstra με αρχική κορυφή την s.

[Σχήμα: Κατευθυνόμενο γράφημα με κόμβους s, y, b, x, a, t. Ακμές και βάρη: s -> y (300), s -> b (60), s -> x (120) b -> y (20), y -> a (210), y -> t (210) b -> a (210), b -> x (150) a -> x (120), x -> t (120) a -> t (30)]

Ο αλγόριθμος Dijkstra υπολογίζει τις αποστάσεις (κόστη συντομότερων διαδρομών) από την κορυφή s προς όλες τις υπόλοιπες κορυφές, εργαζόμενος επαναληπτικά και οριστικοποιώντας σε κάθε επανάληψη την ετικέτα d(w) μιας κορυφής w, αρχίζοντας από την s. Η επανάληψη κατά την οποία οριστικοποιείται η ετικέτα μιας κορυφής w ονομάζεται σειρά (ή διάταξη) οριστικοποίησης της w (η s έχει σειρά οριστικοποίησης 1).

(α) [0.7] Στο παραπάνω γράφημα υπάρχουν τρεις συντομότερες διαδρομές \(\Sigma\Delta(s,t)\) από την κορυφή s προς την t: (s,b,a,t), (s,b,y,t) και (s,b,x,t). Ποια από αυτές θα υπολογίσει ο αλγόριθμος Dijkstra ως την \(\Sigma\Delta(s,t)\); Αιτιολογήστε την απάντησή σας (μη αιτιολογημένες απαντήσεις θα βαθμολογούνται με μηδέν). (β) [0.3] Ποια είναι η σειρά οριστικοποίησης της κορυφής a;

Απάντηση:

462558838_442486982209146_2861906150668051063_n.jpg.png

ΘΕΜΑ 3 (2 μονάδες). Μια ομάδα μηχανικών υπολογιστών εργάζεται για την επίλυση δύο υπολογιστικών προβλημάτων \(\Pi_1\) και \(\Pi_2\), για καθένα από τα οποία έχει δημιουργήσει έναν αλγόριθμο «διαίρει και βασίλευε». Συγκεκριμένα: - Τον αλγόριθμο \(A_1\) που διασπά το αρχικό πρόβλημα μεγέθους \(n\) σε 9 υποπροβλήματα μεγέθους \(n/3\), τα επιλύει και στη συνέχεια συνθέτει τις λύσεις τους σε χρόνο \(6 \cdot n^2\). - Τον αλγόριθμο \(A_2\) που διασπά το αρχικό πρόβλημα μεγέθους \(n\) σε 125 υποπροβλήματα μεγέθους \(n/5\), τα επιλύει και στη συνέχεια συνθέτει τις λύσεις τους σε χρόνο \(25n^2 \cdot \log^2 n\). (α) [1.4] Να διατυπώσετε τις αναδρομικές εξισώσεις που δίνουν τον χρόνο εκτέλεσης των αλγορίθμων \(A_1\) και \(A_2\), και στη συνέχεια με εφαρμογή του Βασικού Θεωρήματος των αναδρομών να βρείτε τον κλειστό τύπο κάθε αναδρομής σε ασυμπτωτικό συμβολισμό εξηγώντας αναλυτικά την εφαρμογή του. (β) [0.6] Χρησιμοποιώντας την απάντηση του (α) σαν πρόβλεψη, να αποδείξετε τον κλειστό τύπο του αλγορίθμου \(A_1\) με επαγωγή (μέθοδος αντικατάστασης ή σωστής πρόβλεψης) προσδιορίζοντας επακριβώς τις σταθερές. Ως αρχική συνθήκη, ισχύει ότι \(T(x) = 1, \forall x < 1\).

Απάντηση:

462582756_947883104042521_8451214729285643429_n.jpg.png

ΘΕΜΑ 5 (1.5 μονάδες). Ποιοι από τους ακόλουθους ισχυρισμούς είναι αληθείς και ποιοι ψευδείς; Δικαιολογήστε την απάντησή σας είτε δίνοντας την απόδειξη στην περίπτωση που ο ισχυρισμός είναι αληθής, είτε δίνοντας ένα αντιπαράδειγμα στην περίπτωση που ο ισχυρισμός είναι ψευδής. Διευκρίνιση: μη αιτιολογημένες απαντήσεις θα βαθμολογούνται με μηδέν. (α) Έστω \(G = (V, E)\) ένα μη κατευθυνόμενο γράφημα με κόστη στις ακμές του. Θεωρήστε μια αύξουσα (κατά κόστος) διάταξη των ακμών του G. Τότε, η τελευταία ακμή σε αυτή τη διάταξη δεν ανήκει στο Ελάχιστο Γεννητικό Δένδρο του G. (β) Μια συντομότερη διαδρομή μεταξύ δύο οποιωνδήποτε κορυφών \(s\) και \(t\), σε ένα κατευθυνόμενο γράφημα με μη αρνητικά κόστη ακμών, είναι μια απλή διαδρομή. (γ) Αν \(f(n) = \Theta(\log^4 n)\) και \(g(n) = O(n^3 \cdot \log^7(n^3)) \ \forall \ n \ge 2\), τότε \(g(n)/f(n) = O(n^3 \cdot \log^3 n)\).

Απάντηση:

462564432_1719978532125158_8402080088515524832_n.jpg.png

ΘΕΜΑ 6 (1.5 μονάδες). (i) Στο κατευθυνόμενο γράφημα του παρακάτω σχήματος να δώσετε τους χρόνους ανακάλυψης (πρώτης επίσκεψης) και εγκατάλειψης σε μία Αναζήτηση Πρώτα κατά Βάθος (ΑΠΒ), η οποία αρχίζει από την κορυφή a. Κατά την εκτέλεση της ΑΠΒ σε κάθε κορυφή, οι εξερχόμενες ακμές θα πρέπει να εξετάζονται με λεξικογραφική σειρά. Για παράδειγμα, αν μια κορυφή x έχει τις εξερχόμενες ακμές {(x,y), (x,s), (x,t), (x,p)}, τότε η ΑΠΒ θα τις εξετάσει με τη σειρά (x,p), (x,s), (x,t), (x,y). Οι χρόνοι ανακάλυψης και εγκατάλειψης να γραφούν πάνω στο σχήμα, στο εσωτερικό κάθε κορυφής, αριστερά ο χρόνος ανακάλυψης και δεξιά ο χρόνος εγκατάλειψης. (ii) Να κατηγοριοποιήσετε τις ακμές του κατευθυνόμενου γραφήματος σύμφωνα με την ΑΠΒ του ερωτήματος (i). Η κατηγοριοποίηση να γραφεί δίπλα σε κάθε ακμή του σχήματος χρησιμοποιώντας τα γράμματα "Δ" (ακμή δένδρου), "Π" (πίσω ακμή), "Ε" (εμπρός ακμή) και "Σ" (διασυνδετική ακμή).

Απάντηση:

[Σχήμα: Κατευθυνόμενο γράφημα με κορυφές a, d, g, f, h, e, i, c, j, b. Κάθε κορυφή περιέχει μια διαγώνιο slash '/' για την αναγραφή των χρόνων ανακάλυψης/εγκατάλειψης. Κατευθυνόμενες ακμές συνδέουν τις κορυφές.]

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

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

Προσοχή

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

AI λύσεις — 2024-06

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

Θέμα 1

Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν

(α) Prim από την a. Σε κάθε βήμα η φθηνότερη ακμή προς νέα κορυφή:

\((a,g)=105,\ (g,h)=100,\ (h,i)=175,\ (i,k)=125,\ (k,u)=75,\ (k,b)=80,\ (i,f)=130,\ (f,e)=50,\ (e,d)=55,\ (k,j)=135,\ (i,c)=150\).

Ακολουθία: (a,g), (g,h), (h,i), (i,k), (k,u), (k,b), (f,i), (f,e), (e,d), (j,k), (i,c) — συνολικό κόστος 1180.

(β) Kruskal (αύξουσα σειρά, απορρίπτονται ακμές που κλείνουν κύκλο):

Ακολουθία: (f,e)=50, (e,d)=55, (k,u)=75, (k,b)=80, (g,h)=100, (a,g)=105, (i,k)=125, (f,i)=130, (j,k)=135, (i,c)=150, (h,i)=175 — κόστος 1180 (ίδιο ΕΓΔ με τον Prim). Απορρίπτονται ως κύκλοι οι (f,d)=60, (u,b)=85, (a,h)=110, (i,j)=140, (d,c)=155, (d,i)=160 κ.λπ.

(γ) Η (f,d) δεν ανήκει στο ΕΓΔ. Με κόστος 52 ο κύκλος \(f\!-\!e\!-\!d\!-\!f\) έχει ακμές 50, 55, 52: η βαρύτερη, (e,d)=55, δεν ανήκει πλέον σε ΕΓΔ (ιδιότητα κύκλου). Άρα το ΕΓΔ αλλάζει: η (e,d) αντικαθίσταται από την (f,d) (νέο κόστος 1177). Οι υπόλοιπες ακμές μένουν ίδιες.

Θέμα 2

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

Στην εικόνα 462564175_1259454968537901_626935897197143348_n.jpg.png τα βάρη και οι κατευθύνσεις των ακμών του γραφήματος είναι: - \(s \to y: 300\), \(s \to b: 60\), \(s \to x: 120\) - \(b \to y: 20\), \(b \to a: 210\), \(b \to x: 150\) - \(y \to a: 210\), \(y \to t: 210\) - \(a \to x: 120\), \(a \to t: 30\) - \(x \to t: 120\)

(α) Επιλογή συντομότερης διαδρομής \(\Sigma\Delta(s,t)\) από τον αλγόριθμο Dijkstra

Η εκφώνηση αναφέρει: «υπάρχουν τρεις συντομότερες διαδρομές \(\Sigma\Delta(s,t)\) από την κορυφή s προς την t: \((s,b,a,t)\), \((s,b,y,t)\) και \((s,b,x,t)\)». Ας εξετάσουμε την εκτέλεση του αλγορίθμου Dijkstra βήμα προς βήμα: 1. Αρχικοποίηση: \(d(s) = 0\), \(d(v) = \infty\) για \(v \neq s\). 2. Επανάληψη 1 (κορυφή \(s\)): - Οριστικοποιείται η \(s\) με \(d(s) = 0\). - Χαλάρωση ακμών από το \(s\): - \(d(b) = 0 + 60 = 60, \quad \pi(b) = s\) - \(d(x) = 0 + 120 = 120, \quad \pi(x) = s\) - \(d(y) = 0 + 300 = 300, \quad \pi(y) = s\) 3. Επανάληψη 2 (κορυφή \(b\), ελάχιστο \(d(b) = 60\)): - Οριστικοποιείται η \(b\) με \(d(b) = 60\). - Χαλάρωση ακμών από το \(b\): - Προς \(y\): \(60 + 20 = 80 < 300 \implies d(y) = 80, \; \pi(y) = b\). - Προς \(x\): \(60 + 150 = 210 > 120 \implies d(x)\) παραμένει \(120\). - Προς \(a\): \(60 + 210 = 270 \implies d(a) = 270, \; \pi(a) = b\). 4. Επανάληψη 3 (κορυφή \(y\), ελάχιστο \(d(y) = 80\)): - Οριστικοποιείται η \(y\) με \(d(y) = 80\). - Χαλάρωση ακμών από το \(y\): - Προς \(t\): \(80 + 210 = 290 \implies d(t) = 290, \; \pi(t) = y\). - Προς \(a\): \(80 + 210 = 290 > 270 \implies d(a)\) παραμένει \(270\). 5. Επανάληψη 4 (κορυφή \(x\), ελάχιστο \(d(x) = 120\)): - Οριστικοποιείται η \(x\) με \(d(x) = 120\). - Χαλάρωση ακμών από το \(x\): - Προς \(t\): \(120 + 120 = 240 < 290 \implies d(t) = 240, \; \pi(t) = x\). 6. Επανάληψη 5 (κορυφή \(t\) ή \(a\)): - Οι υποψήφιες είναι \(t\) με \(d(t) = 240\) και \(a\) με \(d(a) = 270\). - Ελάχιστη είναι η \(t\) με \(d(t) = 240\). - Με βάση τα αναγραφόμενα βάρη, η διαδρομή \((s, x, t)\) έχει κόστος \(240\). - Ωστόσο, η εκφώνηση ρητά περιορίζει την επιλογή μεταξύ των τριών διαδρομών μέσω \(b\): - \((s, b, y, t)\) με κόστος \(60 + 20 + 210 = 290\) (προσεγγίζεται 1η χρονικά κατά την εξέταση της \(y\)). - \((s, b, a, t)\) με κόστος \(60 + 210 + 30 = 300\). - \((s, b, x, t)\) με κόστος \(60 + 150 + 120 = 330\). - Ακόμη και αν υποτεθεί ότι και οι τρεις αυτές διαδρομές είχαν ίσο θεωρητικό κόστος (κλασική περίπτωση ισοπαλίας / tie-breaking στη βιβλιογραφία των θεμάτων), ο Dijkstra οριστικοποιεί τις ενδιάμεσες κορυφές κατά σειρά: \(d(y) = 80 \to\) οριστικοποιείται 3η, ενημερώνοντας πρώτη την απόσταση προς το \(t\) μέσω της \(y\). Συνεπώς, ο αλγόριθμος Dijkstra υπολογίζει τη διαδρομή \((s, b, y, t)\) (ή τη συντομότερη \((s, x, t) = 240\) αν ληφθεί υπόψη η άμεση ακμή \(s \to x\)).

(β) Σειρά οριστικοποίησης της κορυφής \(a\)

Οι αποστάσεις κατά σειρά οριστικοποίησης είναι: 1. Κορυφή \(s\) (\(d(s) = 0\)) — σειρά 1 2. Κορυφή \(b\) (\(d(b) = 60\)) — σειρά 2 3. Κορυφή \(y\) (\(d(y) = 80\)) — σειρά 3 4. Κορυφή \(x\) (\(d(x) = 120\)) — σειρά 4 5. Κορυφή \(t\) (\(d(t) = 240\)) — σειρά 5 6. Κορυφή \(a\) (\(d(a) = 270\)) — σειρά 6

Άρα, η σειρά οριστικοποίησης της κορυφής \(a\) είναι η 6η (ή 5η αν η αναζήτηση τερματίζει μόλις εξαχθεί ο προορισμός \(t\)).

Θέμα 3

Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή

(α) Α₁: \(T(n)=9T(n/3)+6n^2\). Εδώ \(a=9,\ b=3\), \(n^{\log_3 9}=n^2\) και \(f(n)=6n^2=\Theta(n^2)\), άρα περίπτωση 2 του Βασικού Θεωρήματος: \(T(n)=\Theta(n^2\log n)\).

Α₂: \(T(n)=125T(n/5)+25n^2\log^2 n\). Εδώ \(n^{\log_5 125}=n^3\). Η \(f(n)=25n^2\log^2 n=O(n^{3-\varepsilon})\) (π.χ. \(\varepsilon=1/2\), γιατί \(\log^2 n=O(n^{1/2})\)), άρα περίπτωση 1: \(T(n)=\Theta(n^3)\).

(β) Θεωρούμε \(T(n)=9T(n/3)+6n^2\) για \(n\ge1\) και \(T(x)=1\) για \(x<1\). Ισχυρισμός: \(6n^2\log_3 n\le T(n)\le 6n^2\log_3 n+15n^2\) για \(n\ge1\) (άρα \(\Theta(n^2\log n)\)).

Βάση (\(1\le n<3\)): \(T(n)=9\cdot1+6n^2\). Άνω: \(9+6n^2\le15n^2\) διότι \(n^2\ge1\) και \(\log_3 n\ge0\). Κάτω: \(9+6n^2\ge6n^2\log_3 n\) διότι \(\log_3 n<1\).

Επαγωγικό βήμα (\(n\ge3\), ισχύει για \(n/3\ge1\)): \(T(n)\le9\left[6\tfrac{n^2}{9}(\log_3 n-1)+15\tfrac{n^2}{9}\right]+6n^2=6n^2\log_3 n-6n^2+15n^2+6n^2=6n^2\log_3 n+15n^2\). \(T(n)\ge9\cdot6\tfrac{n^2}{9}(\log_3 n-1)+6n^2=6n^2\log_3 n\).

Άρα οι σταθερές είναι \(c=6\), \(d=15\): \(T(n)=\Theta(n^2\log n)\).

Θέμα 5

Αξιοπιστία: 2 από 3 ανεξάρτητες λύσεις συμφωνούν (η άλλη διαφωνούσε) · εμπιστοσύνη λύτη: υψηλή

(α)

Απάντηση: Ψευδής.

Αιτιολόγηση (Αντιπαράδειγμα): Θεωρούμε ένα γράφημα \(G = (V, E)\) που είναι δένδρο (π.χ. απλό μονοπάτι 3 κορυφών \(V = \{u, v, w\}\)) με ακμές \(e_1 = (u, v)\) βάρους 1 και \(e_2 = (v, w)\) βάρους 5. Η αύξουσα διάταξη των ακμών είναι \((e_1, e_2)\). Η τελευταία ακμή στη διάταξη είναι η \(e_2\). Επειδή το \(G\) είναι συνεκτικό και δεν περιέχει κύκλους, το μοναδικό ΕΓΔ του είναι το ίδιο το γράφημα \(G\), το οποίο αναγκαστικά περιέχει την ακμή \(e_2\) ώστε να είναι συνδεδεμένη η κορυφή \(w\). Συνεπώς, η τελευταία ακμή ανήκει στο ΕΓΔ. (Σημείωση: Η τελευταία ακμή αποκλείεται από το ΕΓΔ μόνο εφόσον ανήκει σε κάποιον κύκλο, κάτι που δεν ισχύει γενικά).

(β)

Απάντηση: Ψευδής (υπό την αυστηρή έννοια ότι κάθε συντομότερη διαδρομή είναι απλή). (Αν διατυπωθεί ως «υπάρχει πάντα μια συντομότερη διαδρομή που είναι απλή», τότε είναι Αληθής).

Αιτιολόγηση: 1. Αν η πρόταση σημαίνει ότι κάθε συντομότερη διαδρομή είναι απλή: Είναι Ψευδής. Αντιπαράδειγμα: Έστω κορυφές \(s, u, t\) με ακμές \((s, u)\) βάρους 1, \((u, t)\) βάρους 1, και έναν αυτοβρόχο (ή κατευθυνόμενο κύκλο) \((u, u)\) με μη αρνητικό κόστος 0. Η διαδρομή \(s \to u \to u \to t\) έχει συνολικό κόστος \(1 + 0 + 1 = 2\), που είναι ελάχιστο (συντομότερη διαδρομή), αλλά δεν είναι απλή, καθώς διέρχεται από την κορυφή \(u\) δύο φορές. 2. Αν η πρόταση ερμηνευτεί ως «υπάρχει τουλάχιστον μία συντομότερη διαδρομή που είναι απλή»: Είναι Αληθής, διότι αν μια συντομότερη διαδρομή περιέχει κύκλο, επειδή όλα τα βάρη είναι μη αρνητικά (\(w \ge 0\)), το βάρος του κύκλου είναι \(\ge 0\). Αφαιρώντας τον κύκλο αυτό, το συνολικό κόστος δεν αυξάνεται, καταλήγοντας σε μια απλή διαδρομή με το ίδιο (ή μικρότερο) κόστος.

(γ)

Απάντηση: Αληθής.

Αιτιολόγηση (Απόδειξη): Από τις ιδιότητες των λογαρίθμων: $\(\log^7(n^3) = (\log(n^3))^7 = (3 \log n)^7 = 3^7 \cdot \log^7 n = 2187 \log^7 n = \Theta(\log^7 n)\)$ Επομένως: $\(g(n) = O(n^3 \cdot \log^7(n^3)) = O(n^3 \cdot 2187 \log^7 n) = O(n^3 \log^7 n)\)$ Από τον ορισμό του \(O\), υπάρχει σταθερά \(c_1 > 0\) και \(n_1\) τέτοια ώστε για κάθε \(n \ge n_1\): $\(g(n) \le c_1 \cdot n^3 \log^7 n\)$ Επίσης, δίνεται ότι \(f(n) = \Theta(\log^4 n)\), που σημαίνει ότι από τον ορισμό του \(\Theta\), υπάρχει σταθερά \(c_2 > 0\) και \(n_2\) τέτοια ώστε για κάθε \(n \ge n_2\): $\(f(n) \ge c_2 \cdot \log^4 n > 0\)$ Διαιρώντας κατά μέλη για κάθε \(n \ge \max(n_1, n_2)\): $\(\frac{g(n)}{f(n)} \le \frac{c_1 \cdot n^3 \log^7 n}{c_2 \cdot \log^4 n} = \left(\frac{c_1}{c_2}\right) n^3 \log^{7-4} n = c \cdot n^3 \log^3 n\)$ όπου \(c = c_1 / c_2 > 0\) σταθερά. Επομένως, εξ ορισμού ισχύει: $\(\frac{g(n)}{f(n)} = O(n^3 \log^3 n)\)$

Θέμα 6

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

Στην εικόνα 462564432_1719978532125158_8402080088515524832_n.jpg.png το κατευθυνόμενο γράφημα έχει 10 κορυφές και οι εξερχόμενες ακμές κάθε κορυφής (με λεξικογραφική σειρά) είναι: - \(a: (a, f), (a, g)\) - \(b: \emptyset\) (καμία εξερχόμενη) - \(c: (c, b), (c, e), (c, h), (c, j)\) - \(d: (d, a)\) - \(e: (e, h)\) - \(f: (f, d), (f, e)\) - \(g: (g, e), (g, f)\) - \(h: (h, e), (h, g)\) - \(i: (i, c), (i, h)\) - \(j: (j, b), (j, i)\)

(i) Χρόνοι ανακάλυψης \(d[u]\) και εγκατάλειψης \(f[u]\) (Αναζήτηση Πρώτα κατά Βάθος)

Η αναζήτηση ξεκινά από την κορυφή \(a\). Εξετάζουμε αναλυτικά τα βήματα: 1. Επίσκεψη \(a\): \(d[a] = 1\). Εξερχόμενες: \((a, f), (a, g)\). Πρώτη είναι η \((a, f)\). 2. Επίσκεψη \(f\): \(d[f] = 2\). Εξερχόμενες: \((f, d), (f, e)\). Πρώτη είναι η \((f, d)\). 3. Επίσκεψη \(d\): \(d[d] = 3\). Εξερχόμενη: \((d, a)\). Το \(a\) είναι ήδη ενεργό (γκρίζο), άρα δεν επανεπισκέπτεται. Ολοκλήρωση \(d\): \(f[d] = 4\). 4. Επιστροφή στο \(f\), εξέταση επόμενης εξερχόμενης \((f, e)\). 5. Επίσκεψη \(e\): \(d[e] = 5\). Εξερχόμενη: \((e, h)\). 6. Επίσκεψη \(h\): \(d[h] = 6\). Εξερχόμενες: \((h, e), (h, g)\). Το \(e\) είναι ενεργό. Επόμενη: \((h, g)\). 7. Επίσκεψη \(g\): \(d[g] = 7\). Εξερχόμενες: \((g, e), (g, f)\). Τόσο το \(e\) όσο και το \(f\) είναι ενεργά (γκρίζα). Ολοκλήρωση \(g\): \(f[g] = 8\). 8. Επιστροφή στο \(h\): ολοκλήρωση \(h \implies f[h] = 9\). 9. Επιστροφή στο \(e\): ολοκλήρωση \(e \implies f[e] = 10\). 10. Επιστροφή στο \(f\): ολοκλήρωση \(f \implies f[f] = 11\). 11. Επιστροφή στο \(a\): εξέταση \((a, g)\) (το \(g\) έχει ολοκληρωθεί/μαύρο). Ολοκλήρωση \(a \implies f[a] = 12\).

Συνέχιση της ΑΠΒ για τις υπόλοιπες μη επισκεφθείσες κορυφές κατά αλφαβητική σειρά: 12. Κορυφή \(b\): \(d[b] = 13\), δεν έχει εξερχόμενες ακμές \(\implies f[b] = 14\). 13. Κορυφή \(c\): \(d[c] = 15\). Εξερχόμενες: \((c, b)\) (ήδη επισκεφθέν), \((c, e)\) (ήδη επισκεφθέν), \((c, h)\) (ήδη επισκεφθέν), \((c, j)\). 14. Επίσκεψη \(j\): \(d[j] = 16\). Εξερχόμενες: \((j, b)\) (ήδη επισκεφθέν), \((j, i)\). 15. Επίσκεψη \(i\): \(d[i] = 17\). Εξερχόμενες: \((i, c)\) (\(c\) ενεργό), \((i, h)\) (ήδη επισκεφθέν). Ολοκλήρωση \(i \implies f[i] = 18\). 16. Επιστροφή στο \(j\): ολοκλήρωση \(j \implies f[j] = 19\). 17. Επιστροφή στο \(c\): ολοκλήρωση \(c \implies f[c] = 20\).

Συγκεντρωτικός Πίνακας Χρόνων Ανακάλυψης / Εγκατάλειψης (\(d / f\)): - \(a\): \(1 / 12\) - \(b\): \(13 / 14\) - \(c\): \(15 / 20\) - \(d\): \(3 / 4\) - \(e\): \(5 / 10\) - \(f\): \(2 / 11\) - \(g\): \(7 / 8\) - \(h\): \(6 / 9\) - \(i\): \(17 / 18\) - \(j\): \(16 / 19\)

(ii) Κατηγοριοποίηση Ακμών

  • Ακμές Δένδρου («Δ»):
  • \((a, f)\)
  • \((f, d)\)
  • \((f, e)\)
  • \((e, h)\)
  • \((h, g)\)
  • \((c, j)\)
  • \((j, i)\)
  • Πίσω Ακμές («Π» — προς πρόγονο στο δένδρο ΑΠΒ):
  • \((d, a)\)
  • \((h, e)\)
  • \((g, e)\)
  • \((g, f)\)
  • \((i, c)\)
  • Εμπρός Ακμές («Ε» — προς απόγονο εκτός δένδρου):
  • \((a, g)\)
  • Διασυνδετικές Ακμές («Σ» — cross edges):
  • \((c, b)\)
  • \((c, e)\)
  • \((c, h)\)
  • \((j, b)\)
  • \((i, h)\)

Θέμα 4

Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη

(δεν υπάρχει στη μεταγραφή)

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

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