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

Abstract

Ας υποθέσουμε ότι θέλουμε να παντρέψουμε πέντε κορίτσια με πέντε αγόρια. Ας υποθέσουμε επίσης ότι ζούμε σε μία μητριαρχική κοινωνία όπου ο λόγος των γυναικών υπερέχει εκείνου των αντρών, οπότε καταγράφουμε τις επιθυμίες μόνο των κοριτσιών. Κάθε αγόρι θα δεχτεί να παντρευτεί όποιο κορίτσι το επιλέξει. Ενδιαφερόμαστε όμως για ένα πλήρες ταίριασμα, δηλαδή, με άλλα λόγια, να παντρέψουμε κορίτσια και αγόρια κατά τις επιθυμίες των κοριτσιών και να μη μείνει κορίτσι (αλλά ούτε και αγόρι) ανύπαντρο. Το πρόβλημα αυτό είναι γνωστό στη βιβλιογραφία ως πρόβλημα του γάμου [1].
Η ύπαρξη ή μη λύσης στο παραπάνω πρόβλημα με τα ως άνω δεδομένα διαπιστώνεται εύκολα. Τι γίνεται όμως, αν τα δεδομένα αυξηθούν, αν ,για παράδειγμα, τα κορίτσια γίνουν 100;
Προβλήματα τέτοιας φύσεως απασχόλησαν τον Phillip Hall, ο οποίος έδωσε θεωρητική απάντηση το 1935 [1] (απέδειξε το πρόβλημα με χρήση μαθηματικής επαγωγής), ενώ οι αλγοριθμικές λύσεις ήρθαν πολύ αργότερα [4] και πλέον υπάρχουν πολλές μεταγραφές σε γλώσσες προγραμματισμού [5].
Στην εργασία αυτή παρουσιάζουμε τις ικανές και αναγκαίες συνθήκες ύπαρξης πλήρους ταιριάσματος σε διμερή γραφήματα μέσα από παραδείγματα και κατασκευάζουμε αλγοριθμικά λύσεις.. Στη συνέχεια, περιγράφουμε τον κώδικα που υλοποιήσαμε στο προγραμματιστικό περιβάλλον του Scratch1, για τις περιπτώσεις όπου το initial matching (που δεν εισάγεται από τον χρήστη, αλλά υπολογίζεται δυναμικά) αφήνει αταίριαστο το πολύ ένα ζευγάρι κορυφών. Θα πρέπει να σημειωθεί ότι στο Scratch δεν μπορούν να οριστούν δυσδιάστατοι πίνακες και pointers, θέτοντας όρια εκ των προτέρων στη συγγραφή κώδικα και, γι’ αυτόν ακριβώς το λόγο η περίπτωσή μας γίνεται πιο πολύπλοκη. Παραμένει, ωστόσο, ένα αξιόλογο εργαλείο εισαγωγής των μαθητών στον κόσμο των αλγόριθμων και του προγραμματισμού.