Что удивительного в этой картине? 
На самом деле она уникальна.
Матрица 17 х 17 раскрашена в четыре цвета, но на ней нельзя построить ни одного (!) прямоугольника так, чтобы все ее углы были одного цвета.
Это относится к прямоугольникам любого размера с вершинами в разных точках и краями, параллельными осям.
Икс И й .
Для сравнения, если изменить цвет в любой ячейке, появится сразу множество однотонных прямоугольников.
Например, если цвет верхней левой ячейки изменен с синего на красный.
Аналогично, если вы измените одну случайную ячейку из середины.
Эта задача из области комбинаторного анализа помещать 20 ноября 2009 года Уильям Гасарч из Математического института Клэя, ранее опубликовавший фундаментальную работу работа по раскраске матриц, и в ней доказал раскрашиваемость или нераскрашиваемость матриц почти всех размеров четырьмя цветами без полихроматических прямоугольников.
Неизвестен в своем стол Осталось всего несколько размеров: 17х17, 18х18 и 12х21. Математики Бернд Штайнбах из Института компьютерных наук Технического университета Фрайбергской горной академии (Германия) и Кристиан Постхофф, ранее работавший на кафедре компьютерных и информационных технологий Вест-Индского университета (Тринидад и Тобаго) удалось раскрасить График 17х17 в четырёх цветах без единого однотонного прямоугольника! Более того, они также смогли раскрасить матрицу 18х18. Таким образом, единственным нерешённым на сегодняшний день форматом остаётся 21х12. Результаты работы «Самые сложные четырехцветные сетки без прямоугольников – решение открытой многозначной задачи» а алгоритм Штейнбаха-Посттгофа будет опубликован на Международном симпозиуме по многозначной логике 14 мая 2012 г.
в Виктории (Канада).
Обратите внимание, что раскраска графиков имеет большое практическое значение и используется при планировании, распределении регистров в микропроцессорах, распределении кэша исполняемого кода, распределении частот в радиосвязи для максимизации пропускной способности канала и минимизации помех, распараллеливании численных методов, вычислениях производных, цифровых водяных знаках, кластерном анализе и во многих других областях.
Теги: #многозначная функция #комбинаторика #раскраска графов #Алгоритмы
-
Фичино, Марсилио
19 Oct, 24 -
Сколько Стоят Фокусы У Фокусников?
19 Oct, 24
