Θεωρία Γραφημάτων και Εφαρμογές — Αύγουστος 2021¶
Μεταγραφή από τις φωτογραφίες της εξέτασης Αυγούστου 2021.
319.png¶
Ερώτηση: 1 (Ελεύθερου Κειμένου)
Βρείτε άν η σχέση { (u, v) | υπάρχει κλειστό ίχνος που περιέχει τις κορυφές u , v } είναι μεταβατική, όταν οι u , v είναι κορυφές του κατευθυνόμενου γραφήματος.
[Σχήμα: Κατευθυνόμενο γράφημα με 4 κορυφές (1, 3, 4, 5). Προσανατολισμένες ακμές: 1 -> 3, 3 -> 4, 4 -> 1, 1 -> 5, 4 -> 5.]
318.png¶
Ερώτηση: 2 (Ελεύθερου Κειμένου)
Βρείτε ένα δέντρο επικάλυψης Τ1 , ώστε ο κύκλος ( 1 , _ , 5 , _ , 4 , _ , 3 , _ , 1 ) να είναι στοιχειώδης ως προς το Τ1 . Βρείτε ένα δέντρο επικάλυψης Τ2 , ώστε ο ίδιος κύκλος ( 1 , _ , 5 , _ , 4 , _ , 3 , _ , 1 ) να μην είναι στοιχειώδης ως προς το Τ2 .
[Σχήμα: Μη κατευθυνόμενο γράφημα με 6 κορυφές (1, 2, 3, 4, 5, 6). Ακμές: (3, 1), (3, 4), (4, 5), (1, 5), (1, 2), (2, 5), (2, 6), (5, 6).]
316.png¶
Ερώτηση: 5 (Ελεύθερου Κειμένου)
Βρείτε όλα τα (διαφορετικά μεταξύ τους) δέντρα επικάλυψης του γραφήματος.
[Σχήμα: Μη κατευθυνόμενο γράφημα με 6 κορυφές. Ακμές: (3, 4), (4, 1), (1, 2), (2, 5), (5, 4), (2, 6).]
317.png¶
[Λείπει από τη φωτογραφία: κεφαλίδα της ερώτησης (αριθμός και τύπος)]
Έστω Τ το δέντρο επικάλυψης που αποτελείται από τις έντονες ακμές. Να γραφτεί το υπο-γράφημα που προκύπτει μετά την αφαίρεση της κορυφής 3, ως άθροισμα στοιχειωδών κύκλων ως προς το Τ .
[Σχήμα: Μη κατευθυνόμενο γράφημα με κορυφές 1 έως 7. Έντονες ακμές δέντρου Τ: (3, 1), (1, 4), (4, 2), (2, 6), (4, 5), (7, 5). Λοιπές (μη έντονες) ακμές: (3, 4), (1, 2), (2, 5), (5, 6), (4, 7).]
Screenshot_20210821-151627_Messenger.jpg¶
[Λείπει από τη φωτογραφία: κεφαλίδα της ερώτησης (αριθμός και τύπος)]
Προσθέστε μία ακμή στο γράφημα, ώστε το νέο γράφημα να μην έχει γέφυρες.
[Σχήμα: Μη κατευθυνόμενο γράφημα με 7 κορυφές (1, 2, 3, 4, 5, 6, 7). Ακμές: (3, 1), (1, 5), (4, 7), (4, 5), (5, 2), (2, 6), (5, 6).]
320.png¶
Ερώτηση: 7 (Ελεύθερου Κειμένου)
Βρείτε όλα τα (διαφορετικά μεταξύ τους) μη-επεκτάσιμα μονοπάτια, που δεν έχουν ως άκρο μία από τις κορυφές 3, 4 .
[Σχήμα: Μη κατευθυνόμενο γράφημα με 6 κορυφές (1, 2, 3, 4, 5, 6). Ακμές: (3, 1), (1, 4), (4, 5), (1, 5), (1, 2), (2, 5), (2, 6).]
Λύσεις (⚪ AI, μη επαληθευμένο)
Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (gemini-3.7-flash, sonnet), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο
Προσοχή
Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.
AI λύσεις — 2021-08¶
Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.
Θέμα 1¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: μέτρια
Κατευθυνόμενο γράφημα: 1→3, 3→4, 4→1, 1→5, 4→5. Κλειστά ίχνη (χωρίς επανάληψη ακμής) υπάρχουν μόνο γύρω από τον κύκλο 1→3→4→1· η κορυφή 5 δεν έχει εξερχόμενη ακμή, άρα δεν ανήκει σε κανένα κλειστό ίχνος μήκους ≥1. Η σχέση είναι:
\(R=\{1,3,4\}\times\{1,3,4\}\) (εννέα ζεύγη).
Μεταβατική: αν \((u,v),(v,w)\in R\) τότε \(u,w\in\{1,3,4\}\) άρα \((u,w)\in R\). Αν θεωρηθεί και το τετριμμένο κλειστό ίχνος μήκους 0, προστίθεται το \((5,5)\) και η μεταβατικότητα ισχύει πάλι (το μόνο ζεύγος με 5 είναι το \((5,5)\)).
Απάντηση: ναι, είναι μεταβατική. (Επαληθεύτηκε με πρόγραμμα.)
Θέμα 2¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
Κύκλος \(C=(1,5,4,3,1)\) με ακμές 15, 54, 43, 31. Ο \(C\) είναι στοιχειώδης ως προς το δέντρο T όταν ακριβώς μία ακμή του είναι χορδή (εκτός T), οι άλλες τρεις ανήκουν στο T.
T1: ακμές 15, 45, 34, 12, 26 (κορυφές 1–6, 5 ακμές, συνεκτικό). Από τον \(C\) λείπει μόνο η 31, άρα ο \(C\) είναι ο στοιχειώδης κύκλος της 31.
T2: ακμές 34, 45, 25, 12, 26 (δέντρο). Από τον \(C\) λείπουν δύο ακμές (15 και 31), άρα ο \(C\) έχει δύο χορδές και δεν είναι στοιχειώδης.
(Επαληθεύτηκε ότι και τα δύο είναι δέντρα επικάλυψης.)
Θέμα 5¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
Ακμές: 34, 41, 12, 25, 54, 26 (6 κορυφές, 6 ακμές). Ο μοναδικός κύκλος είναι 4–1–2–5–4 (ακμές 41, 12, 25, 54). Οι 34 και 26 είναι κρεμασμένες ακμές (γέφυρες), άρα ανήκουν σε κάθε δέντρο επικάλυψης. Ένα δέντρο έχει 5 ακμές, άρα αφαιρούμε μία ακριβώς ακμή του κύκλου: 4 επιλογές.
Απάντηση: 4 δέντρα επικάλυψης: το γράφημα χωρίς την 41, ή χωρίς τη 12, ή χωρίς την 25, ή χωρίς την 54. (Επαληθεύτηκε: 4.)
Θέμα (317.png, αριθμός άγνωστος): γράφημα μετά την αφαίρεση της 3, ως άθροισμα στοιχειωδών κύκλων¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
T = {31, 14, 42, 26, 45, 75}, μη-T ακμές: 34, 12, 25, 56, 47. Η 3 είναι φύλλο του T (μόνο η 31), άρα το T−3 παραμένει δέντρο επικάλυψης του Γ−3. Οι ακμές του Γ−3: 14, 42, 26, 45, 75 (T) και χορδές 12, 25, 56, 47 (η 34 φεύγει με την 3). Όλοι οι βαθμοί του Γ−3 είναι άρτιοι (1:2, 2:4, 4:4, 5:4, 6:2, 7:2), άρα είναι άθροισμα κύκλων, και μάλιστα των στοιχειωδών κύκλων των χορδών του: - \(C(12)\): 1–4–2–1 - \(C(25)\): 2–4–5–2 - \(C(56)\): 5–4–2–6–5 - \(C(47)\): 4–5–7–4
Έλεγχος: κάθε ακμή του Γ−3 προκύπτει περιττές φορές: π.χ. η 24 εμφανίζεται σε \(C(12)\), \(C(25)\), \(C(56)\) (3 φορές, μένει), η 14 μόνο στον \(C(12)\), η 45 σε \(C(25)\), \(C(56)\), \(C(47)\) (3), η 26 στον \(C(56)\), η 57 στον \(C(47)\) (1).
Απάντηση: \(\Gamma-3 = C(12)+C(25)+C(56)+C(47)\). (Επαληθεύτηκε με πρόγραμμα.)
Σημείωση: η κεφαλίδα της ερώτησης λείπει· η διατύπωση που διαβάστηκε είναι αυτή που λύθηκε.
Θέμα (Screenshot_20210821, αριθμός άγνωστος): ακμή χωρίς γέφυρες¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
Ακμές: 31, 15, 47, 45, 52, 26, 56. Γέφυρες: 31, 15, 54, 47 (το τρίγωνο 5-2-6 είναι το μόνο που κλείνει κύκλο). Μονοπάτι 3–1–5–4–7 περιέχει και τις τέσσερις. Αν προσθέσουμε την {3,7} δημιουργείται ο κύκλος 3–1–5–4–7–3 που τις περιέχει όλες.
Απάντηση: προσθέτουμε την ακμή {3,7}. (Επαληθεύτηκε: καμία γέφυρα.)
Θέμα 7¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: μέτρια
Ακμές: 31, 14, 45, 15, 12, 25, 26. Μη-επεκτάσιμα μονοπάτια (και τα δύο άκρα δεν έχουν γείτονα εκτός μονοπατιού). Εξαντλητική αναζήτηση βρίσκει 9, με άκρα: - 3–1–2–5–4, 3–1–2–6, 3–1–4–5–2–6, 3–1–5–2–6, 3–1–5–4, 4–1–2–5, 4–1–5–2–6, 4–5–1–2–6, 5–4–1–2–6.
Ζητούνται όσα δεν έχουν άκρο ούτε την 3 ούτε την 4. Αυτό ικανοποιεί μόνο το 5–4–1–2–6 (τα άκρα του είναι 5, 6).
Απάντηση: ένα μόνο μονοπάτι, το \((5,4,1,2,6)\). Η ερμηνεία «κανένα άκρο στο {3,4}» είναι υπόθεση της λύσης· αν εννοείται «όχι και τα δύο άκρα», η απάντηση θα ήταν διαφορετική.