Θεωρία Γραφημάτων και Εφαρμογές — Ιανουάριος 2022¶
Μεταγραφή από τις φωτογραφίες grafimataJune2024.jpg και 20220130_224306.jpg.
grafimataJune2024.jpg¶
Θεωρία Γραφημάτων & Εφαρμογές - Διακριτά Μαθ/κά ΙΙ 2021 - 2022 Όλες οι απαντήσεις πρέπει να είναι σαφείς και να εξηγούνται επαρκώς με βάση τη θεωρία, εκτός από το θέμα 7 όπου απαντάτε 'σωστό' ή 'λάθος'.
1 Βρείτε άν το κατευθυνόμενο γράφημα G1 είναι ισχυρά συνεκτικό 1,5 μονάδα
[Σχήμα: Κατευθυνόμενο γράφημα G1 με κορυφές 0, 1, 2, 3] [Σχήμα: Μη-κατευθυνόμενο γράφημα G2 με κορυφές a, b, c, d, e, με έντονες ακμές]
2 Στο μη-κατευθυνόμενο γράφημα G2 βρείτε τους κύκλους που είναι στοιχειώδεις ως προς το δέντρο επικάλυψης που αποτελείται από τις έντονες ακμές. 1,5 μονάδα
3 Στο κατευθυνόμενο γράφημα G1 βρείτε όλα τα μη-επεκτάσιμα μονοπάτια με άκρο την κορυφή 3. 1,5 μονάδα
4 Βρείτε μία παράσταση που να είναι ίση με την \(A \oplus (A \oplus \Gamma) \oplus (B \oplus A)\) , και όπου κάθε ένα από τα σύνολα A, B, \(\Gamma\) να εμφανίζεται το πολύ μία φορά. 1 μονάδα
5 Στο μη-κατευθυνόμενο γράφημα G3 βρείτε τις δισυνεκτικές συνιστώσες ως προς ακμές. 1,5 μονάδα
[Σχήμα: Μη-κατευθυνόμενο γράφημα G3 με κορυφές a, b, c, d, e, f]
6 Αποδείξτε ότι: τα άκρα ενός μονοπατιού που έχει μέγιστο μήκος, δεν είναι κομβικά σημεία. 1,5 μονάδα
7 Για κάθε μία από τις παρακάτω υποθετικές ιδιότητες, βρείτε άν είναι σωστή ή λάθος. Οι ερωτήσεις είναι ισοβαρείς. Δεν χρειάζεται να εξηγήσετε τις απαντήσεις σας. Το \(\Gamma\) είναι πάντα ένα τυχαίο μη-κατευθυνόμενο γράφημα. 1,5 μονάδα
a Άν το \(\Gamma\) είναι συνεκτικό, κάποια διαδρομή του \(\Gamma\) θα περιέχει όλες τις κορυφές του \(\Gamma\). b Άν το \(\Gamma\) δεν είναι δισυνεκτικό ως προς κορυφές, δεν θα είναι δισυνεκτικό ως προς ακμές. c Άν το \(\Gamma\) έχει ακριβώς n κορυφές και m ακμές, και το \(\Gamma\) δεν είναι συνεκτικό, θα είναι \(n > m+1\). [συμπληρώθηκε από 20220130_224306.jpg]
20220130_224306.jpg¶
1 Βρείτε άν το κατευθυνόμενο γράφημα G1 είναι ισχυρά συνεκτικό 1,5 μονάδα
[Σχήμα: Κατευθυνόμενο γράφημα G1 με κορυφές 1, 2, 3, 4] [Σχήμα: Μη-κατευθυνόμενο γράφημα G2 με κορυφές a, b, c, d, e, με έντονες ακμές]
2 Στο μη-κατευθυνόμενο γράφημα G2 βρείτε τους κύκλους που δεν είναι στοιχειώδεις ως προς το δέντρο επικάλυψης που αποτελείται από τις έντονες ακμές. 1,5 μονάδα
3 Στο μη-κατευθυνόμενο γράφημα G1 βρείτε όλα τα μη-επεκτάσιμα μονοπάτια με άκρο την κορυφή 3. 1,5 μονάδα
4 Βρείτε μία παράσταση που να είναι ίση με την \((B \oplus A) \oplus B \oplus (A \oplus A) \oplus (B \oplus A)\) , και όπου κάθε ένα από τα σύνολα A, B να εμφανίζεται το πολύ μία φορά. 1 μονάδα
5 Στο μη-κατευθυνόμενο γράφημα G3 βρείτε τις δισυνεκτικές συνιστώσες ως προς ακμές που δεν περιέχουν την κορυφή a. 1,5 μονάδα
[Σχήμα: Μη-κατευθυνόμενο γράφημα G3 με κορυφές a, b, c, d, e, f]
6 Αποδείξτε ότι: τα άκρα ενός μονοπατιού που έχει μέγιστο μήκος, δεν είναι κομβικά σημεία. 1,5 μονάδα
7 Για κάθε μία από τις παρακάτω υποθετικές ιδιότητες, βρείτε άν είναι σωστή ή λάθος. Οι ερωτήσεις είναι ισοβαρείς. Δεν χρειάζεται να εξηγήσετε τις απαντήσεις σας. Το \(\Gamma\) είναι πάντα ένα τυχαίο μη-κατευθυνόμενο γράφημα. 1,5 μονάδα
a Άν υπάρχει κλειστό ίχνος του \(\Gamma\) που περιέχει μία ακμή \(\{a, b\}\) , θα υπάρχει και κύκλος του \(\Gamma\) που περιέχει την \(\{a, b\}\) . b Άν το \(\Gamma\) είναι συνεκτικό, κάποιο μονοπάτι του \(\Gamma\) θα περιέχει όλες τις κορυφές του \(\Gamma\) . c Άν το \(\Gamma\) έχει ακριβώς n κορυφές και m ακμές, και το \(\Gamma\) δεν είναι συνεκτικό, θα είναι \(n > m+1\) .
Λύσεις (⚪ AI, μη επαληθευμένο)
Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (antigravity-gemini, sonnet), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο
Προσοχή
Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.
AI λύσεις — 2022-01¶
Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.
Θέμα 1¶
Αξιοπιστία: λύθηκε με βάση τις φωτογραφίες του θέματος· μία λύση AI
Εκδοχή Α (grafimataJune2024.jpg): Στο κατευθυνόμενο γράφημα \(G_1\) με κορυφές \(\{0, 1, 2, 3\}\), η κορυφή 2 έχει μόνο εισερχόμενες ακμές (όπως η \((3, 2)\) και η \((1, 2)\)) και καμία εξερχόμενη ακμή (\(d^+(2)=0\)). Επομένως δεν υπάρχει κατευθυνόμενο μονοπάτι από την κορυφή 2 προς οποιαδήποτε άλλη κορυφή. Άρα το \(G_1\) δεν είναι ισχυρά συνεκτικό.
Εκδοχή Β (20220130_224306.jpg): Το \(G_1\) έχει κορυφές \(\{1, 2, 3, 4\}\) με ακμές \((1, 2)\), \((2, 1)\), \((3, 2)\), \((3, 4)\), \((4, 3)\). Από τις κορυφές \(\{1, 2\}\) δεν ξεκινά καμία κατευθυνόμενη ακμή προς το σύνολο \(\{3, 4\}\), άρα δεν υπάρχει μονοπάτι από το 1 ή το 2 προς το 3 ή το 4. Άρα το \(G_1\) δεν είναι ισχυρά συνεκτικό.
Θέμα 2¶
Αξιοπιστία: λύθηκε με βάση τις φωτογραφίες του θέματος· μία λύση AI
Στο γράφημα \(G_2\) με κορυφές \(\{a, b, c, d, e\}\), το δέντρο επικάλυψης \(T\) που αποτελείται από τις έντονες ακμές είναι: $\(E(T) = \{\{a, b\}, \{b, c\}, \{c, e\}, \{d, e\}\}\)$ (μονοπάτι \(a - b - c - e - d\), 4 ακμές σε 5 κορυφές). Οι λεπτές ακμές (χορδές εκτός \(T\)) είναι οι: \(\{a, d\}\), \(\{b, d\}\) και \(\{b, e\}\).
Εκδοχή Α (grafimataJune2024.jpg): Ζητούνται οι κύκλοι που είναι στοιχειώδεις ως προς το \(T\). Κάθε χορδή συνδυάζεται με το μοναδικό μονοπάτι του \(T\) που συνδέει τα άκρα της και παράγει έναν στοιχειώδη κύκλο: 1. Χορδή \(\{a, d\}\): Το μονοπάτι στο \(T\) είναι \(a - b - c - e - d\). Στοιχειώδης κύκλος: \((a, b, c, e, d, a)\) (μήκους 5). 2. Χορδή \(\{b, d\}\): Το μονοπάτι στο \(T\) είναι \(b - c - e - d\). Στοιχειώδης κύκλος: \((b, c, e, d, b)\) (μήκους 4). 3. Χορδή \(\{b, e\}\): Το μονοπάτι στο \(T\) είναι \(b - c - e\). Στοιχειώδης κύκλος: \((b, c, e, b)\) (μήκους 3).
Εκδοχή Β (20220130_224306.jpg): Ζητούνται οι κύκλοι που δεν είναι στοιχειώδεις ως προς το \(T\). Είναι οι κύκλοι του \(G_2\) που περιέχουν τουλάχιστον δύο χορδές: - Το τρίγωνο \((a, b, d, a)\), με ακμές \(\{\{a, b\}, \{b, d\}, \{a, d\}\}\) (περιέχει τις δύο χορδές \(\{a, d\}\) και \(\{b, d\}\)). - Το τρίγωνο \((b, d, e, b)\), με ακμές \(\{\{b, d\}, \{d, e\}, \{b, e\}\}\) (περιέχει τις δύο χορδές \(\{b, d\}\) και \(\{b, e\}\)). - Ο κύκλος 4 κορυφών \((a, b, e, d, a)\), με ακμές \(\{\{a, b\}, \{b, e\}, \{d, e\}, \{a, d\}\}\) (περιέχει τις δύο χορδές \(\{a, d\}\) και \(\{b, e\}\)).
Θέμα 3¶
Αξιοπιστία: λύθηκε με βάση τις φωτογραφίες του θέματος· μία λύση AI
Ένα μονοπάτι είναι μη-επεκτάσιμο αν δεν μπορεί να επεκταθεί από κανένα από τα άκρα του.
Εκδοχή Β (20220130_224306.jpg): (Σημείωση: Στην εκφώνηση αναγράφεται εκ παραδρομής «μη-κατευθυνόμενο», όμως το \(G_1\) είναι κατευθυνόμενο). Στο \(G_1\) οι ακμές που προσπίπτουν στο 3 είναι η εισερχόμενη \((4, 3)\) και οι εξερχόμενες \((3, 4)\) και \((3, 2)\). - Το μονοπάτι \((3, 4)\) ξεκινά από το 3 και καταλήγει στο 4: - Στο τέλος 4, ο μόνος εξερχόμενος γείτονας είναι το 3 (\(N_{out}(4) = \{3\} \subseteq V(P)\)). - Στην αρχή 3, ο μόνος εισερχόμενος γείτονας είναι το 4 (\(N_{in}(3) = \{4\} \subseteq V(P)\)). Συνεπώς δεν επεκτείνεται ούτε προς τα εμπρός ούτε προς τα πίσω. - Μονοπάτι με τέλος το 3 δεν μπορεί να είναι μη-επεκτάσιμο, γιατί από το 3 υπάρχει πάντα η εξερχόμενη ακμή \((3, 2)\) προς κορυφή εκτός του μονοπατιού. Απάντηση: Το μονοπάτι \((3, 4)\).
Εκδοχή Α (grafimataJune2024.jpg): Αντίστοιχα στο γράφημα της Εκδοχής Α με κορυφές \(\{0, 1, 2, 3\}\), όπου η κορυφή 0 παίζει το ρόλο της 4 με 2-κύκλο μεταξύ 0 και 3, το μη-επεκτάσιμο μονοπάτι με άκρο το 3 είναι το \((3, 0)\).
Θέμα 4, εκδοχή Α¶
Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή
Η συμμετρική διαφορά \(\oplus\) είναι αντιμεταθετική, προσεταιριστική, με \(X\oplus X=\varnothing\). \(A\oplus(A\oplus\Gamma)=(A\oplus A)\oplus\Gamma=\Gamma\). Άρα η παράσταση είναι \(\Gamma\oplus(B\oplus A)\).
Απάντηση: \(A\oplus B\oplus\Gamma\) (κάθε σύνολο μία φορά).
Θέμα 4, εκδοχή Β¶
Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή
\((B\oplus A)\oplus B\oplus(A\oplus A)\oplus(B\oplus A)\): ο όρος \(A\oplus A=\varnothing\) φεύγει. Μένουν \(B\) τρεις φορές και \(A\) δύο: \(B\oplus B\oplus B=B\), \(A\oplus A=\varnothing\).
Απάντηση: \(B\).
Θέμα 5¶
Αξιοπιστία: λύθηκε με βάση τις φωτογραφίες του θέματος· μία λύση AI
Εκδοχή Α (grafimataJune2024.jpg): Στο σχήμα \(G_3\), η κορυφή \(f\) είναι εκκρεμής (βαθμού 1) συνδεδεμένη αποκλειστικά με την κορυφή \(e\) μέσω της ακμής \(\{e, f\}\). Η ακμή \(\{e, f\}\) είναι γέφυρα. Οι υπόλοιπες ακμές ανήκουν στα τρίγωνα \((a, b, d, a)\) και \((b, c, e, b)\), άρα καμία άλλη ακμή δεν είναι γέφυρα. Συνεπώς, οι δισυνεκτικές συνιστώσες ως προς ακμές (που ορίζονται από τη σχέση διπροσβασιμότητας \(R_\iota\), όπου δύο κορυφές ανήκουν στην ίδια συνιστώσα αν δεν χωρίζονται από γέφυρα) είναι: 1. Το υπογράφημα με κορυφές \(\{a, b, c, d, e\}\) και όλες τις ακμές των δύο τριγώνων. 2. Η μεμονωμένη κορυφή \(\{f\}\) (ή η συνιστώσα της γέφυρας \(\{e, f\}\) ανάλογα με τη σύμβαση).
Εκδοχή Β (20220130_224306.jpg): Στην Εκδοχή Β ζητούνται: «οι δισυνεκτικές συνιστώσες ως προς ακμές που δεν περιέχουν την κορυφή a». Στο σχήμα της Εκδοχής Β, η κορυφή \(f\) συνδέεται τόσο με το \(c\) όσο και με το \(e\) σχηματίζοντας το τρίγωνο \((c, e, f, c)\), οπότε δεν υπάρχει καμία γέφυρα στο \(G_3\). Επομένως ολόκληρο το γράφημα \(\{a, b, c, d, e, f\}\) είναι μία ενιαία δισυνεκτική συνιστώσα ως προς ακμές (που περιέχει το \(a\)). Άρα δεν υπάρχει καμία δισυνεκτική συνιστώσα ως προς ακμές που να μην περιέχει την κορυφή \(a\). (Αν εννοούνταν ως προς κορυφές, τότε επειδή το \(b\) είναι κομβικό σημείο, η ζητούμενη συνιστώσα θα ήταν το block \(\{b, c, e, f\}\)).
Θέμα 6¶
Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή
Έστω \(P=(v_0,v_1,\dots,v_k)\) μονοπάτι μέγιστου μήκους σε συνεκτικό γράφημα (αν το γράφημα δεν είναι συνεκτικό, δουλεύουμε στη συνεκτική του συνιστώσα). Έστω ότι το \(v_0\) είναι κομβικό σημείο, δηλ. το \(\Gamma-v_0\) έχει περισσότερες συνεκτικές συνιστώσες. Το \(v_1,\dots,v_k\) είναι συνεκτικό και ανήκει σε μία συνιστώσα \(C\) του \(\Gamma-v_0\). Υπάρχει άλλη συνιστώσα \(D\) του \(\Gamma-v_0\). Επειδή η συνιστώσα του Γ που περιέχει το \(v_0\) είναι συνεκτική και το \(D\) δεν συνδέεται με άλλη συνιστώσα του \(\Gamma-v_0\), κάποια κορυφή \(w\in D\) είναι γειτονική του \(v_0\). Τότε \(w\notin P\) και το \((w,v_0,v_1,\dots,v_k)\) είναι μονοπάτι μήκους \(k+1\) — αντίφαση με τη μεγιστότητα. Ομοίως για το \(v_k\).
Συμπέρασμα: τα άκρα μονοπατιού μέγιστου μήκους δεν είναι κομβικά σημεία.
Θέμα 7, εκδοχή Α¶
Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή
- (a) Σωστό: σε συνεκτικό γράφημα, μια διαδρομή (επιτρέπονται επαναλήψεις) μπορεί να περάσει από όλες τις κορυφές (π.χ. διασχίζοντας ένα δέντρο επικάλυψης με επιστροφές).
- (b) Λάθος: δύο τρίγωνα που μοιράζονται μία κορυφή: χωρίς γέφυρες (δισυνεκτικό ως προς ακμές) αλλά η κοινή κορυφή είναι κομβικό σημείο.
- (c) Λάθος: τρίγωνο συν απομονωμένη κορυφή: μη συνεκτικό με \(n=4\), \(m=3\), άρα \(n=m+1\), όχι \(n>m+1\). (Αληθής είναι η αντίστροφη: \(n>m+1\Rightarrow\) μη συνεκτικό.)
Θέμα 7, εκδοχή Β¶
Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή
- (a) Σωστό: ένα κλειστό ίχνος αναλύεται σε ακμοξένους κύκλους, άρα κάθε ακμή του ανήκει σε κάποιον κύκλο.
- (b) Λάθος: το αστέρι \(K_{1,3}\) είναι συνεκτικό αλλά κανένα μονοπάτι του δεν περνά και από τα 3 φύλλα.
- (c) Λάθος: όπως στην εκδοχή Α (τρίγωνο συν απομονωμένη κορυφή).