| More

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

Views: 7 Downloads: 4
Α. Αρχοντάκη, M. Διονυσίδου, X. Κατσούλης, M. Μανιάτης, A. Μίτσης, X. Μωραϊτης, A. Ναυπλιώτου, Γ. Νιάρχου, Δ. Ξαγοράρη

Abstract


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


Keywords


graphs;algorithms

Full Text:

PDF

References


Phillip Hall, On Representatives of subsets, J. London Math, Soc., 10 (1): 26-30, 1935.

Grade 6 Math Circles, Graph Theory, Centre for Education in Mathematics and Computing, University of Waterloo, Canada:

http://www.cemc.uwaterloo.ca/events/mathcircles/2015-16/Fall/Junior6_Nov18.pdf

K.M. Koh, F.M. Dong, E.G. Tay, Graphs and Their Applications , Mathematical Medley I Volume 33 No. 2, December 2006.

Susie Jameson, Edexcel AS and A Level Modular Mathematics Decision Mathematics 1 D1 (Edexcel GCE Modular Maths), Pearson.

Maximum matching algorithm σε python, c++, Java: http://www.geeksforgeeks.org/maximum-bipartite-matching/

The Euler Archive, http://eulerarchive.maa.org//pages/E053.html


Refbacks

  • There are currently no refbacks.