Раскраска в 4 цвета
Насекомые. Раскраска для малышей, с карандашами (4 цвета)
Натолкнулся в Интернете на задачу, которая называется "Теорема о четырех красках". Вот ее страница в Википедии. Если не знаете эту задачу, то прочтите - интересная история.
.png "Чему нас может научить теорема о четырех красках в разработке ПО / Хабр")
Математикам не хватило четырех цветов для раскраски плоскости
Британcкий математик-любитель Обри ди Грей впервые за последние 60 лет улучшил результат решения известной математической задачи о хроматическом числе плоскости. Это число — наименьшее количество красок, с помощью которых можно так раскрасить плоскость, чтобы на фиксированной единице расстояния например, сантиметр нигде не нашлось двух точек одинакового цвета. Эту задачу не стоит путать с похожей, но уже решенной задачей о раскрашивании карт. Раньше было известно, что хроматическое число плоскости лежит между четырьмя и семью включительно, а теперь Ди Грей показал, что в четыре цвета плоскость точно раскрасить нельзя. Препринт работы опубликован на arXiv. Исторически задача о раскрашивании плоскости была сформулирована в х годах Эрдёшем и, независимо от него, в году Нелсоном.
В этом уроке мы разберем, что такое раскраска графов и как это относится к цифрам на вершинах. Также покажем примеры раскраски графов разных типов, так как в каждом случае этот процесс немного отличается. Цвета — это целые положительные цифры. Графы нужно раскрашивать так, чтобы соседние вершины имели разные цвета. Еще стоит использовать как можно меньше цветов. Первый пример на схеме выше не совсем верный, потому что соседним вершинам присваивается один и тот же цвет.
