Θεωρία Γραφημάτων και Εφαρμογές — Ιανουάριος 2021 — Ελεύθερου κειμένου¶
Μεταγραφή από τις φωτογραφίες 2021-01-27_192103.png, IMG_20210128_015255.jpg και Screenshot_2021-02-23-18-27-37-689_com.miui.gallery.jpg.
2021-01-27_192103.png¶
Ερώτηση 1 / 14 (Ελεύθερου Κειμένου — 2 Βαθμοί)
Βρείτε δύο κορυφές που βρίσκονται στην ίδια κλειστή διαδρομή, και δεν βρίσκονται στο ίδιο κλειστό ίχνος.
[Σχήμα: Μη κατευθυνόμενο γράφημα με 7 κορυφές (1, 2, 3, 4, 5, 6, 7). Ακμές: (3, 1), (3, 4), (1, 4), (4, 7), (1, 2), (1, 5), (2, 5), (2, 6), (5, 6).]
IMG_20210128_015255.jpg¶
Ερώτηση 5 / 14 (Ελεύθερου Κειμένου — 2 Βαθμοί)
Συμβολίζουμε με \(X*Y\) την συμμετρική διαφορά των συνόλων \(X, Y\). Βρείτε μία παράσταση που να είναι ίση με την \((A*B)*(A*A)*(B*A)\) , και όπου κάθε ένα από τα σύνολα \(A, B\) να εμφανίζεται το πολύ μία φορά.
Screenshot_2021-02-23-18-27-37-689_com.miui.gallery.jpg¶
Θεωρία Γραφημάτων και Εφαρμογές Ιανουάριος-Φεβρουάριος 2021 Προβολή Άσκησης
Προβλήματα: Δείγμα
Ερώτηση 12 / 14 (Ελεύθερου Κειμένου — 2 βαθμοί)
Βρείτε το υπο-γράφημα που είναι αποτέλεσμα του αθροίσματος των κύκλων: ( 1 , {1, 2} , 2 , {2, 6} , 6 , {6, 5} , 5 , {5, 1} , 1 ) , ( 1 , {1, 2} , 2 , {2, 5} , 5 , {5, 4} , 4 , {4, 1} , 1 ) , ( 1 , {1, 5} , 5 , {5, 4} , 4 , {4, 3} , 3 , {3, 1} , 1 ) .
Σημείωση: το στιγμιότυπο οθόνης περιέχει κόκκινες διαγραφές πάνω σε ορισμένα σύνολα και παράθυρο συνομιλίας· δεν μεταγράφονται.
[Σχήμα: Μη κατευθυνόμενο γράφημα με 6 κορυφές (1, 2, 3, 4, 5, 6). Ακμές: (1, 2), (2, 6), (1, 6), (6, 5), (1, 3), (3, 4), (1, 4), (4, 5), (1, 5), (2, 5).]
Λύσεις (⚪ AI, μη επαληθευμένο)
Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (sonnet), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο
Προσοχή
Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.
AI λύσεις — 2021-01-a¶
Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.
Θέμα 1¶
Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή
Ιδέα: σε κλειστή διαδρομή επιτρέπεται επανάληψη ακμών· σε κλειστό ίχνος όχι. Η κορυφή 7 έχει βαθμό 1 (μόνη ακμή η {4,7}). Ένα κλειστό ίχνος που περνά από την 7 θα έπρεπε να χρησιμοποιεί δύο διαφορετικές ακμές της 7 (μία για να μπει, μία για να βγει) — αδύνατο.
Άρα η 7 δεν ανήκει σε κανένα κλειστό ίχνος (η {4,7} είναι γέφυρα). Όμως η κλειστή διαδρομή \((1,\{1,4\},4,\{4,7\},7,\{7,4\},4,\{4,1\},1)\) περιέχει τις 1 και 7.
Απάντηση: οι κορυφές 1 και 7 (κάθε ζεύγος με την 7 κάνει δουλειά, π.χ. και 4, 7).
Θέμα 5¶
Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή
Η \(\oplus\) (συμμετρική διαφορά) είναι αντιμεταθετική και προσεταιριστική, και \(X\oplus X=\varnothing\), \(X\oplus\varnothing=X\). - \(A\oplus A=\varnothing\). - \((A\oplus B)\oplus(B\oplus A)=\varnothing\), αφού \(A\oplus B=B\oplus A\).
Άρα \((A\oplus B)\oplus(A\oplus A)\oplus(B\oplus A)=\varnothing\oplus\varnothing=\varnothing\).
Απάντηση: η παράσταση ισούται με \(\varnothing\) (δεν χρειάζεται καμία εμφάνιση των A, B).
Θέμα 12¶
Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή
Το άθροισμα κύκλων είναι η συμμετρική διαφορά των συνόλων ακμών (ακμή που εμφανίζεται άρτιες φορές φεύγει). Οι ακμές των κύκλων: - \(C_1\): 12, 26, 56, 15 - \(C_2\): 12, 25, 45, 14 - \(C_3\): 15, 45, 34, 13
Πλήθος εμφανίσεων: 12 → 2 (φεύγει), 15 → 2 (φεύγει), 45 → 2 (φεύγει), και μία φορά οι 26, 56, 25, 14, 34, 13.
Απάντηση: υπογράφημα με ακμές {2,6}, {5,6}, {2,5}, {1,4}, {3,4}, {1,3} (κορυφές 1–6): δύο ξένα τρίγωνα, τα (2,6,5) και (1,4,3). (Επαληθεύτηκε με πρόγραμμα.)