gkotsis @ tsiou Fitter, happier, more productive

11Nov/099

match game

Το post αυτό είναι κυρίως αντρικό. Απόδειξη ο τίτλος του post και η αντίστοιχη εικόνα:

amstrad cpc 6128

Audio clip: Adobe Flash Player (version 9 or above) is required to play this audio clip. Download the latest version here. You also need to have JavaScript enabled in your browser.

Στη θεωρία γράφων, υπάρχει αυτό που λέμε bipartite graph. Ένας γράφος με δύο σύνολα κορυφών Α,Β με τις ακμές του γράφου (σύνολο Ε) που ενώνουν μία κορυφή από το Α στο Β.

bg

Αν θεωρήσουμε ότι στο γράφο αυτό βάζουμε ετεροφυλόφιλους μονογαμικούς (η πλειοψηφία δηλαδή…λέμε τώρα) άνδρες (A) και γυναίκες (B) , τότε το πρόβλημα ταιριάσματος αντρόγυνων ανάγεται σε αυτό που ονομάζεται matching, δηλαδή η επιλογή ενός υποσυνόλου από το Ε -χωρίς επανάληψη κορυφών- καλύπτοντας όλες τις κορυφές του συνόλου Α (κάποιες κορυφές του Β θα μείνουν προφανώς ορφανές). Επίσης μπορούμε να θεωρήσουμε ότι από κάθε κορυφή a του συνόλου Α υπάρχει μια ακμή προς κάθε κορυφή b του συνόλου B (complete bipartite graph). Το βάρος της ακμής είναι μεγάλο αν ταιριάζουν, και μικρό αν δεν ταιριάζουν οι δύο άνθρωποι-κορυφές (ανθρωποκορυφή….σαν το john korfa).

Το παραπάνω πρόβλημα λέγεται “maximum weight matching in complete bipartite graphs” στη θεωρία γράφων, και αν δεν κάνω λάθος ο αλγόριθμος τρέχει πολύ γρήγορα, σε χρόνο Ο(W*sqrt(n)), όπου n ο συνολικός αριθμός κορυφών και W το πλήθος των ακμών.

Διαφορές θεωρίας και πράξης:

  • ο αλγόριθμος αυτός μας βρίσκει ταιριάσματα που μεγιστοποιούν το συνολικό βάρος. Έτσι με μεγάλη πιθανότητα αποκλείει επιμέρους matches που έχουν μεγαλύτερο βάρος. Η μαζική ευτυχία δηλαδή προηγείται της ατομικής
  • προφανώς πολλοί επιλέγουν λάθος ανθρώπους, μειώνοντας έτσι το συνολικό βάρος
  • επίσης κάποιοι επιλέγουν να μην έχουν σύντροφο, ίσως γιατί δεν βρίσκουν κάποιον με αρκετά μεγάλο βάρος ή για οποιοδήποτε άλλο λόγο που δε με ενδιαφέρει τώρα

Απορία 1: Πόσο μεγάλη μπορεί να είναι η απόκλιση ανάμεσα στη μαθηματική και πρακτική επίλυση του προβλήματος?
Απορία 2: Προς γυναίκες που ανήκουν στο σετ Β: είναι μαθηματικά βέβαιο ότι -όσο και να το θέλουν- κάποιες ανά πάσα στιγμή θα μένουν στη ψάθα. Δε λέω για εσένα απαραίτητα, αλλά κάποιες θα μείνουν. Άραγε το γνωρίζουν?

ΥΓ: Στην πράξη, το πρόβλημα ίσως να μπορεί να αναχθεί σε θεωρία παιγνίων, γιατί είμαι σίγουρος ότι συμπεριφερόμαστε πιο εγωιστικά. Βέβαια στην πράξη δεν ξέρουμε και το βάρος κάθε ακμής…και βεβαίως ούτε και εγώ ξέρω γιατί έχω γράψει τα παραπάνω

Filed under: she, tsiou Leave a comment
Comments (9) Trackbacks (1)
  1. για τα εκλαικευμένα “μαθηματικα ντέρτια” του admin

    ps αυτες οι αποριες θελουν ποτο ,roccky και φιλους
    οχι κερσορα και μια οθονη απεναντι μας…

  2. Πάρε και αυτή τη θεωρία. Όταν χρησιμοποιούμε μαθηματικα μοντέλα για να ερμηνεύσουμε φαινόμενα της κοινωνικής ζωής που δεν μπορούν να μοντελοποιηθούν εκ φύσεως, α) έχουμε χάσει τη μπάλα, β) μας τυραννάνε και βρίσκουμε τρόπο να τα βάλουμε στα κουτάκια τους και να τα εξηγήσουμε, ακόμα και αν λέμε μαλακίες,
    γ) προσελκύουμε σχόλια από αργόσχολους και τσιμπάει-εύκολα ανθρώπους (η γραφούσα π.χ.).
    Δύο παρατηρήσεις που δεν έχουν να κάνουν με τη θεωρία την οποία τη θεωρώ αβάσιμη εξ αρχής.
    α) Κάνεις την παραδοχή ότι το Α επιλέγει το Β άρα κάποιες γκόμενες θα μείνουν μόνες τους. Αλήθεια? Εγώ ήξερα ότι οι γυναίκες είναι αυτές που πάντα επιλέγουν και με επιβεβαιώνει η ζωή καθημερινά.
    β) Η έκφραση μένω στην ψάθα δεν υπάρχει. Υπάρχει το πεθαίνω στην ψάθα και είναι για τις περιπτώσεις που μένεις στα γεράματα χωρίς λεφτά.
    Αν εννοείς ότι σε κάποια φάση κάποιες γυναίκες καταλήγουν μόνες τους, δεκτό. Σε προκαλώ βέβαια να μου πεις πόσοι από τους άντρες που ξέρεις έχουν συνέχεια γκόμενες. Και για αυτούς μπορώ να σου πω με μεγάλη βεβαιότητα ότι ΔΕΝ γνωρίζουν οτι θα μείνουν μόνοι τους γιατι ως γνωστόν οι άντρες δεν τα πάνε και τόσο καλά με την αντίληψη.

  3. Ανασφαλής φίλη μου,
    Σου απαντάω αντίστοιχα, σχετικά με τις παρατηρήσεις σου:

    Α) Αν κατάλαβες τι έγραψα, δεν έχει νόημα να με ρωτάς αν κάποιες γκόμενες θα μείνουν μόνες τους. Όχι μόνο θα μείνουν, αλλά μένουν ανά πάσα στιγμή – ακόμα και τώρα-. Επίσης διάβασα ξανά το ποστ, και δε βλέπω πουθενά να λέω ότι ο άντρας διαλέγει (ούτε και η γυναίκα). Δε με απασχολεί.
    Β) Θενξ για την ψάθα :-)

     Όσο για το closing παραλήρημά σου σε προκαλώ να διαβάσεις αυτά που με κατηγόρησες στην αρχή, και μετά να δεις αν σε αφορούν.

  4. Όλο-εξυπνάδες φίλε μου, προφανώς ούτε και εσυ διάβασες τι έγραψα :D

    α)Αν υπάρχουν 2 ομάδες, άντρες και γυναίκες, γιατί υπάρχουν μόνο άτομα από το δεύτερο σύνολο που παραμένουν μόνα? Γιατί θεωρείς ότι η πρώτη ομάδα είναι μικρότερη και έχει το δικαίωμα επιλογής, αλλιώς πώς?. Ε εγώ σου λέω ότι αυτό ανατρέπεται από διαδικασίες που συμβαίνουν στην πραγματική ζωή και δεν έχουν σχέση με γράφους και μοντέλα. Και όχι δεν σε ρωτάω τιποτα.
    β)De nada. Αλλά δεν έχω closing παραλήρημα. Η τελευταία παράγραφος είναι για το Β. Και πηγαίνει στο ότι “μένουν στην ψάθα” άτομα και από τις 2 ομάδες και πάλι δεν έχει σχέση με μοντέλα και γράφους. Το γεγονός ότι αναφέρεσαι μόνο στις γυναίκες δεν μπορώ να καταλάβω και απλά σου υποδεικνύω ότι η ζωή άλλα δείχνει. Δεν βλέπω στην απάντησή μου να σε κατηγορώ για κάτι. Και δεν με απασχόλησε να το κάνω :D .

    Επίσης οι χαρακτηρισμοί (ανασφαλής χεχε) χρησιμοποιούνται όταν δεν μπορούμε ή βαριόμαστε να αντικρούσουμε επιχειρήματα και βρίσκουμε έναν εύκολο μπακαλίστικο τρόπο να δημιουργήσουμε εντυπώσεις. Υποψιάζομαι ότι το όλο-εξυπνάδες στην αρχή χτυπάει περισσότερο από ότι έγραψα μετά. Πάρε και ένα σχετικό ωραιότατο ποστ από το οποίο απομονώνω την παρακάτω πρόταση:
    “Ξαφνικά, η συζήτηση από τη δική τους ανεπάρκεια να επιχειρηματολογήσουν θα μετατοπιστεί στη δική μου συμπεριφορά.”

    http://www.greekgastronomer.com/?p=1259

    Άντε τώρα να δουλέψω και λίγο.

  5. 1) προφανώς κάποιος έχει μειωμένη αντίληψη: που γράφω ότι η ομάδα των αντρών έχει δικαίωμα επιλογής? ή έστω από που προκύπτει αυτό? (btw για αυτό το λόγο σε κατηγόρησα ως ανασφαλή)
    2) για το Β δεν έχω κάτι να προσθέσω. τα γράφω στο ποστ

    over and out

  6. 1) Σου απαντώ και γω στο α της προηγούμενης απάντησης από που προκύπτει. Το διάβασες?
    2)Οχι δεν το γράφεις. Και αν διαβάσεις το β της προηγούμενης απάντησης θα δεις τι δε γράφεις.
    Κοινώς διάβασε και μετά.

  7. λοιπον η ολη θεωρια χαλαει στην αρχη.τι σημαινει ετεροφυλλοφιλοι μονογαμικοι.καταρχας ολοι πηδιοντε με ολες και το αναποδο.και δευτερον εχεις δει εσυ καμια γυναικα μόνη.και να μη της κατσει καποιος απ’την ομαδα Α θα πάει με κάποια μόνη απ’την ομάδα Β…

  8. σήμερα έμαθα ότι υπάρχει και το SMP
    (που βέβαια δεν είναι το ίδιο…)


Leave a comment


Anti-Spam Protection by WP-SpamFree

You’re still glowin’, you’re still crowin’