Το θεώρημα του Dirac

Έχουμε μια συγκέντρωση n \geqslant 3 ατόμων, στην οποία κάθε άτομο γνωρίζεται με τουλάχιστον άλλα n/2 άτομα. Το θεώρημα του Dirac λέει ότι σε αυτήν την περίπτωση μπορούμε να καθίσουμε όλους σε ένα κυκλικό τραπέζι ώστε κάθε άτομο να γνωρίζει και τους δύο που κάθονται δίπλα του.

(Το πρόβλημα υποθέτει ότι η σχέση γνωριμίας είναι συμμετρική. Αν o A γνωρίζει τον B τότε και ο B γνωρίζει τον A.)

Ο Dirac από τον οποίο πήρε το όνομα αυτό το θεώρημα είναι ο Gabriel Andrew Dirac, θετός γιος του διάσημου θεωρητικού φυσικού Paul Dirac. Η απόδειξη του θεωρήματος που θα δώσουμε είναι του Louis Pósa ο οποίος και ανακάλυψε αυτήν την απόδειξη στην ηλικία των δεκαπέντε ετών.

Προτού όμως δώσουμε την απόδειξη ας παρατηρήσουμε ότι το φράγμα n/2 δεν μπορεί να βελτιωθεί. Για παράδειγμα αν έχουμε m άνδρες που όλοι γνωρίζονται μεταξύ τους, m γυναίκες που όλες γνωρίζονται μεταξύ τους αλλά κανένας άνδρας δεν γνωρίζει καμιά γυναίκα, τότε έχουμε συνολικά n=2m άτομα όπου το κάθε άτομο γνωρίζει ακριβώς m-1 = n/2 - 1 άλλα άτομα. Όπως όμως και να τους καθίσουμε στο τραπέζι κάποιος άνδρας θα κάθεται δίπλα σε κάποια γυναίκα που δεν θα γνωρίζει. (Το φράγμα δεν μπορεί να βελτιωθεί ούτε στην περίπτωση που έχουμε περιττό αριθμό ατόμων. Η απόδειξη αφήνεται ως άσκηση.)

Ας προχωρήσουμε στην απόδειξη του θεωρήματος. Βάζουμε αρχικά στην σειρά όσα περισσότερα άτομα μπορούμε ώστε ο καθένας να γνωρίζει τους δίπλα του. Έστω ότι η σειρά είναι A_1A_2 \cdots A_k. Σίγουρα ο A_1 γνωρίζει μόνο κάποιους από τους A_2, \ldots , A_k. Διότι αν γνωρίζει κάποιον άλλο που δεν τον έχουμε βάλει ακόμα στην σειρά μπορούμε να το βάλουμε δίπλα του για να μεγαλώσουμε την σειρά. Άρα k \geqslant n/2 + 1. Ομοίως ο A_k γνωρίζει μόνο κάποιους από τους A_1, \ldots , A_{k-1}. Ξέρουμε όμως ότι τόσο ο A_1 όσο και ο A_k γνωρίζουν τουλάχιστον n/2 άτομα. Ισχυριζόμαστε ότι υπάρχει 1 \leqslant i \leqslant k-1 ώστε ο A_k γνωρίζει τον A_i και ο A_1 γνωρίζει τον A_{i+1}. Αυτό είναι άμεση συνέπεια της αρχής της περιστεροφωλιάς. Πράγματι, υπάρχουν τουλάχιστον n/2 δείκτες i ώστε ο A_k γνωρίζει τον A_i και τουλάχιστον n/2 δείκτες i ώστε ο A_1 γνωρίζει τον A_{i+1}. Επειδή όμως υπάρχουν ακριβώς k-1 \leqslant n-1 δείκτες i, κάποιος από αυτούς πρέπει να είναι κοινός και για τους δύο. Μπορούμε τώρα αυτά τα k άτομα να τα καθίσουμε σε ένα κυκλικό τραπέζι με την σειρά A_1 \cdots A_{i-1} A_i A_k A_{k-1} \cdots A_{i+1} όπως φαίνεται και στο πιο κάτω σχήμα.

Αν k=n τότε τελειώσαμε. Ας υποθέσουμε λοιπόν ότι k \neq n. Έστω X το σύνολο των ατόμων που δεν έχουν καθίσει στο τραπέζι. Γνωρίζουμε ότι 1 \leqslant |X| = n-k \leqslant n/2 - 1. Επειδή όμως κάθε άτομο του συνόλου X γνωρίζει τουλάχιστον n/2 άτομα, θα γνωρίζει κάποιον που ήδη κάθεται στο τραπέζι. Αλλά βάζοντας αυτόν πρώτο και κάποιο που γνωρίζει και ο οποίος κάθεται στο τραπέζι δεύτερο μπορούμε να βάλουμε k+1 άτομα στην σειρά ώστε ο κάθε ένας να γνωρίζει τους δίπλα του. Αυτό φυσικά είναι άτοπο αφού υποθέσαμε ότι είχαμε ήδη βάλει στην σειρά όσα περισσότερα άτομα μπορούσαμε. Άρα k=n και όλοι κάθονται στο τραπέζι όπως θέλαμε. \square

Advertisements

About Δημήτρης Χριστοφίδης

Course Leader in Mathematics at UCLan Cyprus.
This entry was posted in 05C45 - Eulerian and Hamiltonian graphs and tagged , . Bookmark the permalink.

2 Responses to Το θεώρημα του Dirac

  1. Ο/Η Petros SilentO λέει:

    Γεια σου μεγάλε Δημήτρη! Δεν τον διάβασα τον Ντίρακ, δύσκολος μωρέ, αλλά διάβασα ένα ανέκδοτο για τον Πόμπο και τα μυρμήγκια του που είχες γράψει κάπου αλλού και σε βρήκα!

Σχολιάστε

Εισάγετε τα παρακάτω στοιχεία ή επιλέξτε ένα εικονίδιο για να συνδεθείτε:

Λογότυπο WordPress.com

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό WordPress.com. Αποσύνδεση / Αλλαγή )

Φωτογραφία Twitter

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Twitter. Αποσύνδεση / Αλλαγή )

Φωτογραφία Facebook

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Facebook. Αποσύνδεση / Αλλαγή )

Φωτογραφία Google+

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Google+. Αποσύνδεση / Αλλαγή )

Σύνδεση με %s