Θεωρία Γραφημάτων και Εφαρμογές — Ιανουάριος 2021 — Θεωρία Σ/Λ (δείγμα)¶
Μεταγραφή από 12 φωτογραφίες (IMG_20210127_181510–181703).
IMG_20210127_181510.jpg¶
Θεωρία Σ/Λ: Δείγμα
Ερώτηση 1 / 12 (Σωστό / Λάθος — 1 βαθμός)
Άν ένα συνεκτικό γράφημα έχει μία τουλάχιστον ακμή: για οποιαδήποτε κορυφή u του γραφήματος, θα υπάρχει ένα μη-επεκτάσιμο μονοπάτι που περιέχει την u .
- [ ] Σωστό
- [ ] Λάθος
IMG_20210127_181518.jpg¶
Θεωρία Σ/Λ: Δείγμα
Ερώτηση 2 / 12 (Σωστό / Λάθος — 1 βαθμός)
Δύο κορυφές που βρίσκονται σε διαφορετικές δισυνεκτικές συνιστώσες ως προς ακμές ενός γραφήματος, δεν μπορούν να περιέχονται στο ίδιο κλειστό ίχνος.
- [ ] Σωστό
- [ ] Λάθος
IMG_20210127_181551.jpg¶
Θεωρία Σ/Λ: Δείγμα
Ερώτηση 3 / 12 (Σωστό / Λάθος — 1 βαθμός)
Άν υπάρχει ένας κύκλος που περιέχει όλες τις ακμές, το γράφημα δεν θα έχει κομβικά σημεία.
- [ ] Σωστό
- [ ] Λάθος
IMG_20210127_181559.jpg¶
Θεωρία Σ/Λ: Δείγμα
Ερώτηση 4 / 12 (Σωστό / Λάθος — 1 βαθμός)
Αν σε ένα γράφημα υπάρχει ένα ίχνος που περιέχει όλες τις κορυφές, το γράφημα θα είναι συνεκτικό.
- [ ] Σωστό
- [ ] Λάθος
IMG_20210127_181608.jpg¶
Θεωρία Σ/Λ: Δείγμα
Ερώτηση 5 / 12 (Σωστό / Λάθος — 1 βαθμός)
Σε κάθε γράφημα \(\Gamma\) η σχέση \(\{ (u, v) \mid \text{υπάρχει κλειστό ίχνος που περιέχει τις κορυφές } u, v \text{ του } \Gamma \}\) θα είναι μεταβατική.
- [ ] Σωστό
- [ ] Λάθος
Σημείωση: η φωτογραφία περιέχει χειρόγραφες απαντήσεις φοιτητή.
IMG_20210127_181615.jpg¶
Θεωρία Σ/Λ: Δείγμα
Ερώτηση 6 / 12 (Σωστό / Λάθος — 1 βαθμός)
Ένα άκυκλο γράφημα με n κορυφές θα έχει ακριβώς n-1 ακμές.
- [ ] Σωστό
- [ ] Λάθος
IMG_20210127_181623.jpg¶
Θεωρία Σ/Λ: Δείγμα
Ερώτηση 7 / 12 (Σωστό / Λάθος — 1 βαθμός)
Δύο δισυνεκτικές συνιστώσες ως προς κορυφές ενός γραφήματος δεν γίνεται να έχουν κοινή κορυφή.
- [ ] Σωστό
- [ ] Λάθος
IMG_20210127_181629.jpg¶
Θεωρία Σ/Λ: Δείγμα
Ερώτηση 8 / 12 (Σωστό / Λάθος — 1 βαθμός)
Σε κάθε γράφημα που είναι δισυνεκτικό ως προς κορυφές και έχει μία τουλάχιστον ακμή, θα υπάρχει ένας κύκλος που περιέχει όλες τις κορυφές.
- [ ] Σωστό
- [ ] Λάθος
IMG_20210127_181638.jpg¶
Θεωρία Σ/Λ: Δείγμα
Ερώτηση 9 / 12 (Σωστό / Λάθος — 1 βαθμός)
Άν σε ένα ισχυρά συνεκτικό κατευθυνόμενο γράφημα κάθε ακμή γίνει μη-κατευθυνόμενη, το γράφημα που θα προκύψει θα είναι συνεκτικό.
- [ ] Σωστό
- [ ] Λάθος
IMG_20210127_181647.jpg¶
Θεωρία Σ/Λ: Δείγμα
Ερώτηση 10 / 12 (Σωστό / Λάθος — 1 βαθμός)
Άν υπάρχει ένας κύκλος που περιέχει όλες τις κορυφές, το γράφημα δεν θα έχει γέφυρες.
- [ ] Σωστό
- [ ] Λάθος
Σημείωση: η φωτογραφία περιέχει χειρόγραφες απαντήσεις φοιτητή.
IMG_20210127_181653.jpg¶
Θεωρία Σ/Λ: Δείγμα
Ερώτηση 11 / 12 (Σωστό / Λάθος — 1 βαθμός)
Δύο κορυφές ενός γραφήματος που είναι άκρα μίας ανοιχτής διαδρομής, θα είναι και άκρα κάποιου ανοιχτού ίχνους.
- [ ] Σωστό
- [ ] Λάθος
Σημείωση: η φωτογραφία περιέχει χειρόγραφες απαντήσεις φοιτητή.
IMG_20210127_181703.jpg¶
Θεωρία Σ/Λ: Δείγμα
Ερώτηση 12 / 12 (Σωστό / Λάθος — 1 βαθμός)
Ένα γράφημα με n κορυφές που περιέχει κύκλο, θα έχει τουλάχιστον n ακμές.
- [ ] Σωστό
- [ ] Λάθος
Επιπλέον πηγές χωρίς μεταγραφή εδώ (λύσεις →
2021-01-deigma.solutions.md, ή διπλότυπες φωτογραφίες της ίδιας σελίδας):Screenshot_2.png,grafhmata21-luseisSL.png
Λύσεις (🟡 community)
Κατάσταση: 🟡 community Πηγή: στιγμιότυπο λύσεων από φοιτητή (grafhmata21-luseisSL.png)
Προσοχή
Το στιγμιότυπο δίνει ημερομηνία 2021-02 στην κεφαλίδα του (ένδειξη του μεταγραφέα)· αντιστοιχίστηκε στο δείγμα 2021-01 επειδή τέσσερις από τις έξι προτάσεις του ταιριάζουν με ερωτήσεις του δείγματος, με μικρές διαφορές διατύπωσης· η επιβεβαίωση είναι εκτιμώμενη. Δύο από τις έξι προτάσεις του στιγμιότυπου (η 2 «άκυκλο γράφημα με n κορυφές και τουλάχιστον n-1 ακμές» και η 6 «δύο ισχυρά συνεκτικές συνιστώσες … κατευθυνόμενου γραφήματος») δεν βρίσκονται στο δείγμα· ενδέχεται να προέρχονται από άλλη παραλλαγή του χαρτιού.
Λύσεις — Θεωρία Γραφημάτων και Εφαρμογές — Ιανουάριος 2021 (δείγμα Σ/Λ)¶
Στιγμιότυπο λύσεων από φοιτητή· οι ενδείξεις «(σωστό)» και «(λάθος)» είναι του αρχικού στιγμιότυπου.
grafhmata21-luseisSL.png¶
Ερώτηση: 1 (Βαθμός: 1.00 / 1.00) (Σωστό / Λάθος)
Δύο κορυφές ενός γραφήματος που είναι άκρα ενός μονοπατιού, θα είναι και άκρα κάποιου ανοιχτού ίχνους.
Απάντηση
- [x] Σωστό (σωστό)
- [ ] Λάθος (λάθος)
Ερώτηση: 2 (Βαθμός: 1.00 / 1.00) (Σωστό / Λάθος)
Ένα άκυκλο γράφημα με n κορυφές και τουλάχιστον n-1 ακμές θα είναι συνεκτικό.
Απάντηση
- [x] Σωστό (σωστό)
- [ ] Λάθος (λάθος)
Ερώτηση: 3 (Βαθμός: 1.00 / 1.00) (Σωστό / Λάθος)
Δύο ακμές που βρίσκονται σε διαφορετικές δισυνεκτικές συνιστώσες ως προς κορυφές ενός γραφήματος, δεν μπορούν να περιέχονται στον ίδιο κύκλο.
Απάντηση
- [x] Σωστό (σωστό)
- [ ] Λάθος (λάθος)
Ερώτηση: 4 (Βαθμός: 1.00 / 1.00) (Σωστό / Λάθος)
Άν ένα συνεκτικό γράφημα έχει μία τουλάχιστον ακμή: για οποιαδήποτε κορυφή u του γραφήματος, θα υπάρχει ένα μη-επεκτάσιμο μονοπάτι που περιέχει την u .
Απάντηση
- [x] Σωστό (σωστό)
- [ ] Λάθος (λάθος)
Ερώτηση: 5 (Βαθμός: 1.00 / 1.00) (Σωστό / Λάθος)
Σε κάθε γράφημα που είναι δισυνεκτικό ως προς κορυφές και έχει μία τουλάχιστον ακμή, θα υπάρχει μία κλειστή διαδρομή που περιέχει όλες τις κορυφές.
Απάντηση
- [x] Σωστό (σωστό)
- [ ] Λάθος (λάθος)
Ερώτηση: 6 (Βαθμός: 1.00 / 1.00) (Σωστό / Λάθος)
Δύο ισχυρά συνεκτικές συνιστώσες ενός κατευθυνόμενου γραφήματος δεν γίνεται να συνδέονται με διαδρομή.
Απάντηση
- [ ] Σωστό (λάθος)
- [x] Λάθος (σωστό)