UK 
EnglishТипова
Polski🎨 Розфарбовування Графів
Розфарбуйте граф так, щоб суміжні вершини мали різні кольори: жадібні алгоритми, хроматичне число та класичні застосування на кшталт розкладу.
Про розфарбування графів
Ця симуляція призначає кольори вершинам графа так, щоб жодні дві суміжні вершини не мали однакового кольору — задача, відома як правильне розфарбування вершин. Найменша кількість кольорів, яка це забезпечує, — це хроматичне число, що позначається χ(G). Ви можете будувати випадкові графи Ердеша–Реньї або завантажувати пресети, як-от граф Петерсена, повний K₅, цикл C₇, двочастковий K₃,₃ та колесо W₆, а потім розфарбовувати їх жадібним алгоритмом, Уельш-Пауелл або DSatur.
Бічна панель дозволяє задати кількість вузлів (5–20), ймовірність ребра p (0,1–0,7) для випадкових графів та алгоритм розфарбування. «Color!» одразу запускає обрану евристику, тоді як «Step-by-Step» просувається по одній вершині за раз, щоб можна було спостерігати порядок і вибір найменшого доступного кольору. Панель у реальному часі показує використані кольори, максимальний ступінь Δ, кількість ребер та чи відсутні конфлікти у розфарбуванні. Розфарбування графів лежить в основі складання розкладу екзаменів, розподілу регістрів у компіляторах та призначення радіочастот.
Часті запитання
Що таке хроматичне число?
Хроматичне число χ(G) — це найменша кількість кольорів, необхідних для розфарбування кожної вершини так, щоб жодне ребро не з'єднувало дві вершини одного кольору. Симулятор показує кількість кольорів, фактично використаних обраною евристикою, яка дорівнює χ(G), коли евристика оптимальна, але може перевищувати це значення в інших випадках.
Як жадібний алгоритм розфарбовує граф?
Жадібне розфарбування відвідує вершини у фіксованому порядку й надає кожній найменший за номером колір, ще не використаний її сусідами. Він швидкий і завжди дає коректне розфарбування, але кількість необхідних кольорів сильно залежить від порядку вершин.
Що роблять повзунки кількості вузлів та ймовірності ребра?
Повзунок вузлів задає кількість вершин випадкового графа, від 5 до 20. Ймовірність ребра p, від 0,1 до 0,7, — це шанс, що будь-яка пара вершин з'єднана ребром, за моделлю Ердеша–Реньї G(n,p). Більше p означає щільніші графи, які зазвичай потребують більше кольорів.
Чим Уельш-Пауелл відрізняється від простого жадібного алгоритму?
Уельш-Пауелл — це жадібне розфарбування, застосоване до вершин, відсортованих за спаданням ступеня, тож вершини з високим ступенем розфарбовуються першими. Такий порядок часто зменшує кількість кольорів порівняно з довільною послідовністю та гарантує розфарбування з використанням щонайбільше на один колір більше за максимальний ступінь.
Що таке алгоритм DSatur?
DSatur, скорочення від «ступінь насичення», повторно розфарбовує нерозфарбовану вершину з найбільшою кількістю різних кольорів уже наявних серед її сусідів, вирішуючи нічию за найвищим ступенем. Він динамічно адаптує порядок у міру розстановки кольорів і зазвичай знаходить близькі до оптимальних розфарбування, точно розфарбовуючи всі двочасткові графи.
Чи завжди симулятор знаходить справжнє хроматичне число?
Не обов'язково. Жадібний алгоритм, Уельш-Пауелл і DSatur — це евристики, тому вони можуть використовувати більше кольорів, ніж мінімум. Знаходження точного хроматичного числа NP-складне в загальному випадку, тому для довільних графів ці методи дають хороші, швидкі відповіді, а не гарантований оптимум.
Чому двочастковому пресету потрібно лише два кольори?
Двочастковий граф, наприклад K₃,₃, розділяє свої вершини на дві групи з ребрами лише між групами. Оскільки жодне ребро не лежить усередині групи, одну групу можна розфарбувати кольором один, а іншу — кольором два, даючи хроматичне число рівно два для будь-якого графа без непарного циклу.
Що стверджує теорема про чотири фарби?
Теорема про чотири фарби стверджує, що будь-який планарний граф (той, що можна намалювати без перетину ребер) можна розфарбувати щонайбільше чотирма кольорами. Вона відповідає розфарбуванню країн на карті так, щоб сусіди відрізнялися, і була першою великою теоремою, доведеною зі значною допомогою комп'ютера у 1976 році.
Як максимальний ступінь Δ пов'язаний з розфарбуванням?
Максимальний ступінь Δ — це найбільша кількість ребер, що сходяться в одній вершині. Жадібне розфарбування ніколи не потребує більше за Δ + 1 колір, а теорема Брукса уточнює це до значення Δ для зв'язних графів, що не є повними чи непарними циклами.
Які реальні задачі використовують розфарбування графів?
Вершини можуть представляти екзамени, регістри процесора, частоти передавачів або працівників, а ребра позначають конфлікти, які мають відрізнятися. Розфарбування тоді складає розклад екзаменів без накладок, розподіляє регістри без перезапису, призначає частоти без взаємних завад і пакує завдання в найменшу кількість часових слотів, віддзеркалюючи кольори, показані тут.