Graf dwudzielny
![]() | Ten artykuł od 2011-04 zawiera treści, przy których brakuje odnośników do źródeł. Należy dodać przypisy do treści niemających odnośników do źródeł. Dodanie listy źródeł bibliograficznych jest problematyczne, ponieważ nie wiadomo, które treści one uźródławiają. Sprawdź w źródłach: Encyklopedia PWN • Google Books • Google Scholar • Federacja Bibliotek Cyfrowych • BazHum • BazTech • RCIN • Internet Archive (texts / inlibrary) Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się w dyskusji tego artykułu. Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu. |
![](http://upload.wikimedia.org/wikipedia/commons/3/3d/Biparite_graph.png)
![](http://upload.wikimedia.org/wikipedia/commons/a/a6/K_3_4.png)
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.
Definicja formalna
Grafem dwudzielnym nazywamy trójkę gdzie:
oraz
i są zbiorami wierzchołków, 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 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.
Dowód
Niech oznacza ilość wierzchołków grafu
- Cykl Hamiltona możemy wyznaczyć, biorąc na przemian wierzchołki leżące w zbiorach i Jeśli:
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
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)
Przypisy
- ↑ Reinhard Diestel: Graph Theory. Nowy Jork: 2000, s. 14–15. ISBN 0-387-95014-1.
- p
- d
- e
Najważniejsze pojęcia |
więcej... |
---|---|
Wybrane klasy grafów |
|
Algorytmy grafowe | |
problemy grafowe | |
Inne zagadnienia |