Spisu treści:
Definicja - Co oznacza wykres dwudzielny?
Dwustronny wykres to wykres, na którym zestaw wierzchołków wykresu można podzielić na dwa niezależne zestawy, a żadne dwa wierzchołki wykresu w tym samym zestawie nie sąsiadują ze sobą. Innymi słowy, wykresy dwustronne można uznać za równe dwóm kolorowym wykresom. Dwuczęściowe wykresy są najczęściej używane w modelowaniu relacji, szczególnie między dwiema całymi oddzielnymi klasami obiektów.
Dwustronny wykres jest również znany jako bigraph.
Techopedia wyjaśnia wykres dwudzielny
Dwuczęściowy wykres ma dwa zestawy wierzchołków, na przykład A i B, z możliwością, że po narysowaniu krawędzi połączenie powinno być w stanie połączyć między dowolnym wierzchołkiem A do dowolnego wierzchołka B. Jeśli wykres nie zawiera żadnego cykl nieparzysty (liczba wierzchołków na wykresie jest nieparzysta), wówczas jego widmo jest symetryczne. Liczba chromatyczna, która jest minimalną liczbą kolorów wymaganą do pokolorowania wierzchołków bez sąsiadujących wierzchołków o takich samych kolorach, musi być mniejsza lub równa dwa w przypadku wykresu dwustronnego. Wszystkie typy wykresów acyklicznych (wykresy bez cykli graficznych) są przykładami grafów dwustronnych. Wykres cykliczny jest uważany za dwustronny, jeśli wszystkie zaangażowane cykle są równej długości. Zgodnie z twierdzeniem o kolorowaniu linii Koninga wszystkie wykresy dwudzielne są grafami klasy 1.
Dwuczęściowe wykresy są szeroko stosowane we współczesnej teorii kodowania, oprócz wykorzystywania w modelowaniu relacji.
