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

Μεταγραφή των θεμάτων από το αρχείο του eClass «Εξεταση Σεπτ 2017 - Απαντησεις.pdf». Οι απαντήσεις και οι αποδείξεις που υπάρχουν στο ίδιο αρχείο δεν μεταγράφονται εδώ.

Εξεταση Σεπτ 2017 - Απαντησεις.pdf¶

Θεωρία Γραφημάτων και Εφαρμογές - Διακριτά Μαθηματικά ΙΙ Σεπτέμβριος 2017

Όλα τα γραφήματα είναι μη-κατευθυνόμενα, αν δεν αναφέρεται κάτι άλλο.

ΕΓΘΑ : Σ. Κοσμαδάκης, «Εισαγωγή στα Γραφήματα, Θεωρία-Ασκήσεις».

Α1 Έστω τα σύνολα \(S_1 = \{1, 2\}\) και \(S_2 = \{0, 2\}\).

α Είναι η σχέση \(\{ (z, w) \mid z - w = 1 \}\) συμμετρική στο \(S_1\); Είναι συμμετρική στο \(S_2\);

β Είναι η σχέση \(\{ (z, w) \mid z - w = 1 \text{ ή } z - w = -1 \}\) μεταβατική στο \(S_1\); Είναι μεταβατική στο \(S_2\);

Είναι απαραίτητο να εξηγήσετε τις απαντήσεις σας.

Α2 Να αποδειχτεί ότι: οι κορυφές οποιουδήποτε δέντρου μπορούν να διαμεριστούν σε δύο υποσύνολα (διαμερίσματα), έτσι ώστε: κάθε ακμή του δέντρου να έχει τα άκρα της σε διαφορετικά διαμερίσματα. Χρησιμοποιήστε την επαγωγή για τα δέντρα.

Β1 Για κάθε μία από τις παρακάτω προτάσεις, βρείτε αν ισχύει ή δεν ισχύει. Δεν είναι απαραίτητο να εξηγήσετε τις απαντήσεις σας.

1 Για κάθε γράφημα \(G\), η παρακάτω σχέση ανάμεσα στις κορυφές του είναι μεταβατική: \(\{ (u, v) \mid \text{υπάρχει ένα κλειστό ίχνος του } G \text{ που περιέχει τις } u, v \}\).

2 Αν μία ακμή ενός γραφήματος είναι γέφυρα, δεν μπορεί να περιέχεται σε κύκλο.

3 Αν ένα γράφημα περιέχει μία κλειστή διαδρομή, θα περιέχει και κάποιο κύκλο.

4 Κάθε γράφημα με \(n\) κορυφές και \(m\) ακμές, έχει ακριβώς \(m - n + 1\) στοιχειώδεις κύκλους.

Β2 Για κάθε μία από τις παρακάτω προτάσεις, βρείτε ένα γράφημα όπου δεν ισχύει. Είναι απαραίτητο να δικαιολογήσετε επαρκώς τις απαντήσεις σας.

1 Για κάθε γράφημα \(G\), η παρακάτω σχέση ανάμεσα στις κορυφές του είναι μεταβατική: \(\{ (u, v) \mid \text{υπάρχει ένας κύκλος του } G \text{ που περιέχει τις } u, v \}\).

2 Αν ένα γράφημα με \(n\) κορυφές περιέχει κύκλο, θα έχει τουλάχιστον \(n\) ακμές.

3 Αν η σχέση \(\{ (u, v) \mid \text{υπάρχει διαδρομή του } G \text{ από την } u \text{ στη } v \}\) ανάμεσα στις κορυφές ενός κατευθυνόμενου γραφήματος \(G\) είναι συμμετρική: το \(G\) θα είναι ισχυρά συνεκτικό.

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

Γ1 Αποδείξτε τα παρακάτω, χρησιμοποιώντας ιδιότητες από τη θεωρία.

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

2 Αν σε ένα συνεκτικό γράφημα υπάρχουν δύο τουλάχιστον (διαφορετικές) δισυνεκτικές συνιστώσες ως προς ακμές, θα υπάρχει γέφυρα.

3 Αν τα κατευθυνόμενα γραφήματα \(G_1 = (V_1, E_1)\), \(G_2 = (V_2, E_2)\) έχουν (τουλάχιστον μία) κοινή κορυφή και είναι ισχυρά συνεκτικά: το γράφημα \(G = (V_1 \cup V_2, E_1 \cup E_2)\) θα είναι ισχυρά συνεκτικό.

Γ2 Αποδείξτε τα παρακάτω, χρησιμοποιώντας ιδιότητες από τη θεωρία.

1 Αν μία κορυφή \(w\) ενός γραφήματος \(G\) είναι κομβικό σημείο, και το \(G\) δεν έχει γέφυρες: η κορυφή \(w\) θα ανήκει σε δύο τουλάχιστον (διαφορετικές) δισυνεκτικές συνιστώσες ως προς κορυφές.

2 Κάθε συνεκτικό γράφημα με \(n\) κορυφές και \(n+2\) ακμές, περιέχει το πολύ επτά κύκλους.

Λύσεις (🟢 official)

Κατάσταση: 🟢 official Πηγή: eClass μαθήματος, αρχείο «Θέματα Εξετάσεων και Απαντήσεις» (Εξεταση Σεπτ 2017 - Απαντησεις.pdf)

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

Οι λύσεις μεταφέρονται από το αρχείο του eClass όπως είναι, χωρίς αλλαγές.

Εξεταση Σεπτ 2017 - Απαντησεις.pdf¶

Θεωρία Γραφημάτων και Εφαρμογές - Διακριτά Μαθηματικά ΙΙ Σεπτέμβριος 2017¶

Όλα τα γραφήματα είναι μη-κατευθυνόμενα , αν δεν αναφέρεται κάτι άλλο.

ΕΓΘΑ : Σ. Κοσμαδάκης, «Εισαγωγή στα Γραφήματα, Θεωρία-Ασκήσεις».

Α1 Έστω τα σύνολα S1 = {1 , 2} και S2 = {0 , 2} . α Eίναι η σχέση { (z , w) | zw = 1 } συμμετρική στο S1 ; Eίναι συμμετρική στο S2 ;

β Eίναι η σχέση { (z , w) | zw = 1 ή zw = 1 } μεταβατική στο S1 ; Eίναι μεταβατική στο S2 ; Είναι απαραίτητο να εξηγήσετε τις απαντήσεις σας.

α Μια σχέση R πάνω σε ένα σύνολο Α ονομάζεται συμμετρική αν:

όταν ισχύει x R y , θα ισχύει και y R x – βλέπε ΕΓΘΑ 1.2.

Έστω η σχέση Q = { (z , w) | z  w = 1 } πάνω στο S1 = {1 , 2} :

για τα στοιχεία x = 2 , y = 1 του S1 , ισχύει x Q y , αλλά δεν ισχύει y Q x , οπότε αυτή η τριάδα είναι αντιπαράδειγμα για την συμμετρία της Q . Άρα, η Q δεν είναι συμμετρική στο S1.

Έστω η σχέση Q = { (z , w) | z  w = 1 } πάνω στο S2 = {0 , 2} :

η Q είναι κενή στο S2 , οπότε δεν υπάρχει αντιπαράδειγμα για την συμμετρία της Q . Άρα, η Q είναι συμμετρική στο S2.

β Μια σχέση R πάνω σε ένα σύνολο Α ονομάζεται μεταβατική αν:

όταν ισχύει x R y και y R z , θα ισχύει και x R z – βλέπε ΕΓΘΑ 1.2.

Έστω η σχέση Q = { (z , w) | z  w = 1 ή z  w =  1 } πάνω στο S1 = {1 , 2} :

για τα στοιχεία x = 1 , y = 2 , z = 1 του S1 , ισχύει x Q y και y Q z , αλλά δεν ισχύει x Q z , οπότε αυτή η τριάδα είναι αντιπαράδειγμα για την μεταβατικότητα της Q . Άρα, η Q δεν είναι μεταβατική στο S1.

Επίσης, αντιπαράδειγμα για την μεταβατικότητα της Q στο S1 είναι και η εξής τριάδα: x = 2 , y = 1 , z = 2 .

Έστω η σχέση Q = { (z , w) | z  w = 1 ή z  w =  1 } πάνω στο S2 = {0 , 2} :

η Q είναι κενή στο S2 , οπότε δεν υπάρχει αντιπαράδειγμα για την μεταβατικότητα της Q . Άρα, η Q είναι μεταβατική στο S2.

Α2 Να αποδειχτεί ότι: oι κορυφές οποιουδήποτε δέντρου μπορούν να διαμεριστούν σε δύο υποσύνολα (διαμερίσματα), έτσι ώστε: κάθε ακμή του δέντρου να έχει τα άκρα της σε διαφορετικά διαμερίσματα. Χρησιμοποιείστε την επαγωγή για τα δέντρα.

Για την επαγωγή για τα δέντρα, βλέπε ΕΓΘΑ 3.1 .

Εργαζόμαστε όπως για την Πρόταση 3.1.2: αποδεικνύουμε με επαγωγή ότι η ζητούμενη ιδιότητα ισχύει για όλα τα γραφήματα της υπο-κλάσης T(n), για κάθε n≥1.

Aρχική περίπτωση n = 1

Kάθε γράφημα στην Τ(1) έχει μόνο μία κορυφή και καμμία ακμή. Αφού δεν υπάρχουν ακμές ώστε να διαψευστεί το ζητούμενο, ισχύει.

Eπαγωγικό βήμα Έστω ότι το ζητούμενο ισχύει για n = i  1  1. Θα δείξουμε ότι ισχύει για n = i .

Αν το δέντρο G είναι στην Τ(i), i>1, θα είναι G = (V U {a}, E U {{a, b}}) , όπου G  = (V, E) είναι δέντρο της υπο-κλάσης Τ(i  1), και a  V, b є V.

Aπό την επαγωγική υπόθεση, υπάρχει τρόπος να διαμεριστούν οι κορυφές του G  σε δύο υποσύνολα, έστω V1 και V2 , έτσι ώστε: κάθε ακμή του G  να έχει τα άκρα της σε διαφορετικά διαμερίσματα.

Για να διαμερίσουμε τις κορυφές του G : χρησιμοποιούμε τον παραπάνω διαμερισμό των κορυφών του G  , και τοποθετούμε την κορυφή a -- τη μοναδική κορυφή του G που δεν είναι και κορυφή του G  -- στο διαμέρισμα που δεν βρίσκεται η κορυφή b.

Κάθε ακμή του G θα έχει τα άκρα της σε διαφορετικά διαμερίσματα: για τις ακμές του G  αυτό ισχύει λόγω της επαγωγικής υπόθεσης. Για την ακμή {a, b} -- τη μοναδική ακμή του G που δεν είναι και ακμή του G  -- ισχύει επειδή η κορυφή a τοποθετήθηκε στο διαμέρισμα που δεν βρίσκεται η κορυφή b.

Β1 Για κάθε μία από τις παρακάτω προτάσεις, βρείτε άν ισχύει ή δεν ισχύει . Δεν είναι απαραίτητο να εξηγήσετε τις απαντήσεις σας.

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

ΙΣΧΥΕΙ Έστω Q = { (u, v) | υπάρχει ένα κλειστό ίχνος του G που περιέχει τις u , v } η σχέση της εκφώνησης, πάνω στο σύνολο των κορυφών ενός γραφήματος G. Έστω ότι, για τις κορυφές a , b , c του G , ισχύει a Q b και b Q c .

Άν c = a : το κλειστό ίχνος του G που περιέχει τις a , b περιέχει τις a , a -- δηλαδή, περιέχει τις a , c. Άρα ισχύει a Q c .

Άν c  a : γνωρίζουμε -- βλέπε ΕΓΘΑ Πρόταση 4.2.4. -- ότι υπάρχει μία μοναδική δισυνεκτική συνιστώσα ως προς ακμές του G -- έστω Η -- που περιέχει την κορυφή b . Οι κορυφές της Η είναι W = {b} U { u | υπάρχει κλειστό ίχνος που περιέχει τις b , u}. Επειδή έχουμε a Q b και b Q c , οι κορυφές a , c θα ανήκουν στην Η. Γνωρίζουμε -- βλέπε Ορισμός δισυνεκτικής συνιστώσας ως προς ακμές , ΕΓΘΑ 4.2. -- ότι το γράφημα Η είναι δισυνεκτικό ως προς ακμές. Επομένως, υπάρχουν δύο μονοπάτια με αρχή την a και τέλος τη c, χωρίς κοινές ακμές. Άρα ισχύει a Q c .

Σε κάθε περίπτωση ισχύει a Q c , οπότε η σχέση Q είναι μεταβατική στο (τυχαίο) G.

2 Άν μία ακμή ενός γραφήματος είναι γέφυρα, δεν μπορεί να περιέχεται σε κύκλο.

ΙΣΧΥΕΙ Βλέπε ΕΓΘΑ Πρόταση 2.3.1.

3 Άν ένα γράφημα περιέχει μία κλειστή διαδρομή, θα περιέχει και κάποιο κύκλο.

ΔΕΝ ΙΣΧΥΕΙ Ένα γράφημα με ακριβώς μία ακμή e = {a , b}, περιέχει κλειστές διαδρομές -- για παράδειγμα, τις (a, e, b, e, a) , (b, e, a, e, b, e, a, e, b) κοκ -- αλλά δεν περιέχει κύκλο. Βλέπε και ΕΓΘΑ 2.2.

4 Κάθε γράφημα με n κορυφές και m ακμές, έχει ακριβώς mn+1 στοιχειώδεις κύκλους.

ΔΕΝ ΙΣΧΥΕΙ Άν Σε ένα γράφημα που αποτελείται από δύο απομονωμένες κορυφές έχουμε n=2 και m=0 , οπότε m  n+1 =  1 !

H πρόταση ισχύει για τα συνεκτικά γραφήματα και μόνο γι' αυτά. Βλέπε ΕΓΘΑ 3.3.

Β2 Για κάθε μία από τις παρακάτω προτάσεις, βρείτε ένα γράφημα όπου δεν ισχύει . Είναι απαραίτητο να δικαιολογήσετε επαρκώς τις απαντήσεις σας. .
1 Για κάθε γράφημα G, η παρακάτω σχέση ανάμεσα στις κορυφές του είναι μεταβατική: { (u, v) | υπάρχει ένας κύκλος του G που περιέχει τις u , v } .

Έστω Q = { (u, v) | υπάρχει ένας κύκλος του G που περιέχει τις u , v }

η σχέση της εκφώνησης, πάνω στο σύνολο των κορυφών του παρακάτω γραφήματος G:

Ισχύει a Q b και b Q c . Όμως, κάθε κλειστή διαδρομή που περιέχει τις a , c θα επαναλαμβάνει την κορυφή c -- επομένως δεν ισχύει a Q c . Άρα, η σχέση Q δεν είναι μεταβατική στο γράφημα G.

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

Το παρακάτω μη-συνεκτικό γράφημα έχει 4 κορυφές και 3 ακμές, και περιέχει κύκλο.

Σημείωση Κάθε συνεκτικό γράφημα με n κορυφές που περιέχει κύκλο, έχει τουλάχιστον n ακμές (γιατί;)

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

Έστω G ένα γράφημα που αποτελείται από δύο απομονωμένες κορυφές:

Στο γράφημα G δεν υπάρχει διαδρομή μεταξύ των δύο κορυφών του, οπότε το G δεν είναι ισχυρά συνεκτικό.

Επίσης, η σχέση { (u , v) | υπάρχει διαδρομή του G από την u στη v } ανάμεσα στις κορυφές του G είναι κενή, οπότε δεν υπάρχει αντιπαράδειγμα για την συμμετρία της -- άρα, η σχέση είναι συμμετρική.

Ενα άλλο παράδειγμα είναι το γράφημα

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

Έστω G το παρακάτω γράφημα:

Η κορυφή b είναι κομβικό σημείο, επειδή δεν υπάρχει κύκλος που να περιέχει τις ακμές {b, a} και {b, c} -- βλέπε ΕΓΘΑ Πρόταση 2.3.2.

Το G δεν έχει γέφυρες, επειδή κάθε ακμή του περιέχεται σε κάποιο κύκλο -- ΕΓΘΑ Πρόταση 2.3.1. Eπομένως, από την ΕΓΘΑ Πρόταση 4.2.2, το G είναι δισυνεκτικό ως προς ακμές

Γ1 Αποδείξτε τα παρακάτω, χρησιμοποιώντας ιδιότητες από τη θεωρία.

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

Έστω ένα κλειστό ίχνος δ = (a, e, a1, e1,..., an, en, an+1) , όπου an+1 = a , n  1 .

Θεωρούμε το ίχνος δ1 = (a1, e1,..., an, en, an+1) : επειδή an+1 = a  a1 (αλλοιώς η ακμή e θα ήταν βρόχος) υπάρχει μονοπάτι μ με αρχή την a1 και τέλος την an+1 = a , το οποίο προκύπτει με απαλοιφή των επαναλήψεων κορυφών στο δ1 -- βλέπε ΕΓΘΑ Πρόταση 2.2.1.

Από τον τρόπο που γίνεται η απαλοιφή των επαναλήψεων κορυφών, οι ακμές του μ θα είναι και ακμές του ίχνους δ1. Επειδή το δ είναι ίχνος, η ακμή e = {a, a1} δεν εμφανίζεται στο δ1 , οπότε δεν θα εμφανίζεται ούτε στο μονοπάτι μ. Άρα, το μ μαζύ με την ακμή e σχηματίζουν ένα κύκλο.

Σημείωση Άν η κλειστή διαδρομή δ δεν είναι ίχνος, δεν προκύπτει πάντα κύκλος. Βλέπε ΕΓΘΑ Ασκήσεις 2.5, 2.

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

Aπό την ΕΓΘΑ Πρόταση 4.2.4.: Για κάθε κορυφή a ενός συνεκτικού γραφήματος G, υπάρχει μοναδική δισυνεκτική συνιστώσα ως προς ακμές που περιέχει την a, και οι κορυφές της είναι {a} U { u | υπάρχει κλειστό ίχνος που περιέχει τις κορυφές a, u }. Επομένως, άν υπάρχουν δύο διαφορετικές δισυνεκτικές συνιστώσες ως προς ακμές, θα υπάρχουν δύο κορυφές a , b που δεν περιέχονται σε κάποιο κλειστό ίχνος. Aπό την ΕΓΘΑ Πρόταση 4.2.4., θα υπάρχει ακμή e του G τέτοια ώστε: οι κορυφές a, b να μην είναι στην ίδια συνεκτική συνιστώσα του G  e. Oπότε το G  e έχει τουλάχιστον δύο συνεκτικές συνιστώσες, άρα η ακμή e είναι γέφυρα (βλέπε ΕΓΘΑ 2.3.)

3 Άν τα κατευθυνόμενα γραφήματα G1 = (V1 , E1) , G2 = (V2 , E2) έχουν (τουλάχιστον μία) κοινή κορυφή και είναι ισχυρά συνεκτικά: το γράφημα G = (V1V2 , E1E2) θα είναι ισχυρά συνεκτικό.

Έστω a μία κοινή κορυφή των G1 , G2 . Από την ΕΓΘΑ Πρόταση 4.3.4., γνωρίζουμε ότι υπάρχει μοναδική ισχυρά συνεκτική συνιστώσα Η = (W, Κ) του G που περιέχει την a, και οι κορυφές της είναι W = {a} U { u | υπάρχει κλειστή διαδρομή του G που περιέχει τις κορυφές a, u }. Επειδή τα G1 , G2 είναι ισχυρά συνεκτικά (βλέπε ΕΓΘΑ 4.3.) και η a είναι κοινή τους κορυφή, θα έχουμε V1  W και V2  W , άρα V1  V2 = W . Eπειδή κάθε ακμή με άκρα στο W είναι και ακμή της Η, θα έχουμε H = G .

Άρα το G είναι ισχυρά συνεκτική συνιστώσα του G, που σημαίνει ότι είναι ισχυρά συνεκτικό ( ΕΓΘΑ 4.3.)

Γ2 Αποδείξτε τα παρακάτω, χρησιμοποιώντας ιδιότητες από τη θεωρία.

1 Άν μία κορυφή w ενός γραφήματος G είναι κομβικό σημείο, και το G δεν έχει γέφυρες: η κορυφή w θα ανήκει σε δύο τουλάχιστον (διαφορετικές) δισυνεκτικές συνιστώσες ως προς κορυφές.

Από την ΕΓΘΑ Πρόταση 4.1.4. γνωρίζουμε ότι, άν μία ακμή e δεν είναι γέφυρα, υπάρχει μοναδική δισυνεκτική συνιστώσα ως προς κορυφές Η = (W, Κ) που περιέχει την e, και είναι Κ = {e} U { e  | υπάρχει κύκλος που περιέχει τις ακμές e, e  } , W= { u | η u είναι κορυφή κάποιας ακμής στο Κ}.

Επειδή η κορυφή w είναι κομβικό σημείο, από την ΕΓΘΑ Πρόταση 2.3.2. υπάρχουν ακμές e1={w, x} και e2={w, y} , ώστε να μην υπάρχει κύκλος που να περιέχει τις e1 , e2 -- επίσης, από την υπόθεση οι ακμές e1 , e2 δεν είναι γέφυρες.

Έστω Η1 = (W1, Κ1) , Η2 = (W2, Κ2) οι δισυνεκτικές συνιστώσες ως προς κορυφές που περιέχουν τις e1 , e2 αντίστοιχα. Επειδή e1  Κ1 θα έχουμε w  W1 -- αντίστοιχα, w  W2 . Επειδή δεν υπάρχει κύκλος που να περιέχει τις e1 , e2 , θα έχουμε e1  Κ2 και e2  Κ1 , που σημαίνει ότι οι Η1 , Η2 είναι διαφορετικές δισυνεκτικές συνιστώσες ως προς κορυφές.

2 Κάθε συνεκτικό γράφημα με n κορυφές και n+2 ακμές, περιέχει το πολύ επτά κύκλους.¶

Σε οποιοδήποτε γράφημα, κάθε κύκλος είναι είτε στοιχειώδης είτε το άθροισμα κάποιων στοιχειωδών κύκλων – βλέπε ΕΓΘΑ Πρόταση 3.3.1. Άρα, οι μόνοι δυνατοί κύκλοι είναι οι τρείς στοιχειώδεις, και όποια από τα αθροίσματά τους είναι κύκλοι.

Οι στοιχειώδεις κύκλοι – ΕΓΘΑ 3.3 – είναι όσες οι χορδές του γραφήματος ως προς κάποιο δέντρο επικάλυψης, δηλαδή (n+2)  n  1) = 3.

Τα (διαφορετικά μεταξύ τους) αθροίσματα στοιχειωδών κύκλων είναι: τρία αθροίσματα δύο κύκλων, και ένα άθροισμα τριών κύκλων. Συνολικά, οι δυνατοί κύκλοι είναι το πολύ 3+3+1 = 7 .

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

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