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)

Linki zewnętrzne

• Szablon:Otwarty dostęp Graph, bipartite Szablon:Lang, Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2024-10-05].