Kolorowanie grafu

Pokoloruj graf jak najmniejszą liczbą kolorów

O tym kalkulatorze

Kalkulator kolorowania grafu wyznacza liczbę chromatyczną χ(G) — najmniejszą liczbę kolorów potrzebną do pokolorowania wierzchołków grafu tak, by żadna krawędź nie łączyła dwóch wierzchołków tego samego koloru — i pokazuje jedno optymalne kolorowanie. Wpisz liczbę wierzchołków i listę krawędzi; kalkulator oblicza χ dokładnie metodą podziału i ograniczeń, podaje maksymalny stopień Δ i największą klikę ω (dolne ograniczenie χ), oznacza grafy dwudzielne i pełne oraz rysuje pokolorowany graf. Przydatny przy układaniu harmonogramów, przydziale rejestrów, kolorowaniu map i nauce o liczbach chromatycznych.

Jak pokolorować graf

  1. Wpisz liczbę wierzchołków; są numerowane od 1 do n.
  2. Podaj krawędzie jako pary, np. 1-2, 2-3 — jedna para na każde połączenie.
  3. Odczytaj liczbę chromatyczną χ(G) i kolor przypisany każdemu wierzchołkowi.
  4. Porównaj χ z największą kliką ω, aby zobaczyć, dlaczego potrzeba tylu kolorów, lub wczytaj gotowy przykład, aby poeksperymentować.

Typowe przykłady

  • Trójkąt (K₃) wymaga 3 kolorów — każda para jego wierzchołków jest sąsiednia.
  • Cykle parzyste są dwudzielne i wymagają tylko 2 kolorów; cykle nieparzyste, takie jak C₅, wymagają 3.
  • Graf pełny Kₙ wymaga dokładnie n kolorów.
  • Największa klika o rozmiarze ω wymusza co najmniej ω kolorów, więc χ(G) ≥ ω.
  • Graf Grötzscha wymaga 4 kolorów, choć nie zawiera trójkąta, więc χ może przekraczać liczbę klikową.

Najczęściej zadawane pytania

Czym jest liczba chromatyczna?

Liczba chromatyczna χ(G) to najmniejsza liczba kolorów potrzebna do pokolorowania wierzchołków grafu tak, by żadna krawędź nie łączyła dwóch wierzchołków tego samego koloru.

Jak wyznaczana jest minimalna liczba kolorów?

Ponieważ graf jest mały, kalkulator szuka dokładnie: próbuje 1 koloru, potem 2 i tak dalej, zwracając pierwszą liczbę, dla której istnieje poprawne kolorowanie. Ta liczba jest na pewno prawdziwym minimum.

Czym są maksymalny stopień i największa klika?

Maksymalny stopień Δ to największa liczba krawędzi schodzących się w jednym wierzchołku. Największa klika ω to największy zbiór wierzchołków, które są parami sąsiednie; ponieważ wszystkie muszą mieć różne kolory, χ(G) wynosi co najmniej ω.

Dlaczego graf bez trójkątów może wymagać wielu kolorów?

Duża klika wymusza wiele kolorów, ale nie jest jedynym powodem. Cykle nieparzyste i grafy takie jak graf Grötzscha wymagają dodatkowych kolorów nawet bez żadnego trójkąta, więc χ(G) może być większa od liczby klikowej.

Czy rozmiar grafu jest ograniczony?

Tak. Dokładne kolorowanie grafów jest obliczeniowo trudne, dlatego kalkulator ogranicza graf do 12 wierzchołków, aby wyniki były natychmiastowe i ścisłe.