Метод Эйлера — Паркера — метод построения ортогонального квадрата для заданного латинского квадрата порядка . Предложен Паркером в 1959 годуParker E.T. Orthogonal Latin squares // Proc. Natl. Acad. Sci. USA. Vol. 45(6). 1959. pp. 859–862..
Метод
Метод поиска состоит из трех шагов: Построение множества трансверсалей заданного латинского квадрата. Выбор из них подмножеств из непересекающихся трансверсалей. Формирование ортогональных латинских квадратов из найденных подмножеств.
Построение трансверсалей и выбор непересекающихся подмножеств из них возможно реализовать с использованием метода полного перебора, однако более эффективной практической реализацией является полиномиальное сведение данных задач к , для решения которой эффективным является применение (DLX).
При поиске ортогональных диагональных латинских квадратов вместо трансверсалей общего вида используются диагональные трансверсали, в состав которых входит по одному элементу с главной и побочной диагонали квадрата.
Формирование ортогонального квадрата из найденного подмножества из непересекающихся трансверсалей производится путем заполнения каждой -й трансверсали значением в формируемом ортогональном квадрате.
Историческая справка
Леонардом Эйлером в ходе решения задачи о 36 офицерах была выдвинута гипотеза о том, что пары ортогональных латинских квадратов не существуют для всех размерностей . Верность гипотезы для размерности была подтверждена Томасом Клаузеном в 1842 году. Поиск контрпримера к гипотезе Эйлера был осуществлен в 1957 году Пейджем и Томпкинсом с использованием метода полного перебора на компьютере SWAC, однако он не увенчался успехом ввиду необходимости огромных вычислительных затрат. В 1959 году Паркером было предложено построение ортогонального квадрата с использованием трансверсалей и компьютера UNIVAC и был найден контрпример к гипотезе Эйлера для порядка . Аналогичный результат, опровергающий гипотезу Эйлера, был опубликован том же году в работе Бозе и Шринкхенде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.. В 1992 году Брауном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, имеющий одновременно 4 ортогональных диагональных латинских квадрата, 3 из которых приведены в статье, а 4-й был найден О. Заикиным с использованием подхода на базе SAT. В настоящее время известны диагональные латинские квадраты порядка 10, имеющие 1, 2, 3, 4, 5, 6, 7, 8 и 10 нормализованных ортогональных диагональных латинских квадратов (). Они формируют 42 комбинаторных структуры (графа из диагональных латинских квадратов на множестве бинарного отношения ортогональности). Большая часть из них была найдена в проекте добровольных распределенных вычислений Gerasim@Home начиная с 2017 г. Вопросы о существовании диагональных латинских квадратов порядка 10 с большим числом нормализованных ортогональных латинских квадратов и о существовании клики мощностью более двух из попарно ортогональных латинских квадратов порядка 10 в настоящее время являются открытыми.
См. также Латинский квадрат Трансверсаль
Примечания
Литература Кнут Д.Э. Искусство программирования. Т. 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. 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.
Категория:Комбинаторика Категория:Латинские квадраты