Έχουμε μια συγκέντρωση $n\geq3$ ατόμων, στην οποία κάθε άτομο γνωρίζεται με τουλάχιστον άλλα n/2 άτομα. Το θεώρημα του Dirac λέει ότι σε αυτήν την περίπτωση μπορούμε να καθίσουμε όλους σε ένα κυκλικό τραπέζι ώστε κάθε άτομο να γνωρίζει και τους δύο που κάθονται δίπλα του.
(Το πρόβλημα υποθέτει ότι η σχέση γνωριμίας είναι συμμετρική. Αν o A γνωρίζει τον B τότε και ο B γνωρίζει τον A.)
Ο Dirac από τον οποίο πήρε το όνομα αυτό το θεώρημα είναι ο Gabriel Andrew Dirac, θετός γιος του διάσημου θεωρητικού φυσικού Paul Dirac.
Διαβάστε περισσότερα εδώ.
Δεν υπάρχουν σχόλια:
Δημοσίευση σχολίου