Θεωρία Γραφημάτων και Εφαρμογές — Σεπτέμβριος 2024¶
Μεταγραφή από το στιγμιότυπο Screenshot_2024-09-27-01-13-28-984.jpg.
Screenshot_2024-09-27-01-13-28-984.jpg¶
Θεωρία Γραφημάτων & Εφαρμογές - Διακριτά Μαθ/κά ΙΙ Σεπτέμβριος 2024 Όλες οι απαντήσεις πρέπει να είναι σαφείς και να εξηγούνται επαρκώς με βάση τη θεωρία, εκτός από το θέμα 7 όπου απαντάτε 'σωστό' ή 'λάθος'.
Συμπληρώστε τα στοιχεία σας και επιστρέψτε τα θέματα μαζί με την κόλλα σας
1 Στο κατευθυνόμενο γράφημα G1, βρείτε τις ισχυρά συνεκτικές συνιστώσες. 1,5 μονάδα
[Σχήμα: Κατευθυνόμενο γράφημα G1 με κορυφές 1, 2, 3, 4] [Σχήμα: Μη-κατευθυνόμενο γράφημα G2 με κορυφές a, b, c, d, e]
2 Στο μη-κατευθυνόμενο γράφημα G2, βρείτε όλα τα δέντρα επικάλυψης ως προς τα οποία ο κύκλος \((b, \_ e, \_ c, \_ b)\) δεν είναι στοιχειώδης.. 1,5 μονάδα
3 Στο μη-κατευθυνόμενο γράφημα G2 βρείτε όλα τα μη-επεκτάσιμα μονοπάτια με άκρο την κορυφή a, που δεν έχουν μέγιστο μήκος. 1,5 μονάδα
4 Βρείτε μία παράσταση που να είναι ίση με την \(B \oplus (A \oplus A) \oplus (B \oplus A) \oplus A\) , και όπου κάθε ένα από τα σύνολα A, B να εμφανίζεται το πολύ μία φορά. 1 μονάδα
5 Στο μη-κατευθυνόμενο γράφημα G3 βρείτε ένα επαγόμενο υπο-γράφημα με τέσσερις τουλάχιστον κορυφές, που να είναι δέντρο. 1,5 μονάδα
[Σχήμα: Μη-κατευθυνόμενο γράφημα G3 με κορυφές a, b, c, d, e, f]
6 Αποδείξτε ότι: τα άκρα ενός μονοπατιού που έχει μέγιστο μήκος, δεν είναι κομβικά σημεία. 1,5 μονάδα
7 Για κάθε μία από τις παρακάτω υποθετικές ιδιότητες, βρείτε άν είναι σωστή ή λάθος. Δεν χρειάζεται να εξηγήσετε τις απαντήσεις σας. Το \(\Gamma\) είναι πάντα ένα τυχαίο μη-κατευθυνόμενο γράφημα, με δύο τουλάχιστον κορυφές. Οι ερωτήσεις είναι ισοβαρείς. 2 μονάδες
a Δύο διαφορετικές δισυνεκτικές συνιστώσες του \(\Gamma\) ως προς κορυφές, δεν μπορούν να έχουν κοινή ακμή. b Άν το \(\Gamma\) είναι συνεκτικό, κάποια διαδρομή του \(\Gamma\) θα περιέχει όλες τις κορυφές του \(\Gamma\) . c Άν το \(\Gamma\) δεν είναι δισυνεκτικό ως προς ακμές, θα υπάρχει κορυφή που δεν περιέχεται σε κύκλο. d Άν το \(\Gamma\) δεν είναι δισυνεκτικό ως προς ακμές, θα έχει γέφυρα.
Επιπλέον πηγές χωρίς μεταγραφή εδώ (άλλη παραλλαγή του χαρτιού, όχι διπλότυπα· βλ. σημειώσεις):
Sept2024.png,Sept2024vol2.jpg
Λύσεις (⚪ AI, μη επαληθευμένο)
Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (antigravity-gemini, gemini-3.7-flash, sonnet), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο
Προσοχή
Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.
AI λύσεις — 2024-09¶
Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.
Θέμα 1, 2, 3, 5¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν
Δεν λύθηκαν: τα σχήματα G1, G2, G3 δεν έχουν μεταγραφεί με ακμές.
Θέμα 4¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
\(B\oplus(A\oplus A)\oplus(B\oplus A)\oplus A\): το \(B\) εμφανίζεται δύο φορές και το \(A\) τέσσερις (δύο στο \(A\oplus A\), μία στο \(B\oplus A\), μία μόνο του). Άρα \(B\oplus B=\varnothing\) και \(A\oplus A\oplus A\oplus A=\varnothing\).
Απάντηση: \(\varnothing\).
Θέμα 6¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
Έστω \(P=(v_0,\dots,v_k)\) μονοπάτι μέγιστου μήκους. Αν το \(v_0\) ήταν κομβικό σημείο, το \(\Gamma-v_0\) θα είχε μια συνιστώσα \(D\) διαφορετική από αυτή που περιέχει το \(v_1,\dots,v_k\). Επειδή το Γ (στη συνιστώσα του) είναι συνεκτικό, κάποια \(w\in D\) είναι γειτονική του \(v_0\). Τότε \((w,v_0,\dots,v_k)\) είναι μονοπάτι μήκους \(k+1\) — αντίφαση. Ομοίως για το \(v_k\).
Θέμα 7¶
Αξιοπιστία: 2 από 3 ανεξάρτητες λύσεις συμφωνούν (η άλλη διαφωνούσε) · εμπιστοσύνη λύτη: μέτρια
- (a) Σωστό: δύο διαφορετικές δισυνεκτικές συνιστώσες ως προς κορυφές έχουν το πολύ μία κοινή κορυφή.
- (b) Λάθος: το αστέρι \(K_{1,3}\) είναι συνεκτικό αλλά κανένα μονοπάτι του δεν περνά από όλα τα φύλλα.
- (c) Λάθος: δύο τρίγωνα ενωμένα με γέφυρα: έχει γέφυρα (άρα δεν είναι δισυνεκτικό ως προς ακμές), αλλά κάθε κορυφή ανήκει σε κύκλο.
- (d) Λάθος: ένα μη συνεκτικό γράφημα (π.χ. δύο απομονωμένες κορυφές) δεν είναι δισυνεκτικό ως προς ακμές αλλά δεν έχει γέφυρα. (Αν στο μάθημα δισυνεκτικό ως προς ακμές σημαίνει «συνεκτικό χωρίς γέφυρες», η πρόταση αποτυγχάνει ακριβώς για τα μη συνεκτικά.)