Θεωρία Γραφημάτων και Εφαρμογές — Ιανουάριος 2023¶
Μεταγραφή από τις φωτογραφίες 2024.jpg (σετ Α) και IMG_20250117_173405.jpg (σετ Β).
2024.jpg¶
Θεωρία Γραφημάτων & Εφαρμογές - Διακριτά Μαθ/κά ΙΙ Ιανουάριος 2023 Άριστα = 15 μονάδες
Κάθε απάντηση πρέπει να εξηγείται επαρκώς με βάση τη θεωρία. Σε ερωτήματα που ζητείται να βρεθούν ορισμένα στοιχεία, ενδέχεται να μην υπάρχουν. Το \(\Gamma\) είναι πάντα ένα μη-κατευθυνόμενο γράφημα.
1 Αποδείξτε ότι: άν για τα σύνολα A, B, C, D ισχύει \(A \oplus B \oplus C = D\), θα ισχύει και \(B \oplus C = D \oplus A\). 1 μονάδα
2 Βρείτε ένα συνεκτικό \(\Gamma\) με 6 κορυφές, που να έχει περισσότερες από τρείς δισυνεκτικές συνιστώσες ως προς ακμές. 1,5 μονάδα
3 Έστω η σχέση \(P = \{ (0, 0) , (2, 2) , (4, 4) \}\) πάνω στο σύνολο των ακέραιων αριθμών. 1 μονάδα \(\alpha\) Βρείτε άν η P είναι συμμετρική. \(\beta\) Βρείτε άν η P είναι μεταβατική.
4 Στο κατευθυνόμενο γράφημα G1: \(\alpha\) βρείτε μία κλειστή διαδρομή που να μην είναι κλειστό ίχνος. \(\beta\) βρείτε ένα κλειστό ίχνος που να μην είναι κύκλος. 2 μονάδες
[Σχήμα: Κατευθυνόμενο γράφημα G1 με κορυφές 1, 2, 3, 4] [Σχήμα: Μη-κατευθυνόμενο γράφημα G2 με κορυφές a, b, c, d, e, f, με έντονες ακμές]
5 Στο κατευθυνόμενο γράφημα G1, βρείτε τις ισχυρά συνεκτικές συνιστώσες. 1,5 μονάδα
6 Στο μη-κατευθυνόμενο γράφημα G2: \(\alpha\) βρείτε τους κύκλους που είναι στοιχειώδεις ως προς το δέντρο επικάλυψης που αποτελείται από τις έντονες ακμές. \(\beta\) βρείτε ακόμη δύο δέντρα επικάλυψης. 2 μονάδες
7 Στο μη-κατευθυνόμενο γράφημα G2 βρείτε ένα μη-επεκτάσιμο μονοπάτι που να μην έχει άκρο το [Λείπει από τη φωτογραφία: κορυφή στο τέλος της πρότασης, κομμένη από το άκρο]· [Λείπει από τη φωτογραφία: αρχή της δεύτερης πρότασης, κρυμμένη από το χέρι] ένα μη-επεκτάσιμο μονοπάτι που να έχει άκρο το c. 2 μονάδες
8 Αποδείξτε ότι: Άν το \(\Gamma\) είναι συνεκτικό και έχει n κορυφές και n ακμές (\(n \ge 3\)), θα έχει κύκλο. 1 μονάδα
9 Στο μη-κατευθυνόμενο γράφημα G2 βρείτε ένα υπογράφημα που να περιέχει τις κορυφές b κα[Λείπει από τη φωτογραφία: τέλος της λέξης «και»] να είναι δισυνεκτικό ως προς κορυφές, αλλά να μήν είναι δισυνεκτική συνιστώσα ως προς κορυφές. 1,5 μονάδα
10 Αποδείξτε ότι: Δύο διαφορετικές συνεκτικές συνιστώσες ενός μη-κατευθυνόμενου γραφήματος δεν μπορούν να έχουν κοινή κορυφή. 1 μονάδα
Συμπληρώστε τα στοιχεία σας και επιστρέψτε τα θέματα
IMG_20250117_173405.jpg¶
Θεωρία Γραφημάτων & Εφαρμογές - Διακριτά Μαθ/κά ΙΙ Ιανουάριος 2023 Άριστα = 15 μονάδες
Κάθε απάντηση πρέπει να εξηγείται επαρκώς με βάση τη θεωρία. Σε ερωτήματα που ζητείται να βρεθούν ορισμένα στοιχεία, ενδέχεται να μην υπάρχουν. Το Γ είναι πάντα ένα μη-κατευθυνόμενο γράφημα.
1 Αποδείξτε ότι, για οποιαδήποτε σύνολα A, B, C, ισχύει \((A \oplus B) \oplus (B \oplus C) \oplus (C \oplus A) = \varnothing\) . 1 μονάδα
2 Βρείτε ένα Γ δισυνεκτικό ως προς ακμές, που να έχει ακριβώς δύο δισυνεκτικές συνιστώσες ως προς κορυφές. 1,5 μονάδα
3 Έστω η σχέση \(P = \{ (0, 0) , (2, 0) , (0, 2) \}\) πάνω στο σύνολο των ακέραιων αριθμών. 1 μονάδα \(\alpha\) Βρείτε άν η P είναι συμμετρική. \(\beta\) Βρείτε άν η P είναι μεταβατική.
4 Στο κατευθυνόμενο γράφημα G1: \(\alpha\) βρείτε μία κλειστή διαδρομή που να μην είναι κλειστό ίχνος. \(\beta\) βρείτε ένα κλειστό ίχνος που να μην είναι κύκλος. 2 μονάδες
[Σχήμα: Κατευθυνόμενο γράφημα G1 με κορυφές 1, 2, 3, 4] [Σχήμα: Μη-κατευθυνόμενο γράφημα G2 με κορυφές a, b, c, d, e, με έντονες ακμές]
5 Στο κατευθυνόμενο γράφημα G1, βρείτε τις ισχυρά συνεκτικές συνιστώσες. 1,5 μονάδα
6 Στο μη-κατευθυνόμενο γράφημα G2: \(\alpha\) βρείτε τους κύκλους που δεν είναι στοιχειώδεις ως προς το δέντρο επικάλυψης που αποτελείται από τις έντονες ακμές. \(\beta\) βρείτε ακόμη δύο δέντρα επικάλυψης. 2 μονάδες
7 Στο μη-κατευθυνόμενο γράφημα G2 βρείτε ένα μη-επεκτάσιμο μονοπάτι με άκρο το d, και ένα μη-επεκτάσιμο μονοπάτι με άκρο το e. 2 μονάδες
8 Αποδείξτε ότι: Άν το Γ δεν είναι δισυνεκτικό ως προς ακμές, δεν θα είναι δισυνεκτικό ως προς κορυφές. 1 μονάδα
9 Στο μη-κατευθυνόμενο γράφημα G2 βρείτε ένα υπογράφημα με δύο τουλάχιστον κορυφές, που να είναι δισυνεκτικό ως προς κορυφές αλλά να μην είναι δισυνεκτική συνιστώσα ως προς κορυφές. 1,5 μονάδα
10 Αποδείξτε ότι: Άν το κατευθυνόμενο γράφημα G είναι ισχυρά συνεκτικό, κάθε ακμή του θα περιέχεται σε κάποιο (κατευθυνόμενο) κύκλο. 1,5 μονάδα
Επιπλέον πηγές χωρίς μεταγραφή εδώ (διπλότυπες φωτογραφίες της ίδιας σελίδας, σετ Β):
received_844357006632344.jpg
Λύσεις (⚪ AI, μη επαληθευμένο)
Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (antigravity-gemini, gemini-3.1-pro-preview, gemini-3.7-flash, sonnet), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο
Προσοχή
Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.
AI λύσεις — 2023-01¶
Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.
Θέμα 1, σετ Α¶
Αξιοπιστία: ⚠ οι ανεξάρτητες λύσεις διαφωνούν: δες όλες και έλεγξε μόνος σου · εμπιστοσύνη λύτη: χαμηλή
Λύση 1: Δίνεται \(A\oplus B\oplus C=D\). Εφαρμόζουμε \(A\oplus\) και στα δύο μέλη: \(A\oplus A\oplus B\oplus C=A\oplus D\), δηλ. \(B\oplus C=D\oplus A\) (διότι \(A\oplus A=\varnothing\)).
Λύση 2: Η πράξη της συμμετρικής διαφοράς \(\oplus\) είναι προσεταιριστική και αντιμεταθετική. Επίσης, για κάθε σύνολο \(X\) ισχύει \(X \oplus X = \varnothing\) και \(X \oplus \varnothing = X\).
Παίρνοντας τη συμμετρική διαφορά με το σύνολο \(A\) και στα δύο μέλη της ισότητας \(A \oplus B \oplus C = D\): $\((A \oplus B \oplus C) \oplus A = D \oplus A\)$ Λόγω της αντιμεταθετικότητας και της προσεταιριστικότητας: $\((A \oplus A) \oplus (B \oplus C) = D \oplus A\)$ $\(\varnothing \oplus (B \oplus C) = D \oplus A\)$ $\(B \oplus C = D \oplus A\)$
Λύση 3 (τρίτη γνώμη): Η πράξη της συμμετρικής διαφοράς \(\oplus\) μεταξύ συνόλων έχει την ιδιότητα της προσεταιριστικότητας και της αντιμεταθετικότητας. Επίσης, για οποιοδήποτε σύνολο \(X\) ισχύει \(X \oplus X = \varnothing\) και \(X \oplus \varnothing = X\). Χρησιμοποιώντας αυτές τις ιδιότητες, μπορούμε να αναδιατάξουμε τους όρους ως εξής: \((A \oplus B) \oplus (B \oplus C) \oplus (C \oplus A) = (A \oplus A) \oplus (B \oplus B) \oplus (C \oplus C) = \varnothing \oplus \varnothing \oplus \varnothing = \varnothing\).
Θέμα 2, σετ Α¶
Αξιοπιστία: ⚠ οι ανεξάρτητες λύσεις διαφωνούν: δες όλες και έλεγξε μόνος σου · εμπιστοσύνη λύτη: χαμηλή
Λύση 1: Αν θεωρήσουμε ότι κάθε κορυφή που δεν είναι άκρο γέφυρας πλαισιώνεται σε κάποια συνιστώσα (και μεμονωμένες κορυφές μετράνε ως συνιστώσες), ένα μονοπάτι/δέντρο με 6 κορυφές έχει 5 γέφυρες και κάθε κορυφή είναι από μόνη της δισυνεκτική συνιστώσα ως προς ακμές: 6 > 3. (Αν οι συνιστώσες είχαν υποχρεωτικά ≥2 κορυφές, με 6 κορυφές θα ήταν το πολύ 3, άρα η ερώτηση προϋποθέτει ότι οι μονοκόρυφες μετράνε.)
Απάντηση: το μονοπάτι \(P_6\) (\(1-2-3-4-5-6\)): 6 δισυνεκτικές συνιστώσες ως προς ακμές, οι \(\{i\}\).
Λύση 2: Μια δισυνεκτική συνιστώσα ως προς ακμές (2-edge-connected component) είναι ένα μέγιστο υπογράφημα χωρίς γέφυρες. Κάθε ακμή-γέφυρα χωρίζει το γράφημα σε διαφορετικές δισυνεκτικές συνιστώσες ως προς ακμές, ενώ μια μεμονωμένη κορυφή (ή κορυφές που συνδέονται μόνο μέσω γεφυρών) συνιστά τετριμμένη δισυνεκτική συνιστώσα (\(K_1\)).
Έστω το απλό μονοπάτι \(\Gamma = P_6\) με κορυφές \(V = \{v_1, v_2, v_3, v_4, v_5, v_6\}\) και ακμές: $\(E = \{\{v_1, v_2\}, \{v_2, v_3\}, \{v_3, v_4\}, \{v_4, v_5\}, \{v_5, v_6\}\}\)$ Το \(\Gamma\) είναι συνεκτικό με 6 κορυφές. Όλες οι 5 ακμές του είναι γέφυρες (bridges). Συνεπώς, οι δισυνεκτικές συνιστώσες ως προς ακμές είναι οι 6 μεμονωμένες κορυφές \(\{v_1\}, \{v_2\}, \{v_3\}, \{v_4\}, \{v_5\}, \{v_6\}\), δηλαδή 6 συνιστώσες, και ισχύει \(6 > 3\).
(Αντίστοιχα, αν θεωρηθεί ένα τρίγωνο \(v_1-v_2-v_3-v_1\) ενωμένο με ένα μονοπάτι \(v_3-v_4-v_5-v_6\), οι δισυνεκτικές συνιστώσες ως προς ακμές είναι 4: το τρίγωνο \(\{v_1, v_2, v_3\}\) και οι κορυφές \(\{v_4\}, \{v_5\}, \{v_6\}\), όπου πάλι \(4 > 3\).)
Λύση 3 (τρίτη γνώμη): Ένα γράφημα είναι δισυνεκτικό ως προς ακμές αν είναι συνεκτικό και δεν έχει γέφυρες (κάθε ακμή του ανήκει σε κάποιο κύκλο). Για να έχει ακριβώς δύο δισυνεκτικές συνιστώσες ως προς κορυφές (blocks), πρέπει να διαθέτει ακριβώς ένα σημείο άρθρωσης (cut-vertex) που να ενώνει αυτά τα δύο blocks. Ένα τέτοιο γράφημα \(\Gamma\) είναι το γράφημα "πεταλούδα" (butterfly graph), το οποίο αποτελείται από δύο τρίγωνα που μοιράζονται ακριβώς μία κοινή κορυφή. Συγκεκριμένα: - Σύνολο κορυφών: \(V = \{1, 2, 3, 4, 5\}\) - Σύνολο ακμών: \(E = \{(1,2), (2,3), (3,1), (3,4), (4,5), (5,3)\}\) Το γράφημα αυτό δεν έχει γέφυρες (άρα είναι δισυνεκτικό ως προς ακμές) και η κορυφή 3 είναι το μοναδικό σημείο άρθρωσης, χωρίζοντας το γράφημα σε ακριβώς δύο δισυνεκτικές συνιστώσες ως προς κορυφές (τα τρίγωνα \(\{1,2,3\}\) και \(\{3,4,5\}\)).
Θέμα 3, σετ Α¶
Αξιοπιστία: ⚠ οι ανεξάρτητες λύσεις διαφωνούν: δες όλες και έλεγξε μόνος σου · εμπιστοσύνη λύτη: χαμηλή
Λύση 1: \(P=\{(0,0),(2,2),(4,4)\}\). - (α) Συμμετρική: κάθε ζεύγος είναι της μορφής \((x,x)\), άρα το αντίστροφο ανήκει στην P. - (β) Μεταβατική: \((x,y),(y,z)\in P\Rightarrow x=y=z\), άρα \((x,z)=(x,x)\in P\).
Λύση 2: \(\alpha)\) Συμμετρική: Ναι. Μια σχέση \(P\) είναι συμμετρική αν για κάθε \((x, y) \in P\) ισχύει \((y, x) \in P\). Εδώ όλα τα στοιχεία της σχέσης είναι της μορφής \((x, x)\) [συγκεκριμένα \((0,0), (2,2), (4,4)\)], επομένως για κάθε \((x, y) \in P\) ισχύει \(x = y\), άρα και \((y, x) = (x, y) \in P\).
\(\beta)\) Μεταβατική: Ναι. Μια σχέση \(P\) είναι μεταβατική αν \((x, y) \in P\) και \((y, z) \in P \implies (x, z) \in P\). Επειδή όλα τα ζεύγη έχουν ίσα στοιχεία, η συνθήκη \((x, y) \in P\) και \((y, z) \in P\) ικανοποιείται μόνο όταν \(x = y = z\), απ' όπου έπεται άμεσα ότι \((x, z) = (x, y) \in P\).
Λύση 3 (τρίτη γνώμη): \(\alpha\) Η σχέση \(P\) είναι συμμετρική αν για κάθε \((x, y) \in P\) ισχύει και \((y, x) \in P\). Ελέγχουμε τα στοιχεία της \(P\): - Για το \((0, 0) \in P\), ισχύει \((0, 0) \in P\). - Για το \((2, 0) \in P\), ισχύει \((0, 2) \in P\). - Για το \((0, 2) \in P\), ισχύει \((2, 0) \in P\). Εφόσον ικανοποιείται η συνθήκη για όλα τα ζεύγη, η σχέση \(P\) είναι συμμετρική.
\(\beta\) Η σχέση \(P\) είναι μεταβατική αν για κάθε \((x, y) \in P\) και \((y, z) \in P\) συνεπάγεται ότι \((x, z) \in P\). Παρατηρούμε ότι \((2, 0) \in P\) και \((0, 2) \in P\). Για να είναι η σχέση μεταβατική, θα έπρεπε υποχρεωτικά να ισχύει και \((2, 2) \in P\). Επειδή το \((2, 2) \notin P\), η σχέση \(P\) δεν είναι μεταβατική.
Θέμα 8, σετ Α¶
Αξιοπιστία: ⚠ οι ανεξάρτητες λύσεις διαφωνούν: δες όλες και έλεγξε μόνος σου · εμπιστοσύνη λύτη: χαμηλή
Λύση 1: Έστω Γ συνεκτικό με \(n\ge3\) κορυφές και \(n\) ακμές. Έστω ότι είναι άκυκλο. Τότε συνεκτικό και άκυκλο σημαίνει δέντρο, και κάθε δέντρο με \(n\) κορυφές έχει \(n-1\) ακμές — αντίφαση. Άρα έχει κύκλο. (Εναλλακτικά: ένα δέντρο επικάλυψης έχει \(n-1\) ακμές· η επιπλέον ακμή είναι χορδή που δημιουργεί κύκλο.)
Λύση 2: Έστω \(\Gamma = (V, E)\) ένα συνεκτικό μη-κατευθυνόμενο γράφημα με \(|V| = n\) και \(|E| = n\) (\(n \ge 3\)).
Από τη βασική θεωρία γραφημάτων, ένα γράφημα είναι δέντρο αν και μόνο αν είναι συνεκτικό και άκυκλο. Επιπλέον, κάθε δέντρο με \(n\) κορυφές έχει ακριβώς \(n - 1\) ακμές.
Επειδή το \(\Gamma\) είναι συνεκτικό και έχει \(|E| = n > n - 1\) ακμές, δεν μπορεί να είναι άκυκλο (δεν είναι δέντρο). Επομένως, το \(\Gamma\) περιέχει τουλάχιστον έναν κύκλο.
(Ισοδύναμα: Κάθε δέντρο επικάλυψης \(T\) του \(\Gamma\) έχει \(n-1\) ακμές. Εφόσον \(|E| = n\), υπάρχει μία ακμή \(e \in E \setminus E(T)\). Η προσθήκη της ακμής \(e\) στο δέντρο \(T\) δημιουργεί έναν στοιχειώδη κύκλο.)
Λύση 3 (τρίτη γνώμη): Έστω ένα γράφημα \(\Gamma\) το οποίο δεν είναι δισυνεκτικό ως προς ακμές. Αν το \(\Gamma\) δεν είναι συνεκτικό, τότε εξ ορισμού δεν είναι ούτε δισυνεκτικό ως προς κορυφές. Αν το \(\Gamma\) είναι συνεκτικό, τότε, αφού δεν είναι δισυνεκτικό ως προς ακμές, περιέχει τουλάχιστον μία γέφυρα, έστω την ακμή \(e = (u, v)\). - Αν το \(\Gamma\) έχει μόνο 2 κορυφές, εξ ορισμού δεν είναι δισυνεκτικό ως προς κορυφές (απαιτούνται τουλάχιστον 3 κορυφές). - Αν το \(\Gamma\) έχει \(\ge 3\) κορυφές, η αφαίρεση της γέφυρας \(e\) αποσυνδέει το γράφημα σε δύο συνεκτικές συνιστώσες, έστω \(C_u\) (που περιέχει το \(u\)) και \(C_v\) (που περιέχει το \(v\)). Αφού το συνολικό πλήθος των κορυφών είναι \(\ge 3\), τουλάχιστον μία από τις δύο συνιστώσες θα έχει \(\ge 2\) κορυφές. Έστω, χωρίς βλάβη της γενικότητας, ότι η \(C_u\) έχει \(\ge 2\) κορυφές. Τότε υπάρχει μια κορυφή \(w \neq u\) στην \(C_u\). Κάθε μονοπάτι από το \(w\) προς το \(v\) στο αρχικό γράφημα \(\Gamma\) πρέπει υποχρεωτικά να περάσει από τη γέφυρα \(e\), και συνεπώς από την κορυφή \(u\). Αν αφαιρέσουμε την κορυφή \(u\) από το \(\Gamma\), δεν θα υπάρχει πλέον μονοπάτι από το \(w\) στο \(v\), άρα το γράφημα αποσυνδέεται. Επομένως, το \(u\) είναι σημείο άρθρωσης (cut-vertex). Αφού το \(\Gamma\) διαθέτει σημείο άρθρωσης, δεν είναι δισυνεκτικό ως προς κορυφές.
Θέμα 10, σετ Α¶
Αξιοπιστία: ⚠ οι ανεξάρτητες λύσεις διαφωνούν: δες όλες και έλεγξε μόνος σου · εμπιστοσύνη λύτη: χαμηλή
Λύση 1: Έστω \(C_1\ne C_2\) συνεκτικές συνιστώσες με κοινή κορυφή \(v\). Κάθε \(x\in C_1\) ενώνεται με το \(v\) με μονοπάτι, και κάθε \(y\in C_2\) το ίδιο, άρα το \(x\) ενώνεται με το \(y\) (μέσω του \(v\)). Επομένως το \(C_1\cup C_2\) είναι συνεκτικό υπογράφημα που περιέχει το \(C_1\). Από τη μεγιστότητα των συνιστωσών, \(C_1=C_1\cup C_2=C_2\), αντίφαση.
Λύση 2: Σε ένα μη-κατευθυνόμενο γράφημα \(G = (V, E)\), η συνδεσιμότητα ορίζει μια σχέση ισοδυναμίας \(\sim\) στο σύνολο των κορυφών \(V\): \(u \sim v \iff\) υπάρχει μονοπάτι που συνδέει το \(u\) με το \(v\) (με \(u \sim u\)).
Οι συνεκτικές συνιστώσες του \(G\) ορίζονται ως τα μέγιστα συνεκτικά υπογραφήματα που επάγονται από τις κλάσεις ισοδυναμίας της σχέσης \(\sim\). Επειδή οι κλάσεις ισοδυναμίας οποιασδήποτε σχέσης ισοδυναμίας αποτελούν διαμέριση (partition) του συνόλου \(V\), δύο διαφορετικές κλάσεις ισοδυναμίας είναι ξένες μεταξύ τους (\(V_1 \cap V_2 = \varnothing\)). Συνεπώς, δύο διαφορετικές συνεκτικές συνιστώσες δεν μπορούν να έχουν κοινή κορυφή.
(Με απαγωγή σε άτοπο: Έστω ότι δύο διαφορετικές συνιστώσες \(C_1, C_2\) είχαν κοινή κορυφή \(w\). Τότε για κάθε \(u \in V(C_1)\) υπάρχει μονοπάτι \(u \leftrightsquigarrow w\) και για κάθε \(v \in V(C_2)\) υπάρχει μονοπάτι \(w \leftrightsquigarrow v\). Ενώνοντας τα δύο μονοπάτια, υπάρχει μονοπάτι \(u \leftrightsquigarrow v\). Άρα το \(C_1 \cup C_2\) θα ήταν συνεκτικό υπογράφημα, άτοπο καθώς τα \(C_1, C_2\) είναι μέγιστα συνεκτικά και \(C_1 \neq C_2\).)
Λύση 3 (τρίτη γνώμη): Έστω \(G = (V, E)\) ένα ισχυρά συνεκτικό κατευθυνόμενο γράφημα και έστω μια τυχαία κατευθυνόμενη ακμή του \(e = (u, v) \in E\). Εξ ορισμού, σε ένα ισχυρά συνεκτικό γράφημα υπάρχει κατευθυνόμενο μονοπάτι από κάθε κορυφή προς κάθε άλλη κορυφή. Επομένως, υπάρχει ένα κατευθυνόμενο μονοπάτι \(P\) από την κορυφή \(v\) προς την κορυφή \(u\). Μπορούμε να επιλέξουμε το \(P\) να είναι στοιχειώδες μονοπάτι (simple path), οπότε δεν θα περιέχει την ακμή \((u, v)\) (αφού ξεκινάει από το \(v\) και καταλήγει στο \(u\) χωρίς να επαναλαμβάνει κορυφές). Αν ακολουθήσουμε την ακμή \(e = (u, v)\) και στη συνέχεια το μονοπάτι \(P\) από το \(v\) στο \(u\), σχηματίζεται ένας κλειστός περίπατος που δεν επαναλαμβάνει κορυφές, δηλαδή ένας κατευθυνόμενος κύκλος. Άρα, κάθε ακμή \(e\) του \(G\) περιέχεται σε τουλάχιστον έναν κατευθυνόμενο κύκλο.
Θέμα 1, σετ Β¶
Αξιοπιστία: ⚠ οι ανεξάρτητες λύσεις διαφωνούν: δες όλες και έλεγξε μόνος σου · εμπιστοσύνη λύτη: χαμηλή
Λύση 1: Η \(\oplus\) είναι αντιμεταθετική και προσεταιριστική. Κάθε σύνολο εμφανίζεται δύο φορές: \(A\) στους \((A\oplus B)\), \((C\oplus A)\), \(B\) στους \((A\oplus B)\), \((B\oplus C)\), \(C\) στους \((B\oplus C)\), \((C\oplus A)\). Άρα το αποτέλεσμα είναι \((A\oplus A)\oplus(B\oplus B)\oplus(C\oplus C)=\varnothing\). (Ισοδύναμα: στοιχείο \(x\) ανήκει σε άρτιο πλήθος από τα τρία σύνολα \(A\oplus B\) κλπ.)
Λύση 2: Η πράξη της συμμετρικής διαφοράς \(\oplus\) είναι προσεταιριστική και αντιμεταθετική. Επίσης, για κάθε σύνολο \(X\) ισχύει \(X \oplus X = \varnothing\) και \(X \oplus \varnothing = X\).
Παίρνοντας τη συμμετρική διαφορά με το σύνολο \(A\) και στα δύο μέλη της ισότητας \(A \oplus B \oplus C = D\): $\((A \oplus B \oplus C) \oplus A = D \oplus A\)$ Λόγω της αντιμεταθετικότητας και της προσεταιριστικότητας: $\((A \oplus A) \oplus (B \oplus C) = D \oplus A\)$ $\(\varnothing \oplus (B \oplus C) = D \oplus A\)$ $\(B \oplus C = D \oplus A\)$
Λύση 3 (τρίτη γνώμη): Η πράξη της συμμετρικής διαφοράς \(\oplus\) μεταξύ συνόλων έχει την ιδιότητα της προσεταιριστικότητας και της αντιμεταθετικότητας. Επίσης, για οποιοδήποτε σύνολο \(X\) ισχύει \(X \oplus X = \varnothing\) και \(X \oplus \varnothing = X\). Χρησιμοποιώντας αυτές τις ιδιότητες, μπορούμε να αναδιατάξουμε τους όρους ως εξής: \((A \oplus B) \oplus (B \oplus C) \oplus (C \oplus A) = (A \oplus A) \oplus (B \oplus B) \oplus (C \oplus C) = \varnothing \oplus \varnothing \oplus \varnothing = \varnothing\).
Θέμα 2, σετ Β¶
Αξιοπιστία: ⚠ οι ανεξάρτητες λύσεις διαφωνούν: δες όλες και έλεγξε μόνος σου · εμπιστοσύνη λύτη: χαμηλή
Λύση 1: Δύο τρίγωνα που μοιράζονται μία κορυφή (bowtie): \(\{a,b,c\}\) και \(\{c,d,e\}\). Δεν έχει γέφυρες (κάθε ακμή είναι σε τρίγωνο), άρα είναι δισυνεκτικό ως προς ακμές. Η \(c\) είναι κομβικό σημείο και οι δισυνεκτικές συνιστώσες ως προς κορυφές είναι ακριβώς τα δύο τρίγωνα.
Απάντηση: το bowtie (5 κορυφές, 6 ακμές).
Λύση 2: Μια δισυνεκτική συνιστώσα ως προς ακμές (2-edge-connected component) είναι ένα μέγιστο υπογράφημα χωρίς γέφυρες. Κάθε ακμή-γέφυρα χωρίζει το γράφημα σε διαφορετικές δισυνεκτικές συνιστώσες ως προς ακμές, ενώ μια μεμονωμένη κορυφή (ή κορυφές που συνδέονται μόνο μέσω γεφυρών) συνιστά τετριμμένη δισυνεκτική συνιστώσα (\(K_1\)).
Έστω το απλό μονοπάτι \(\Gamma = P_6\) με κορυφές \(V = \{v_1, v_2, v_3, v_4, v_5, v_6\}\) και ακμές: $\(E = \{\{v_1, v_2\}, \{v_2, v_3\}, \{v_3, v_4\}, \{v_4, v_5\}, \{v_5, v_6\}\}\)$ Το \(\Gamma\) είναι συνεκτικό με 6 κορυφές. Όλες οι 5 ακμές του είναι γέφυρες (bridges). Συνεπώς, οι δισυνεκτικές συνιστώσες ως προς ακμές είναι οι 6 μεμονωμένες κορυφές \(\{v_1\}, \{v_2\}, \{v_3\}, \{v_4\}, \{v_5\}, \{v_6\}\), δηλαδή 6 συνιστώσες, και ισχύει \(6 > 3\).
(Αντίστοιχα, αν θεωρηθεί ένα τρίγωνο \(v_1-v_2-v_3-v_1\) ενωμένο με ένα μονοπάτι \(v_3-v_4-v_5-v_6\), οι δισυνεκτικές συνιστώσες ως προς ακμές είναι 4: το τρίγωνο \(\{v_1, v_2, v_3\}\) και οι κορυφές \(\{v_4\}, \{v_5\}, \{v_6\}\), όπου πάλι \(4 > 3\).)
Λύση 3 (τρίτη γνώμη): Ένα γράφημα είναι δισυνεκτικό ως προς ακμές αν είναι συνεκτικό και δεν έχει γέφυρες (κάθε ακμή του ανήκει σε κάποιο κύκλο). Για να έχει ακριβώς δύο δισυνεκτικές συνιστώσες ως προς κορυφές (blocks), πρέπει να διαθέτει ακριβώς ένα σημείο άρθρωσης (cut-vertex) που να ενώνει αυτά τα δύο blocks. Ένα τέτοιο γράφημα \(\Gamma\) είναι το γράφημα "πεταλούδα" (butterfly graph), το οποίο αποτελείται από δύο τρίγωνα που μοιράζονται ακριβώς μία κοινή κορυφή. Συγκεκριμένα: - Σύνολο κορυφών: \(V = \{1, 2, 3, 4, 5\}\) - Σύνολο ακμών: \(E = \{(1,2), (2,3), (3,1), (3,4), (4,5), (5,3)\}\) Το γράφημα αυτό δεν έχει γέφυρες (άρα είναι δισυνεκτικό ως προς ακμές) και η κορυφή 3 είναι το μοναδικό σημείο άρθρωσης, χωρίζοντας το γράφημα σε ακριβώς δύο δισυνεκτικές συνιστώσες ως προς κορυφές (τα τρίγωνα \(\{1,2,3\}\) και \(\{3,4,5\}\)).
Θέμα 3, σετ Β¶
Αξιοπιστία: ⚠ οι ανεξάρτητες λύσεις διαφωνούν: δες όλες και έλεγξε μόνος σου · εμπιστοσύνη λύτη: χαμηλή
Λύση 1: \(P=\{(0,0),(2,0),(0,2)\}\). - (α) Συμμετρική: το \((2,0)\) έχει αντίστροφο \((0,2)\in P\) και το \((0,0)\) το ίδιο του. - (β) Όχι μεταβατική: \((2,0)\in P\), \((0,2)\in P\) αλλά \((2,2)\notin P\).
Λύση 2: \(\alpha)\) Συμμετρική: Ναι. Μια σχέση \(P\) είναι συμμετρική αν για κάθε \((x, y) \in P\) ισχύει \((y, x) \in P\). Εδώ όλα τα στοιχεία της σχέσης είναι της μορφής \((x, x)\) [συγκεκριμένα \((0,0), (2,2), (4,4)\)], επομένως για κάθε \((x, y) \in P\) ισχύει \(x = y\), άρα και \((y, x) = (x, y) \in P\).
\(\beta)\) Μεταβατική: Ναι. Μια σχέση \(P\) είναι μεταβατική αν \((x, y) \in P\) και \((y, z) \in P \implies (x, z) \in P\). Επειδή όλα τα ζεύγη έχουν ίσα στοιχεία, η συνθήκη \((x, y) \in P\) και \((y, z) \in P\) ικανοποιείται μόνο όταν \(x = y = z\), απ' όπου έπεται άμεσα ότι \((x, z) = (x, y) \in P\).
Λύση 3 (τρίτη γνώμη): \(\alpha\) Η σχέση \(P\) είναι συμμετρική αν για κάθε \((x, y) \in P\) ισχύει και \((y, x) \in P\). Ελέγχουμε τα στοιχεία της \(P\): - Για το \((0, 0) \in P\), ισχύει \((0, 0) \in P\). - Για το \((2, 0) \in P\), ισχύει \((0, 2) \in P\). - Για το \((0, 2) \in P\), ισχύει \((2, 0) \in P\). Εφόσον ικανοποιείται η συνθήκη για όλα τα ζεύγη, η σχέση \(P\) είναι συμμετρική.
\(\beta\) Η σχέση \(P\) είναι μεταβατική αν για κάθε \((x, y) \in P\) και \((y, z) \in P\) συνεπάγεται ότι \((x, z) \in P\). Παρατηρούμε ότι \((2, 0) \in P\) και \((0, 2) \in P\). Για να είναι η σχέση μεταβατική, θα έπρεπε υποχρεωτικά να ισχύει και \((2, 2) \in P\). Επειδή το \((2, 2) \notin P\), η σχέση \(P\) δεν είναι μεταβατική.
Θέμα 8, σετ Β¶
Αξιοπιστία: ⚠ οι ανεξάρτητες λύσεις διαφωνούν: δες όλες και έλεγξε μόνος σου · εμπιστοσύνη λύτη: χαμηλή
Λύση 1: Ισοδύναμο: δισυνεκτικό ως προς κορυφές ⇒ δισυνεκτικό ως προς ακμές. Χρησιμοποιούμε ότι το δισυνεκτικό ως προς κορυφές γράφημα είναι συνεκτικό και έχει \(n\ge3\) κορυφές. Έστω ότι έχει γέφυρα \(e=\{u,v\}\). Αφαιρώντας την \(e\), το γράφημα χωρίζεται στις συνιστώσες \(C_u\ni u\) και \(C_v\ni v\). Επειδή \(n\ge3\), μία από αυτές, έστω η \(C_u\), έχει και άλλη κορυφή \(x\ne u\). Κάθε μονοπάτι από το \(x\) στο \(v\) πρέπει να χρησιμοποιήσει την \(e\), άρα να περάσει από το \(u\). Στο \(\Gamma-u\) το \(x\) και το \(v\) δεν συνδέονται, δηλ. το \(u\) είναι κομβικό σημείο — αντίφαση.
Σημείωση: χρειάζεται \(n\ge3\) (το \(K_2\) έχει γέφυρα αλλά όχι κομβικό σημείο)· εξαρτάται από τον ορισμό των σημειώσεων.
Λύση 2: Έστω \(\Gamma = (V, E)\) ένα συνεκτικό μη-κατευθυνόμενο γράφημα με \(|V| = n\) και \(|E| = n\) (\(n \ge 3\)).
Από τη βασική θεωρία γραφημάτων, ένα γράφημα είναι δέντρο αν και μόνο αν είναι συνεκτικό και άκυκλο. Επιπλέον, κάθε δέντρο με \(n\) κορυφές έχει ακριβώς \(n - 1\) ακμές.
Επειδή το \(\Gamma\) είναι συνεκτικό και έχει \(|E| = n > n - 1\) ακμές, δεν μπορεί να είναι άκυκλο (δεν είναι δέντρο). Επομένως, το \(\Gamma\) περιέχει τουλάχιστον έναν κύκλο.
(Ισοδύναμα: Κάθε δέντρο επικάλυψης \(T\) του \(\Gamma\) έχει \(n-1\) ακμές. Εφόσον \(|E| = n\), υπάρχει μία ακμή \(e \in E \setminus E(T)\). Η προσθήκη της ακμής \(e\) στο δέντρο \(T\) δημιουργεί έναν στοιχειώδη κύκλο.)
Λύση 3 (τρίτη γνώμη): Έστω ένα γράφημα \(\Gamma\) το οποίο δεν είναι δισυνεκτικό ως προς ακμές. Αν το \(\Gamma\) δεν είναι συνεκτικό, τότε εξ ορισμού δεν είναι ούτε δισυνεκτικό ως προς κορυφές. Αν το \(\Gamma\) είναι συνεκτικό, τότε, αφού δεν είναι δισυνεκτικό ως προς ακμές, περιέχει τουλάχιστον μία γέφυρα, έστω την ακμή \(e = (u, v)\). - Αν το \(\Gamma\) έχει μόνο 2 κορυφές, εξ ορισμού δεν είναι δισυνεκτικό ως προς κορυφές (απαιτούνται τουλάχιστον 3 κορυφές). - Αν το \(\Gamma\) έχει \(\ge 3\) κορυφές, η αφαίρεση της γέφυρας \(e\) αποσυνδέει το γράφημα σε δύο συνεκτικές συνιστώσες, έστω \(C_u\) (που περιέχει το \(u\)) και \(C_v\) (που περιέχει το \(v\)). Αφού το συνολικό πλήθος των κορυφών είναι \(\ge 3\), τουλάχιστον μία από τις δύο συνιστώσες θα έχει \(\ge 2\) κορυφές. Έστω, χωρίς βλάβη της γενικότητας, ότι η \(C_u\) έχει \(\ge 2\) κορυφές. Τότε υπάρχει μια κορυφή \(w \neq u\) στην \(C_u\). Κάθε μονοπάτι από το \(w\) προς το \(v\) στο αρχικό γράφημα \(\Gamma\) πρέπει υποχρεωτικά να περάσει από τη γέφυρα \(e\), και συνεπώς από την κορυφή \(u\). Αν αφαιρέσουμε την κορυφή \(u\) από το \(\Gamma\), δεν θα υπάρχει πλέον μονοπάτι από το \(w\) στο \(v\), άρα το γράφημα αποσυνδέεται. Επομένως, το \(u\) είναι σημείο άρθρωσης (cut-vertex). Αφού το \(\Gamma\) διαθέτει σημείο άρθρωσης, δεν είναι δισυνεκτικό ως προς κορυφές.
Θέμα 10, σετ Β¶
Αξιοπιστία: ⚠ οι ανεξάρτητες λύσεις διαφωνούν: δες όλες και έλεγξε μόνος σου · εμπιστοσύνη λύτη: χαμηλή
Λύση 1: Έστω ισχυρά συνεκτικό G και ακμή \(u\to v\). Αν \(u=v\) (βρόχος), είναι ήδη κύκλος. Αλλιώς, από την ισχυρή συνεκτικότητα υπάρχει κατευθυνόμενο μονοπάτι από το \(v\) στο \(u\) (παίρνουμε το συντομότερο, ώστε να μην επαναλαμβάνει κορυφές). Μαζί με την \(u\to v\) σχηματίζει κατευθυνόμενο κύκλο που περιέχει την ακμή.
Λύση 2: Σε ένα μη-κατευθυνόμενο γράφημα \(G = (V, E)\), η συνδεσιμότητα ορίζει μια σχέση ισοδυναμίας \(\sim\) στο σύνολο των κορυφών \(V\): \(u \sim v \iff\) υπάρχει μονοπάτι που συνδέει το \(u\) με το \(v\) (με \(u \sim u\)).
Οι συνεκτικές συνιστώσες του \(G\) ορίζονται ως τα μέγιστα συνεκτικά υπογραφήματα που επάγονται από τις κλάσεις ισοδυναμίας της σχέσης \(\sim\). Επειδή οι κλάσεις ισοδυναμίας οποιασδήποτε σχέσης ισοδυναμίας αποτελούν διαμέριση (partition) του συνόλου \(V\), δύο διαφορετικές κλάσεις ισοδυναμίας είναι ξένες μεταξύ τους (\(V_1 \cap V_2 = \varnothing\)). Συνεπώς, δύο διαφορετικές συνεκτικές συνιστώσες δεν μπορούν να έχουν κοινή κορυφή.
(Με απαγωγή σε άτοπο: Έστω ότι δύο διαφορετικές συνιστώσες \(C_1, C_2\) είχαν κοινή κορυφή \(w\). Τότε για κάθε \(u \in V(C_1)\) υπάρχει μονοπάτι \(u \leftrightsquigarrow w\) και για κάθε \(v \in V(C_2)\) υπάρχει μονοπάτι \(w \leftrightsquigarrow v\). Ενώνοντας τα δύο μονοπάτια, υπάρχει μονοπάτι \(u \leftrightsquigarrow v\). Άρα το \(C_1 \cup C_2\) θα ήταν συνεκτικό υπογράφημα, άτοπο καθώς τα \(C_1, C_2\) είναι μέγιστα συνεκτικά και \(C_1 \neq C_2\).)
Λύση 3 (τρίτη γνώμη): Έστω \(G = (V, E)\) ένα ισχυρά συνεκτικό κατευθυνόμενο γράφημα και έστω μια τυχαία κατευθυνόμενη ακμή του \(e = (u, v) \in E\). Εξ ορισμού, σε ένα ισχυρά συνεκτικό γράφημα υπάρχει κατευθυνόμενο μονοπάτι από κάθε κορυφή προς κάθε άλλη κορυφή. Επομένως, υπάρχει ένα κατευθυνόμενο μονοπάτι \(P\) από την κορυφή \(v\) προς την κορυφή \(u\). Μπορούμε να επιλέξουμε το \(P\) να είναι στοιχειώδες μονοπάτι (simple path), οπότε δεν θα περιέχει την ακμή \((u, v)\) (αφού ξεκινάει από το \(v\) και καταλήγει στο \(u\) χωρίς να επαναλαμβάνει κορυφές). Αν ακολουθήσουμε την ακμή \(e = (u, v)\) και στη συνέχεια το μονοπάτι \(P\) από το \(v\) στο \(u\), σχηματίζεται ένας κλειστός περίπατος που δεν επαναλαμβάνει κορυφές, δηλαδή ένας κατευθυνόμενος κύκλος. Άρα, κάθε ακμή \(e\) του \(G\) περιέχεται σε τουλάχιστον έναν κατευθυνόμενο κύκλο.
Θέματα που δεν λύθηκαν (και στα δύο σετ)¶
Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη
Θέμα 4¶
Αξιοπιστία: λύθηκε με βάση τις φωτογραφίες του θέματος· μία λύση AI
Στο Σετ Α (2024.jpg), το κατευθυνόμενο γράφημα \(G_1\) έχει κορυφές \(V = \{1, 2, 3, 4\}\) και κατευθυνόμενες ακμές: \((2, 1)\), \((1, 4)\), \((2, 4)\) (καμπύλη με βέλος προς το 4), \((4, 2)\) (κατακόρυφη με βέλος προς το 2), \((4, 3)\), \((3, 2)\).
\(\alpha)\) Κλειστή διαδρομή που να μην είναι κλειστό ίχνος: Μία κλειστή διαδρομή που επαναλαμβάνει ακμή: \((2, 1, 4, 2, 1, 4, 2)\), δηλαδή με ακμές \(((2,1), (1,4), (4,2), (2,1), (1,4), (4,2))\). Η ακμή \((2, 1)\) επαναλαμβάνεται, άρα είναι κλειστή διαδρομή αλλά όχι ίχνος.
\(\beta)\) Κλειστό ίχνος που να μην είναι κύκλος: Μία κλειστή διαδρομή με διακριτές ακμές αλλά με επανάληψη κορυφής: Θεωρούμε τους δύο ξένους ως προς τις ακμές κύκλους \(C_1: 2 \to 1 \to 4 \to 2\) (ακμές \((2,1), (1,4), (4,2)\)) και \(C_2: 2 \to 4 \to 3 \to 2\) (ακμές \((2,4), (4,3), (3,2)\)). Συνθέτοντάς τους παίρνουμε την κλειστή διαδρομή: \((2, 1, 4, 2, 4, 3, 2)\) με ακολουθία ακμών: \(((2, 1), (1, 4), (4, 2), (2, 4), (4, 3), (3, 2))\). Και οι 6 ακμές είναι διακριτές (σημειώνεται ότι η \((4,2)\) και η \((2,4)\) είναι δύο αντίθετες κατευθυνόμενες ακμές), συνεπώς πρόκειται για ίχνος. Επειδή οι κορυφές 2 και 4 επαναλαμβάνονται, δεν είναι κύκλος.
(Στο Σετ Β, με ακμές \((1,2), (1,4), (4,2), (4,3), (3,2), (2,3)\): για το \(\alpha\) αρκεί η \((2, 3, 2, 3, 2)\) που επαναλαμβάνει την ακμή \((2,3)\), ενώ για το \(\beta\) η ένωση των κύκλων \(2 \to 3 \to 2\) και \(2 \to 4 \to 3 \to 2\) δίνει κλειστό ίχνος χωρίς επανάληψη ακμών).
Θέμα 5¶
Αξιοπιστία: λύθηκε με βάση τις φωτογραφίες του θέματος· μία λύση AI
Στο κατευθυνόμενο γράφημα \(G_1\):
Σετ Α (2024.jpg): Υπάρχει ο κατευθυνόμενος κύκλος που διέρχεται από όλες τις κορυφές: \(1 \to 4 \to 3 \to 2 \to 1\) (μέσω των ακμών \((1,4), (4,3), (3,2), (2,1)\)). Συνεπώς, κάθε κορυφή είναι προσβάσιμη από κάθε άλλη κορυφή μέσω κατευθυνόμενου μονοπατιού. Άρα το \(G_1\) είναι ισχυρά συνεκτικό και έχει ακριβώς μία ισχυρά συνεκτική συνιστώσα, με σύνολο κορυφών \(\{1, 2, 3, 4\}\).
Σετ Β (IMG_20250117_173405.jpg): Αν οι ακμές από την κορυφή 1 είναι \((1,2)\) και \((1,4)\) με μηδενικό εσωτερικό βαθμό εισόδου (\(d^-(1)=0\)), η κορυφή 1 δεν είναι προσβάσιμη από καμία άλλη κορυφή. Τότε οι ισχυρά συνεκτικές συνιστώσες είναι: - \(\{1\}\) (τετριμμένη) - \(\{2, 3, 4\}\) (καθώς \(2 \to 3 \to 2\) και \(4 \to 3 \to 2 \to 4\), άρα οι 2, 3, 4 είναι αμοιβαία προσβάσιμες).
Θέμα 6¶
Αξιοπιστία: λύθηκε με βάση τις φωτογραφίες του θέματος· μία λύση AI
Σετ Α (2024.jpg): Το \(G_2\) έχει \(n=6\) κορυφές \(\{a, b, c, d, e, f\}\) και \(m=7\) ακμές. Το δέντρο επικάλυψης \(T\) (έντονες ακμές) αποτελείται από τις \(n-1=5\) ακμές: \(E(T) = \{\{a, b\}, \{b, c\}, \{c, e\}, \{d, e\}, \{c, f\}\}\). Οι χορδές (ακμές εκτός \(T\)) είναι οι δύο λεπτές ακμές: \(\{a, d\}\) και \(\{b, d\}\).
\(\alpha)\) Στοιχειώδεις κύκλοι ως προς το \(T\): Κάθε χορδή \(e \notin T\) ορίζει μοναδικό στοιχειώδη κύκλο μαζί με το μονοπάτι του \(T\) που συνδέει τα άκρα της: 1. Χορδή \(\{b, d\}\): Το μονοπάτι στο \(T\) ανάμεσα στα \(b\) και \(d\) είναι \(b - c - e - d\). Ο στοιχειώδης κύκλος είναι: \((b, c, e, d, b)\) (μήκους 4). 2. Χορδή \(\{a, d\}\): Το μονοπάτι στο \(T\) ανάμεσα στα \(a\) και \(d\) είναι \(a - b - c - e - d\). Ο στοιχειώδης κύκλος είναι: \((a, b, c, e, d, a)\) (μήκους 5).
\(\beta)\) Ακόμη δύο δέντρα επικάλυψης: Προσθέτοντας μία χορδή και αφαιρώντας μία ακμή του αντίστοιχου στοιχειώδους κύκλου: 1. \(T_1 = (V, (E(T) \setminus \{\{b, c\}\}) \cup \{\{b, d\}\})\) με ακμές: \(\{\{a, b\}, \{b, d\}, \{d, e\}, \{c, e\}, \{c, f\}\}\). 2. \(T_2 = (V, (E(T) \setminus \{\{a, b\}\}) \cup \{\{a, d\}\})\) με ακμές: \(\{\{a, d\}, \{d, e\}, \{c, e\}, \{b, c\}, \{c, f\}\}\).
(Στο Σετ Β, όπου \(V=\{a, b, c, d, e\}\), \(E(T)=\{\{a,b\}, \{b,d\}, \{d,e\}, \{e,c\}\}\) και χορδές \(\{a,d\}, \{b,e\}\), το υποερώτημα \(\alpha\) ζητά τους κύκλους που δεν είναι στοιχειώδεις: αυτός είναι ο κύκλος \((a, b, e, d, a)\), που προκύπτει ως συμμετρική διαφορά των δύο στοιχειωδών κύκλων \((a, b, d, a)\) και \((b, d, e, b)\) και περιέχει και τις δύο χορδές).
Θέμα 7¶
Αξιοπιστία: λύθηκε με βάση τις φωτογραφίες του θέματος· μία λύση AI
Ένα μονοπάτι \(P = (u, \dots, v)\) είναι μη-επεκτάσιμο αν και μόνο αν \(N(u) \subseteq V(P)\) και \(N(v) \subseteq V(P)\) (όλοι οι γείτονες των άκρων του ανήκουν ήδη στο μονοπάτι).
Σετ Α (2024.jpg): - Μη-επεκτάσιμο μονοπάτι με άκρο το \(c\): Δεν υπάρχει. Αιτιολόγηση: Οι γείτονες του \(c\) είναι οι \(\{b, e, f\}\). Η κορυφή \(f\) έχει βαθμό 1 (\(N(f) = \{c\}\)), άρα σε οποιοδήποτε μονοπάτι την περιέχει πρέπει υποχρεωτικά να είναι ακραία κορυφή. Αν ένα μονοπάτι είχε άκρο το \(c\) και δεν περιείχε το \(f\), θα μπορούσε να επεκταθεί κατά την ακμή \(\{c, f\}\). Αν περιείχε το \(f\), επειδή \(f\) και \(c\) συνδέονται άμεσα και το \(f\) έχει βαθμό 1, το μονοπάτι θα έπρεπε να είναι το τετριμμένο \((f, c)\) μήκους 1. Όμως το \((f, c)\) επεκτείνεται προς το \(b\) ή το \(e\), άρα δεν είναι μη-επεκτάσιμο. Συνεπώς κανένα μη-επεκτάσιμο μονοπάτι δεν μπορεί να έχει άκρο το \(c\) (επαληθεύοντας τη ρητή επισήμανση της εκφώνησης: «Σε ερωτήματα που ζητείται να βρεθούν ορισμένα στοιχεία, ενδέχεται να μην υπάρχουν»). - Μη-επεκτάσιμο μονοπάτι που να μην έχει άκρο το \(c\): Το μονοπάτι Hamilton \((a, d, e, b, c, f)\) διέρχεται από όλες τις κορυφές του γραφήματος. Επειδή \(V(P) = V(G_2)\), κανένα από τα άκρα του (\(a\) και \(f\)) δεν μπορεί να επεκταθεί, και κανένα άκρο δεν είναι το \(c\).
Σετ Β (IMG_20250117_173405.jpg): Στο Σετ Β ζητείται: μη-επεκτάσιμο μονοπάτι με άκρο το \(d\), και μη-επεκτάσιμο μονοπάτι με άκρο το \(e\). - Με άκρο το \(d\): Το μονοπάτι Hamilton \((c, e, b, a, d)\) περιέχει όλες τις 5 κορυφές \(\{a, b, c, d, e\}\), άρα είναι μη-επεκτάσιμο με άκρα τα \(c\) και \(d\). - Με άκρο το \(e\): Δεν υπάρχει, διότι η κορυφή \(c\) είναι εκκρεμής συνδεδεμένη μόνο με το \(e\) (\(N(c)=\{e\}\)), οπότε για τον ίδιο λόγο κάθε μονοπάτι με άκρο το \(e\) είτε επεκτείνεται προς το \(c\) είτε είναι το \((c, e)\) που επεκτείνεται προς τα \(b, d\).
Θέμα 9¶
Αξιοπιστία: λύθηκε με βάση τις φωτογραφίες του θέματος· μία λύση AI
Ένα υπογράφημα είναι δισυνεκτικό ως προς κορυφές αν είναι συνεκτικό, έχει τουλάχιστον 3 κορυφές (ή μία ακμή \(K_2\) κατά ορισμένες συμβάσεις) και δεν έχει κομβικά σημεία (ισοδύναμα: αποτελείται από έναν κύκλο ή ένωση κύκλων με κοινές κορυφές). Μία δισυνεκτική συνιστώσα ως προς κορυφές είναι ένα μεγιστοτικό δισυνεκτικό υπογράφημα.
Σετ Α (2024.jpg): Ζητείται υπογράφημα που να περιέχει τις κορυφές \(b\) και \(d\) (ή \(b\) και \(c\)), να είναι δισυνεκτικό ως προς κορυφές αλλά να μην είναι δισυνεκτική συνιστώσα: Η δισυνεκτική συνιστώσα του \(G_2\) που περιέχει την κορυφή \(b\) είναι το επαγόμενο υπογράφημα στις κορυφές \(\{a, b, c, d, e\}\) (μεγιστοτικό block). Οποιοσδήποτε απλός κύκλος περιέχεται μέσα σε αυτό το block είναι δισυνεκτικό υπογράφημα, αλλά όχι δισυνεκτική συνιστώσα: - Υπογράφημα: Ο κύκλος \(C = (b, c, e, d, b)\) με κορυφές \(\{b, c, d, e\}\) και ακμές \(\{\{b,c\}, \{c,e\}, \{d,e\}, \{b,d\}\}\). Είναι δισυνεκτικό ως προς κορυφές (απλός κύκλος χωρίς κομβικά σημεία), περιέχει τις κορυφές \(b\) και \(d\), αλλά δεν είναι δισυνεκτική συνιστώσα αφού επεκτείνεται γνήσια με την προσθήκη της κορυφής \(a\) και των ακμών \(\{a,b\}, \{a,d\}\). - Εναλλακτικά, το τρίγωνο με κορυφές \(\{a, b, d\}\) και ακμές \(\{\{a,b\}, \{b,d\}, \{a,d\}\}\) περιέχει τις \(b, d\) και είναι δισυνεκτικό αλλά μη μεγιστοτικό.
Σετ Β (IMG_20250117_173405.jpg): Ζητείται υπογράφημα με δύο τουλάχιστον κορυφές, δισυνεκτικό αλλά όχι δισυνεκτική συνιστώσα: Το τρίγωνο \(\{a, b, d\}\) με ακμές \(\{\{a, b\}, \{a, d\}, \{b, d\}\}\) (ή το τρίγωνο \(\{b, d, e\}\) με ακμές \(\{\{b, d\}, \{d, e\}, \{b, e\}\}\)). Είναι δισυνεκτικό ως κύκλος \(C_3\), αλλά δεν είναι δισυνεκτική συνιστώσα διότι περιέχεται γνήσια στο block \(\{a, b, d, e\}\).