Σήμερα ασχοληθήκαμε με ιδιότητες των μεγίστων ταιριασμάτων σε διμερή γραφήματα. Σ’ ένα διμερές γράφημα δεν υπάρχει εν γένει πλήρες ταίριασμα (μιας πλευράς του) οπότε είναι λογικό να αναζητούμε όσο γίνεται μεγαλύτερα ταιριάσματα.

Δείξαμε κατ’ αρχήν ότι ένα ταίριασμα είναι μέγιστο αν και μόνο αν δεν υπάρχουν επαυξάνοντα μονοπάτια στο γράφημά μας ως προς αυτό το ταίριασμα.

Έπειτα δείξαμε το θέωρημα Konig-Egervary που λέει ότι σ’ένα διμερές γράφημα το ένα μέγιστο ταίριασμα έχει τόσες ακμές όσες κορυφές έχει ένα ελάχιστο κάλυμμα κορυφών (ένα σύνολο κορυφών U λέγεται κάλυμμα αν κάθε ακμή του γραφήματος έχει τουλάχιστον ένα άκρο της στο U).

Τέλος επαναδιατυπώσαμε το Θ. Konig-Egervary στη γλώσσα πινάκων με στοιχεία 0 ή 1.