Jak mam wprowadzić mój graf?

Użyj trybu listy krawędzi, aby wpisać jedną krawędź w linii, np. A-B, lub oddzielone przecinkami, np. A-B, B-C, C-A. Użyj trybu listy sąsiedztwa, aby zapisać każdy wierzchołek, a po nim dwukropek i jego sąsiadów, np. A: B, C. Pętle własne są odrzucane, ponieważ wierzchołek nie może być pokolorowany inaczej niż on sam.

Dlaczego DSATUR nie zawsze znajduje prawdziwą liczbę chromatyczną?

Kolorowanie grafu jest problemem NP-trudnym, więc żaden znany szybki algorytm nie zawsze znajduje minimalną liczbę kolorów. DSATUR jest doskonałą praktyczną heurystyką i często pokrywa się z prawdziwą liczbą chromatyczną, ale na grafach o specyficznej strukturze może użyć więcej kolorów niż to konieczne. Kalkulator podaje zarówno liczbę użytych kolorów, jak i dolne ograniczenie z największej znalezionej kliki, dzięki czemu można ocenić dokładność odpowiedzi.

Jakie jest rzeczywiste zastosowanie kolorowania grafów?

Kolorowanie grafów modeluje układanie planu egzaminów (każdy egzamin to wierzchołek, konflikty to krawędzie, kolory to przedziały czasowe), przydzielanie częstotliwości radiowych (wierzchołki to nadajniki, krawędzie to zakłócenia), alokację rejestrów w kompilatorach, kolorowanie map, rozwiązywanie sudoku oraz przypisywanie zadań maszynom przy ograniczeniach konfliktów.

Czy liczba chromatyczna jest zawsze równa największej klice?

Nie. Liczba klikowa omega(G) jest zawsze dolnym ograniczeniem liczby chromatycznej chi(G) i są one równe dla grafów doskonałych, takich jak grafy dwudzielne, drzewa, grafy przedziałowe i grafy cięciwowe. Dla ogólnych grafów chi(G) może być ściśle większa niż omega(G); klasycznym przykładem są grafy Mycielskiego, które nie zawierają trójkątów, ale wymagają dowolnie wielu kolorów.

Kalkulator Kolorowania Grafów

Znajdź liczbę chromatyczną i poprawne kolorowanie wierzchołków dowolnego grafu nieskierowanego. Podaj krawędzie lub listę sąsiedztwa, by uzyskać minimalną liczbę kolorów, przypisanie kolorów, animowane przejście DSATUR i wizualizację grafu.

BezpłatneBez rejestracjiNatychmiastowe wyniki

Kalkulator Kolorowania GrafówWypróbuj teraz — za darmo ▼

⚡ Wypróbuj przykład:

4-cykl C₄ Trójkąt K₃ Pełny K₅ Pięciokąt C₅ Koło W₆ Dwudzielny K₃,₃ Przykładowe sąsiedztwo Planowanie egzaminów

Format wejściowy

⬌ Lista krawędzi

⧇ Lista sąsiedztwa

Dane grafu

Format krawędzi: A-B lub A B, oddzielone przecinkami lub nowymi liniami. Maks. 60 wierzchołków i 600 krawędzi.

Format sąsiedztwa: A: B, C, D — jeden wierzchołek w linii, a po nim jego sąsiedzi.

Algorytm

Tryb Auto wybiera dokładne wyszukiwanie dla małych grafów i DSATUR dla większych.

Embed Kalkulator Kolorowania Grafów Widget

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.

Definicja liczby chromatycznej

χ(G) = min { k : G dopuszcza prawidłowe k-kolorowanie }

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:

A-B, B-C, C-D, D-A
A-C

Lista sąsiedztwa

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

A: B, C, D
B: A, D
C: A
D: A, B

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

Wybierz format: Przełączaj się między listą krawędzi a listą sąsiedztwa za pomocą przycisków opcji.
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).
Wybierz algorytm: Pozostaw "Automatyczny" dla optymalnych wyników lub wybierz konkretnie: Welsh-Powell, zachłanny, DSATUR lub dokładny z nawrotami.
Kliknij "Pokoloruj graf": Poniżej pojawi się liczba chromatyczna, lista kolorów, interaktywny graf SVG oraz animacja krok po kroku.
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

Cytuj ten materiał, stronę lub narzędzie w następujący sposób:

"Kalkulator Kolorowania Grafów" na https://MiniWebtool.com/pl/kalkulator-kolorowania-grafow/ z MiniWebtool, https://MiniWebtool.com/

autor: zespół miniwebtool. Zaktualizowano: 20 kwietnia 2026

Dostępne API dla deweloperów: Uruchom to narzędzie z aplikacji, automatyzacji lub agenta za pomocą jednego żądania HTTP JSON. Zobacz dokumentację API

Możesz także wypróbować nasz AI Rozwiązywacz Matematyczny GPT, aby rozwiązywać swoje problemy matematyczne poprzez pytania i odpowiedzi w języku naturalnym.