Θεωρία Γραφημάτων και Εφαρμογές — Ιούνιος 2019¶
Μεταγραφή από το αρχείο του eClass «Εξεταση Ιουνιου 2019 - Απαντησεις.pdf».
Εξεταση Ιουνιου 2019 - Απαντησεις.pdf¶
Διακριτά Μαθηματικά ΙΙ - Ιούνιος 2019
ΕΓΘΑ : Σ. Κοσμαδάκης, «Εισαγωγή στα Γραφήματα, Θεωρία-Ασκήσεις».
Το Γ είναι πάντα ένα τυχαίο μη-κατευθυνόμενο γράφημα.
1 Οι \(c_1, c_2, c_3\) είναι κύκλοι του Γ, και \(c_3 = c_1 \oplus c_2\). Αποδείξτε ότι: \(c_2 \oplus c_3 = c_1\).
2 Έστω ότι το Γ είναι συνεκτικό, έχει \(n\) κορυφές, και έχει \(n\) ακμές. Αποδείξτε ότι το Γ έχει κύκλο.
3 Βρείτε κάποιο συνεκτικό Γ που δεν έχει γέφυρα και που έχει κομβικό σημείο.
4 Έστω ότι το Γ είναι δισυνεκτικό ως προς κορυφές. Αποδείξτε ότι το Γ είναι δισυνεκτικό ως προς ακμές.
5 Το Γ έχει \(m\) ακμές, \(n\) κορυφές, και ακριβώς δύο συνεκτικές συνιστώσες. Αποδείξτε ότι: \(m \geq n-2\).
6 Αποδείξτε ότι:
- Η σχέση \(P = \{(u, v) : u+v = 0\}\) πάνω στο σύνολο των ακέραιων αριθμών, είναι συμμετρική.
- Η σχέση \(Q = \{(u, v) : u+v = 3\}\) πάνω στο σύνολο των θετικών ακέραιων αριθμών, δεν είναι μεταβατική.
7 α Αποδείξτε ότι: Κάθε διαδρομή που είναι μονοπάτι, είναι και ανοιχτό ίχνος.
β Στο κατευθυνόμενο γράφημα του σχήματος, βρείτε ένα ανοιχτό ίχνος που να μην είναι μονοπάτι.
[Σχήμα: κατευθυνόμενο γράφημα με κορυφές 0, 1, 2, 3. Ακμές με βέλη: 0→1, 1→2 (ευθύγραμμη, στο πάνω μέρος), 2→1 (καμπύλη κάτω από την 1→2), 1→3 (καμπύλη προς τα κάτω), 3→2.]
8 Για το κατευθυνόμενο γράφημα του παραπάνω σχήματος:
α Βρείτε άν είναι ισχυρά συνεκτικό.
β Βρείτε ένα υπογράφημα που να είναι ισχυρά συνεκτικό, αλλά να μήν είναι ισχυρά συνεκτική συνιστώσα.
Λύσεις (🟢 official)
Κατάσταση: 🟢 official Πηγή: eClass μαθήματος, αρχείο «Θέματα Εξετάσεων και Απαντήσεις» (Εξεταση Ιουνιου 2019 - Απαντησεις.pdf)
Λύσεις — Θεωρία Γραφημάτων και Εφαρμογές — Ιούνιος 2019¶
Οι λύσεις μεταφέρονται από το αρχείο του eClass όπως είναι, χωρίς αλλαγές.
Εξεταση Ιουνιου 2019 - Απαντησεις.pdf¶
Διακριτά Μαθηματικά ΙΙ Ιούνιος 2019
ΕΓΘΑ : Σ. Κοσμαδάκης, «Εισαγωγή στα Γραφήματα, Θεωρία-Ασκήσεις».
Το Γ είναι πάντα ένα τυχαίο μη-κατευθυνόμενο γράφημα.
1 Οι c1, c2, c3 είναι κύκλοι του Γ, και c3 = c1c2. Αποδείξτε ότι: c2c3 = c1 .
Έστω Εi το σύνολο των ακμών που διατρέχει ο κύκλος ci , i = 1,2,3. Από τον ορισμό του αθροίσματος κύκλων – βλέπε ΕΓΘΑ 3.3 – και χρησιμοποιώντας την υπόθεση παίρνουμε Ε3 = Ε1 Ε2 . Για να δείξουμε ότι c2 c3 = c1 , αρκεί να δείξουμε ότι Ε2 Ε3 = Ε1 .
Αντικαθιστούμε στην παράσταση Ε2 Ε3 το Ε3 με το Ε1 Ε2 , και εφαρμόζουμε την αντιμεταθετικότητα και την προσεταιριστικότητα της συμμετρικής διαφοράς συνόλων – βλέπε ΕΓΘΑ 1.1 Ερώτημα 2 : Ε2 Ε3 = Ε2 (Ε1 Ε2) = Ε2 ( Ε2 Ε1) = (Ε2 Ε2) Ε1 .
Για κάθε σύνολο Α , Α A = (Α A) U( A Α) = U = , Α = ( Α) U( Α ) = U Α = Α . Επομένως, (Ε2 Ε2) Ε1 = Ε1 = Ε1.
2 Έστω ότι το Γ είναι συνεκτικό, έχει n κορυφές, και έχει n ακμές. Αποδείξτε ότι το Γ έχει κύκλο.
Α Τρόπος Γνωρίζουμε ότι ένα συνεκτικό και άκυκλο γράφημα (δέντρο) που έχει n κορυφές, θα έχει ακριβώς n 1 ακμές – βλέπε ΕΓΘΑ 3.1 , Πρόταση 3.1.2 ii . Άρα το Γ δεν μπορεί να είναι άκυκλο.
Β Τρόπος To Γ θα έχει ακριβώς n n 1= 1 χορδή ως προς κάποιο (τυχαίο) δέντρο επικάλυψης Τ – βλέπε ΕΓΘΑ 3.3. Επομένως υπάρχει ακριβώς ένας στοιχειώδης κύκλος ως προς το Τ . Άρα το Γ έχει κύκλο.
3 Βρείτε κάποιο συνεκτικό Γ που δεν έχει γέφυρα και που έχει κομβικό σημείο.
Στο γράφημα του σχήματος υπάρχουν ακριβώς δύο κύκλοι. Κάθε ακμή του γραφήματος περιέχεται σε έναν από τους δύο κύκλους, επομένως δεν υπάρχει γέφυρα -- βλέπε ΕΓΘΑ Πρόταση 2.3.1.
Κανείς κύκλος δεν περιέχει ταυτόχρονα τις ακμές {b, a} και {b, c} , επομένως η κορυφή c είναι κομβικό σημείο -- βλέπε ΕΓΘΑ Πρόταση 2.3.2.
4 Έστω ότι το Γ είναι δισυνεκτικό ως προς κορυφές. Αποδείξτε ότι το Γ είναι δισυνεκτικό ως προς ακμές.
ΕΓΘΑ 4.1 : Αφού το Γ είναι δισυνεκτικό ως προς κορυφές, για οποιεσδήποτε διαφορετικές κορυφές a, b του Γ θα ισχύει a Rκ b . Δηλαδή, υπάρχουν δύο (διαφορετικά) μονοπάτια με αρχή την a και τέλος τη b , χωρίς κοινές κορυφές εκτός από τις a, b . Αυτά τα μονοπάτια δεν έχουν κοινές ακμές, αφού τα άκρα μίας κοινής ακμής θα ήταν κοινές κορυφές των δύο μονοπατιών. Επομένως θα ισχύει a Rι b , που σημαίνει ότι το Γ είναι δισυνεκτικό ως προς ακμές -- βλέπε ΕΓΘΑ 4.2.
5 Το Γ έχει m ακμές, n κορυφές, και ακριβώς δύο συνεκτικές συνιστώσες. Αποδείξτε ότι: m n2 .
Έστω Gj = (Vj , Ej) , j = 1, 2 , οι συνεκτικές συνιστώσες του γραφήματος Γ = (V, E) . Κάθε Gj είναι συνεκτικό, οπότε |Ej| |Vj| 1 , j = 1, 2 (1) (από ΕΓΘΑ Πρόταση 2.4.3. ii ). Τα σύνολα Vj διαμερίζουν τις κορυφές του Γ – ΕΓΘΑ 2.3 – οπότε
n = j = 1, 2 |Vj| (2)
Τα σύνολα Ej διαμερίζουν τις κορυφές του Γ – ΕΓΘΑ 2.3 και Ασκήσεις 2.5, 2 – οπότε
m = j = 1, 2 |Ej| (3)
Aντικαθιστώντας στην (3) το |Ej| βάσει της (1) και χρησιμοποιώντας την (2) , έχουμε
-
m j = 1, 2 (|Vj| 1) = ( j = 1, 2 |Vj|) 2 = n 2 .
-
6 Αποδείξτε ότι:
-
Η σχέση P = { (u, v) : u+v = 0 } πάνω στο σύνολο των ακέραιων αριθμών, είναι συμμετρική. Η σχέση Q = { (u, v) : u+v = 3 } πάνω στο σύνολο των θετικών ακέραιων αριθμών, δεν είναι μεταβατική.
Μια σχέση R πάνω σε ένα σύνολο Α ονομάζεται συμμετρική αν:
όταν ισχύει x R y , θα ισχύει και y R x – βλέπε ΕΓΘΑ 1.2.
Όταν ισχύει x P y για δύο ακέραιους αριθμούς x , y , θα έχουμε x+y = 0 . Άρα y+x = 0 , οπότε θα ισχύει και y P x . Eπομένως η σχέση P είναι συμμετρική, πάνω στο σύνολο των ακέραιων αριθμών. Μια σχέση R πάνω σε ένα σύνολο Α ονομάζεται μεταβατική αν:
όταν ισχύει x R y και y R z , θα ισχύει και x R z – βλέπε ΕΓΘΑ 1.2.
Έστω η τριάδα θετικών ακέραιων x=1 , y=2 , z=1 : Bλέπουμε ότι x+y = 3 και y+z = 3 , άρα ισχύει x Q y και y Q z . Όμως x+z 3 , άρα δεν ισχύει x Q z : η τριάδα x=1 , y=2 , z=1 είναι αντιπαράδειγμα για την μεταβατικότητα της Q , πάνω στο σύνολο των θετικών ακέραιων αριθμών.
- 7 α Αποδείξτε ότι: Κάθε διαδρομή που είναι μονοπάτι, είναι και ανοιχτό ίχνος. β Στο κατευθυνόμενο γράφημα του σχήματος, βρείτε ένα ανοιχτό ίχνος
που να μην είναι μονοπάτι.
α ΕΓΘΑ 2.2 : Ονομάζουμε μονοπάτι ένα ίχνος που δεν επαναλαμβάνει κορυφές (οι όροι της ακολουθίας που είναι κορυφές είναι διαφορετικοί μεταξύ τους).
Άρα, κάθε μονοπάτι είναι ίχνος με διαφορετικά άκρα, δηλαδή είναι ανοιχτό ίχνος.
β Η διαδρομή (1 , (1,3) , 3 , (3,2) , 2 , (2,1) , 1 , (1, 2) , 2) είναι ανοιχτό ίχνος -- τα άκρα της είναι διαφορετικά, και δεν επαναλαμβάνει ακμή. Η διαδρομή δεν είναι μονοπάτι, αφού επαναλαμβάνονται οι κορυφές 1 και 2.
- 8 Για το κατευθυνόμενο γράφημα του παραπάνω σχήματος: α Βρείτε άν είναι ισχυρά συνεκτικό.
β Βρείτε ένα υπογράφημα που να είναι ισχυρά συνεκτικό, αλλά να μήν είναι ισχυρά συνεκτική συνιστώσα .
α ΕΓΘΑ 4.3 : Ένα γράφημα είναι ισχυρά συνεκτικό αν, για οποιεσδήποτε διαφορετικές κορυφές a , b , υπάρχουν δύο μονοπάτια: ένα με αρχή την a και τέλος τη b , και ένα με αρχή τη b και τέλος την a. Στο γράφημα του παραπάνω σχήματος δεν υπάρχει μονοπάτι με τέλος την κορυφή 0 (καμμία ακμή δεν καταλήγει εκεί). Άρα το γράφημα δεν είναι ισχυρά συνεκτικό.
β Έστω F το υπογράφημα που αποτελείται από τις κορυφές και τις ακμές της κλειστής διαδρομής δ = (1 , (1,3) , 3 , (3,2) , 2 , (2,1) , 1) . Το F είναι ισχυρά συνεκτικό, αφού κάθε κορυφή του είναι προσβάσιμη από κάθε άλλη μέσω της δ .
Το F δεν είναι ισχυρά συνεκτική συνιστώσα: Άν προστεθεί στο F μόνο η ακμή (1, 2) παραμένει ισχυρά συνεκτικό. Αυτό αντιφάσκει με τον ορισμό της ισχυρά συνεκτικής συνιστώσας ( ΕΓΘΑ 4.3.)