Н. Макарова

 

ПОДРОБНО О КВАЗИ-РАЗНОСТНОЙ МАТРИЦЕ

 

Часть II

 

Данная страница является продолжением страницы

http://www.natalimak1.narod.ru/quazi.htm

 

 

В первой части статьи были рассмотрены квази-разностные матрицы (КРМ) для составления латинских квдаратов и пар ОЛК, где латинские квадраты содержат подквадрат 1х1. Здесь будут рассмотрены КРМ для построения пар ОЛК, в которых латинские квадраты содержат латинский подквадрат 3х3. Понятно, что латинские квадраты пары ОЛК не могут содержать латинский подквадрат 2х2, так как не существует пары ортогональных латинских квадратов порядка 2. Хотя один латинский квадрат (без ортогонального соквадрата) может содержать латинский подквадрат 2х2. Вот пример такого латинского квадрата 20-го порядка (рис. 1):

 

 

Рис. 1

 

Данный латинский квадрат весь состоит из латинских подквадратов 2х2. Вот пример аналогичного латинского квадрата 6-го порядка (рис. 2):

 

 

Рис. 2

 

Вообще же латинский квадрат может не содержать ни одного латинского подквадрата. У меня вот лист распечатан из какой-то книги, и не записала на нём название книги, но на листе внизу написано: © 2000 by CRC Press LLC. На этом листе пример латинского квадрата 12-го порядка, не содержащего ни одного латинского подквадрата. Смотрите этот латинский квадрат на рис. 3.

 

 

Рис. 3

 

На этом же листе из книги приведён пример латинского квадрата 7-го порядка, содержащего латинский подквадрат 3х3 (рис. 4). На рисунке подквадрат 3х3 выделен зелёным цветом.

 

 

Рис. 4

 

Понятно, что подквадрат может находиться не только в верхнем или нижнем углу латинского квадрата. Переставив строки и столбцы в приведённом латинском квадрате 7-го порядка, мы получим такое расположение подквадрата (рис. 5):

 

 

Рис. 5

 

Однако вернёмся к квази-разностным матрицам. Здесь будут рассмотрены КРМ пар ОЛК чётного порядка, в которых латинские квадраты содержат латинский подквадрат 3х3. Эти КРМ содержат три символьных элемента, я буду обозначать их a, b, c. Латинский квадрат 4-го порядка не может содержать подквадрат 3х3. Поэтому начнём с латинского квадрата порядка 8. Одиночный латинский квадрат 8-го порядка с подквадратом 3х3 составить очень просто (рис. 6). Однако ортогональный соквадрат к этому латинскому квадрату построить невозможно (речь идёт об ортогональном квадрате такой же точно структуры, то есть содержащем подквадрат 3х3; может быть, ортогональный квадрат другой структуры для этого латинского квадрата и существует).

 

 

Рис. 6

 

КРМ для данного латинского квадрата имеет следующий вид (рис. 7):

 

 

Рис. 7

 

Невозможность построения к данному латинскому квадрату ортогонального соквадрата, означает: к приведённой КРМ невозможно добавить четвёртую строку, чтобы она была совместима с тремя имеющимися строками по известному критерию (о критерии совместимости см. в(о критерии совместимости см.  КРМ невозможно добавить четвёртую строку, чтобы она была совместима с тремя имеющимися строками  первой части статьи). Это очевидно: в КРМ есть только два столбца без символьных элементов, поэтому в четвёртой строке некуда вписать третий символьный элемент.

Символьные элементы a, b, c в этой КРМ принимают значения 6, 7, 8 в любой комбинации.

 

Теперь перехожу к парам ОЛК 10-го порядка, в которых латинские квадраты содержат подквадрат 3х3. Мне известны три вида таких пар. Начну с самой известной пары Паркера. На рис. 8 показана КРМ для данной пары, а на рис. 9 сама эта пара (пара приводится по книге М. Гарднера  “Математические досуги”, М.: Мир, 1972). В латинских квадратах выделены подквадраты 3х3. Понятно, что латинские подквадраты 3х3, содержащиеся в этих ортогональных латинских квадратах, тоже ортогональны. При этом можно брать любую пару ортогональных квадратов 3х3.

 

 

Рис. 8

 

 

Рис. 9

 

Здесь символьные элементы принимают значения 7, 8, 9 в любой комбинации. Например, присвоим эти значения так: a = 9, b = 8, c = 7. Получим следующую пару ОЛК (рис. 10):

 

 

Рис. 10

 

В КРМ первому латинскому квадрату соответствует светло-зелёная строка, второму латинскому квадрату – зелёная строка. Критерий совместимости всех строк выполняется. Здесь разности чисел в строках считаются по модулю 7 = n - 3.

 

Автором второго вида пары ОЛК является Stinson. На рис. 11 показана КРМ этой пары ОЛК, а на рис. 12 сама пара.

 

 

Рис. 11

 

 

Рис. 12

 

Наконец, третий вид пары ОЛК 10-го порядка найден мной в Интернете (ссылка указана на странице, посвящённой ортогональным латинским квадратам 10-го порядка: http://www.natalimak1.narod.ru/aspekty7.htm ). Это самая изящная пара ОЛК. Именно по схеме этой пары я разрабатывала алгоритм построения пар ОЛК серии порядков n ≡ 4 (mod 6). На рис. 13 изображена КРМ для этой пары ОЛК, а на рис. 14 вы видите эту пару.

 

 

Рис. 13

 

 

Рис. 14

 

Здесь символьные элементы принимают значения 0, 8, 9 в любой комбинации (можно также брать такой вариант значений: 8, 9, 10; тогда латинские квадраты будут заполнены в нетрадиционном виде числами от 1 до 10).

 

Пара ОЛК 12-го порядка с подквадратом 3х3 построена мной по алгоритму для серии порядков n = 6k, k>1. Вы видите эту пару на рис. 15 – 16.

 

Первый латинский квадрат

 

 

Рис. 15

 

Второй латинский квадрат

 

 

Рис. 16

 

Здесь символьные элементы принимают значения 0, 10, 11 (или 10, 11, 12) в любой комбинации.

Теперь покажу КРМ этой пары ОЛК (рис. 17):

 

 

Рис. 17

 

Интересная коллекция пар ОЛК, не правда ли? Обратите внимание на одинаковую структуру КРМ для всех показанных пар ОЛК. Для следующих пар ОЛК структура КРМ точно такая же. Одинаковую структуру имеют и латинские квадраты этих пар ОЛК.

 Продолжаю показ коллекции. Пару ОЛК 14-го порядка с подквадратом 3х3 я построила по описанию, приведённому в книге М. Холла “Комбинаторика”. Показываю эту пару на рис. 18 – 19.

 

Первый латинский квадрат

 

 

Рис. 18

 

Второй латинский квадрат

 

 

Рис. 19

 

Понятно, что здесь символьные элементы принимают значения 11, 12, 13 в любой комбинации. Теперь предлагаю посмотреть на КРМ этой пары ОЛК (рис. 20):

 

 

Рис. 20

 

В статье по указанной ниже ссылке приведена пара ОЛК 16-го порядка, в которой латинские квадраты тоже содержат подквадрат 3х3.

 

http://www.emba.uvm.edu/~dinitz/preprints/n2resolvable.pdf

 

Вот  копия КРМ для этой пары ОЛК из статьи (рис. 21):

 

 

Рис. 21

 

Построим латинские квадраты по этой КРМ. Эти квадраты вы видите на рис. 22 – 23.

 

Первый латинский квадрат

 

 

Рис. 22

 

Второй латинский квадрат