Метод Эйлера — Паркера

Метод Эйлера — Паркера — метод построения ортогонального квадрата для заданного латинского квадрата порядка $\text{[math]}$ $\text{[math]}$ $N$ $N$ . Предложен Паркером в 1959 году^[1].

МетодПравить

Пример диагонального латинского квадрата (а); множество его диагональных трансверсалей (б), элементы трансверсалей, лежащие на диагоналях, выделены серым; процесс построения ортогонального диагонального латинского квадрата из непересекающихся трансверсалей по методу Эйлера — Паркера (в).

Метод поиска состоит из трех шагов:

Построение множества трансверсалей заданного латинского квадрата.
Выбор из них подмножеств из $\text{[math]}$ $\text{[math]}$ $N$ непересекающихся трансверсалей.
Формирование ортогональных латинских квадратов из найденных подмножеств.

Построение трансверсалей и выбор непересекающихся подмножеств из них возможно реализовать с использованием метода полного перебора, однако более эффективной практической реализацией является полиномиальное сведение данных задач к задаче о точном покрытии ( Exact cover — версия статьи «Задача о точном покрытии» на английском языке англ.), для решения которой эффективным является применение алгоритма танцующих связей ( Knuth's Algorithm X — версия статьи «Алгоритм танцующих связей» на английском языке англ.) (DLX).

При поиске ортогональных диагональных латинских квадратов вместо трансверсалей общего вида используются диагональные трансверсали, в состав которых входит по одному элементу с главной и побочной диагонали квадрата.

Формирование ортогонального квадрата из найденного подмножества из $\text{[math]}$ $\text{[math]}$ $N$ непересекающихся трансверсалей производится путем заполнения каждой $\text{[math]}$ $\text{[math]}$ $i$ -й трансверсали значением $\text{[math]}$ $\text{[math]}$ $i$ в формируемом ортогональном квадрате.

Историческая справкаПравить

Первая пара ортогональных латинских квадратов порядка 10, найденная Паркером в 1959 г.^[1]

Леонардом Эйлером в ходе решения задачи о 36 офицерах была выдвинута гипотеза о том, что пары ортогональных латинских квадратов не существуют для всех размерностей $\text{[math]}$ $\text{[math]}$ $N=4t+2$ . Верность гипотезы для размерности $\text{[math]}$ $\text{[math]}$ $N=6$ была подтверждена Томасом Клаузеном в 1842 году. Поиск контрпримера к гипотезе Эйлера был осуществлен в 1957 году Пейджем и Томпкинсом с использованием метода полного перебора на компьютере SWAC, однако он не увенчался успехом ввиду необходимости огромных вычислительных затрат. В 1959 году Паркером^[1] было предложено построение ортогонального квадрата с использованием трансверсалей и компьютера UNIVAC и был найден контрпример к гипотезе Эйлера для порядка $\text{[math]}$ $\text{[math]}$ $N=10$ . Аналогичный результат, опровергающий гипотезу Эйлера, был опубликован том же году в работе Бозе и Шринкхенде^[2]. В 1992 году Брауном^[3] описан диагональный латинский квадрат порядка 10, имеющий одновременно 4 ортогональных диагональных латинских квадрата, 3 из которых приведены в статье, а 4-й был найден О. Заикиным с использованием подхода на базе SAT. В настоящее время известны диагональные латинские квадраты порядка 10, имеющие 1, 2, 3, 4, 5, 6, 7, 8 и 10 нормализованных ортогональных диагональных латинских квадратов (последовательность A287695 в OEIS). Они формируют 42 комбинаторных структуры (графа из диагональных латинских квадратов на множестве бинарного отношения ортогональности)^[4]. Большая часть из них была найдена в проекте добровольных распределенных вычислений Gerasim@Home начиная с 2017 г. Вопросы о существовании диагональных латинских квадратов порядка 10 с большим числом нормализованных ортогональных латинских квадратов и о существовании клики мощностью более двух из попарно ортогональных латинских квадратов порядка 10 в настоящее время являются открытыми.

См. такжеПравить

ПримечанияПравить

↑ ¹ ² ³ Parker E.T. Orthogonal Latin squares // Proc. Natl. Acad. Sci. USA. Vol. 45(6). 1959. pp. 859–862.
↑ Bose R.C., Shrikhande S.S. On the falsity of Euler's conjecture about the non-existence of two orthogonal latin squares of order 4t + 2 // Proc Natl Acad Sci U S A. 1959 May; 45(5): 734–737.
↑ Brown J.W., Cherry F., Most L., Most M., Parker E.T., Wallis W.D. Completion of the spectrum of orthogonal diagonal Latin squares // Lecture notes in pure and applied mathematics. 1992. Vol. 139. pp. 43–49.
↑ Список комбинаторных структур из ДЛК порядка 10 на множестве отношения ортогональности (неопр.). Дата обращения: 5 июня 2020. Архивировано 21 мая 2020 года.

ЛитератураПравить

Кнут Д.Э. Искусство программирования. Т. 4А. Комбинаторные алгоритмы. Ч. 1. М.: Вильямс, 2013. 960 с.
Colbourn C.J., Dinitz J.H. Handbook of Combinatorial Designs, Second Edition. Chapman & Hall/CRC, 2006. 1016 p.
Keedwell A.D., Dénes J. Latin Squares and their Applications. Elsevier, 2015. 438 p. doi:10.1016/C2014-0-03412-0
Vatutin E., Nikitina N., Belyshev A., Manzyuk M. On polynomial reduction of problems based on diagonal Latin squares to the exact cover problem // CEUR Workshop Proceedings. Proceedings of the Second International Conference Information, Computation, and Control Systems for Distributed Environments (ICCS-DE 2020). Vol. 2638. Technical University of Aachen, Germany, 2020. urn:nbn:de:0074-2638-1.

[Parker-1] ¹ ² ³ Parker E.T. Orthogonal Latin squares // Proc. Natl. Acad. Sci. USA. Vol. 45(6). 1959. pp. 859–862.

[2] Bose R.C., Shrikhande S.S. On the falsity of Euler's conjecture about the non-existence of two orthogonal latin squares of order 4t + 2 // Proc Natl Acad Sci U S A. 1959 May; 45(5): 734–737.

[3] Brown J.W., Cherry F., Most L., Most M., Parker E.T., Wallis W.D. Completion of the spectrum of orthogonal diagonal Latin squares // Lecture notes in pure and applied mathematics. 1992. Vol. 139. pp. 43–49.

[4] Список комбинаторных структур из ДЛК порядка 10 на множестве отношения ортогональности (неопр.). Дата обращения: 5 июня 2020. Архивировано 21 мая 2020 года.

[1]

[2]

[3]

[4]