—
χ(G) кольорів використано
—
Макс. степінь Δ
—
Кількість ребер
—
Коректне розфарбування
Ця симуляція призначає кольори вершинам графа так, щоб жодні дві суміжні вершини не мали однакового кольору — задача, відома як правильне розфарбовування вершин. Найменша кількість кольорів, що дозволяє цього досягти, називається хроматичним числом і позначається χ(G). Ви можете будувати випадкові графи Ердőша–Реньї або завантажувати пресети, такі як граф Петерсена, повний K₅, цикл C₇, дводольний K₃₃ та колесо W₆, а потім розфарбовувати їх за допомогою жадібного впорядкування, впорядкування Велша–Пауелла або DSatur.
Бічна панель дозволяє задати кількість вершин (5–20), ймовірність ребра p (0.1–0.7) для випадкових графів і алгоритм розфарбовування. Кнопка "Розфарбувати!" одразу запускає обрану евристику, тоді як "Покроково" просуває по одній вершині за раз, щоб ви могли спостерігати за порядком та вибором найменшого доступного кольору. Жива панель показує використані кольори, максимальний степінь Δ, кількість ребер і те, чи є розфарбовування безконфліктним. Розфарбовування графів лежить в основі складання розкладу іспитів, розподілу регістрів у компіляторах та призначення радіочастот.
Що таке хроматичне число?
Хроматичне число χ(G) — це найменша кількість кольорів, потрібна для розфарбування кожної вершини так, щоб жодне ребро не з'єднувало дві вершини одного кольору. Симулятор показує кольори, фактично використані обраною евристикою, що дорівнює χ(G), коли евристика оптимальна, але може перевищувати його в інших випадках.
Як жадібний алгоритм розфарбовує граф?
Жадібне розфарбовування обходить вершини у фіксованому порядку і надає кожній найменший за номером колір, який ще не використаний її сусідами. Воно швидке і завжди дає коректне розфарбовування, але кількість потрібних кольорів сильно залежить від порядку обходу вершин.
Що роблять повзунки кількості вершин та ймовірності ребра?
Повзунок вершин задає, скільки вершин має випадковий граф, від 5 до 20. Ймовірність ребра p, від 0.1 до 0.7, — це шанс того, що будь-яка задана пара вершин з'єднана ребром, згідно з моделлю Ердőша–Реньї G(n,p). Більше p означає щільніші графи, які зазвичай потребують більше кольорів.
Велш–Пауелл — це жадібне розфарбовування, застосоване до вершин, відсортованих за спаданням степеня, тож вершини з високим степенем розфарбовуються першими. Таке впорядкування часто зменшує кількість кольорів порівняно з довільною послідовністю і гарантує розфарбовування, що використовує не більше ніж на один колір більше за максимальний степінь.
DSatur, скорочення від degree of saturation (степінь насиченості), щоразу розфарбовує нерозфарбовану вершину з найбільшою кількістю різних кольорів, уже наявних серед її сусідів, розв'язуючи нічиї за найвищим степенем. Він динамічно адаптує порядок у міру розміщення кольорів і схильний знаходити майже оптимальні розфарбовування, точно розфарбовуючи всі дводольні графи.
Не обов'язково. Жадібний, Велш–Пауелл та DSatur є евристиками, тож вони можуть використовувати більше кольорів, ніж мінімум. Знаходження точного хроматичного числа є NP-складною задачею в загальному випадку, тож для довільних графів ці методи дають добрі, швидкі відповіді, а не гарантований оптимум.
Дводольний граф, такий як K₃₃, розбиває свої вершини на дві групи з ребрами лише між групами. Оскільки жодне ребро не лежить усередині групи, ви можете розфарбувати одну групу першим кольором, а іншу — другим, що дає хроматичне число рівно два для будь-якого графа без непарного циклу.
Теорема чотирьох кольорів стверджує, що будь-який планарний граф, тобто такий, що його можна намалювати без перетину ребер, можна розфарбувати щонайбільше чотирма кольорами. Вона відповідає розфарбовуванню країн на карті так, щоб сусіди відрізнялися, і була першою великою теоремою, доведеною за суттєвої допомоги комп'ютера у 1976 році.
Максимальний степінь Δ — це найбільша кількість ребер, що сходяться в одній вершині. Жадібне розфарбовування ніколи не потребує більше ніж Δ + 1 кольорів, а теорема Брукса уточнює це до Δ кольорів для зв'язних графів, які не є ані повними, ані непарними циклами.
Вершини можуть представляти іспити, регістри процесора, частоти передавачів або працівників, а ребра позначають конфлікти, які мають відрізнятися. Розфарбовування тоді складає розклад іспитів без накладок, розподіляє регістри без перезапису, призначає частоти без взаємних перешкод і пакує задачі в найменшу кількість часових слотів, віддзеркалюючи показані тут кольори.