Что удивительного в этой картинке?
На самом деле она уникальна. Матрица размером 17 х 17 раскрашена четырьмя цветами, при этом на ней нельзя построить ни единого (!) прямоугольника, чтобы все углы его были одного цвета. Имеются в виду прямоугольники любого размера с вершинами в разных точках и рёбрами, параллельными осям x и y.
Для сравнения, если заменить цвет в любой ячейке, то появляется сразу множество монохроматических прямоугольников. Например, если цвет левой верхней ячейки поменять с синего на красный.
Аналогично, если поменять одну случайную ячейку из середины.
Данную задачу из области комбинаторного анализа поставил 20 ноября 2009 года Уильям Гасарч из Математического института Клэя, который ранее опубликовал фундаментальную работу по раскраске матриц, и в ней доказал раскрашиваемость или нераскрашиваемость матриц почти всех размеров четырьмя цветами без многохроматических прямоугольников. Неизвестными в его таблице оставались всего несколько размеров: 17х17, 18х18 и 12Х21.
Математики Бренд Стейнбах (Bernd Steinbach) из института компьютерных наук при Техническом университете Фрайбергской горной академии (Германия), и Кристиан Постхофф (Christian Posthoff), бывший сотрудник департамента компьютерных и информационных технологий Университета Вест-Индии (Тринидад и Тобаго) сумели раскрасить граф 17х17 четырьмя цветами без единого монохроматического прямоугольника! Более того, они сумели также раскрасить матрицу размером 18х18. Таким образом, единственным нерешённым на сегодняшний день форматом остаётся 21х12.
Результаты работы "Most Complex Four-Colored Rectangle-free Grids — Solution of an Open Multiple-Valued Problem" и алгоритм Стейнбаха-Постхоффа будут опубликованы на международном симпозиуме по многозначной логике (International Symposia on Multiple-Valued Logic) 14 мая 2012 года в Виктории (Канада).
Отметим, что раскраска графов имеет большое практическое значение и используется в составлении расписаний, распределении регистров в микропроцессорах, распределении исполняемого кода по кэшу, распределении частот в радиосвязи для максимизации пропускной способности каналов и минимизации интерференции, распараллеливании численных методов, вычислении производных, цифровых водяных знаках, кластерном анализе и многих других сферах.
На самом деле она уникальна. Матрица размером 17 х 17 раскрашена четырьмя цветами, при этом на ней нельзя построить ни единого (!) прямоугольника, чтобы все углы его были одного цвета. Имеются в виду прямоугольники любого размера с вершинами в разных точках и рёбрами, параллельными осям x и y.
Для сравнения, если заменить цвет в любой ячейке, то появляется сразу множество монохроматических прямоугольников. Например, если цвет левой верхней ячейки поменять с синего на красный.
Аналогично, если поменять одну случайную ячейку из середины.
Данную задачу из области комбинаторного анализа поставил 20 ноября 2009 года Уильям Гасарч из Математического института Клэя, который ранее опубликовал фундаментальную работу по раскраске матриц, и в ней доказал раскрашиваемость или нераскрашиваемость матриц почти всех размеров четырьмя цветами без многохроматических прямоугольников. Неизвестными в его таблице оставались всего несколько размеров: 17х17, 18х18 и 12Х21.
Математики Бренд Стейнбах (Bernd Steinbach) из института компьютерных наук при Техническом университете Фрайбергской горной академии (Германия), и Кристиан Постхофф (Christian Posthoff), бывший сотрудник департамента компьютерных и информационных технологий Университета Вест-Индии (Тринидад и Тобаго) сумели раскрасить граф 17х17 четырьмя цветами без единого монохроматического прямоугольника! Более того, они сумели также раскрасить матрицу размером 18х18. Таким образом, единственным нерешённым на сегодняшний день форматом остаётся 21х12.
Результаты работы "Most Complex Four-Colored Rectangle-free Grids — Solution of an Open Multiple-Valued Problem" и алгоритм Стейнбаха-Постхоффа будут опубликованы на международном симпозиуме по многозначной логике (International Symposia on Multiple-Valued Logic) 14 мая 2012 года в Виктории (Канада).
Отметим, что раскраска графов имеет большое практическое значение и используется в составлении расписаний, распределении регистров в микропроцессорах, распределении исполняемого кода по кэшу, распределении частот в радиосвязи для максимизации пропускной способности каналов и минимизации интерференции, распараллеливании численных методов, вычислении производных, цифровых водяных знаках, кластерном анализе и многих других сферах.
