Расслабляющая игра-головоломка без таймера. Цель состоит в том, чтобы использовать наименьшее количество цветов.
Хроматическая расслабляющая игра-головоломка без таймера.
Вам нужно раскрасить все вершины. Вот и все! Но... соседние вершины не могут иметь одинаковый цвет.
Итак, цель состоит в том, чтобы использовать наименьшее количество цветов, а хроматическое число графа — это наименьшее количество цветов, достаточное для раскраски.
Вы начнете с раскраски вершин, при которой вершины графа раскрашиваются таким образом, чтобы соседние вершины имели разные цвета. Вы начнете с простых примеров, а затем перейдете к более сложным графикам. Иногда это легко, иногда очень и очень сложно.
Немного истории математики:
Хроматическое число графа — это наименьшее количество цветов, необходимое для окраски вершин графа так, чтобы никакие две соседние вершины не имели один и тот же цвет.
Первые результаты о раскраске графов касаются почти исключительно плоских графов в виде раскраски карт. Пытаясь раскрасить карту графств Англии, Фрэнсис Гатри постулировал гипотезу четырех цветов, отметив, что четырех цветов было достаточно, чтобы раскрасить карту, так что ни один регион, имеющий общую границу, не получил одного и того же цвета. Брат Гатри передал этот вопрос своему учителю математики Огастесу де Моргану в Университетском колледже, который упомянул его в письме Уильяму Гамильтону в 1852 году. Артур Кэли поднял проблему на собрании Лондонского математического общества в 1879 году. В том же году Альфред Кемпе опубликовал статью, в которой утверждалось, что она установила результат, и в течение десятилетия проблема четырех цветов считалась решенной. За свои достижения Кемпе был избран членом Королевского общества, а затем президентом Лондонского математического общества.
Читать далее
