Розфарбування графа
Розфарбуйте граф найменшою можливою кількістю кольорів
Про цей калькулятор
Калькулятор розфарбування графа знаходить хроматичне число χ(G) — найменшу кількість кольорів, потрібну, щоб розфарбувати вершини графа так, аби жодне ребро не з’єднувало дві вершини одного кольору, — і показує одне оптимальне розфарбування. Введіть кількість вершин і список ребер; калькулятор точно обчислює χ методом гілок і меж, показує максимальний степінь Δ і найбільшу кліку ω (нижня межа для χ), позначає двочасткові й повні графи та малює розфарбований граф. Корисно для складання розкладів, розподілу регістрів, розфарбування карт і вивчення хроматичних чисел.
Як розфарбувати граф
- Введіть кількість вершин; їх нумерують від 1 до n.
- Перелічіть ребра як пари на кшталт 1-2, 2-3 — одна пара на кожне з’єднання.
- Перегляньте хроматичне число χ(G) і колір, призначений кожній вершині.
- Порівняйте χ із найбільшою клікою ω, щоб зрозуміти, чому потрібно саме стільки кольорів, або завантажте шаблон для дослідження.
Типові приклади
- Трикутник (K₃) потребує 3 кольорів — кожна пара його вершин суміжна.
- Парні цикли двочасткові й потребують лише 2 кольорів; непарні цикли, як-от C₅, потребують 3.
- Повний граф Kₙ потребує рівно n кольорів.
- Найбільша кліка розміру ω вимагає щонайменше ω кольорів, тож χ(G) ≥ ω.
- Граф Грьотша потребує 4 кольорів, хоча не містить жодного трикутника, тож χ може перевищувати клікове число.
Поширені запитання
Що таке хроматичне число?
Хроматичне число χ(G) — це найменша кількість кольорів, потрібна, щоб розфарбувати вершини графа так, аби жодне ребро не з’єднувало дві вершини одного кольору.
Як знаходиться мінімальна кількість кольорів?
Оскільки граф невеликий, калькулятор шукає точно: пробує 1 колір, потім 2 і так далі, повертаючи першу кількість, для якої існує правильне розфарбування. Ця кількість гарантовано є справжнім мінімумом.
Що таке максимальний степінь і найбільша кліка?
Максимальний степінь Δ — це найбільша кількість ребер, що сходяться в одній вершині. Найбільша кліка ω — це найбільша множина вершин, попарно суміжних між собою; оскільки всі вони мають бути різних кольорів, χ(G) не менше за ω.
Чому граф без трикутників може все одно потребувати багато кольорів?
Велика кліка вимагає багато кольорів, але це не єдина причина. Непарні цикли та графи на кшталт графа Грьотша потребують додаткових кольорів навіть без жодного трикутника, тож χ(G) може бути більшим за клікове число.
Чи є обмеження на розмір графа?
Так. Точне розфарбування графа — обчислювально складна задача, тому калькулятор обмежує граф 12 вершинами, щоб результати були миттєвими й строгими.