Исследования свойств латинских квадратов
На момент блокировки старого сайта, оставались не проверенными две чистые симметрии ЛК10 — (8,8,8) и (16,16,16).
Существенно различных ЛК с симметрией (8,8,8) существует 6458796, а с симметрией (16,16,16) — 806668715 (из них 806446358 не имеют других чистых симметрий).
На Герасиме были выполнены два проекта по поиску марьяжных ДЛК с этими симметриями. Результаты следующие:
1) Марьяжных ДЛК с симметрией (8,8,8) существует 42, из них 1 двойка и 41 единица. В замыкание входят 1 двойка и 84 единицы, всего 85 ДЛК.
https://yadi.sk/d/xwbu7dJfnBq-9A
2) В проекте было найдено 3099 марьяжных ДЛК с симметрией (16,16,16). Ещё 557 ДЛК были найдены при проверке других симметрий. Всего марьяжных ДЛК с симметрией (16,16,16) существует 3656, в том числе 3233 единицы, 376 двоек, 1 тройка, 44 четвёрки и 2 шестёрки. Их замыкание содержит 7420 марьяжных ДЛК, в том числе 6985 единиц, 388 двоек, 1 тройка, 44 четвёрки и 2 шестёрок.
https://yadi.sk/d/ycYHMjOClFmO8g
На этом проверка чистых симметрий завершилась. Всего было найдено 33490 марьяжных ДЛК, обладающих какой-нибудь чистой симметрией. В том числе:
count[1] = 13167
count[2] = 19846
count[3] = 1
count[4] = 458
count[6] = 8
count[8] = 9
count[10] = 1
Всего: 33490
Их замыкание содержит 71425 марьяжных ДЛК. В том числе:
count[1] = 50260
count[2] = 20661
count[3] = 12
count[4] = 473
count[5] = 1
count[6] = 8
count[8] = 9
count[10] = 1
Всего: 71425
https://yadi.sk/d/YvRpm0-7cpdHPg
На очереди проверка смешанных симметрий. На старом форуме отмечал, что коды смешанных симметрий (они имеют один или два "+") определены в программе Автоизор плохо — они не инварианты относительно эквивалентных преобразований ЛК. В версии Автоизор 3.0 этот недостаток устранён, кроме того, эта версия работает мгновенно. Среди смешанных симметрий только шесть независимы, все прочие смешанные симметрии подчинены какой-нибудь чистой симметрии, а потому ЛК с такими симметриями были уже перечислены. Итого осталось проверить шесть симметрий с кодами:
(1,1,1)+
(1,1,2)+
(1,1,4)+
(1,1,8)+
(1,1,16)+
(1,1,1)++
Теоретически возможны следующие смешанные симметрии:
(1,1,2)+
(1,1,4)+
(1,1,8)+
(1,1,16)+
(1,1,31)+
(1,7,7)+
(1,7,13)+
(1,7,24)+
(1,10,10)+
(1,10,11)+
(1,10,18)+
(1,10,19)+
(1,10,33)+
(1,10,34)+
(1,15,15)+
(1,15,26)+
(1,16,21)+
(1,16,36)+
(1,21,22)+
(1,21,37)+
(1,27,27)+
(1,27,28)+
(1,30,30)+
(1,31,1)+
(1,31,2)+
(1,31,4)+
(1,31,5)+
(1,31,8)+
(1,31,9)+
(1,31,16)+
(1,31,17)+
(1,31,21)+
(1,31,31)+
(1,31,32)+
(1,31,36)+
(1,34,10)+
(1,34,11)+
(1,34,18)+
(1,34,19)+
(1,34,33)+
(1,34,34)+
(1,34,38)+
(1,34,40)+
(1,36,22)+
(1,36,37)+
(1,41,1)+
(1,41,2)+
(1,41,4)+
(1,41,7)+
(1,41,8)+
(1,41,13)+
(1,41,16)+
(1,41,24)+
(1,41,31)+
(1,41,41)+
(1,41,42)+
(1,42,1)+
(1,42,2)+
(1,42,4)+
(1,42,5)+
(1,42,7)+
(1,42,8)+
(1,42,9)+
(1,42,13)+
(1,42,16)+
(1,42,17)+
(1,42,21)+
(1,42,24)+
(1,42,29)+
(1,42,31)+
(1,42,32)+
(1,42,36)+
(1,42,41)+
(1,42,42)+
(1,1,1)++
(1,1,7)++
(1,1,8)++
(1,1,10)++
(1,1,11)++
(1,1,15)++
(1,1,16)++
(1,1,19)++
(1,1,21)++
(1,1,22)++
(1,1,27)++
(1,1,28)++
(1,1,30)++
(1,1,41)++
Легко показать, что симметрии (1,1,31)+ не существует. Подтверждено существование всех шести независимых смешанных симметрий — (1,1,1)+, (1,1,2)+, (1,1,4)+, (1,1,8)+, (1,1,16)+, (1,1,1)++. А так как всякая подчинённая смешанная симметрия подчинена некоторой нетривиальной чистой симметрии, то все ЛК, обладающие такими симметриями, уже были найдены. Перебрав эти ЛК можно установить какие смешанные симметрии реально существуют.
Так как теперь смешанные симметрии получили адекватные коды, то внёс соответствующие изменения в программу find_symm. Версия 3.0 выводит все симметрии, а не только чистые.
Третью версию Канонизатора ДЛК можно скачать по ссылке
https://yadi.sk/d/SKM3rnxw0Oxdhg
Работает вдвое быстрее предыдущей и может обрабатывать громадные файлы (до 5 миллиардов ДЛК). Есть возможность выбрать формат вывода:
— КФ / имена КФ;
— сортировать / не сортировать.
Канонизатор ЛК 2.0 с той же функциональностью, что и Канонизатор ДЛК 3.0.
https://yadi.sk/d/sDSqxfzrRgek-A
Программа Ортогон 3.0 работает втрое быстрее предыдущей версии и это для 32-битного кода. Ускорение получено за счёт перехода при поиске д-трансверсалей от DLX к использованию битовой арифметики (но это всё ещё X-алгоритм Кнута, только "танцующие связи" заменены "танцующими битами", так сказать, DBX-алгоритм 
). Можно рассчитывать ещё на двукратное ускорение при 64-битной компиляции.
https://yadi.sk/d/NE9Ei2tQ0yOjWw
Программа zamyk.exe выполняет алгоритм пакетного файла zamyk.bat, но делает это в два раза быстрее. Входной файл может содержать либо ЛК (в том числе ДЛК), либо 24-символьные имена ЛК, либо 25-символьные имена ДЛК.
https://yadi.sk/d/-6yWKDxW-lYu5A
Программа zamyk_express.exe аналогична программе zamyk.exe, только выполняет замыкание отношения ортогональности на множестве главных классов ДЛК. Поэтому работает быстрее почти в 80 раз, хотя мощность такого экспресс-замыкания обычно меньше мощности замыкания.
https://yadi.sk/d/tcxTRB_byNXkSA
Версия 2.0 утилиты sol_operate которая теперь может обрабатывать файлы практически неограниченного размера.
Подсчёт числа главных классов ДЛК9 (и нормализованных ДЛК9) занял на Герасиме четыре дня. Реально ли выполнить такой же подсчёт для ДЛК10? Сказать трудно, но весьма точные эвристические оценки можно получить довольно быстро. За основу возьмём алгоритм программы counter_var_row.
Файл readme.txt
По запросу нужно ввести номер линейки, программа найдёт все варианты заполнения первой строки и попросит выбрать один из них. Аналогично и для других строк. Если на запрос номера варианта ввести 0, то заполнение текущего квадрата прекращается, а варианты заполнения текущей строки будут сохранены в файл varianty.txt вместе с уже частично заполненным ДЛК.
Если вариантов заполнения текущей строки 0, то на консоль выводится частично заполненный ДЛК. Полный ДЛК выводится на консоль если удастся заполнить все 10 строк.
https://yadi.sk/d/7Ci8oPIBXxtDZQ
И создадим на его основе программу Оценщик.
Файл readme.txt
По запросу нужно ввести номер линейки, глубину поиска (число заполняемых строк), размер выборки (число случайных выборов вариантов заполнения) и точность оценки (число значащих цифр). На основе выборки, для каждой заполняемой строки подсчитывается среднее число вариантов заполнения. Полученные значения перемножаются, а результат умножения выводится на экран.
https://yadi.sk/d/2FmRLJqUII-ctg
Но насколько такие оценки точны? Для проверки этого воспользуемся программой counter_zapoln.
Файл readme.txt
По запросу нужно ввести номер линейки и число заполняемых недиагональных ячеек. Прогресс выводится каждые 5 секунд в виде строки символов '#', а каждые 5 минут дополнительно выводится число уже найденных вариантов заполнения.
https://yadi.sk/d/xz6QTXktnc6eMw
Например, найдём точное число вариантов заполнения первых трёх строк СНДЛК 1-й линейки с помощью программы counter_zapoln, а затем оценим это число с помощью программы Оценщик.
Номер линейки: 1
Число ячеек : 24
############################################################
4041620425############################################################
8142631958############################################################
12248203241############################################################
16362170770########################################
Вариантов : 19123827456
Время поиска : 1404.45 сек
Продолжить? (Y/N):
Программа Оценщик
Линейка : 1
Глубина : 3
Размер : 1000
Точность: 4
Оценка : 1.915E+010
Время : 0.327 сек
Продолжить? (Y/N):
Получили точность оценки 0,15%
Полученные для каждой из 67 линеек оценки числа СНДЛК нужно умножить на соответствующий множитель чтобы получить оценку числа нормализованных ДЛК. Эти множители следующие:
2 -> 7680
3 -> 960
4 -> 3840
5 -> 3840
6 -> 768
7 -> 3840
8 -> 3840
9 -> 7680
10 -> 3840
11 -> 3840
12 -> 3840
13 -> 3840
14 -> 7680
15 -> 320
16 -> 7680
17 -> 7680
18 -> 3840
19 -> 7680
20 -> 7680
21 -> 7680
22 -> 3840
23 -> 7680
24 -> 7680
25 -> 3840
26 -> 7680
27 -> 3840
28 -> 7680
29 -> 7680
30 -> 7680
31 -> 7680
32 -> 3840
33 -> 3840
34 -> 3840
35 -> 3840
36 -> 320
37 -> 960
38 -> 320
39 -> 7680
40 -> 3840
41 -> 7680
42 -> 3840
43 -> 7680
44 -> 7680
45 -> 7680
46 -> 7680
47 -> 7680
48 -> 7680
49 -> 3840
50 -> 1536
51 -> 768
52 -> 3840
53 -> 3840
54 -> 7680
55 -> 7680
56 -> 7680
57 -> 15360
58 -> 15360
59 -> 15360
60 -> 15360
61 -> 15360
62 -> 15360
63 -> 15360
64 -> 7680
65 -> 15360
66 -> 15360
67 -> 7680
Разделив оценку числа нормализованных ДЛК10 на 15360, найдём оценку нижней границы числа главных классов ДЛК10.
Программы Именатор/Деименатор для ЛК/ДЛК ранее уже выкладывались на старом форуме. Выложу их и здесь.
https://yadi.sk/d/ClwlHDE7ILjuaA
Эти программы позволяют по КФ ДЛК (КФ ЛК) получать 25-символьные (24-символьные) имена соответствующих главных классов, и наоборот.
Как отмечалось на старом форуме, отношение ортогональности ДЛК индуцирует отношение ортогональности главных классов ДЛК. А именно, два главных класса ДЛК называются ортогональными если найдётся пара ортогональных ДЛК один из которых принадлежит первому классу, а другой — второму.
Компоненты связности отношения ортогональность на множестве главных классов ДЛК будем для простоты называть компонентами ортогональности (КО) ДЛК. Именем КО будем считать наименьшее из имён всех членов КО.
Имеющиеся списки марьяжных ДЛК можно сократить как минимум вдвое если хранить только представителей КО. Зная представителя, КО легко развернуть в случае необходимости, эту работу выполняет программа zamyk_ko_dlk.
https://yadi.sk/d/HFtM0-s1JbW5HQ
Имеющаяся в том же архиве программа predstav_ko_dlk выполняет обратную работу — превращающим список имён произвольных СНДЛК10 в список наименьших представителей соответствующих компонент ортогональности ДЛК10.
Применим последнюю программу к списку из 9837243 ДЛК про который утверждалось следующее:
1) в список входят только марьяжные ДЛК;
2) каждый ДЛК, входящий в список, входит в него вместе со всем своим замыканием.
Поиск минимального представителя КО ДЛК10
Введено имён: 9837243
. . . . . . . . . . .
Проверено : 4943973
Найдено : 4943969
Сумма ОДЛК : 9880590
Время работы: 4866.89 сек
Поясню, для избежания повторной работы, уже найденные члены компонент ортогональности удаляются из первоначального списка, поэтому Проверено меньше чем Введено.
Видим, что:
1) Найдено меньше чем Проверено, то есть 4 ДЛК из списка не марьяжные;
2) в исходном списке пропущено 43351 марьяжных ДЛК (на эту величину Введено минус 4 не марьяжных меньше чем Сумма ОДЛК).
То есть оба утверждения о списке из 9837243 ДЛК оказались неверными. А корректному списку из 9880590 марьяжных ДЛК соответствует список из 4943969 представителей КО ДЛК.
Строго говоря, про вчерашний список 9880590 марьяжных ДЛК тоже нельзя с абсолютной уверенностью сказать, что он содержит замыкание всякого входящего в него ДЛК. Но это верно для экспресс-замыкания. Кстати, если потребуется развернуть все КО, то нужно применить к списку представителей КО программу zamyk_express. Для развёртывания одной КО или небольшого их числа, лучше использовать программу zamyk_ko_dlk. Список 4943969 представителей КО ДЛК можно посмотреть по ссылке:
https://yadi.sk/d/e35o1tUizrVjLA
Пример применения программы zamyk_express к списку из 4943969 представителей компонент ортогональности ДЛК:
Замыкание компонент ортогональности ДЛК10
Введено ДЛК : 4943969
. . . . . . . . . . . .
Найдено ОДЛК: 9880590
count[1] = 9834934
count[2] = 44916
count[3] = 125
count[4] = 587
count[5] = 3
count[6] = 11
count[7] = 1
count[8] = 11
count[10] = 2
Время работы: 5049.8 сек
Полученные результаты можно посмотреть по ссылке:
https://yadi.sk/d/qXgtJb8AdHme3Q
Компоненту ортогональности ДЛК можно представить графом. В общем случае, это будет орграф с кратными дугами и петлями. Но обладающий следующим свойством:
если графу принадлежит дуга a->b, то ему принадлежит и дуга b->a, возможно, другой кратности.
Например, рассмотрим компоненту Eh6u8eS59KnQjFB5sJAW4oFry:
1 Eh6u8eS59KnQjFB5sJAW4oFry[4]
2 Gz5ZTwk65272HnpkKPPKBMBfP[2]
3 HDhKtH5iB9soZo8aALNBHDECr[2]
4 HDqXSZqDD9jc1WNRtLNBHDECr[2]
1: 2,3,4(2)
2: 1(2)
3: 1(2)
4: 1(2)
Ей соответствует граф с матрицей смежности:
|0 1 1 2|
|2 0 0 0|
|2 0 0 0|
|2 0 0 0|
Дуги 1->2 и 1->3 имеют кратность 1. Им соответствую дуги 2->1 и 3->1 с кратностью 2.
Ещё пример, компонента 2nceygR79Mnc7sdUzShDkxSUi:
1 2nceygR79Mnc7sdUzShDkxSUi[2]
2 2nceygR79Mnc7wME6ShzLjR4L[2]
1: 1,2
2: 1,2
Ей соответствует граф с матрицей смежности:
|1 1|
|1 1|
Этот граф имеет две петли 1-1 и 2-2.
Будем называть две различные компоненты однотипными, если соответствующие им графы изоморфны. Введём также обобщённый тип компонент на основе следующего неполного инварианта графа.
Пусть M обозначает матрицу смежности графа КО. Тогда M[i,i] равно числу петель вершины i, а M[i,j] равно числу дуг i->j.
Удобно взять следующий инвариант:
inv = {P[i]|i in V}, P[i] = (M[i,i],{(M[i,j],M[j,i])|j in V & j != i})
то есть мультимножество упорядоченных пар, первый элемент которой есть число петель вершины i, а второй — мультимножество упорядоченных пар (M[i,j],M[j,i]).
Например, для первой компоненты инвариант равен:
0:(1,2)(1,2)(2,2)
0:(2,1)
0:(2,1)
0:(2,2)
А для второй:
1:(1,1)
1:(1,1)
Все 4943969 компонент распадаются на 38 обобщённых типов. В дальнейшем был найден 39-й обобщённый тип КО.
0:(1,1)
0:(1,1)
#2
0:(1,1)
0:(1,1)
0:(1,1)
0:(1,1)
0:(1,1)
0:(1,1)
0:(1,1)
0:(1,1)
0:(1,1)(1,1)(1,1)(1,1)(1,1)(1,1)(1,1)(1,1)
#3
0:(1,1)
0:(1,1)
0:(1,1)
0:(1,1)
0:(1,1)
0:(1,1)
0:(1,1)
0:(1,1)(1,1)(1,1)(1,1)(1,1)(1,1)(1,1)
#4
0:(1,1)
0:(1,1)
0:(1,1)
0:(1,1)
0:(1,1)
0:(1,1)
0:(1,1)(1,1)
0:(1,1)(1,1)
0:(1,1)(1,1)
0:(1,1)(1,1)
0:(1,1)(1,1)(1,1)(1,1)
0:(1,1)(1,1)(1,1)(1,1)(1,1)(1,1)(1,1)(1,1)(1,1)(1,1)
#5
0:(1,1)
0:(1,1)
0:(1,1)
0:(1,1)
0:(1,1)
0:(1,1)
0:(1,1)(1,1)(1,1)(1,1)(1,1)(1,1)
#6
0:(1,1)
0:(1,1)
0:(1,1)
0:(1,1)
0:(1,1)
0:(1,1)(1,1)(1,1)(1,1)(1,1)
#7
0:(1,1)
0:(1,1)
0:(1,1)
0:(1,1)
0:(1,1)(1,1)
0:(1,1)(1,1)(1,1)(1,1)
#8
0:(1,1)
0:(1,1)
0:(1,1)
0:(1,1)
0:(1,1)(1,1)(1,1)(1,1)
#9
0:(1,1)
0:(1,1)
0:(1,1)
0:(1,1)(1,1)(1,1)
#10
0:(1,1)
0:(1,1)
0:(1,1)(1,1)
#11
0:(1,1)
0:(1,1)
0:(1,1)(1,1)
0:(1,1)(1,1)
#12
0:(1,1)
0:(1,1)
0:(1,1)(1,1)
0:(1,1)(1,1)
0:(1,1)(1,1)
0:(1,1)(1,1)(1,1)(1,1)
#13
0:(1,1)
0:(1,1)
0:(1,1)(1,1)
0:(1,1)(1,1)
0:(1,1)(1,1)
0:(1,1)(1,1)(1,1)(1,1)
0:(1,1)(1,1)(1,1)(1,1)
0:(1,1)(1,1)(1,1)(1,1)
#14
0:(1,1)
0:(1,1)
0:(1,1)(1,1)(1,2)
0:(2,1)
#15
0:(1,1)
0:(1,1)
0:(1,1)(1,1)(1,2)(1,2)
0:(2,1)
0:(2,1)
#16
0:(1,1)
0:(1,1)(1,1)
0:(1,1)(1,1)
0:(1,1)(1,1)
0:(1,1)(1,1)(1,1)
#17
0:(1,1)
0:(1,1)(1,2)
0:(1,2)(1,2)
0:(2,1)
0:(2,1)(2,1)
#18
0:(1,1)
0:(1,1)(1,2)
0:(2,1)
#19
0:(1,1)
1:(1,1)
#20
0:(1,1)(1,1)
0:(1,1)(1,1)
0:(1,1)(1,1)
0:(1,1)(1,1)
#21
0:(1,1)(1,1)
0:(1,1)(1,1)
0:(1,1)(1,1)
0:(1,1)(1,1)
0:(1,1)(1,1)(1,1)(1,1)
0:(1,1)(1,1)(1,1)(1,1)
#22
0:(1,1)(1,1)
0:(1,1)(1,1)
0:(1,1)(1,1)
0:(1,1)(1,1)(1,1)
0:(1,1)(1,1)(1,1)
#23
0:(1,2)
0:(1,2)
0:(1,2)
0:(1,2)
0:(1,2)
0:(2,1)(2,1)(2,1)(2,1)(2,1)
#24
0:(1,2)
0:(1,2)
0:(1,2)
0:(1,2)
0:(2,1)(2,1)(2,1)(2,1)
#25
0:(1,2)
0:(1,2)
0:(1,2)
0:(2,1)(2,1)(2,1)
#26
0:(1,2)
0:(1,2)
0:(1,2)(1,2)
0:(1,2)(1,2)
0:(2,1)(2,1)
0:(2,1)(2,1)(2,1)(2,1)
#27
0:(1,2)
0:(1,2)
0:(2,1)(2,1)
#28
0:(1,2)
0:(1,2)(1,2)
0:(2,1)
0:(2,1)(2,1)
#29
0:(1,2)
0:(2,1)
#30
0:(1,2)(1,2)
0:(1,2)(1,2)
0:(2,1)(2,1)
0:(2,1)(2,1)
#31
0:(1,2)(1,2)
0:(2,1)
0:(2,1)
#32
0:(1,2)(1,2)(1,2)(1,2)
0:(2,1)
0:(2,1)
0:(2,1)
0:(2,1)
#33
0:(1,2)(1,2)(1,2)(2,2)
0:(2,1)
0:(2,1)
0:(2,1)
0:(2,2)
#34
0:(1,2)(1,2)(2,2)
0:(2,1)
0:(2,1)
0:(2,2)
#35
0:(2,2)
0:(2,2)
#36
1:
#37
1:(1,1)
1:(1,1)
#38
2:
#39
0:(2,2)
0:(2,2)
0:(2,2)(2,2)
Программа poisk_predstav_ko_dlk находит минимального представителя компоненты ортогональности ДЛК для каждого ДЛК10 из входного файла. Но, в отличии от программы predstav_ko_dlk, представители распределяются по типам КО.
https://yadi.sk/d/mv_V9Bt2kLVMyQ
Типы 19,36,37,38 имеют петли. Вершинам с петлями соответствуют самоортогональные в обобщённом смысле ДЛК, то есть ДЛК ортогональные своему изоморфу.
#19 -> 4 компоненты, например, 3Xop8AQvSCFhM1mvBGvyi7rph:
1 3Xop8AQvSCFhM1mvBGvyi7rph[1]
2 YYzeuz7JrKbgmcBECUbj7G6Ey[2]
1: 2
2: 1,2
|0 1|
|1 1|
Петлю имеет только вершина степени 2, всего 4 самоортогональных ДЛК этого типа.
#36 -> 33158 компонент, например, 1AS28R5soJXTP7qQ8LjLeSjX6:
1 1AS28R5soJXTP7qQ8LjLeSjX6[1]
1: 1
|1|
Петлю имеет единственная вершина, всего 33158 самоортогональных ДЛК этого типа.
#37 -> 37 компонент, например, 2nceygR79Mnc7sdUzShDkxSUi:
1 2nceygR79Mnc7sdUzShDkxSUi[2]
2 2nceygR79Mnc7wME6ShzLjR4L[2]
1: 1,2
2: 1,2
|1 1|
|1 1|
Петлю имеют обе вершины, всего 74 самоортогональных ДЛК этого типа.
#38 -> 2 компоненты, например, 3Hkc4iof73tCrdW3XQGQvVksJ:
1 3Hkc4iof73tCrdW3XQGQvVksJ[2]
1: 1(2)
|2|
Единственная вершина имеет две петли, всего 2 самоортогональных ДЛК этого типа.
Итак, на момент создания списка 9880590 марьяжных ДЛК имелось 33238 самоортогональных ДЛК в обобщённом смысле. Ранее было найдено 30502 самоортогональных ДЛК в классическом смысле. Им соответствует 30467 компонент ортогональности. Из них:
— 3 типа 19;
— 30429 типа 36;
— 35 типа 37;
— 0 типа 38.
Очевидно, что для самоортогонального в классическом смысле ДЛК его КФ ортогональна собственному отражению либо относительно главной диагонали, либо побочной. Рассмотрим ДЛК YYzeuz7JrKbgmcBECUbj7G6Ey самоортогональный в обобщённом смысле, но не в классическом. Он имеет два соквадрата, один из них его изоморф:
0 4 6 8 1 7 5 9 3 2
9 1 0 4 8 3 7 2 5 6
4 7 2 5 0 6 1 8 9 3
1 8 9 3 5 4 0 6 2 7
5 6 3 9 4 1 2 0 7 8
8 2 7 0 3 5 9 4 6 1
2 5 1 7 9 8 6 3 4 0
3 0 4 2 6 9 8 7 1 5
7 9 5 6 2 0 3 1 8 4
6 3 8 1 7 2 4 5 0 9
получающийся из исходного ДЛК с помощью изоморфизма:
*T 0678541239 0678541239 0678541239
Теоретически, некоторые из 39 обобщённых типов компонент ортогональности могут представлять несколько различных типов. Например, обобщённый тип #12 представляет графы двух типов с каноническими матрицами смежности:
|0 0 0 0 0 1|
|0 0 0 0 0 1|
|0 0 0 0 1 1|
|0 0 0 0 1 1|
|0 0 1 1 0 0|
|1 1 1 1 0 0|
|0 0 0 0 0 1|
|0 0 0 0 1 0|
|0 0 0 1 0 1|
|0 0 1 0 0 1|
|0 1 0 0 0 1|
|1 0 1 1 1 0|
На практике, в каждом обобщённом типе реализован только один тип КО. Они имеют следующие канонические матрицы смежности:
|0 1|
|1 0|
#2
|0 0 0 0 0 0 0 0 1|
|0 0 0 0 0 0 0 0 1|
|0 0 0 0 0 0 0 0 1|
|0 0 0 0 0 0 0 0 1|
|0 0 0 0 0 0 0 0 1|
|0 0 0 0 0 0 0 0 1|
|0 0 0 0 0 0 0 0 1|
|0 0 0 0 0 0 0 0 1|
|1 1 1 1 1 1 1 1 0|
#3
|0 0 0 0 0 0 0 1|
|0 0 0 0 0 0 0 1|
|0 0 0 0 0 0 0 1|
|0 0 0 0 0 0 0 1|
|0 0 0 0 0 0 0 1|
|0 0 0 0 0 0 0 1|
|0 0 0 0 0 0 0 1|
|1 1 1 1 1 1 1 0|
#4
|0 0 0 0 0 0 0 0 0 0 0 1|
|0 0 0 0 0 0 0 0 0 0 0 1|
|0 0 0 0 0 0 0 0 0 0 0 1|
|0 0 0 0 0 0 0 0 0 0 0 1|
|0 0 0 0 0 0 0 0 0 0 0 1|
|0 0 0 0 0 0 0 0 0 0 0 1|
|0 0 0 0 0 0 0 0 0 0 1 1|
|0 0 0 0 0 0 0 0 0 0 1 1|
|0 0 0 0 0 0 0 0 0 0 1 1|
|0 0 0 0 0 0 0 0 0 0 1 1|
|0 0 0 0 0 0 1 1 1 1 0 0|
|1 1 1 1 1 1 1 1 1 1 0 0|
#5
|0 0 0 0 0 0 1|
|0 0 0 0 0 0 1|
|0 0 0 0 0 0 1|
|0 0 0 0 0 0 1|
|0 0 0 0 0 0 1|
|0 0 0 0 0 0 1|
|1 1 1 1 1 1 0|
#6
|0 0 0 0 0 1|
|0 0 0 0 0 1|
|0 0 0 0 0 1|
|0 0 0 0 0 1|
|0 0 0 0 0 1|
|1 1 1 1 1 0|
#7
|0 0 0 0 0 1|
|0 0 0 0 0 1|
|0 0 0 0 0 1|
|0 0 0 0 1 0|
|0 0 0 1 0 1|
|1 1 1 0 1 0|
#8
|0 0 0 0 1|
|0 0 0 0 1|
|0 0 0 0 1|
|0 0 0 0 1|
|1 1 1 1 0|
#9
|0 0 0 1|
|0 0 0 1|
|0 0 0 1|
|1 1 1 0|
#10
|0 0 1|
|0 0 1|
|1 1 0|
#11
|0 0 0 1|
|0 0 1 0|
|0 1 0 1|
|1 0 1 0|
#12
|0 0 0 0 0 1|
|0 0 0 0 0 1|
|0 0 0 0 1 1|
|0 0 0 0 1 1|
|0 0 1 1 0 0|
|1 1 1 1 0 0|
#13
|0 0 0 0 0 0 0 1|
|0 0 0 0 0 0 0 1|
|0 0 0 0 0 1 1 0|
|0 0 0 0 0 1 1 0|
|0 0 0 0 0 1 1 0|
|0 0 1 1 1 0 0 1|
|0 0 1 1 1 0 0 1|
|1 1 0 0 0 1 1 0|
#14
|0 0 0 1|
|0 0 0 1|
|0 0 0 2|
|1 1 1 0|
#15
|0 0 0 0 1|
|0 0 0 0 1|
|0 0 0 0 2|
|0 0 0 0 2|
|1 1 1 1 0|
#16
|0 0 0 0 1|
|0 0 0 1 1|
|0 0 0 1 1|
|0 1 1 0 0|
|1 1 1 0 0|
#17
|0 0 1 0 0|
|0 0 0 2 0|
|1 0 0 0 1|
|0 1 0 0 1|
|0 0 2 2 0|
#18
|0 0 1|
|0 0 2|
|1 1 0|
#19
|0 1|
|1 1|
#20
|0 0 1 1|
|0 0 1 1|
|1 1 0 0|
|1 1 0 0|
#21
|0 0 0 0 1 1|
|0 0 0 0 1 1|
|0 0 0 0 1 1|
|0 0 0 0 1 1|
|1 1 1 1 0 0|
|1 1 1 1 0 0|
#22
|0 0 0 1 1|
|0 0 0 1 1|
|0 0 0 1 1|
|1 1 1 0 0|
|1 1 1 0 0|
#23
|0 0 0 0 0 1|
|0 0 0 0 0 1|
|0 0 0 0 0 1|
|0 0 0 0 0 1|
|0 0 0 0 0 1|
|2 2 2 2 2 0|
#24
|0 0 0 0 1|
|0 0 0 0 1|
|0 0 0 0 1|
|0 0 0 0 1|
|2 2 2 2 0|
#25
|0 0 0 1|
|0 0 0 1|
|0 0 0 1|
|2 2 2 0|
#26
|0 0 0 0 0 1|
|0 0 0 0 0 1|
|0 0 0 0 1 1|
|0 0 0 0 1 1|
|0 0 2 2 0 0|
|2 2 2 2 0 0|
#27
|0 0 1|
|0 0 1|
|2 2 0|
#28
|0 0 0 1|
|0 0 2 0|
|0 1 0 1|
|2 0 2 0|
#29
|0 1|
|2 0|
#30
|0 0 1 1|
|0 0 1 1|
|2 2 0 0|
|2 2 0 0|
#31
|0 0 2|
|0 0 2|
|1 1 0|
#32
|0 0 0 0 2|
|0 0 0 0 2|
|0 0 0 0 2|
|0 0 0 0 2|
|1 1 1 1 0|
#33
|0 0 0 0 2|
|0 0 0 0 2|
|0 0 0 0 2|
|0 0 0 0 2|
|1 1 1 2 0|
#34
|0 0 0 2|
|0 0 0 2|
|0 0 0 2|
|1 1 2 0|
#35
|0 2|
|2 0|
#36
|1|
#37
|1 1|
|1 1|
#38
|2|
#39
|0 0 2|
|0 0 2|
|2 2 0|
Для наглядности можно нарисовать соответствующие схемы. При этом удобно:
1) петли считать неориентированными, то есть рисовать их без стрелок;
2) если две вершины соединены несколькими дугами, то каждую пару разнонаправленных дуг заменять одним ребром (линией без стрелок).
Компоненты ортогональности, в зависимости от обобщённого типа, имеют следующий состав ДЛК по степеням ортогональности:
#2 -> 8[1],1[8]
#3 -> 7[1],1[7]
#4 -> 6[1],4[2],1[4],1[10]
#5 -> 6[1],1[6]
#6 -> 5[1],1[5]
#7 -> 4[1],1[2],1[4]
#8 -> 4[1],1[4]
#9 -> 3[1],1[3]
#10 -> 2[1],1[2]
#11 -> 2[1],2[2]
#12 -> 2[1],3[2],1[4]
#13 -> 2[1],3[2],3[4]
#14 -> 2[1],1[2],1[3]
#15 -> 2[1],2[2],1[4]
#16 -> 1[1],3[2],1[3]
#17 -> 1[1],3[2],1[4]
#18 -> 1[1],2[2]
#19 -> 1[1],1[2]
#20 -> 4[2]
#21 -> 4[2],2[4]
#22 -> 3[2],2[3]
#23 -> 5[1],1[10]
#24 -> 4[1],1[8]
#25 -> 3[1],1[6]
#26 -> 2[1],2[2],1[4],1[8]
#27 -> 2[1],1[4]
#28 -> 1[1],2[2],1[4]
#29 -> 1[1],1[2]
#30 -> 2[2],2[4]
#31 -> 3[2]
#32 -> 4[2],1[4]
#33 -> 4[2],1[5]
#34 -> 3[2],1[4]
#35 -> 2[2]
#36 -> 1[1]
#37 -> 2[2]
#38 -> 1[2]
#39 -> 2[2],1[4]
Запись #4 -> 6[1],4[2],1[4],1[10], например, означает, что компонента ортогональности типа #4 имеет 6 единиц, 4 двойки, 1 четвёрку и 1 десятку.