Πίνακας περιεχομένων:
Ορισμός - Τι σημαίνει το Bipartite Graph;
Ένα διδιάστατο γράφημα είναι ένα γράφημα στο οποίο ένα σύνολο κορυφών γραφημάτων μπορεί να χωριστεί σε δύο ανεξάρτητα σύνολα και δεν υπάρχουν γειτονικές δύο κορυφές γραφημάτων μέσα στο ίδιο σετ. Με άλλα λόγια, τα διμερή γραφήματα μπορούν να θεωρηθούν ως ίσα με δύο χρωματιστά γραφήματα. Τα διμερή γραφήματα χρησιμοποιούνται ως επί το πλείστον σε σχέσεις μοντελοποίησης, ειδικά μεταξύ δύο ολόκληρων ξεχωριστών κατηγοριών αντικειμένων.
Ένα διμερές γράφημα είναι επίσης γνωστό ως bigraph.
Η Techopedia εξηγεί το Bipartite Graph
Ένα διδιάστατο γράφημα έχει δύο ομάδες κορυφών, για παράδειγμα τα Α και Β, με την πιθανότητα ότι όταν μια άκρη έχει σχεδιαστεί, η σύνδεση θα πρέπει να μπορεί να συνδεθεί μεταξύ κάθε κορυφής του Α σε οποιαδήποτε κορυφή στο Β. Εάν το γράφημα δεν περιέχει (ο αριθμός των κορυφών στο γράφημα είναι περίεργο), τότε το φάσμα του είναι συμμετρικό. Ο χρωματικός αριθμός, ο οποίος είναι ο ελάχιστος αριθμός χρωμάτων που απαιτούνται για το χρωματισμό των κορυφών χωρίς γειτονικές κορυφές που μοιράζονται τα ίδια χρώματα, πρέπει να είναι μικρότερη ή ίση με δύο στην περίπτωση ενός διμερούς γραφήματος. Όλοι οι τύποι ακυκλικών γραφημάτων (γραφήματα που δεν έχουν κύκλους γραφημάτων), είναι παραδείγματα διμερών γραφημάτων. Ένα κυκλικό γράφημα θεωρείται διμερές εάν όλοι οι κύκλοι που συμμετέχουν είναι ομοιόμορφου μήκους. Σύμφωνα με το θεώρημα χρωματισμού γραμμών Koning, όλα τα διμερή γραφήματα είναι γραφήματα κατηγορίας 1.
Τα διμερή γραφήματα χρησιμοποιούνται ευρέως στη σύγχρονη θεωρία κωδικοποίησης εκτός από το ότι χρησιμοποιούνται σε σχέσεις μοντελοποίησης.
