| Главная | Эксперименты | Утилиты | Компоненты | Что почитать | Контакты |
|
|
В методе используются трансверсали (transversal), поэтому, прежде всего, определение: трансверсаль квадрата - это коллекция n его элементов, таких, что все они расположены в разных строках, колонках и содержат ровно по одному разу все элементы используемого множества чисел. Пример трансверсалей для квадрата порядка 4:
Так вот, если обе диагонали квадрата образуют трансверсаль, латинский квадрат называется диагональным (doubly diagonalized). (Квадрат, у которого только главная диагональ образует трансверсаль, в статье называется diagonalized. Поскольку диагональным мы называем квадрат с двумя диагоналями, для квадрата с одной диагональю оставим английский термин diagonalized.) Лемма: Для любого n ≥ 3 существует diagonalized латинский квадрат порядка n, в котором есть трансверсаль, не имеющая общих элементов с главной диагональю. Доказательство делится на три части. Для нечетного n циклический латинский квадрат (мультипликативная таблица циклических групп порядка n) может быть сформирован как сумма из n трансверсалей, одна из которых главная диагональ. Например, для n = 3 и множества символов {1,2,3}
Для порядков 4 и 6 просто приводится пара таких квадратов:
Наконец, для четных n ≥ 8 такой квадрат строится из двух циклических латинских квадратов.
Первый квадрат Cn-3 порядка n-3 из символов {1 … n-3}, второй C3 порядка 3 из символов {n-2, n-1, n}. Чтобы заполнить пустые области, выбираем трансверсали квадрата Cn-3 (кроме главной диагонали) и выполняем следующее: Для трансверсали проектируем ее символы вертикально на свободную строку и горизонтально на свободную колонку и заменяем все символы выбранной трансверсали на n-2. Повторяем эту процедуру еще для двух трансверсалей, заменяя их символы на n-1 и n . В результате мы получим diagonalized латинский квадрат из символов {1 … n} . И, поскольку заменены только три трансверсали, существует еще (n-3)-3 ≥ 2 трансверсалей, отличных от главной диагонали. Можно использовать любое деление квадратов на части n = (n-m) + m , где m - нечетное и 3 < m < n-m. Теорема Для любого n ≥ 4 существует диагональный латинский квадрат порядка n. Будем строить диагональный латинский квадрат из 4-х латинских квадрата D1, D2, D3, D4 порядка k ≥ 2. Рассмотрим отдельно два случая - для четных n = 2k и для нечетных n = 2k+1:
Берем квадрат D1, удовлетворяющий лемме. Квадрат D2 строим из него отражением по вертикали и каждый элемент заменяем на (x+k) mod 2k
Квадрат D3 получаем из квадрата D1. Для этого записываем в обратном порядке элементы главной диагонали, а под ними проектируем элементы тансверсали. Полученные пары символов используем для замены элементов в квадрате D1. Квадрат D4 получаем из квадрата D2 аналогично.
Для итогового квадрата порядка 2k меняем верхние трансверсали и нижние диагонали:
Для итогового квадрата порядка 2k+1, как и в первом случае меняем местами верхние трансверсали и нижние диагонали. Затем трансверсали квадратов D1 и D3 проецируем на среднюю строку и колонку и заменяем на n. Центральный элемент тоже равен n.
1↑Ervin Gergely. A Simple Method for Constructing Doubly Diagonalized Latin Squares. 1972.
В приложении исходники описанного алгоритма и приложение
для построения диагонального латинского квадрата. (Порядок квадрата задается
как параметр)
|