Kolorowanie grafów — liczba chromatyczna i zastosowania

Kolorowanie grafów zwykle oznacza kolorowanie wierzchołków: przypisujemy kolor każdemu wierzchołkowi tak, aby sąsiednie wierzchołki nie miały tego samego koloru. Najmniejsza liczba kolorów, która na to pozwala, to liczba chromatyczna, oznaczana przez $\chi(G)$.

Jeśli chcesz szybkiej intuicji, kolory to po prostu etykiety bez konfliktów. Dwa wierzchołki mogą mieć ten sam kolor dokładnie wtedy, gdy nie ma między nimi krawędzi.

Definicja kolorowania grafów w minutę

W poprawnym kolorowaniu każda krawędź łączy dwa wierzchołki o różnych kolorach. To cała zasada.

Jeśli więc $\chi(G)=3$, to jednocześnie prawdziwe są dwa fakty:

• istnieje poprawne kolorowanie przy użyciu $3$ kolorów
• nie istnieje poprawne kolorowanie przy użyciu tylko $2$ kolorów

Dlatego liczba chromatyczna jest minimum, a nie po prostu liczbą kolorów, których akurat użyto na jednym rysunku.

O ile nie zaznaczono inaczej, kolorowanie grafów na kursie wprowadzającym oznacza kolorowanie wierzchołków prostego grafu nieskierowanego. Kolorowanie krawędzi to inny problem z innymi zasadami.

Co naprawdę mierzy liczba chromatyczna

Nazwy kolorów nie mają znaczenia. Możesz użyć czerwonego, niebieskiego i zielonego albo etykiet $1$, $2$ i $3$.

Liczy się podział na grupy. Wszystkie wierzchołki o tym samym kolorze tworzą zbiór, wewnątrz którego nie ma krawędzi, więc taka grupa nie zawiera konfliktów.

To właśnie sprawia, że kolorowanie grafów jest przydatne w zadaniach związanych z harmonogramowaniem i przydziałem zasobów. Jeden kolor często oznacza: „te elementy mogą współdzielić ten sam termin”.

Przykład: dlaczego cykl 5-elementowy wymaga 3 kolorów

Rozważ graf cyklu $C_5$ z krawędziami $AB, BC, CD, DE,$ oraz $EA$.

Najpierw spróbuj użyć $2$ kolorów. Nadaj $A$ kolor $1$, a $B$ kolor $2$. Wtedy kolorowanie wokół cyklu jest wymuszone:

$$A=1,\quad B=2,\quad C=1,\quad D=2$$

Teraz spójrz na $E$. Jest sąsiedni zarówno z $D$, jak i z $A$, więc nie może mieć koloru $2$ z powodu $D$ i nie może mieć koloru $1$ z powodu $A$.

Zatem $2$ kolory nie wystarczają.

Ale $3$ kolory już działają. Jedno poprawne kolorowanie to

$$A=1,\quad B=2,\quad C=1,\quad D=2,\quad E=3$$

więc

$$\chi(C_5)=3$$

Warto zapamiętać ten przykład, bo pokazuje ważny schemat: dla grafów cyklicznych cykl parzysty można pokolorować $2$ kolorami, ale cykl nieparzysty wymaga $3$.

Jak rozumować o kolorowaniu małych grafów

Pomagają dwie szybkie wskazówki.

Po pierwsze, szukaj wymuszonego konfliktu. W przykładzie powyżej naprzemienne używanie dwóch kolorów na cyklu nieparzystym sprawia, że ostatni wierzchołek koliduje z obiema dostępnymi możliwościami.

Po drugie, szukaj dolnego ograniczenia. Jeśli graf zawiera trójkąt, to te trzy wierzchołki są parami sąsiednie, więc już one wymagają $3$ różnych kolorów. Nie zawsze daje to dokładną odpowiedź, ale dowodzi, że liczba chromatyczna wynosi co najmniej $3$.

Typowe błędy w zadaniach o kolorowaniu grafów

Jednym z częstych błędów jest traktowanie wierzchołków jako sąsiednich tylko dlatego, że są narysowane blisko siebie. Ograniczenie kolorowania tworzy wyłącznie rzeczywista krawędź.

Inny błąd to założenie, że każdy wierzchołek potrzebuje własnego koloru. Niesąsiednie wierzchołki mogą mieć ten sam kolor, a dobre kolorowania zwykle wykorzystują kolory wielokrotnie, gdy tylko się da.

Uczniowie czasem mylą też kolorowanie wierzchołków z kolorowaniem krawędzi. Na tej stronie zasada dotyczy sąsiednich wierzchołków, a nie sąsiednich krawędzi.

Ostatni błąd to podawanie liczby kolorów, których akurat użyto, zamiast minimalnej liczby wymaganej. Użycie $4$ kolorów w grafie nie dowodzi, że liczba chromatyczna wynosi $4$.

Gdzie stosuje się kolorowanie grafów

Standardowym zastosowaniem jest układanie harmonogramów. Załóżmy, że każdy wierzchołek oznacza egzamin, a krawędź oznacza, że dwa egzaminy mają wspólnych studentów i nie mogą odbywać się w tym samym czasie. Wtedy jeden kolor może oznaczać jeden przedział czasowy.

W tym modelu liczba chromatyczna mówi, ile najmniej przedziałów czasowych jest możliwych. Jeśli $\chi(G)=4$, to nie istnieje poprawny harmonogram złożony tylko z $3$ przedziałów.

Ta sama idea pojawia się w kolorowaniu map, gdzie sąsiednie regiony muszą się różnić, oraz w projektowaniu kompilatorów, gdzie zmienne potrzebne jednocześnie nie mogą współdzielić tego samego rejestru.

Spróbuj podobnego zadania o kolorowaniu grafów

Narysuj graf z wierzchołkami $P,Q,R,S,T$ i krawędziami $PQ, QR, RS, ST, TP,$ oraz $PR$.

Zacznij od znalezienia trójkąta, aby uzyskać dolne ograniczenie. Następnie spróbuj pokolorować graf jak najmniejszą liczbą kolorów i sprawdź, czy jakieś sąsiednie wierzchołki mają ten sam kolor. Jeśli chcesz pójść dalej, spróbuj własnej wersji na większym grafie i zobacz, czy potrafisz udowodnić, że twoje kolorowanie jest minimalne, a nie tylko poprawne.