6.2 Ταιριάσματα σε διμερή γραφήματα

Μια πολύ χρήσιμη έννοια είναι η έννοια του ταιριάσματος σε ένα γράφημα.

Ορισμός 6.2   (Ανεξάρτητες ακμές, Ταιριάσματα) Δύο ακμές λέγονται ανεξάρτητες αν δεν έχουν κοινή κορυφή. Ένα σύνολο ανεξαρτήτων ακμών $M$ σε ένα γράφημα λέγεται ταίριασμα (matching). Αν το γράφημα είναι διμερές με σύνολα κορυφών $A$ και $B$ τότε ένα ταίριασμα $M$ λέγεται πλήρες ταίριασμα του $A$ (ομοίως για το $B$) αν κάθε κορυφή του $A$ περιέχεται σε κάποια ακμή του $M$.

Σχήμα 6.3: Οι ακμές με έντονη γραμμή αποτελούν ταίριασμα

Παράδειγμα 6.2   Στο Σχ. 6.3(a) το σύνολο των ακμών που έχουν σχεδιαστεί έντονα αποτελεί ένα ταίριασμα. Στο Σχ. 6.3(b) έχουμε ένα διμερές γράφημα με ένα ταίριασμα του πλήρες συνόλου κορυφών $A$ (αριστερές κορυφές). Το ταίριασμα αυτό δεν αποτελεί πλήρες ταίριασμα του $B$ αφού η κορυφή 9 του $B$ δεν «καλύπτεται» από ακμή του ταιριάσματος.

Παράδειγμα 6.3   Ας υποθέσουμε ότι έχουμε προκηρύξει κάποιες θέσεις εργασίας $J_1, \ldots, J_n$ και ότι έχουν κάνει αίτηση γι' αυτές κάποιοι υποψήφιοι $C_1, \ldots, C_m$, με $m \ge n$. Δεν έχει κατ' ανάγκην κάνει αίτηση ο κάθε υποψήφιος για όλες τις θέσεις, αλλά κάθε υποψήφιος έχει κάνει αίτηση για κάποιες από τις προσφερόμενες θέσεις. Σκοπός μας είναι να γεμίσουμε όλες τις θέσεις εργασίας. Δε μπορούμε φυσικά να προσλάβουμε για μια θέση εργασίας κάποιον που δεν έχει κάνει αίτηση γι' αυτή. Φτιάχνουμε ένα διμερές γράφημα με σύνολα κορυφών $A={\left\{{J_1,\ldots,J_n}\right\}}$ και $B = {\left\{{C_1,\ldots,C_m}\right\}}$ και βάζουμε μια ακμή ανάμεσα στις κορυφές $J_k$ και $C_l$ αν και μόνο αν ο υποψήφιος $C_l$ έχει κάνει αίτηση για τη θέση $J_k$. Είναι φανερό τώρα ότι μπορούμε να γεμίσουμε όλες τις θέσεις εργασίας αν και μόνο αν υπάρχει πλήρες ταίριασμα του $A$ στο γράφημα αυτό.

Άσκηση 6.11   Αν ένα διμερές γράφημα με σύνολα κορυφών $A$ και $B$ έχει πλήρες ταίριασμα του $A$ τότε ${\left\vert{B}\right\vert} \ge {\left\vert{A}\right\vert}$.

Παρατήρηση 6.3  

Σχήμα 6.4: Ένα σύνολο $X={\left\{{\alpha, \beta, \gamma, \delta, \epsilon, \zeta, \eta}\right\}}$, κάποια υποσύνολά του $A_1, \ldots, A_5$ και το διμερές γράφημα που αντιστοιχεί στο σύστημα αυτό υποσυνόλων του $X$. Αριστερά (ή δεξιά, δεν έχει σημασία, αλλά πάντως στη μια μεριά μόνο) βάζουμε τα ονόματα των υποσυνόλων, δεξιά τα ονόματα των στοιχείων του $X$ ενώνουμε ένα στοιχείο με ένα υποσύνολο αν και μόνο αν το στοιχείο ανήκει στο υποσύνολο.

Έστω ένα πεπερασμένο σύνολο $X$ και σύστημα $A_1,\ldots,A_n$ υποσυνόλων του. Υπάρχει ένας πολύ φυσιολογικός τρόπος να αντιστοιχίσουμε σε αυτό το σύστημα υποσυνόλων ένα διμερές γράφημα:

σύνολο αριστερών κορυφών είναι τα σύνολα $A_1,\ldots,A_n$ και σύνολο δεξιών κορυφών είναι το $X$. Ενώνουμε την αριστερή κορυφή $A_i$ με τη δεξιά κορυφή $x$ αν και μόνο αν $x \in A_i$.

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

Δείτε το Σχήμα 6.4 για παράδειγμα.

Ορισμός 6.3   Σε ένα διμερές γράφημα, για κάθε σύνολο $J$ αριστερών κορυφών, συμβολίζουμε με $N(J)$ το σύνολο όλων των δεξιών κορυφών που ενώνονται με κάποια κορυφή από το $J$.

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

Θεώρημα 6.3   Σε ένα διμερές γράφημα με σύνολα κορυφών $A$ και $B$ υπάρχει πλήρες ταίριασμα του $A$ αν και μόνο αν για κάθε υποσύνολο $J \subseteq A$ ισχύει

$${\left\vert{N(J)}\right\vert} \ge {\left\vert{J}\right\vert}.$$ (6.1)

Απόδειξη. Το Θεώρημα 6.3 αποτελεί ουσιαστικά μια αναδιατύπωση του Θεωρήματος του Γάμου (Θεώρημα 1.5). Φτιάχνουμε από το διμερές μας γράφημα ένα σύστημα υποσυνόλων του $B$, όπως στην Παρατήρηση 6.3. Η συνθήκη του Θεωρήματος 6.3 αποτελεί απλά αναδιατύπωση της συνθήκης (1.21) του Hall. Το γράφημά μας έχει πλήρες ταίριασμα του $A$ αν και μόνο αν το σύστημα υποσυνόλων του $B$ που φτιάξαμε έχει σύστημα ξένων αντιπροσώπων, πράγμα που, σύμφωνα με το Θεώρημα του Γάμου, ισχύει ακριβώς όταν ισχύει η συνθήκη του Hall, δηλ. η συνθήκη που διατυπώνεται στο Θεώρημα 6.3. $\qedsymbol$

Άσκηση 6.12   Σε ένα διμερές γράφημα με σύνολα κορυφών $A$ και $B$ ισχύει

$${\left\vert{N(J)}\right\vert} \ge {\left\vert{J}\right\vert}-5, \forall J \subseteq A.$$

Δείξτε ότι υπάρχει ταίριασμα $M$ που να περιέχει τουλάχιστον ${\left\vert{A}\right\vert}-5$ κορυφές του $A$.

Υπόδειξη: Προσθέστε 5 κορυφές στο σύνολο $B$ και συνδέσετέ τις με όλες τις κορυφές του $A$. Το νέο αυτό διμερές γράφημα τώρα ικανοποιεί τη συνθήκη του Hall (6.1). Αφού χρησιμοποιήσετε το Θεώρημα 6.3 θα πρέπει από το συμπέρασμά σας να «ξεφορτωθείτε» τις παραπανίσιες κορυφές που εισαγάγατε προηγουμένως.

Μια εύκολη συνέπεια του θεωρήματος του Γάμου είναι η εξής:

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

Απόδειξη. Εστω ότι το $G=(A\cup B, E)$ είναι $r$-κανονικό, $r\ge1$. Θα αποδείξουμε ότι ισχύει η υπόθεση του Θεωρήματος 6.3. Εστω $J \subseteq A$ και $E_1$ το σύνολο των ακμών που ξεκινούν από κάποια κορυφή του $J$. Επειδή το $G$ είναι $r$-κανονικό έχουμε ότι ${\left\vert{E_1}\right\vert} = r {\left\vert{J}\right\vert}$.

Εστω επίσης $E_2$ το σύνολο των ακμών που καταλήγουν σε κάποια από τις κορυφές του $N(J)$, δηλ. σε κάποιο από τους γείτονες του $J$. Ξανά έχουμε ${\left\vert{E_2}\right\vert} = r {\left\vert{N(J)}\right\vert}$.

Αλλά προφανώς ισχύει $E_1 \subseteq E_2$. Αρα $r {\left\vert{J}\right\vert} \le r {\left\vert{N(J)}\right\vert}$, το οποίο συνεπάγεται

$${\left\vert{N(J)}\right\vert} \ge {\left\vert{J}\right\vert}.$$

$\qedsymbol$

Άσκηση 6.13   Αν ένα διμερές γράφημα είναι $r$-κανονικό δείξτε ότι έχει $r$ ξένα μεταξύ τους πλήρη ταιριάσματα.

Υπόδειξη: Χρησιμοποιήστε το Πόρισμα 6.1. Αφού βρείτε ένα πλήρες ταίρασμα διαγράψτε όλες τις ακμές του από το γράφημά σας. Τι ιδιότητες έχει το γράφημα που απομένει;

Άσκηση 6.14   Παίρνουμε μια συνηθισμένη τράπουλα (52 φύλλα σε 13 είδη ( $A, 2, 3, \ldots, 10, J, Q, K$), από 4 κάθε είδος ( $\clubsuit, \spadesuit, \heartsuit, \diamondsuit)$), την ανακατεύουμε και την μοιράζουμε σε 13 σωρούς των 4 φύλλων. (Τα περιεχόμενα των σωρών τα βλέπουμε, τα φύλλα δηλ. κοιτάνε προς τα πάνω.)

Δείξτε ότι είναι πάντα δυνατό να επιλέξουμε ένα φύλλο από κάθε σωρό ώστε στο τέλος να έχουμε ένα φύλλο από κάθε είδος.

Υπόδειξη: Φτιάξτε ένα διμερές γράφημα με τους 13 σωρούς αριστερά και τα 13 είδη δεξιά. Βάλτε μια ακμή από ένα σωρό σε ένα είδος αν και μόνο αν το είδος αυτό εμφανίζεται στο σωρό. Δείξτε ότι το διμερές γράφημα έχει πλήρες ταίριασμα και των δύο πλευρών του. Ένα τέτοιο ταίριασμα σας λέει τι είδος να διαλέξετε από κάθε σωρό.