Kalkulator Kolorowania Grafów

O Kalkulator Kolorowania Grafów

Kalkulator Kolorowania Grafów oblicza liczbę chromatyczną χ(G) i wyznacza prawidłowe kolorowanie wierzchołków dla dowolnego grafu nieskierowanego. Wprowadź swój graf jako listę krawędzi lub listę sąsiedztwa, a narzędzie zwróci minimalną liczbę kolorów potrzebnych do tego, aby żadne dwa sąsiednie wierzchołki nie miały tego samego koloru, wraz z interaktywną wizualizacją SVG, animowanym śladem algorytmu DSATUR oraz szczegółowym zestawieniem przypisanych kolorów.

Co to jest kolorowanie grafów?

Prawidłowe kolorowanie wierzchołków grafu G = (V, E) polega na przypisaniu koloru każdemu wierzchołkowi w taki sposób, aby końce każdej krawędzi miały różne kolory. Liczba chromatyczna, oznaczana jako χ(G), to najmniejsza liczba kolorów, dla której takie kolorowanie istnieje. Obliczanie χ(G) jest problemem NP-trudnym, ale posiada piękną teorię matematyczną i wiele praktycznych zastosowań: planowanie egzaminów, przydzielanie częstotliwości radiowych, alokacja rejestrów w kompilatorach oraz słynne twierdzenie o czterech barwach dla map płaskich.

Kluczowe twierdzenia i ograniczenia

• Ograniczenia trywialne: 1 ≤ χ(G) ≤ |V| dla każdego grafu.
• Dolne ograniczenie klikowe: χ(G) ≥ ω(G), gdzie ω(G) to rozmiar największej kliki.
• Charakterystyka grafów dwudzielnych: χ(G) ≤ 2 wtedy i tylko wtedy, gdy G nie zawiera cyklu nieparzystego (König).
• Twierdzenie Brooksa: χ(G) ≤ Δ(G), chyba że G jest grafem pełnym lub cyklem nieparzystym – wtedy χ(G) = Δ(G) + 1. Δ(G) to maksymalny stopień wierzchołka.
• Twierdzenie o czterech barwach: Każdy graf planarny jest 4-kolorowalny.
• Górne ograniczenie zachłanne: Każdy algorytm zachłanny używa co najwyżej Δ(G) + 1 kolorów.

Algorytmy używane przez ten kalkulator

DSATUR (Degree of Saturation)

Wprowadzony przez Daniela Brélaza w 1979 roku, DSATUR jest jedną z najsilniejszych praktycznych heurystyk kolorowania grafów. Wielokrotnie wybiera niepokolorowany wierzchołek, którego sąsiedzi używają już największej liczby różnych kolorów (stopień nasycenia), rozstrzygając remisy na podstawie stopnia wierzchołka, i przypisuje mu najmniejszy kolor nieużywany przez sąsiadów. DSATUR jest optymalny dla grafów dwudzielnych i wielu strukturalnych rodzin grafów, generując wysokiej jakości kolorowania w milisekundach nawet dla grafów o setkach wierzchołków.

Welsh-Powell

Algorytm Welsha-Powella sortuje wierzchołki w porządku malejącego stopnia, a następnie koloruje je zachłannie. Działa w czasie O(|V|²) i gwarantuje użycie co najwyżej Δ(G) + 1 kolorów. Jest niezwykle szybki i często stanowi dobre pierwsze przybliżenie, choć DSATUR zazwyczaj osiąga lepsze wyniki w grafach o zróżnicowanej strukturze lokalnej.

Zachłanny (kolejność wejściowa)

Najprostszy algorytm: przechodzi przez wierzchołki w kolejności ich wprowadzenia i przypisuje każdemu najmniejszy dostępny kolor. Wynik jest zależny od kolejności danych wejściowych, ale losowa kolejność może służyć jako punkt odniesienia dla bardziej zaawansowanych heurystyk.

Dokładny z nawrotami (Backtracking)

Dla małych grafów (do około 18 wierzchołków) kalkulator może znaleźć rzeczywistą liczbę chromatyczną, próbując k = 2, 3, 4, ... i usiłując pokolorować graf za pomocą przeszukiwania z nawrotami (depth-first backtracking). Algorytm ten sortuje wierzchołki według stopnia i stosuje cięcia, gdy kolorowanie staje się niemożliwe. Gdy algorytm dokładny odniesie sukces, wynik jest oznaczony jako "Dokładny".

Formaty wejściowe

Lista krawędzi

Zapisz każdą krawędź jako dwie etykiety wierzchołków oddzielone myślnikiem, spacją lub strzałką. Oddziel krawędzie przecinkami lub znakami nowej linii. Etykiety mogą zawierać litery, cyfry lub podkreślenia. Przykład:

Lista sąsiedztwa

Zapisz każdy wierzchołek, dwukropek, a następnie listę jego sąsiadów oddzielonych przecinkami. Przykład:

Pętle własne są odrzucane, ponieważ wierzchołek nie może mieć koloru innego niż on sam. Zduplikowane krawędzie są usuwane, a graf jest traktowany jako nieskierowany.

Jak korzystać z tego kalkulatora

1. Wybierz format: Przełączaj się między listą krawędzi a listą sąsiedztwa za pomocą przycisków opcji.
2. Wprowadź graf: Wklej swoje dane lub kliknij jeden z szybkich przykładów (trójkąt, graf pełny K₅, koło, graf dwudzielny K₃,₃, planowanie egzaminów).
3. Wybierz algorytm: Pozostaw "Automatyczny" dla optymalnych wyników lub wybierz konkretnie: Welsh-Powell, zachłanny, DSATUR lub dokładny z nawrotami.
4. Kliknij "Pokoloruj graf": Poniżej pojawi się liczba chromatyczna, lista kolorów, interaktywny graf SVG oraz animacja krok po kroku.
5. Eksploruj: Naciśnij Odtwórz, aby zobaczyć proces kolorowania, przeciągaj wierzchołki, aby zmienić układ, i używaj przycisków Wstecz / Dalej do ręcznego sterowania animacją.

Praktyczne zastosowania kolorowania grafów

Planowanie egzaminów

Niech każdy egzamin będzie wierzchołkiem, a krawędź łączy te egzaminy, na które zapisany jest co najmniej jeden wspólny student. Prawidłowe kolorowanie k kolorami daje harmonogram z k przedziałami czasowymi bez konfliktów. Liczba chromatyczna to minimalna liczba potrzebnych sesji.

Przydzielanie częstotliwości radiowych

Nadajniki znajdujące się w zasięgu wzajemnych zakłóceń muszą nadawać na różnych częstotliwościach. Liczba chromatyczna grafu zakłóceń to minimalna liczba potrzebnych pasm częstotliwości.

Alokacja rejestrów

W kompilatorach zakresy życia zmiennych to wierzchołki; jeśli dwa zakresy nakładają się w czasie, tworzona jest krawędź. k-kolorowanie pozwala przypisać zmienne do k rejestrów procesora bez kolizji.

Kolorowanie map

Kraje dzielące granicę muszą mieć różne kolory. Twierdzenie o czterech barwach (Appel-Haken, 1976) dowodzi, że cztery kolory zawsze wystarczają dla dowolnej mapy płaskiej.

Sudoku i zagadki logiczne

Rozwiązane Sudoku to 9-kolorowanie grafu, którego wierzchołkami jest 81 komórek, a krawędzie łączą komórki w tym samym wierszu, kolumnie lub kwadracie 3×3. Kolorowanie grafów jest matematycznym fundamentem wielu zagadek optymalizacyjnych.

Interesujące przypadki szczególne

• Graf pełny K_n: χ(K_n) = n. Każda para wierzchołków jest sąsiednia, więc wszystkie kolory muszą być różne.
• Cykl C_n: χ(C_n) = 2 jeśli n jest parzyste, 3 jeśli n jest nieparzyste.
• Drzewo: Każde drzewo o ≥ 2 wierzchołkach ma χ = 2 (drzewa są dwudzielne).
• Graf dwudzielny: χ = 2, jeśli graf ma przynajmniej jedną krawędź.
• Graf Petersena: Słynny graf 3-regularny o χ = 3.
• Koło W_n: Wierzchołek centralny połączony z cyklem n-wierzchołkowym. χ = 3 jeśli n jest parzyste, 4 jeśli n jest nieparzyste.

Często zadawane pytania

Co to jest liczba chromatyczna grafu?

Liczba chromatyczna χ(G) to najmniejsza liczba kolorów potrzebna do pokolorowania wierzchołków grafu tak, aby sąsiedzi nie mieli tego samego koloru. Grafy dwudzielne mają liczbę chromatyczną najwyżej 2; każdy graf zawierający trójkąt ma co najmniej 3; a zgodnie z twierdzeniem Brooksa liczba ta zazwyczaj nie przekracza maksymalnego stopnia wierzchołka.

Jakiego algorytmu używa ten kalkulator?

Dla małych grafów kalkulator stosuje dokładne wyszukiwanie z nawrotami. Dla większych grafów używa heurystyki DSATUR, która inteligentnie wybiera kolejność kolorowania na podstawie nasycenia sąsiadów. Możesz również wybrać inne metody z menu rozwijanego.

Jak wprowadzić dane?

Użyj trybu listy krawędzi (np. A-B) lub listy sąsiedztwa (A: B, C). Pamiętaj, że pętle własne nie są dozwolone.

Dlaczego DSATUR nie zawsze podaje wynik optymalny?

Ponieważ problem jest NP-trudny, co oznacza, że dla bardzo dużych lub specyficznie skonstruowanych grafów znalezienie minimum w krótkim czasie jest niemożliwe. DSATUR jest jednak bardzo bliski ideałowi w większości praktycznych przypadków.

Jaki jest największy graf, który można tu obliczyć?

Kalkulator obsługuje do 60 wierzchołków i 600 krawędzi. Algorytm dokładny powyżej 18 wierzchołków może automatycznie przełączyć się na DSATUR, jeśli obliczenia trwałyby zbyt długo.

Dalsza lektura

• Kolorowanie grafu — Wikipedia
• Algorytm DSATUR (ang.) — Wikipedia
• Wielomian chromatyczny — Wikipedia
• Twierdzenie o czterech barwach — Wikipedia
• Twierdzenie Brooksa — Wikipedia