Пушкарёв И. А. 3(2017)

УДК 004.4

И. А. Пушкарёв, И. А. Клюкин

ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ДЛЯ РЕШЕНИЯ ЗАДАЧИ ПОИСКА ЭКЗОТИЧЕСКИХ СТРУКТУР,

НЕДОПОЛНИМЫХ ДО ЛАТИНСКОГО КВАДРАТА

      Вопрос о дополнимости подмножеств клеток квадрата со стороной n, раскрашенных в n цветов так, чтобы ни в одной строке и ни в одном столбце не содержалось бы двух одноцветных клеток, до латинского квадрата, то есть – такого, в котором в любой строке и в любом столбце все клетки были бы разноцветными, является одним из старых классических вопросов современной комбинаторики расположений.

      Кроме классического общеизвестного результата Райзера [1] и теоремы Галвина о «предписанном заполнении» следует отметить доказательство Б. Сметанюком так называемой «гипотезы Эванса» [2, 5] о том, что любое расположение n-1 клетки, не содержащее ни в строках, ни в столбцах двух одноцветных клеток, дополнимо до латинского квадрата.

     Теорема Сметанюка не означает, что любое раскрашенное множество клеток, содержащее больше, чем n-1 клетку не является дополнимым. Можно представить себе недополнимое множество, содержащее, не менее, чем n+1 клеток, такое, что удаление любой клетки делает его дополнимым до латинского квадрата – «минимальное недополнимое подмножество».

     Работа посвящена построению большого семейства «стандартных» минимальных больших недополнимых подмножеств и обсуждению задачи поиска «нестандартных» больших недополнимых подмножеств.

       Ключевые слова: латинский квадрат, недополнимая структура, теорема Сметанюка.