Θεώρημα Γάμου (Hall's Marriage Theorem)

Συντονιστής: Demetres

Απάντηση
Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 9010
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:
Επικοινωνία Demetres

Θεώρημα Γάμου (Hall's Marriage Theorem)

#1

Μη αναγνωσμένη δημοσίευση από Demetres »

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

Θεώρημα Γάμου: Έστω διμερές γράφημα με μέρη A και B. Τότε υπάρχει ένα πλήρες ταίριασμα από το A στο B αν και μόνο αν για κάθε υποσύνολο S του A έχουμε |N(S)| \geqslant |S|.

Υπενθύμιση ορολογιών
Το G είναι διμερές γράφημα με μέρη A και B αν κάθε κορυφή του G ανήκει σε ακριβώς ένα από τα A,B και κάθε ακμή του G έχει την μία κορυφή της στο A και την άλλη στο B.

Ένα ταίριασμα (matching) είναι ένα σύνολο ακμών οι οποίες δεν έχουν κοινές κορυφές.

Ένα πλήρες ταίριασμα (complete matching) από το A στο B είναι ένα ταίριασμα το οποίο για κάθε κορυφή a του A έχει μία ακμή της οποίας το ένα άκρο της είναι το a.

Για ένα υποσύνολο κορυφών S ενός γραφήματος G το N_G(S) = N(S) είναι το σύνολο όλων των κορυφών οι οποίες είναι γειτονικές σε τουλάχιστον μία κορυφή του S.

Επίσης για ένα υποσύνολο κορυφών C γράφουμε N_C(S) για το N(S) \cap C.
Παράδειγμα 1: Έστω A = \{1,2,3\},B=\{4,5,6\} και ότι οι ακμές του G είναι οι 14,15,24,26,36. (Γράφουμε 14 αντί του πιο σωστού \{1,4\}.)

Τότε: \displaystyle{N(\emptyset) = \emptyset, N(1) = \{4,5\}, N(2) = \{4,6\}, N(3) = \{6\}, N(1,2) = \{4,5,6\}, N(1,3) = \{4,5,6\}, N(2,3) = \{4,6\}, N(1,2,3) = \{4,5,6\}}.
Επειδή |N(S)| \geqslant |S| για κάθε S τότε έχουμε ένα πλήρες ταίριασμα. Πράγματι έχουμε το ταίριασμα 15,24,36.

Παράδειγμα 2: Όπως στο Παράδειγμα 1 αλλά αγνοώντας την ακμή 24.

Τώρα είναι N(2,3) = \{6\} άρα δεν μπορούμε να έχουμε πλήρες ταίριασμα.

Απόδειξη:
Το «μόνο αν» είναι προφανές αφού αν έχουμε ένα πλήρες ταίριασμα, για κάθε υποσύνολο S του A, μόνο από τις ακμές του ταιριάσματος βλέπουμε ότι |N(S)| \geqslant |S|.

Για το «αν» προχωράμε με επαγωγή στο |A|. Για |A| = 1 είναι προφανές. Έστω λοιπόν ότι |A| = n και ότι το θεώρημα ισχύει για κάθε k < n.

Υποθέτουμε πρώτα ότι για κάθε υποσύνολο S του A με 0 < |S| < n ισχύει η ισχυρότερη συνθήκη |N(S)| \geqslant |S| + 1. Παίρνουμε οποιαδήποτε κορυφή a του A και την ταιριάζουμε με μια κορυφή b του B. (Μπορούμε να το κάνουμε αφού |N(a)| \geqslant 2.) Κοιτάμε τώρα το διμερές γράφημα G' που λαμβάνεται από το G αν αφαιρέσουμε τις κορυφές a και b. Έστω A' = A \setminus \{a\}. Για κάθε μη κενό υποσύνολο S του A' έχουμε |N_G(S)| \geqslant |S|+1 και άρα |N_{G'|(S)| \geqslant |S|. Από την επαγωγική υπόθεση έχουμε ένα πλήρες ταίριασμα από τα A' στο B' = B \setminus \{b\}. Αυτό το ταίριασμα μαζί με την ακμή ab μας δίνει ένα πλήρες ταίριασμα από το A στο B.

Μένει να ελέγξουμε την περίπτωση όπου υπάρχει ένα υποσύνολο S του A με 0 < |A| < n για το οποίο ισχύει ότι |N(A)| = |A|. Επειδή |S| < n και για κάθε υποσύνολο T του S ισχύει |T| \leqslant N(T), υπάρχει ένα πλήρες ταίριασμα από το S στο B. Ασφαλώς σε αυτό το ταίριασμα το σύνολο των κορυφών του B που χρησιμοποιούνται είναι το N(S).

Κοιτάμε τώρα το διμερές γράφημα G' που λαμβάνεται από το G αν αφαιρέσουμε τις κορυφές των συνόλων S και N(S).

Μένει λοιπόν να βρούμε ένα πλήρες ταίριασμα στο G' από το A' = A \setminus S στο B' = B \setminus N(S). Για κάθε υποσύνολο S' του A \setminus S έχουμε |N_G(S' \cup S)| \geqslant |S' \cup S| = |S'| + |S| και άρα |N_{G'}(S')| \geqslant |S'| αφού όλοι οι γείτονες του S είναι το N(S) το οποίο έχει μέγεθος |S|. Άρα επαγωγικά υπάρχει πλήρες ταίριασμα από το A' στο B' και η απόδειξη ολοκληρώθηκε.
Άλλα παραδείγματα:
viewtopic.php?f=59&t=3004 (Η πρώτη από τις δύο ασκήσεις)
viewtopic.php?f=59&t=19234
viewtopic.php?f=111&t=32362
viewtopic.php?f=111&t=52912
IMC 2011/2/2
Putnam 2012/B3
Ετικέτες:
θεωρία-γραφημάτων
θεώρημα-γάμου
Κορυφή
Απάντηση

Επιστροφή στο “Συνδυαστική-Πιθανότητες (Φοιτητές)”

Μέλη σε σύνδεση

Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 0 επισκέπτες