Θεωρία Γραφημάτων και Εφαρμογές — Ιούλιος 2024 — παραλλαγή¶
Μεταγραφή από τη φωτογραφία IMG_7349.jpg.
IMG_7349.jpg¶
[Λείπει από τη φωτογραφία: επικεφαλίδα και οδηγίες σελίδας]
1 Στο κατευθυνόμενο γράφημα G1: βρείτε ένα υπογράφημα που να είναι ισχυρά συνεκτικό, αλλά να μήν είναι ισχυρά συνεκτική συνιστώσα. 1,5 μονάδα
[Σχήμα: Κατευθυνόμενο γράφημα G1 με κορυφές 0, 1, 2, 3] [Σχήμα: Μη-κατευθυνόμενο γράφημα G2 με κορυφές a, b, c, d, e]
2 Στο μη-κατευθυνόμενο γράφημα G2 βρείτε όλα τα δέντρα επικάλυψης. 1,5 μονάδα
3 Στο μη-κατευθυνόμενο γράφημα G2 βρείτε όλα τα μη-επεκτάσιμα μονοπάτια με άκρο την κορυφή b. 1,5 μονάδα
4 Βρείτε μία παράσταση που να είναι ίση με την \(B \oplus (A \oplus \Gamma) \oplus (B \oplus A)\) , και όπου κάθε ένα από τα σύνολα A, B, \(\Gamma\) να εμφανίζεται το πολύ μία φορά. 1 μονάδα
5 Στο μη-κατευθυνόμενο γράφημα G3 βρείτε τις δισυνεκτικές συνιστώσες ως προς κορυφές που δεν περιέχουν την κορυφή a. 1,5 μονάδα
[Σχήμα: Μη-κατευθυνόμενο γράφημα G3 με κορυφές a, b, c, d, e, f]
6 Έστω ότι το \(\Gamma\) είναι συνεκτικό, έχει \(n \ge 3\) κορυφές, και έχει n ακμές. Αποδείξτε ότι το \(\Gamma\) θα έχει κύκλο. 1,5 μονάδα
7 Για κάθε μία από τις παρακάτω υποθετικές ιδιότητες, βρείτε άν είναι σωστή ή λάθος. Οι ερωτήσεις είναι ισοβαρείς. Δεν χρειάζεται να εξηγήσετε τις απαντήσεις σας. Το \(\Gamma\) είναι πάντα ένα τυχαίο μη-κατευθυνόμενο γράφημα. 1,5 μονάδα
a Άν το \(\Gamma\) είναι δισυνεκτικό ως προς κορυφές, κάποιος κύκλος του θα περιέχει όλες τις κορυφές του. b Άν το \(\Gamma\) είναι δισυνεκτικό ως προς ακμές, κάθε ακμή του θα περιέχεται σε κάποιο κύκλο. c Άν το \(\Gamma\) έχει ακριβώς n κορυφές και m ακμές, και \(n > m+1\) , το \(\Gamma\) δεν θα είναι συνεκτικό.
Λύσεις (⚪ AI, μη επαληθευμένο)
Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (antigravity-gemini, gemini-3.7-flash, sonnet), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο
Προσοχή
Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.
AI λύσεις — 2024-07-b¶
Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.
Θέμα 1¶
Αξιοπιστία: λύθηκε με βάση τις φωτογραφίες του θέματος· μία λύση AI
Στο κατευθυνόμενο γράφημα \(G_1\), οι κορυφές είναι \(\{0, 1, 2, 3\}\). Οι κορυφές \(\{1, 2, 3\}\) σχηματίζουν έναν κατευθυνόμενο κύκλο (κύκλος \(1 \to 2 \to 3 \to 1\)), ενώ η κορυφή 0 έχει μόνο εξερχόμενη ακμή \((0, 1)\) προς τον κύκλο και καμία εισερχόμενη (\(d^-(0)=0\)).
Επομένως, η μεγιστοτική ισχυρά συνεκτική συνιστώσα που περιέχει τις κορυφές του κύκλου είναι το επαγόμενο υπογράφημα με σύνολο κορυφών \(C = \{1, 2, 3\}\) (καθώς όλες είναι αμοιβαία προσβάσιμες).
Ζητείται: ένα υπογράφημα που να είναι ισχυρά συνεκτικό, αλλά να μην είναι ισχυρά συνεκτική συνιστώσα. - Ένα υπογράφημα αποτελούμενο από μία μεμονωμένη κορυφή του κύκλου, π.χ. \(H = (\{1\}, \varnothing)\) (ή \(\{2\}\), ή \(\{3\}\)), είναι εξ ορισμού ισχυρά συνεκτικό (κάθε κορυφή είναι τετριμμένα προσβάσιμη από τον εαυτό της). - Δεν είναι όμως ισχυρά συνεκτική συνιστώσα, διότι δεν είναι μεγιστοτικό: περιέχεται γνήσια στην ισχυρά συνεκτική συνιστώσα \(\{1, 2, 3\}\).
Θέμα 2¶
Αξιοπιστία: λύθηκε με βάση τις φωτογραφίες του θέματος· μία λύση AI
Στο μη-κατευθυνόμενο γράφημα \(G_2\) με κορυφές \(V = \{a, b, c, d, e\}\), το γράφημα αποτελείται από δύο τρίγωνα που μοιράζονται αποκλειστικά την κορυφή \(b\) (bowtie / butterfly graph): - Τρίγωνο \(T_1\) στις κορυφές \(\{a, b, d\}\) με ακμές \(E_1 = \{\{a, b\}, \{a, d\}, \{b, d\}\}\). - Τρίγωνο \(T_2\) στις κορυφές \(\{b, c, e\}\) με ακμές \(E_2 = \{\{b, c\}, \{c, e\}, \{b, e\}\}\).
Ένα δέντρο επικάλυψης ενός γραφήματος με κομβικό σημείο \(b\) που χωρίζει το γράφημα σε δύο δισυνεκτικές συνιστώσες προκύπτει επιλέγοντας ανεξάρτητα ένα δέντρο επικάλυψης για κάθε συνιστώσα. Σε κάθε τρίγωνο (κύκλο 3 κορυφών), ένα δέντρο επικάλυψης προκύπτει αφαιρώντας ακριβώς μία ακμή (3 επιλογές από το \(T_1\) και 3 επιλογές από το \(T_2\)).
Συνεπώς υπάρχουν συνολικά \(3 \times 3 = 9\) δέντρα επικάλυψης, καθένα με 4 ακμές: 1. \(E_1 \setminus \{\{a, d\}\} \cup E_2 \setminus \{\{c, e\}\} = \{\{a, b\}, \{b, d\}, \{b, c\}, \{b, e\}\}\) (αστέρι με κέντρο το \(b\)) 2. \(E_1 \setminus \{\{a, d\}\} \cup E_2 \setminus \{\{b, e\}\} = \{\{a, b\}, \{b, d\}, \{b, c\}, \{c, e\}\}\) 3. \(E_1 \setminus \{\{a, d\}\} \cup E_2 \setminus \{\{b, c\}\} = \{\{a, b\}, \{b, d\}, \{b, e\}, \{c, e\}\}\) 4. \(E_1 \setminus \{\{b, d\}\} \cup E_2 \setminus \{\{c, e\}\} = \{\{a, b\}, \{a, d\}, \{b, c\}, \{b, e\}\}\) 5. \(E_1 \setminus \{\{b, d\}\} \cup E_2 \setminus \{\{b, e\}\} = \{\{a, b\}, \{a, d\}, \{b, c\}, \{c, e\}\}\) 6. \(E_1 \setminus \{\{b, d\}\} \cup E_2 \setminus \{\{b, c\}\} = \{\{a, b\}, \{a, d\}, \{b, e\}, \{c, e\}\}\) 7. \(E_1 \setminus \{\{a, b\}\} \cup E_2 \setminus \{\{c, e\}\} = \{\{a, d\}, \{b, d\}, \{b, c\}, \{b, e\}\}\) 8. \(E_1 \setminus \{\{a, b\}\} \cup E_2 \setminus \{\{b, e\}\} = \{\{a, d\}, \{b, d\}, \{b, c\}, \{c, e\}\}\) 9. \(E_1 \setminus \{\{a, b\}\} \cup E_2 \setminus \{\{b, c\}\} = \{\{a, d\}, \{b, d\}, \{b, e\}, \{c, e\}\}\)
Θέμα 3¶
Αξιοπιστία: λύθηκε με βάση τις φωτογραφίες του θέματος· μία λύση AI
Ένα μονοπάτι είναι μη-επεκτάσιμο αν και μόνο αν κανένα από τα άκρα του δεν μπορεί να συνδεθεί με γειτονική κορυφή που δεν ανήκει ήδη στο μονοπάτι. Ειδικότερα, αν η κορυφή \(b\) είναι άκρο του μονοπατιού, για να μην είναι επεκτάσιμο από το \(b\) πρέπει όλοι οι γείτονες του \(b\) να περιέχονται ήδη στο μονοπάτι: $\(N(b) \subseteq V(P)\)$ Στο γράφημα \(G_2\), οι γείτονες του \(b\) είναι όλες οι υπόλοιπες 4 κορυφές: \(N(b) = \{a, d, c, e\}\). Επομένως, ένα τέτοιο μονοπάτι θα έπρεπε να είναι μονοπάτι Hamilton (να περιέχει όλες τις κορυφές \(\{a, b, c, d, e\}\)) με άκρο το \(b\).
Όμως, ένα μονοπάτι δεν μπορεί να επαναλαμβάνει κορυφές. Επειδή η κορυφή \(b\) είναι το μοναδικό κοινό σημείο των δύο τριγώνων \(\{a, b, d\}\) και \(\{b, c, e\}\), οποιοδήποτε μονοπάτι ξεκινά ή καταλήγει στο \(b\) μπορεί να επισκεφθεί κορυφές μόνο από το ένα τρίγωνο (αν μεταβεί π.χ. στο \(\{a, d\}\), δεν μπορεί να μεταβεί στο \(\{c, e\}\) χωρίς να περάσει ξανά από το \(b\), πράγμα αδύνατο σε μονοπάτι). Άρα οποιοδήποτε μονοπάτι με άκρο το \(b\) περιέχει το πολύ δύο από τους τέσσερις γείτονες του \(b\). Συνεπώς, από το \(b\) μπορεί πάντα να επεκταθεί προς τις μη επισκεφθείσες κορυφές του άλλου τριγώνου.
Απάντηση: Δεν υπάρχει κανένα μη-επεκτάσιμο μονοπάτι με άκρο την κορυφή \(b\). (Η απάντηση αυτή εναρμονίζεται πλήρως με την οδηγία των εξετάσεων: «Σε ερωτήματα που ζητείται να βρεθούν ορισμένα στοιχεία, ενδέχεται να μην υπάρχουν»).
Θέμα 4¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
\(B\oplus(A\oplus\Gamma)\oplus(B\oplus A)\): τα \(B\) και \(A\) εμφανίζονται από δύο φορές και φεύγουν (\(X\oplus X=\varnothing\), η \(\oplus\) είναι αντιμεταθετική και προσεταιριστική).
Απάντηση: \(\Gamma\).
Θέμα 5¶
Αξιοπιστία: λύθηκε με βάση τις φωτογραφίες του θέματος· μία λύση AI
Στο μη-κατευθυνόμενο γράφημα \(G_3\), οι κορυφές είναι \(\{a, b, c, d, e, f\}\) και οι ακμές είναι: - \(\{\{a, b\}, \{a, d\}, \{b, d\}\}\) (τρίγωνο \(\{a, b, d\}\)) - \(\{\{b, d\}, \{b, e\}, \{d, e\}\}\) (τρίγωνο \(\{b, d, e\}\)) - \(\{b, c\}\) (ακμή προς την εκκρεμή κορυφή \(c\), βαθμού 1) - \(\{e, f\}\) (ακμή προς την εκκρεμή κορυφή \(f\), βαθμού 1)
Οι δισυνεκτικές συνιστώσες ως προς κορυφές (blocks) είναι τα μεγιστοτικά υπογραφήματα χωρίς κομβικά σημεία (κάθε απλός κύκλος ή ένωση κύκλων, καθώς και κάθε μεμονωμένη γέφυρα μαζί με τα δύο άκρα της): 1. Το υπογράφημα με κορυφές \(\{a, b, d, e\}\) και ακμές \(\{\{a, b\}, \{a, d\}, \{b, d\}, \{b, e\}, \{d, e\}\}\) (περιέχει την κορυφή \(a\)). 2. Η γέφυρα \(\{b, c\}\) με κορυφές \(\{b, c\}\) (δεν περιέχει την κορυφή \(a\)). 3. Η γέφυρα \(\{e, f\}\) με κορυφές \(\{e, f\}\) (δεν περιέχει την κορυφή \(a\)).
Απάντηση: Οι δισυνεκτικές συνιστώσες ως προς κορυφές που δεν περιέχουν την κορυφή \(a\) είναι: - Το υπογράφημα που αποτελείται από την ακμή \(\{b, c\}\) και τις κορυφές \(\{b, c\}\). - Το υπογράφημα που αποτελείται από την ακμή \(\{e, f\}\) και τις κορυφές \(\{e, f\}\).
Θέμα 6¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
Έστω Γ συνεκτικό με \(n\ge3\) κορυφές και \(n\) ακμές. Αν ήταν άκυκλο, θα ήταν δέντρο, και ένα δέντρο με \(n\) κορυφές έχει \(n-1\) ακμές — αντίφαση. Άρα έχει κύκλο. (Ισοδύναμα: ένα δέντρο επικάλυψης έχει \(n-1\) ακμές, η υπόλοιπη ακμή είναι χορδή και κλείνει κύκλο.)
Θέμα 7¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: μέτρια
- (a) Λάθος: το \(K_{2,3}\) είναι δισυνεκτικό ως προς κορυφές (5 κορυφές) αλλά δεν έχει κύκλο με 5 κορυφές (οι κύκλοι του είναι μήκους 4). Επαληθεύτηκε με πρόγραμμα.
- (b) Σωστό: δισυνεκτικό ως προς ακμές σημαίνει χωρίς γέφυρες, και ακμή που δεν είναι γέφυρα ανήκει σε κύκλο.
- (c) Σωστό: αν \(n>m+1\), δηλ. \(m<n-1\), το γράφημα έχει λιγότερες από \(n-1\) ακμές, ενώ κάθε συνεκτικό γράφημα με \(n\) κορυφές έχει \(m\ge n-1\). Άρα δεν είναι συνεκτικό.