Teoria grafów: zadania z rozwiązaniami krok po kroku

1Wierzchołki, krawędzie i stopnie

Graf składa się z wierzchołków (punktów) i krawędzi (linii łączących dwa wierzchołki). W grafie prostym nie ma pętli ani krawędzi wielokrotnych.

Stopień wierzchołka to liczba krawędzi, które się w nim stykają. Każda krawędź ma dwa końce, więc dodaje 1 do stopnia każdego z nich. Daje to lemat o uściskach dłoni:

Dwa wnioski: suma stopni jest zawsze parzysta, a liczba wierzchołków o nieparzystym stopniu też jest parzysta.

• Graf pełny K_n łączy każdą parę: n(n − 1)/2 krawędzi.
• Pełny graf dwudzielny K_m,n łączy każdy wierzchołek jednej strony z każdym wierzchołkiem drugiej: m·n krawędzi.
• Graf k-regularny o n wierzchołkach ma n·k/2 krawędzi.

Macierz sąsiedztwa ma 1 na pozycji (i, j), gdy i oraz j są połączone. Dla grafu nieskierowanego jest symetryczna, suma wiersza to stopień, a element (i, j) macierzy Mᴸ zlicza marsze o długości L z i do j.

2Euler i Hamilton

Cykl Eulera przechodzi każdą krawędź dokładnie raz i wraca do początku. Ścieżka Eulera przechodzi każdą krawędź raz, ale może skończyć się gdzie indziej. Dla grafu spójnego:

• wszystkie stopnie parzyste: istnieje cykl Eulera;
• dokładnie dwa stopnie nieparzyste: istnieje ścieżka Eulera, od jednego wierzchołka nieparzystego do drugiego;
• więcej niż dwa stopnie nieparzyste: ani jedno, ani drugie.

Cykl Hamiltona odwiedza każdy wierzchołek dokładnie raz. Nie ma prostego testu stopni dla niego. W K_n jest (n − 1)!/2 różnych cykli Hamiltona: ustal początek, uporządkuj pozostałe n − 1 wierzchołków i podziel przez 2 ze względu na dwa kierunki.

3Drzewa

Drzewo to graf spójny bez cykli. Każde drzewo o n wierzchołkach ma dokładnie n − 1 krawędzi. Dodanie dowolnej krawędzi tworzy cykl; usunięcie dowolnej krawędzi rozspójnia graf.

Las złożony z c drzew o n wierzchołkach ma n − c krawędzi. Graf spójny o m krawędziach zachowuje drzewo rozpinające po usunięciu m − n + 1 krawędzi.

Lemat o uściskach dłoni zlicza liście: Σ deg = 2(n − 1). Krótka postać to L = 2 + Σ (d − 2) po wierzchołkach o stopniu d ≥ 3. Drzewo z dwoma wierzchołkami stopnia 3 i resztą liści ma 2 + 1 + 1 = 4 liście.

4Dijkstra i minimalne drzewa rozpinające

Algorytm Dijkstry znajduje najkrótsze odległości od wierzchołka startowego w grafie z wagami nieujemnymi.

1. Nadaj wierzchołkowi startowemu odległość 0, a każdemu innemu ∞.
2. Zatwierdź niezatwierdzony wierzchołek o najmniejszej odległości; jego odległość jest już ostateczna.
3. Dla każdego sąsiada v zaktualizuj d(v) = min(d(v), d(u) + w(u, v)).
4. Powtarzaj, aż wierzchołek docelowy zostanie zatwierdzony.

Minimalne drzewo rozpinające łączy wszystkie wierzchołki przy najmniejszej łącznej wadze. Kruskal sortuje krawędzie od lekkich do ciężkich i bierze każdą, chyba że zamyka cykl. Prim rozbudowuje jedno drzewo od wierzchołka startowego, zawsze dodając najlżejszą krawędź wychodzącą z niego. Oba kończą po n − 1 krawędziach.

5Typowe błędy

• Zapomnienie o podzieleniu sumy stopni przez 2, by dostać liczbę krawędzi.
• Sprawdzanie istnienia cyklu Eulera bez upewnienia się, że graf jest spójny.
• Zatwierdzenie wierzchołka w algorytmie Dijkstry, zanim ma najmniejszą tymczasową odległość.
• Branie n − 1 najlżejszych krawędzi bez sprawdzania cykli.
• Liczenie cykli Hamiltona w K_n jako n! zamiast (n − 1)!/2.

6Jak wyglądają zadania egzaminacyjne

• Łatwe: stopnie i krawędzie. Używasz lematu o uściskach dłoni, liczysz krawędzie grafów K_n, K_m,n, regularnych i drzew, odczytujesz macierz sąsiedztwa albo klikasz wierzchołek o danym stopniu.
• Średnie: ścieżki Eulera i drzewa. Rozstrzygasz, czy graf ma cykl lub ścieżkę Eulera, liczysz liście drzewa, liczysz krawędzie do usunięcia dla drzewa rozpinającego albo liczysz cykle Hamiltona w K_n.
• Trudne: najkrótsze ścieżki i drzewa rozpinające. Wykonujesz algorytm Dijkstry, znajdujesz wierzchołek zatwierdzony w danej rundzie, wyznaczasz wagę minimalnego drzewa rozpinającego, klikasz krawędź, którą Kruskal lub Prim doda jako następną, albo liczysz marsze za pomocą macierzy sąsiedztwa.