Loading AI tools
typ grafu zdefiniowany istnieniem pewnej bisekcji wierzchołków Z Wikipedii, wolnej encyklopedii
Graf dwudzielny – graf, którego zbiór wierzchołków można podzielić na dwa rozłączne zbiory tak, że krawędzie nie łączą wierzchołków tego samego zbioru. Równoważnie: graf, który nie zawiera cykli nieparzystej długości. Jeśli pomiędzy wszystkimi parami wierzchołków należących do różnych zbiorów istnieje krawędź, graf taki nazywamy pełnym grafem dwudzielnym lub kliką dwudzielną i oznaczamy gdzie i oznaczają liczności zbiorów wierzchołków[1].
Pojęcie można uogólnić na trzy (graf trójdzielny) i więcej zbiorów.
Grafem dwudzielnym nazywamy trójkę gdzie:
oraz
i są zbiorami wierzchołków, to zbiór krawędzi.
Sformułowane zostało twierdzenie, które pozwala określić, czy graf dwudzielny jest grafem hamiltonowskim.
Niech będzie grafem dwudzielnym i niech:
będzie podziałem wierzchołków
Jeśli ma cykl Hamiltona, to:
Jeśli ma ścieżkę Hamiltona, to wartości i różnią się co najwyżej o 1.
Dla pełnych grafów dwudzielnych zachodzi też implikacja w lewo, tj. jeśli:
to ma cykl Hamiltona.
Jeśli i różnią się co najwyżej o 1, to ma ścieżkę Hamiltona.
Niech oznacza ilość wierzchołków grafu
wyznacza drogę zamkniętą przechodzącą dokładnie raz przez każdy wierzchołek, to
muszą należeć do jednego ze zbiorów podziału, bez straty ogólności załóżmy, że należą one do Ponieważ istnieje krawędź liczba musi być parzysta, a więc wszystkie wierzchołki należą do z czego wynika, że:
W przypadku ścieżki Hamiltona można zastosować podobne wyszukiwanie, zakończyć je na wierzchołku W przypadku, gdy nie jest parzyste, jeden ze zbiorów ma jeden dodatkowy wierzchołek.
Załóżmy jest pełnym grafem dwudzielnym, tj.:
Jeżeli:
to dla każdego „przemiennego” indeksowania wierzchołków wyznacza cykl Hamiltona w Gdy jeden z podziałów, np. jest mniejszy wystarczy wyjść z niego przez
Aby przekonać się, czy dany graf jest dwudzielny, wystarczy użyć algorytmu przeszukiwania grafu (BFS lub DFS) i kolorować wierzchołki (początkowo o kolorze neutralnym) na dwa kolory tak, aby przechodzony wierzchołek miał kolor przeciwny względem poprzednika. Jeśli natrafimy na dwa wierzchołki o tym samym kolorze połączone krawędzią, to graf nie jest dwudzielny. W przeciwnym wypadku graf jest dwudzielny, podział zbioru wierzchołków na rozłączne podzbiory wyznaczają ich kolory.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.