Θεωρία Γραφημάτων και Εφαρμογές — Σεπτέμβριος 2020

Μεταγραφή από τα αρχεία «Sept2020.pdf» και «Themata_Sept2020.pdf».

Sept2020.pdf

Ερώτηση: 1 (Βαθμός: 2.00)
(Ελεύθερου Κειμένου)

Βρείτε όλα τα υπο-γραφήματα που είναι δισυνεκτικές συνιστώσες ως προς ακμές.

[Σχήμα: Μη κατευθυνόμενο γράφημα με κορυφές 1 έως 7. Ακμές: {1,3}, {1,7}, {7,4}, {1,5} (καμπύλη ακμή), {3,4}, {4,5}, {2,5}, {2,6}, {5,6}.]

Ερώτηση: 2 (Βαθμός: 2.00)
(Ελεύθερου Κειμένου)

Βρείτε ένα υπο-γράφημα με 7 κορυφές και ακριβώς 6 ακμές, που να έχει κύκλο.

[Σχήμα: Μη κατευθυνόμενο γράφημα με κορυφές 1 έως 7. Ακμές: {1,2}, {1,3}, {1,7}, {7,4}, {3,4}, {4,5}, {2,5}, {2,6}, {5,6}.]

Ερώτηση: 3 (Βαθμός: 2.00)
(Ελεύθερου Κειμένου)

Έστω Τ το δέντρο επικάλυψης που αποτελείται από τις έντονες ακμές. Βρείτε έναν στοιχειώδη κύκλο ως προς το Τ που να περιέχει το πολύ μία ακμή του Τ με άκρο την κορυφή 2 .

[Σχήμα: Γράφημα με κορυφές 1 έως 6. Έντονες ακμές: δέντρο επικάλυψης T. Λεπτές ακμές: οι υπόλοιπες, μαζί με καμπύλη ακμή μεταξύ των κορυφών 3 και 2.]

Ερώτηση: 4 (Βαθμός: 2.00)
(Ελεύθερου Κειμένου)

Βρείτε ένα υπο-γράφημα με 7 κορυφές και ακριβώς 6 ακμές, που να μην είναι δέντρο.

[Σχήμα: Μη κατευθυνόμενο γράφημα με κορυφές 1 έως 7, με τις ίδιες ακμές όπως στην Ερώτηση 1.]

Ερώτηση: 5 (Βαθμός: 1.00)
(Ελεύθερου Κειμένου)

Έστω Τ το δέντρο επικάλυψης που αποτελείται από τις έντονες ακμές. Να γραφτεί ο κύκλος ( 1 , _ , 2 , _ , 4 , _ , 3 , _ , 1 ) ως άθροισμα στοιχειωδών κύκλων ως προς το Τ .

[Σχήμα: Γράφημα με κορυφές 1 έως 6. Έντονες ακμές: δέντρο επικάλυψης T. Λεπτές ακμές: οι υπόλοιπες.]

Ερώτηση: 6 (Βαθμός: 2.00)
(Ελεύθερου Κειμένου)

Αφαιρέστε μία κορυφή α του παρακάτω γραφήματος Γ , ώστε το γράφημα Γ-α να είναι συνεκτικό και να έχει περισσότερα κομβικά σημεία από το Γ .

[Σχήμα: Μη κατευθυνόμενο γράφημα Γ με κορυφές 1 έως 7. Ακμές: {1,3}, {1,7}, {7,4}, {3,4}, {2,4}, {4,5}, {2,5}, {2,6}, {5,6}.]

Themata_Sept2020.pdf

Σ-Λ

Ερώτηση: 1 (Βαθμός: 1.00)

(Σωστό / Λάθος)

Ένα γράφημα με n κορυφές και το πολύ n-1 ακμές θα είναι άκυκλο.

• [ ] Σωστό
• [ ] Λάθος

Ερώτηση: 2 (Βαθμός: 1.00)

(Σωστό / Λάθος)

Άν υπάρχει ένας κύκλος που περιέχει όλες τις κορυφές, το γράφημα δεν θα έχει γέφυρες.

• [ ] Σωστό
• [ ] Λάθος

Ερώτηση: 3 (Βαθμός: 1.00)

(Σωστό / Λάθος)

Άν σε ένα κατευθυνόμενο γράφημα υπάρχει ένα κλειστό ίχνος που περιέχει όλες τις κορυφές, το γράφημα θα είναι ισχυρά συνεκτικό.

• [ ] Σωστό
• [ ] Λάθος

Ερώτηση: 4 (Βαθμός: 1.00)

(Σωστό / Λάθος)

Σε κάθε κατευθυνόμενο γράφημα Γ η σχέση { (u, v) | υπάρχει κλειστό ίχνος που περιέχει τις κορυφές u , v του Γ } θα είναι συμμετρική.

• [ ] Σωστό
• [ ] Λάθος

Ερώτηση: 5 (Βαθμός: 1.00)

(Σωστό / Λάθος)

Άν ένα συνεκτικό γράφημα έχει μία τουλάχιστον ακμή: για οποιαδήποτε κορυφή u του γραφήματος, θα υπάρχει ένα ίχνος με άκρο την u .

• [ ] Σωστό
• [ ] Λάθος

Ερώτηση: 6 (Βαθμός: 1.00)

(Σωστό / Λάθος)

Σε κάθε γράφημα που είναι δισυνεκτικό ως προς κορυφές και έχει μία τουλάχιστον ακμή, θα υπάρχει ένα κλειστό ίχνος που περιέχει όλες τις κορυφές.

• [ ] Σωστό
• [ ] Λάθος

Ερώτηση: 7 (Βαθμός: 1.00)

(Σωστό / Λάθος)

Κάθε διαδρομή που είναι ανοιχτό ίχνος, θα είναι και μονοπάτι.

• [ ] Σωστό
• [ ] Λάθος

Ερώτηση: 8 (Βαθμός: 1.00)

(Σωστό / Λάθος)

Κάθε διαδρομή που είναι κλειστό ίχνος, θα είναι και κύκλος.

• [ ] Σωστό
• [ ] Λάθος

Προβλήματα

Ερώτηση: 1 (Βαθμός: 2.00)

(Ελεύθερου Κειμένου)

Προσθέστε μία ακμή στο γράφημα, ώστε το νέο γράφημα να μην έχει γέφυρες.

[Σχήμα: Μη κατευθυνόμενο γράφημα με κορυφές 2, 3, 4, 5, 6, 7.]

Ερώτηση: 2 (Βαθμός: 2.00)

(Ελεύθερου Κειμένου)

Προσθέστε μία ακμή στο γράφημα, ώστε το νέο γράφημα να έχει ακριβώς μία γέφυρα.

[Σχήμα: Μη κατευθυνόμενο γράφημα με κορυφές 1, 2, 3, 4, 5, 6, 7.]

Ερώτηση: 3

(Ελεύθερου Κειμένου)

Βρείτε τρία διαφορετικά δέντρα επικάλυψης του γραφήματος.

[Σχήμα: Γράφημα με κορυφές 1, 2, 3, 4, 5, 6.]

Ερώτηση: 4 (Βαθμός: 2.00)

(Ελεύθερου Κειμένου)

Βρείτε άν το γράφημα είναι δισυνεκτικό ως προς κορυφές, είτε δισυνεκτικό ως προς ακμές.

[Σχήμα: Γράφημα με κορυφές 1, 2, 3, 4, 5, 6.]

Ερώτηση: 5 (Βαθμός: 2.00)

(Ελεύθερου Κειμένου)

Προσθέστε μία ακμή στο γράφημα, ώστε το νέο γράφημα να έχει ακριβώς μία γέφυρα.

[Σχήμα: Γράφημα με κορυφές 2, 3, 4, 5, 6, 7.]

Ερώτηση: 6

(Ελεύθερου Κειμένου)

Βρείτε ένα δέντρο επικάλυψης Τ , ώστε δύο τουλάχιστον από τις ακμές {1, 3} , {3, 4} , {4, 5} , {5, 2} να μην περιέχονται στο Τ .

[Σχήμα: Γράφημα με κορυφές 1, 2, 3, 4, 5, 6.]

Επιπλέον πηγές χωρίς μεταγραφή εδώ (λύσεις → 2020-09.solutions.md, ή διπλότυπες φωτογραφίες ή παραλλαγές της εξέτασης που δεν μεταφέρθηκαν, βλ. σημείωση στο frontmatter): 470.png, 471.png, unknown-17.png, unknown.png, A97A7F23-0429-4772-AA8C-FD636770321D.png.jpg, received_3850122665016835.webp, received_810079962865535.webp, simmetrikimetabatiki4.png, simmetrikometabatiko2.JPG, 472.png, 474.png, 475.png, 476.png

Λύσεις (🟡 community)

Κατάσταση: 🟡 community Πηγή: φωτογραφίες και στιγμιότυπα λύσεων από φοιτητές (472, 474, 475, 476)

Προσοχή

Οι ερωτήσεις Σωστό/Λάθος των 472, 475 και 476 δεν υπάρχουν στη μεταγραφή της συνεδρίας 2020-09 (βλ. σημειώσεις της συνεδρίας)· οι απαντήσεις τους είναι συμπληρωματικές. Η ίδια πρόταση «Άν τα άκρα μίας ακμής είναι κομβικά σημεία, η ακμή θα είναι γέφυρα» εμφανίζεται στα 472 και 476 με αντίθετη επιλογή. Η επιλογή «Λάθος» του 472 συμφωνεί με το ότι η πρόταση είναι ψευδής (αντιπαράδειγμα: κύκλος 1-2-3-4 με κρεμαστές κορυφές στα 1 και 2· η ακμή 1-2 δεν είναι γέφυρα). Το 476 σημειώνει «Σωστό» με ένδειξη «λάθος», άρα μάλλον αντιπροσωπεύει λανθασμένη επιλογή φοιτητή.

Λύσεις — Θεωρία Γραφημάτων και Εφαρμογές — Σεπτέμβριος 2020

Στιγμιότυπα και φωτογραφίες λύσεων και αναθεωρήσεων κουίζ από φοιτητές· δεν προέρχονται από τον διδάσκοντα. Οι ενδείξεις «(σωστό)» και «(λάθος)» δίπλα σε κάθε επιλογή είναι του αρχικού στιγμιότυπου.

474.png

Βρείτε ένα υπο-γράφημα με 7 κορυφές και ακριβώς 6 ακμές, που να μην είναι δέντρο.

[Σχήμα: Μη κατευθυνόμενο γράφημα με 7 κορυφές (1, 2, 3, 4, 5, 6, 7). Ακμές: (3, 1), (3, 4), (1, 7), (7, 4), (1, 5), (4, 5), (5, 2), (2, 6), (5, 6).]

Απάντηση

Δέντρο είναι ένα συνεκτικό και άκυκλο μη-κατευθυνόμενο γράφημα. Έτσι μπορούμε να πάρουμε το υπογράφημα: \(G' = ( \{1, 2, 3, 4, 5, 6, 7\}, \{\{1, 3\}, \{3, 4\}, \{4, 5\}, \{5, 6\}, \{6, 2\}, \{2, 5\}\} )\). Το \(G'\) περιέχει τον κύκλο 2-5-6. (Επίσης δεν είναι συνεκτικό εφόσον το 7 είναι η 2η συνεκτική συνιστώσα του)

472.png

Άν τα άκρα μίας ακμής είναι κομβικά σημεία, η ακμή θα είναι γέφυρα.

Απάντηση

• [ ] Σωστό (λάθος)
• [x] Λάθος (σωστό)

475.png

Ερώτηση: 6 (Βαθμός: 1.00 / 1.00) (Σωστό / Λάθος)

Μία κορυφή που περιέχεται σε κύκλο δεν μπορεί να είναι άκρο γέφυρας.

Απάντηση

• [ ] Σωστό (λάθος)
• [x] Λάθος (σωστό)

476.png

Άν τα άκρα μίας ακμής είναι κομβικά σημεία, η ακμή θα είναι γέφυρα.

Απάντηση

• [x] Σωστό (λάθος)
• [ ] Λάθος (σωστό)

✔ Επιβεβαίωσε · ✖ Βρήκα λάθος

---

✖ Βρήκα λάθος στη μεταγραφή