Θεωρία Γραφημάτων και Εφαρμογές — Σεπτέμβριος 2023¶
Μεταγραφή από τη φωτογραφία 1000015148.png.
1000015148.png¶
Θεωρία Γραφημάτων & Εφαρμογές - Διακριτά Μαθ/κά ΙΙ
Σεπτέμβριος 2023
Άριστα = 15 μονάδες
Κάθε απάντηση πρέπει να εξηγείται επαρκώς με βάση τη θεωρία. Σε ερωτήματα που ζητείται να βρεθούν ορισμένα στοιχεία, ενδέχεται να μην υπάρχουν. Το Γ είναι πάντα ένα μη-κατευθυνόμενο γράφημα.
1 Αποδείξτε ότι, για οποιαδήποτε σύνολα A , B, ισχύει \(A \oplus (A \oplus B) \oplus (B \oplus A) = A\) . 1 μονάδα
2 Βρείτε ένα Γ δισυνεκτικό ως προς ακμές, που να έχει ακριβώς δύο κομβικά σημεία. 1,5 μονάδα
3 Έστω η σχέση \(P = \{ (u, v) \mid u+v \le 2 \}\) πάνω στο σύνολο των ακέραιων αριθμών. α Αποδείξτε ότι η P είναι συμμετρική. β Αποδείξτε ότι η P δεν είναι μεταβατική. 1 μονάδα
4 Στο κατευθυνόμενο γράφημα G1: α βρείτε μία κλειστή διαδρομή που να μην είναι κλειστό ίχνος. β βρείτε ένα κλειστό ίχνος που να μην είναι κύκλος. 2 μονάδες
G1 :
[Σχήμα: κατευθυνόμενο γράφημα G1 με κορυφές 0, 1, 2, 3]
G2 :
[Σχήμα: μη-κατευθυνόμενο γράφημα G2 με κορυφές a, b, c, d, e]
5 Στο κατευθυνόμενο γράφημα G1, βρείτε τις ισχυρά συνεκτικές συνιστώσες. 1,5 μονάδα
6 Στο μη-κατευθυνόμενο γράφημα G2: α βρείτε τους κύκλους που είναι στοιχειώδεις ως προς το δέντρο επικάλυψης που αποτελείται από τις έντονες ακμές. β βρείτε ακόμη δύο δέντρα επικάλυψης 2 μονάδες
7 Στο μη-κατευθυνόμενο γράφημα G2 βρείτε ένα μη-επεκτάσιμο μονοπάτι με άκρο το d, και ένα μη-επεκτάσιμο μονοπάτι που να περιέχει το b και να μην περιέχει το a. 2 μονάδες
8 Αποδείξτε ότι: Άν το Γ είναι δισυνεκτικό ως προς κορυφές, κάθε ακμή του θα περιέχεται σε κάποιο κύκλο. 1,5 μονάδα
9 Στο μη-κατευθυνόμενο γράφημα G2 βρείτε ένα υπογράφημα με δύο τουλάχιστον κορυφές, που να είναι δισυνεκτικό ως προς ακμές και να μην είναι δισυνεκτική συνιστώσα ως προς ακμές. 1,5 μονάδα
Για κάθε μία από τις παρακάτω υποθετικές ιδιότητες βρείτε άν είναι σωστή ή λάθος. Δεν χρειάζεται να εξηγήσετε τις απαντήσεις σας. 1 μονάδα
[Λείπει από τη φωτογραφία: αρχή της πρότασης] το Γ περιέχει κλειστό ίχνος, θα περιέχει και κύκλο. [Λείπει από τη φωτογραφία: αρχή της πρότασης] το Γ έχει τουλάχιστον δύο κύκλους και είναι συνεκτικό, θα έχει κομβικό σημείο.
[Λείπει από τη φωτογραφία: αρχή της γραμμής] ώστε τα στοιχεία σας και επιστρέψτε τα θέματα
Λύσεις (⚪ AI, μη επαληθευμένο)
Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (gemini-3.7-flash, sonnet), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο
Προσοχή
Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.
AI λύσεις — 2023-09¶
Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.
Θέμα 1¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
\((A\oplus B)\oplus(B\oplus A)=\varnothing\) (η \(\oplus\) είναι αντιμεταθετική και \(X\oplus X=\varnothing\)). Άρα \(A\oplus\varnothing=A\). Εναλλακτικά, ο όρος \(A\oplus(A\oplus B)=B\) και \(B\oplus(B\oplus A)=A\).
Θέμα 2¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
Τρία τρίγωνα στη σειρά: \(\{a,b,c\}\), \(\{c,d,e\}\), \(\{e,f,g\}\) (συνολικά 7 κορυφές, 9 ακμές). Κάθε ακμή ανήκει σε τρίγωνο, άρα δεν υπάρχουν γέφυρες· είναι δισυνεκτικό ως προς ακμές. Κομβικά σημεία: ακριβώς οι \(c\) και \(e\) (η αφαίρεση καθεμιάς αποσυνδέει το γράφημα· σε οποιαδήποτε άλλη κορυφή το γράφημα μένει συνεκτικό). Επαληθεύτηκε με πρόγραμμα: κομβικά {3,5} (στην αρίθμηση 1–7), γέφυρες καμία.
Απάντηση: η αλυσίδα τριών τριγώνων που μοιράζονται διαδοχικά μία κορυφή.
Θέμα 3¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
\(P=\{(u,v)\mid u+v\le2\}\). - (α) Συμμετρική: αν \(u+v\le2\) τότε \(v+u\le2\), άρα \((v,u)\in P\). - (β) Όχι μεταβατική: \((3,-1)\in P\) (άθροισμα 2), \((-1,3)\in P\) (άθροισμα 2), αλλά \((3,3)\notin P\) (6 > 2).
Θέμα 8¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: μέτρια
Έστω Γ δισυνεκτικό ως προς κορυφές (συνεκτικό, χωρίς κομβικά σημεία, \(n\ge3\)) και ακμή \(e=\{u,v\}\). Μια ακμή δεν ανήκει σε κύκλο ακριβώς όταν είναι γέφυρα (αν υπάρχει άλλο μονοπάτι \(u\)–\(v\) χωρίς την \(e\), μαζί με την \(e\) δίνει κύκλο· αλλιώς η \(e\) είναι γέφυρα). Αν η \(e\) ήταν γέφυρα, τότε, αφού \(n\ge3\), ένα από τα δύο άκρα της, έστω \(u\), έχει άλλη κορυφή \(x\) στη συνιστώσα του μετά την αφαίρεση της \(e\). Κάθε μονοπάτι από το \(x\) στο \(v\) περνά από το \(u\), άρα το \(u\) είναι κομβικό σημείο — αντίφαση. Άρα η \(e\) ανήκει σε κύκλο.
(Η υπόθεση \(n\ge3\) είναι απαραίτητη: το \(K_2\) δεν έχει κομβικό σημείο αλλά η ακμή του δεν είναι σε κύκλο.)
Θέμα Σ/Λ (πρώτη πρόταση)¶
Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: μέτρια
Η αρχή της πρότασης λείπει από τη φωτογραφία· υποθέτουμε ότι είναι «Άν το Γ περιέχει κλειστό ίχνος, θα περιέχει και κύκλο». Σωστό: ένα (μη τετριμμένο) κλειστό ίχνος αναλύεται σε ακμοξένους κύκλους.
Θέμα Σ/Λ (δεύτερη πρόταση)¶
Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: μέτρια
Υποθέτουμε «Άν το Γ έχει τουλάχιστον δύο κύκλους και είναι συνεκτικό, θα έχει κομβικό σημείο». Λάθος: το \(K_4\) είναι συνεκτικό, έχει πολλούς κύκλους και κανένα κομβικό σημείο.
Θέματα 4, 5, 6, 7, 9¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν
Δεν λύθηκαν: τα σχήματα G1 και G2 δεν έχουν μεταγραφεί με ακμές.