Κατανόηση των Διμερισμάτων στη Θεωρία Γραφημάτων

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

Για παράδειγμα, θεωρήστε ένα γράφημα με 4 κορυφές {a,b,c,d} και χωρίζουμε το σύνολο κορυφών σε δύο μέρη: {a,b} και {CD}. Το γράφημα είναι διμερές επειδή όλες οι ακμές συνδέουν κορυφές από διαφορετικά μέρη.

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