💍 Το Θεώρημα Γάμου του Hall: Πότε υπάρχει τέλειο ταίριασμα;

Φανταστείτε \(n\) γυναίκες και \(n\) άνδρες. Κάθε γυναίκα δηλώνει ποιοι από τους άνδρες θα ήταν αποδεκτοί ως σύζυγοι.

Μπορούμε άραγε να πραγματοποιήσουμε τους γάμους έτσι ώστε κάθε γυναίκα να παντρευτεί έναν άνδρα από τη λίστα της και κανένας άνδρας να μην παντρευτεί δύο γυναίκες;

Το ερώτημα ακούγεται σαν γρίφος αντιστοίχισης. Στην πραγματικότητα οδηγεί σε ένα από τα θεμελιώδη θεωρήματα της Συνδυαστικής: το Θεώρημα Γάμου του Hall.

📌 Το Θεώρημα του Hall

Έστω ότι η \(i\)-οστή γυναίκα έχει ως αποδεκτούς άνδρες ένα σύνολο \(W_i\).

Υπάρχει αντιστοίχιση κάθε γυναίκας με διαφορετικό άνδρα από τη λίστα της αν και μόνο αν κάθε σύνολο \(X\) γυναικών, συνολικά, έχει στη διάθεσή του τουλάχιστον \(|X|\) διαφορετικούς άνδρες.

🤔 Γιατί είναι αναγκαία αυτή η συνθήκη;

Ας πάρουμε, για παράδειγμα, οποιεσδήποτε \(5\) γυναίκες.

Αν όλες μαζί έχουν στις λίστες τους μόνο \(4\) διαφορετικούς άνδρες, τότε είναι αδύνατον να βρούμε διαφορετικό σύντροφο για καθεμία.

Κάποιος άνδρας θα έπρεπε αναγκαστικά να χρησιμοποιηθεί δύο φορές.

🚫 \(5\) γυναίκες και μόνο \(4\) διαθέσιμοι άνδρες σημαίνει ότι τέλεια αντιστοίχιση δεν μπορεί να υπάρξει.

Αυτό είναι εύκολο να το δούμε.

Η μεγάλη έκπληξη του θεωρήματος είναι το αντίστροφο.

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

🔗 Η γλώσσα της Θεωρίας Γραφημάτων

Η ιστορία με τους γάμους είναι απλώς ένας εύληπτος τρόπος να περιγράψουμε ένα μαθηματικό πρόβλημα.

Κατασκευάζουμε ένα διμερές γράφημα. Στη μία πλευρά τοποθετούμε τις γυναίκες και στην άλλη τους άνδρες. Ενώνουμε μια γυναίκα με έναν άνδρα όταν εκείνος ανήκει στη λίστα των επιλογών της.

Αν \(X\) είναι ένα σύνολο κορυφών της πρώτης ομάδας, συμβολίζουμε με \(N(X)\) το σύνολο όλων των γειτόνων τους.

Τότε η συνθήκη του Hall γράφεται εξαιρετικά συμπυκνωμένα:

\[ \boxed{|N(X)|\ge |X|} \]

για κάθε υποσύνολο \(X\).

Και αυτή η μία ανισότητα χαρακτηρίζει ακριβώς την ύπαρξη της ζητούμενης αντιστοίχισης.

🧩 Ένα μικρό παράδειγμα

Ας έχουμε τρεις γυναίκες \(A,B,C\) και τρεις άνδρες \(1,2,3\), με επιλογές:

\[ A:\{1,2\},\qquad B:\{2,3\},\qquad C:\{1,3\}. \]

Καμία γυναίκα δεν περιορίζεται σε έναν κοινό μοναδικό άνδρα και κάθε ομάδα γυναικών έχει αρκετούς συνολικά διαθέσιμους άνδρες.

Μια δυνατή αντιστοίχιση είναι:

\[ A\longrightarrow1,\qquad B\longrightarrow2,\qquad C\longrightarrow3. \]

❤️ Όλοι αντιστοιχίστηκαν και κανένας άνδρας δεν χρησιμοποιήθηκε δύο φορές.

🔢 Το ίδιο πρόβλημα μέσα σε έναν πίνακα

Η δεξιά πλευρά της εικόνας παρουσιάζει ένα φαινομενικά διαφορετικό αποτέλεσμα: το Θεώρημα Frobenius–König.

Έστω ένας τετραγωνικός πίνακας \(n\times n\), τα στοιχεία του οποίου είναι μόνο \(0\) και \(1\).

Αναζητούμε \(n\) μονάδες έτσι ώστε να υπάρχει ακριβώς μία σε κάθε γραμμή και μία σε κάθε στήλη.

Αυτές οι μονάδες σχηματίζουν έναν πίνακα μεταθέσεως.

🔍 Με άλλα λόγια: θέλουμε να επιλέξουμε \(n\) θέσεις με τιμή \(1\), χωρίς δύο από αυτές να βρίσκονται στην ίδια γραμμή ή στην ίδια στήλη.

📐 Το Θεώρημα Frobenius–König

Το θεώρημα της εικόνας λέει ότι ένας πίνακας \(0\)-\(1\) τάξης \(n\) περιέχει έναν τέτοιο πίνακα μεταθέσεως ανάμεσα στα μη μηδενικά στοιχεία του αν και μόνο αν δεν υπάρχει υποπίνακας μηδενικών διαστάσεων

\[ r\times s \]

για τον οποίο

\[ \boxed{r+s>n}. \]

Ένας αρκετά μεγάλος ορθογώνιος «όγκος» μηδενικών αποτελεί δηλαδή εμπόδιο στην πλήρη επιλογή των μονάδων.

💡 Δύο θεωρήματα ή η ίδια ιδέα;

Εδώ βρίσκεται το πιο όμορφο σημείο της εικόνας.

Το Θεώρημα Γάμου του Hall και το Θεώρημα Frobenius–König μοιάζουν αρχικά να μιλούν για εντελώς διαφορετικά πράγματα:

💍 το ένα μιλά για αντιστοιχίσεις,
🔢 το άλλο για μηδενικά και μονάδες σε πίνακες.

Στην πραγματικότητα όμως περιγράφουν δύο διαφορετικές όψεις του ίδιου συνδυαστικού προβλήματος.

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

Τότε η επιλογή μιας μονάδας από κάθε γραμμή και κάθε στήλη αντιστοιχεί ακριβώς σε μια τέλεια αντιστοίχιση.

💍 Αντιστοίχιση ανθρώπων
↕
🔗 Τέλεια αντιστοίχιση σε διμερές γράφημα
↕
🔢 Επιλογή ενός \(1\) από κάθε γραμμή και στήλη

📜 Λίγη ιστορία

Το Θεώρημα Γάμου συνδέεται με τον Βρετανό μαθηματικό Philip Hall, ο οποίος δημοσίευσε το σχετικό αποτέλεσμα το 1935.

Η αντίστοιχη θεωρία για πίνακες συνδέεται με τα έργα των Dénes Kőnig και Georg Frobenius στις αρχές του 20ού αιώνα.

🌟 Η μεγάλη ιδέα

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

📚

Έρχεται το πολλαπλό βιβλίο ΝΕΟ — βρες όλες τις επιλογές εδώΠολλαπλό βιβλίο ΝΕΟ — 437 βιβλία σε PDF

PDF & Ψηφιακά Μαθησιακά Αντικείμενα — χωρίς εγγραφή • Portify

📚 437 βιβλία🎬 22.000+ Ψηφιακά Μαθησιακά Αντικείμενα

Δες τα βιβλία →