PL 
EnglishDomyślny
Українська🎨 Kolorowanie grafu
Pokoloruj graf tak, by sąsiedzi się nie powtarzali: porównaj algorytmy zachłanny, Welsh-Powell i DSatur i zobacz, jak blisko liczby chromatycznej trafiają.
O kolorowaniu grafów
Ta symulacja przypisuje kolory wierzchołkom grafu tak, by żadne dwa sąsiadujące wierzchołki nie miały tego samego koloru — jest to problem znany jako właściwe kolorowanie wierzchołków. Najmniejsza liczba kolorów potrzebna do tego celu to liczba chromatyczna, oznaczana χ(G). Możesz budować losowe grafy Erdősa–Rényiego lub wczytywać gotowe przykłady, takie jak graf Petersena, graf pełny K₅, cykl C₇, graf dwudzielny K₃,₃ oraz koło W₆, a następnie kolorować je algorytmem zachłannym, Welsh–Powell lub DSatur.
Panel boczny pozwala ustawić liczbę wierzchołków (5–20), prawdopodobieństwo krawędzi p (0,1–0,7) dla grafów losowych oraz algorytm kolorowania. „Koloruj!" uruchamia wybraną heurystykę od razu, a „Krok po kroku" przesuwa się o jeden wierzchołek naraz, dzięki czemu można obserwować kolejność i wybór najmniejszego dostępnego koloru. Panel na żywo pokazuje liczbę użytych kolorów, maksymalny stopień Δ, liczbę krawędzi oraz to, czy kolorowanie jest wolne od konfliktów. Kolorowanie grafów leży u podstaw planowania egzaminów, alokacji rejestrów w kompilatorach i przydziału częstotliwości radiowych.
Najczęściej zadawane pytania
Czym jest liczba chromatyczna?
Liczba chromatyczna χ(G) to najmniejsza liczba kolorów potrzebna do pokolorowania każdego wierzchołka tak, by żadna krawędź nie łączyła dwóch wierzchołków tego samego koloru. Symulator pokazuje liczbę kolorów faktycznie użytych przez wybraną heurystykę, która jest równa χ(G), gdy heurystyka jest optymalna, ale może ją przekroczyć w innych przypadkach.
Jak algorytm zachłanny koloruje graf?
Kolorowanie zachłanne odwiedza wierzchołki w ustalonej kolejności i nadaje każdemu z nich kolor o najniższym numerze, który nie jest jeszcze użyty przez jego sąsiadów. Jest szybkie i zawsze daje poprawne kolorowanie, ale liczba potrzebnych kolorów mocno zależy od kolejności wierzchołków.
Do czego służą suwaki liczby wierzchołków i prawdopodobieństwa krawędzi?
Suwak wierzchołków ustala, ile wierzchołków ma losowy graf, od 5 do 20. Prawdopodobieństwo krawędzi p, między 0,1 a 0,7, to szansa, że dana para wierzchołków zostanie połączona krawędzią, zgodnie z modelem Erdősa–Rényiego G(n,p). Wyższe p oznacza gęstsze grafy, które zwykle wymagają więcej kolorów.
Czym Welsh–Powell różni się od zwykłego algorytmu zachłannego?
Welsh–Powell to kolorowanie zachłanne zastosowane do wierzchołków posortowanych w kolejności malejącego stopnia, więc wierzchołki o wysokim stopniu są kolorowane jako pierwsze. Taka kolejność często zmniejsza liczbę potrzebnych kolorów w porównaniu z dowolną sekwencją i gwarantuje kolorowanie używające co najwyżej o jeden kolor więcej niż maksymalny stopień.
Czym jest algorytm DSatur?
DSatur, od „degree of saturation" (stopień nasycenia), wielokrotnie koloruje niepokolorowany wierzchołek o największej liczbie różnych kolorów już obecnych wśród sąsiadów, rozstrzygając remisy na korzyść wyższego stopnia. Dostosowuje kolejność dynamicznie w miarę umieszczania kolorów i zwykle znajduje niemal optymalne kolorowania, dokładnie kolorując wszystkie grafy dwudzielne.
Czy symulator zawsze znajduje prawdziwą liczbę chromatyczną?
Niekoniecznie. Zachłanny, Welsh–Powell i DSatur to heurystyki, więc mogą użyć więcej kolorów niż minimum. Znalezienie dokładnej liczby chromatycznej jest ogólnie NP-trudne, więc dla dowolnych grafów te metody dają dobre, szybkie odpowiedzi, a nie gwarantowane optimum.
Dlaczego przykład dwudzielny potrzebuje tylko dwóch kolorów?
Graf dwudzielny, taki jak K₃,₃, dzieli swoje wierzchołki na dwie grupy, a krawędzie prowadzą tylko między grupami. Ponieważ żadna krawędź nie leży wewnątrz grupy, można pokolorować jedną grupę kolorem pierwszym, a drugą kolorem drugim, co daje liczbę chromatyczną równą dokładnie dwa dla każdego grafu bez nieparzystego cyklu.
Co mówi twierdzenie o czterech kolorach?
Twierdzenie o czterech kolorach mówi, że każdy graf planarny — czyli taki, który można narysować bez przecinających się krawędzi — można pokolorować co najwyżej czterema kolorami. Odpowiada to kolorowaniu krajów na mapie tak, by sąsiedzi się różnili, i było pierwszym ważnym twierdzeniem udowodnionym z istotną pomocą komputera, w 1976 roku.
Jak maksymalny stopień Δ wiąże się z kolorowaniem?
Maksymalny stopień Δ to największa liczba krawędzi spotykających się w jednym wierzchołku. Kolorowanie zachłanne nigdy nie potrzebuje więcej niż Δ + 1 kolorów, a twierdzenie Brooksa zaostrza to do Δ kolorów dla grafów spójnych, które nie są ani pełne, ani nieparzystymi cyklami.
Jakie problemy z życia wzięte wykorzystują kolorowanie grafów?
Wierzchołki mogą reprezentować egzaminy, rejestry procesora, częstotliwości nadajników lub pracowników, a krawędzie oznaczają konflikty, które muszą się różnić. Kolorowanie planuje wówczas egzaminy bez kolizji, przydziela rejestry bez nadpisywania, przypisuje częstotliwości wolne od zakłóceń i pakuje zadania w jak najmniejszą liczbę przedziałów czasowych, odzwierciedlając kolory pokazane tutaj.