Graf dwudzielny

Przykładowy graf dwudzielny

Pełny graf dwudzielny $K_{3,4}$

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 $K_{n,m}$ gdzie $n$ i $m$ oznaczają liczności zbiorów wierzchołków.

Pojęcie można uogólnić na trzy (graf trójdzielny) i więcej zbiorów.

Definicja formalna

Grafem dwudzielnym nazywamy trójkę $G(U,V,E)$ gdzie:

$U=\{u_{1},u_{2},\dots ,u_{n}\},$

$V=\{v_{1},v_{2},\dots ,v_{m}\}$

oraz

$E\ \subseteq \ U\ \times \ V.$

$U$ i $V$ są zbiorami wierzchołków, $E$ to zbiór krawędzi.

Warunki wystarczające dla grafu hamiltonowskiego

Sformułowane zostało twierdzenie, które pozwala określić, czy graf dwudzielny jest grafem hamiltonowskim.

Treść twierdzenia

Niech $G$ będzie grafem dwudzielnym i niech:

$V(G)=V_{1}\cup V_{2}$

będzie podziałem wierzchołków $G.$

Jeśli $G$ ma cykl Hamiltona, to:

$|V_{1}|=|V_{2}|.$

Jeśli $G$ ma ścieżkę Hamiltona, to wartości $|V_{1}|$ i $|V_{2}|$ różnią się co najwyżej o 1.

Dla pełnych grafów dwudzielnych zachodzi też implikacja w lewo, tj. jeśli:

$|V_{1}|=|V_{2}|,$

to $G$ ma cykl Hamiltona.

Jeśli $|V_{1}|$ i $|V_{2}|$ różnią się co najwyżej o 1, to $G$ ma ścieżkę Hamiltona.

Dowód

Niech $n$ oznacza ilość wierzchołków grafu $G.$

• Cykl Hamiltona możemy wyznaczyć, biorąc na przemian wierzchołki leżące w zbiorach $V_{1}$ i $V_{2}.$ Jeśli:

$v_{1},v_{2},\dots ,v_{n},v_{1}$

wyznacza drogę zamkniętą przechodzącą dokładnie raz przez każdy wierzchołek, to

$v_{1},v_{3},v_{5},\dots$

muszą należeć do jednego ze zbiorów podziału, bez straty ogólności załóżmy, że należą one do $V_{1}.$ Ponieważ istnieje krawędź $\{v_{n},v_{1}\},$ liczba $n$ musi być parzysta, a więc wszystkie wierzchołki $v_{2},v_{4},\dots ,v_{n}$ należą do $V_{2},$ z czego wynika, że:

$|V_{1}|=|V_{2}|.$

W przypadku ścieżki Hamiltona można zastosować podobne wyszukiwanie, zakończyć je na wierzchołku $v_{n}.$ W przypadku, gdy $n$ nie jest parzyste, jeden ze zbiorów ma jeden dodatkowy wierzchołek.

Załóżmy $G$ jest pełnym grafem dwudzielnym, tj.:

$G=K_{|V_{1}|,|v_{2}|}.$

Jeżeli:

$|V_{1}|=|V_{2}|,$

to dla każdego „przemiennego” indeksowania wierzchołków $v_{1},v_{2},\dots ,v_{n},v_{1}$ wyznacza cykl Hamiltona w $G.$ Gdy jeden z podziałów, np. $V_{1}$ jest mniejszy wystarczy wyjść z niego przez $\{v_{|V_{1}|},v_{|V_{2}|}\}.$

Sprawdzenie dwudzielności

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.

Zobacz też

• klasa grafów
• teoria grafów
• twierdzenie Bondy’ego-Chvátala
• twierdzenie Diraca (1952)
• twierdzenie o liczbie krawędzi
• twierdzenie Ore (1961)