Graph Exer I

Μερικές Απλές Ασκήσεις στις Βασικές Έννοιες της Θεωρίας Γραφημάτων Δημήτρης Φωτάκης Άσκηση 1. Να αποδείξετε ότι το συμπληρωματικό κάθε μη συνεκτικού (συνδεδεμένου, connected) γραφήματος είναι συνεκτικό. Λύση. Έστω μη συνεκτικό γράφημα G(V, E) και έστω u, w δύο οποιεσδήποτε κορυφές του G. Θα πρέπει να δείξω ότι στο συμπληρωματικό γράφημα του G, υπάρχει μονοπάτι μεταξύ των u και w. Αφού το G είναι μη συνεκτικό, θα αποτελείται από περισσότερα του ενός τμήματα. Διακρίνω τις ακόλουθες περιπτώσεις. Περίπτωση 1. Οι κορυφές u και w ανήκουν σε διαφορετικό τμήμα. Τότε η ακμή {u, w} δεν υπάρχει στο γράφημα G (αλλιώς οι δύο κορυφές δεν θα ήταν σε διαφορετικά, αλλά στο ίδιο τμήμα), και επομένως υπάρχει στο συμπληρωματικό του. Περίπτωση 2. Οι κορυφές u και w ανήκουν στο ίδιο τμήμα. Έστω κορυφή v που ανήκει σε διαφορετικό τμήμα από αυτό που ανήκουν οι u και w. Παρατηρώ πάντα υπάρχει μια τέτοια κορυφή v διότι το G είναι μη συνεκτικό και αποτελείται από περισσότερα του ενός τμήματα. Όπως και στην Περίπτωση 1, οι ακμές {u, v} και {v, w} δεν υπάρχουν στο G, και επομένως υπάρχουν στο συμπληρωματικό γράφημα του G. Συνεπώς, στο συμπληρωματικό γράφημα, οι κορυφές u και w συνδέονται μέσω του μονοπατιού uvw. Άσκηση 2. Να αποδείξετε ότι κάθε απλό μη κατευθυνόμενο γράφημα με 11 κορυφές και 53 ακμές δεν έχει κύκλο Euler, αλλά έχει κύκλο Hamilton. Λύση. Το πλήρες γράφημα με 11 κορυφές έχει 55 ακμές. Συνεπώς, κάθε απλό γράφημα με 11 κορυφές και 53 ακμές προκύπτει από το Κ11 με την αφαίρεση δύο ακμών. Για να αποκλείσω την ύπαρξη κύκλου Euler, χρειάζεται να διακρίνω δύο περιπτώσεις: Περίπτωση 1. Οι δύο ακμές που αφαιρέθηκαν από το Κ11 προσπίπτουν στην ίδια κορυφή. Αφού το γράφημα είναι απλό, οι δύο ακμές μπορούν να έχουν μόνο το ένα άκρο τους κοινό. Συνεπώς, το γράφημα με 11 κορυφές και 53 ακμές έχει μία κορυφή

βαθμού 8, δύο κορυφές βαθμού 9, και 8 κορυφές με βαθμό 10. Συνεπώς, δεν μπορεί να έχει κύκλο Euler, αφού περιέχει κάποιες κορυφές με περιττό βαθμό. Περίπτωση 2. Διαφορετικά, το γράφημα με 11 κορυφές και 53 ακμές πρέπει να έχει 4 κορυφές βαθμού 9 και 7 κορυφές βαθμού 10. Και σε αυτή την περίπτωση, το γράφημα δεν μπορεί να έχει κύκλο Euler. Η ύπαρξη κύκλου Hamilton προκύπτει από το Θεώρημα του Ore (το θεώρημα της εκφώνησης του Ερωτήματος 7 της 2ης εργασίας), αφού σε κάθε περίπτωση, το άθροισμα των βαθμών κάθε ζεύγους κορυφών είναι τουλάχιστον 17 > 11. Άσκηση 3. Να αποδείξετε ότι δεν μπορεί να υπάρξει απλό γράφημα με 1. 6 κορυφές με βαθμό 2, 3, 3, 4, 4, και 5 αντίστοιχα. 2. 5 κορυφές με βαθμό 2, 3, 4, 4, και 5 αντίστοιχα. 3. 4 κορυφές με βαθμό 1, 3, 3, και 3 αντίστοιχα. 4. 7 κορυφές με βαθμό 1, 3, 3, 4, 5, 6 και 6 αντίστοιχα. Λύση. (1) Το άθροισμα των βαθμών 2+3+3+4+4+5 = 21 είναι περιττός αριθμός και όχι άρτιος όπως απαιτείται από το Θεώρημα 1.5, σελ. 70, Βιβλίο Μ. Μαυρονικόλα / Άσκηση Αυτοαξιολόγησης 4.7, σελ. 111, Βιβλίο Γ. Βούρου. (2) Σε ένα απλό γράφημα με 5 κορυφές, καμία κορυφή δεν μπορεί να έχει βαθμό μεγαλύτερο του 4. (3) Αφού το γράφημα είναι απλό και έχει μόνο τέσσερις κορυφές, και οι τρεις κορυφές με βαθμό 3 πρέπει να συνδέονται στην τέταρτη κορυφή. Τότε όμως αυτή θα έπρεπε να είχε επίσης βαθμό 3 και όχι 1. (4) Έστω ότι υπήρχε τέτοιο γράφημα. Αφαιρώ την κορυφή βαθμού 1 και την μοναδική ακμή που προσπίπτει σε αυτή. Το αποτέλεσμα είναι ένα γράφημα με 6 κορυφές και τουλάχιστον μία κορυφή με βαθμό 6. Έχουμε εξηγήσει στο (2) ότι τέτοιο γράφημα δεν μπορεί να υπάρξει. Συνεπώς, έχουμε καταλήξει σε άτοπο. Άσκηση 4. Να αποδείξετε ότι κάθε γράφημα περιέχει μία διαδρομή (β. Ορισμό 1.18, Βιβλίο Μ. Μαυρονικόλα) από μια κορυφή u σε μια κορυφή w αν και μόνο αν περιέχει ένα απλό μονοπάτι από τη u στη w. (Βλέπε επίσης Πρόταση 1.2, σελ. 48, Βιβλίο Μ. Μαυρονικόλα για μια επαγωγική διατύπωση της ίδιας ουσιαστικά λύσης). Λύση. Η μία κατεύθυνση είναι προφανής, γιατί κάθε απλό μονοπάτι είναι εξ’ ορισμού διαδρομή. Για την αντίστροφη κατεύθυνση, παρατηρώ ότι αν η διαδρομή μεταξύ u και w δεν αντιστοιχεί σε απλό μονοπάτι, τότε αυτή πρέπει να περιέχει κορυφές που

επαναλαμβάνονται. Όμως, το τμήμα της διαδρομής ανάμεσα σε δύο διαφορετικές εμφανίσεις της ίδιας κορυφής είναι ένας κύκλος (όχι κατ’ ανάγκη απλός). Αφαιρώντας όλους αυτούς τους κύκλους, καταλήγω σε ένα απλό μονοπάτι από τη u στη w. Με απολύτως παρόμοιο τρόπο μπορείτε να αποδείξετε ότι ένα γράφημα περιέχει έναν κύκλο (μία κλειστή διαδρομή) αν και μόνο αν περιέχει έναν απλό κύκλο. Η πρόταση αυτή

είναι

ουσιαστικά

αυτό

που

ζητείται

να

αποδείξετε

στην Άσκηση

Αυτοαξιολόγησης 4.5, Βιβλίο Γ. Βούρου. Άσκηση 5. Να αποδείξετε ότι κάθε κύκλος (κλειστή διαδρομή) είναι η ένωση απλών κύκλων ξένων μεταξύ τους ως προς τις ακμές. Λύση (υπόδειξη). Θεωρήστε το υπογράφημα που προκύπτει αν αφαιρέσουμε όλες τις ακμές του αρχικού γραφήματος που δεν ανήκουν στον κύκλο (κλειστή διαδρομή) που εξετάζουμε. Όλες οι κορυφές του συγκεκριμένου υπογραφήματος έχουν άρτιο βαθμό (και συνεπώς το υπογράφημα περιέχει κύκλο Euler, που φυσικά δεν είναι άλλος από τον αρχικό κύκλο). Τώρα μπορούμε να δουλέψουμε όπως στην απόδειξη του Θεωρήματος 2.19, σελ. 242, Βιβλίο Μ. Μαυρονικόλα, κατεύθυνση (B) προς (C) ή και να εφαρμόσουμε το Θεώρημα 2.19 απευθείας. Άσκηση 6. Είναι δυνατόν ένα γράφημα που περιέχει τουλάχιστον μία ακμή – γέφυρα να έχει κύκλο Hamilton. Τι συμβαίνει με τον κύκλο Euler; Για τον ορισμό της γέφυρας, βλέπε Ερώτημα 4 της 2ης Εργασίας. Να συγκρίνετε αυτή την άσκηση με την Άσκηση Αυτοαξιολόγησης 4.6, Βιβλίο Γ. Βούρου. Λύση. Επειδή η αφαίρεση μιας ακμής – γέφυρας άρει τη συνεκτικότητα του γραφήματος (με άλλα λόγια, κάθε μονοπάτι που συνδέει μια κορυφή στα «δεξιά της γέφυρας» με μία κορυφή στα «αριστερά της γέφυρας» πρέπει να διέρχεται από τη γέφυρα), κάθε κύκλος Hamilton ή κύκλος Euler πρέπει διέρχεται από τη γέφυρα. Αυτό συμβαίνει γιατί ο κύκλος Hamilton διέρχεται από (συνδέει) όλες τις κορυφές του γραφήματος και ο κύκλος Euler διέρχεται από κάθε ακμή του γραφήματος. Όμως, εξ’ ορισμού, μία ακμή – γέφυρα δεν μπορεί να συμμετέχει σε κανένα κύκλο του γραφήματος. Συνεπώς, καταλήξαμε σε άτοπο. Άρα, όταν ένα γράφημα περιέχει τουλάχιστον μία ακμή – γέφυρα, δεν μπορεί να έχει ούτε κύκλο Hamilton ούτε κύκλο Euler.

Είναι ενδιαφέρον να κατανοήσετε γιατί ένα γράφημα που περιέχει τουλάχιστον μία ακμή – γέφυρα δεν μπορεί να έχει όλες τις κορυφές του με άρτιο βαθμό και επομένως να έχει κύκλο Euler. (Υπόδειξη: Χρησιμοποιείστε την Πρόταση 1.11, σελ. 71, Βιβλίο Μ. Μαυρονικόλα, για τα τμήματα του γραφήματος που προκύπτουν από την αφαίρεση της γέφυρας). Άσκηση 6. Ποιος είναι ο μέγιστος αριθμός ακμών που μπορεί να περιέχει ένα απλό διμερές / διχοτομίσιμο γράφημα με κ κορυφές. Λύση. Προφανώς ο μέγιστος αριθμός ακμών συμβαίνει στο πλήρες γράφημα. Αφού όλες οι κορυφές είναι κ, αν το ένα σύνολο κορυφών περιέχει ν κορυφές, το δεύτερο θα περιέχει (κ – ν). Ο συνολικός αριθμός ακμών του Κν,κ–ν είναι ν(κ – ν). Η ποσότητα αυτή μεγιστοποιείται για ν = κ/2 αν το κ είναι άρτιος και για ν = (κ – 1)/2 αν το κ είναι περιττός. Συνεπώς, αν το κ είναι άρτιος, ο μέγιστος αριθμός ακμών είναι κ2 / 4, ενώ αν το κ είναι περιττός, ο μέγιστος αριθμός ακμών είναι (κ2 – 1) / 4. Παρατηρείστε ότι οι αντίστοιχοι αριθμοί είναι πάντα ακέραιοι. Άσκηση 7. Να χαρακτηρίσετε την κλάση των γραφημάτων στα οποία κάθε κύκλος Euler είναι επίσης και κύκλος Hamilton. Λύση. Ένας κύκλος ο οποίος είναι τόσο κύκλος Euler όσο και κύκλος Hamilton πρέπει να διέρχεται από κάθε κορυφή του γραφήματος ακριβώς μία φορά (επειδή είναι κύκλος Hamilton) και από κάθε ακμή του γραφήματος ακριβώς μία φορά (επειδή είναι κύκλος Euler). Αυτό μπορεί να συμβεί μόνο αν το γράφημα είναι ένας απλός κύκλος Cn με n κορυφές και n ακμές (υπενθυμίζουμε ότι ο απλός κύκλος Cn , n ≥ 3, αποτελείται από n κορυφές u1, u2, …, un και n ακμές {u1, u2}, {u2, u3}, …, {un-1, un }, {un, u1}). Συγκεκριμένα, αν το γράφημα περιείχε n + 1 ή περισσότερες ακμές, ο κύκλος Euler δεν θα ήταν κύκλος Hamilton (θα περιείχε περισσότερες από n ακμές και συνεπώς θα διερχόταν από κάποια κορυφή περισσότερες από μία φορές). Αν το γράφημα περιείχε n – 1 ή λιγότερες ακμές, είτε δεν θα περιείχε κανένα κύκλο (θα ήταν δέντρο) είτε δεν θα ήταν συνεκτικό. Σε καμία από τις δύο περιπτώσεις δεν θα είχε ούτε κύκλο Euler ούτε κύκλο Hamilton. Τέλος, το Cn είναι το μοναδικό γράφημα με n κορυφές και n ακμές που περιέχει κύκλο Euler ή / και κύκλο Hamilton. Για το αντίστροφο, είναι προφανές ότι το Cn περιέχει ακριβώς έναν κύκλο ο οποίος είναι τόσο κύκλος Euler όσο και κύκλος Hamilton.