Форум

Приветствую всех посетителей нашего сайта и форума. В виду форс-мажорных обстоятельста наш ресурс долгое время был недоступен. Данные "старого" сайта пока продолжают находиться вне нашего доступа и перспективы пока не ясны. Поэтому было принято решение воссоздать ресурс на новой платформе, перенеся, по возможности, большую часть инфомации. Пока ресурс находится в стадии наполнения, но общаться уже можно. Поэтому - регистрируйтесь и помогайте нам в наполнении сайта и форума новой, актуальной и полезной информацией.
Вы должны войти, чтобы создавать сообщения и темы.

Исследования свойств латинских квадратов

12

Без учёта "холостяков" программа LsEdit выдаёт примеры ДЛК для 36 схем ОДЛК. Канонические имена эти ДЛК вместе с соответствующими компонентами ортогональности приведены ниже в порядке перечисления схем ОДЛК в программе LsEdit (от None symmetric once до Stingray).

Спойлер
1) D3VGrtcRC7TVWobEZScerwzAB -> #1
2) aFmsrPJHKCnqKo4Z7Lvrbz6eK -> #36
3) FmT689WLk3CTvvY6pJB3gPnut -> #10
4) 3jWHkJAk25ybG1mvzGfDG2rG1 -> #29
5) 64iVV9NCnE6DsmJz7MsrgpqBf -> #11
6) Jggf6rLRdCw6i4uAp4saVkSmn -> #19
7) 1Hg9FXBiRB6n4quyCQDR3DXf1 -> #18
8) 3N2dJS6TjKmGiuHUs3Z7E3mxZ -> #38
9) G2fpBZWgMGvCK6LGFCF8S7fb5 -> #37
10) 3soRrGbsrD5HUifU85zN26oJP -> #31
11) 61yzSP1Hn3H1dyufxSeb3HqUU -> #20
12) RruqQiAiw3NkyHj2NNg82RYXk -> #9
13) Tc428wyf93y5gDUg766nJQiHV -> #8
14) 3jWKcedU6JqeMkLo6PNHgzMiE -> #27
15) 5tUqqVuGzBQ6AKRinDNpAi33J -> #6
16) A843rBb2hD4pJ5wV44oDTSAJ3 -> #5
17) 3tkr2aiuHE9is7BrD7EtCtPhC -> #25
18) AD5tvGqFTGRHPyLEsDvykeKdZ -> #3
19) 1h9VXz9ciDjtHW3Y1S2cXb8nS -> #2
20) 1Hg8z7c2n1NNonniqLpHKvHBA -> #24
21) H1ixpc8i97pghpiyWJAVGWpYw -> #23
22) UZ96gRAftFCFyCxVs5NBhGe8q -> #22
23) 3smTUk1nX1bCMNkWpMufgjcZ2 -> #30
24) 1kEzwCRL81YFg3ew7KnQJZCF9 -> #32
25) 2y8DEukBP1wCWpd97PVUNUquv -> #21
26) C8TGSGHfkGUP7CPDm5G5REQpp -> #33
27) C2ds6UbFCRd9Ljn54NGumRZUK -> #12
28) 3yzRVoaTbDdQNwoeXS2AivxzZ -> #28
29) 9xNXmH1Fs6V6gMPo64JkJTW76 -> #7
30) 326vS8mTDE7HSsy6987cin2Gr -> #13
31) 7dbjnoF1nCwuD9VkaGVLCzrPp -> #14
32) C2rKQUwX8Co4Tkx33L4Z98mDQ -> #17
33) H2nef6Sbj3fnkQYxp5zzW1Vrh -> #26
34) 1h9VXz9ciEGw1LSrZS2cWivFY -> #4
35) BtkjJxPg2ETb5LtfX5G1jfa6B -> #15
36) 8g2uBZp4JMBEVhK6bHHWquCuh -> #16

Отсутствуют схемы ОДЛК для КО #34, #35, #39 с представителями:

7U5Y1Xf7a6PwX2G6NGdQ6QwLM
1AFh9aUzTEbGKBM2e9XPedUaS
9s6RSEssP2EVc7dTUKbEVdBRZ

Первый распознаётся программой LsEdit как Rhombus-4(4 CFs), то есть этой схеме ОДЛК соответствуют как минимум две компоненты ортогональности — #30 и #34. С каноническими матрицами смежности:

|0 0 1 1|
|0 0 1 1|
|2 2 0 0|
|2 2 0 0|

|0 0 0 2|
|0 0 0 2|
|0 0 0 2|
|1 1 2 0|

Второй распознаётся как Loop-4(2 CFs), то есть и этой схеме ОДЛК соответствуют как минимум две компоненты ортогональности — #35 и #37. С каноническими матрицами смежности:

|0 2|
|2 0|

|1 1|
|1 1|

Третий можно было бы распознать как Rhombus-4(3 CFs), но такой схемы LsEdit не знает.

Итак, 39 компонент ортогональности получаются редукцией (возможно нулевой) 24 основных схем ОДЛК:

Спойлер
Once -> #1, #36
Line-3 -> #10, #29
Line-4 -> #11, #19
Line-5 -> #18
Loop-4 -> #20, #31, #35, #37, #38
Star-3 -> #9
Star-4 -> #8, #27
Star-5 -> #6
Star-6 -> #5, #25
Star-7 -> #3
Star-8 -> #2, #24
Star-10 -> #23
Rhombus-3 -> #22
Rhombus-4 -> #21, #30, #32, #34, #39
Rhombus-5 -> #33
Fish -> #12, #28
Cross -> #7
Flyer -> #13
Tree -> #14
Venus -> #17
Dedalus-8 -> #4
Dedalus-10 -> #26
Robot -> #15
Stingray -> #16

Array

Так как в статье "Список комбинаторных структур из ДЛК порядка 10 на множестве отношения ортогональности" нет схем ОДЛК соответствующих КО #34, #35 и #39, то нужны следующие три примечания.

1) Цикл-4(2 КФ) распадается на два подвида:
рис. 1, например, 2nceygR79Mnc7sdUzShDkxSUi
рис. 2, например, 1AFh9aUzTEbGKBM2e9XPedUaS

2) Ромб-4(4 КФ) распадается на два подвида:
рис. 3, например, 1En4LSm2aHq5inc9DQCni3r2E
рис. 4, например, 7U5Y1Xf7a6PwX2G6NGdQ6QwLM

3) Новый вид Ромб-4(3 КФ):
рис. 5, единственный пример — 9s6RSEssP2EVc7dTUKbEVdBRZ

Загруженные файлы:
  • Вам нужно войти, чтобы просматривать прикрепленные файлы..
Array

В качестве стандартного представителя симметрии (1,1,1)+ возьмём автоморфизм:

*T 0123456789 0123456789 0123456789

Тем самым задача перечисления ЛК10, обладающих симметрией (1,1,1)+, сводится к задаче перечисления ЛК10 симметричных относительно главной диагонали (обычно, именно такие ЛК и называются симметричными).

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

Поэтому все симметричные ЛК10 делятся на семь типов в зависимости от состава главной диагонали:
1) 10 одинаковых элементов;
2) 2,8;
3) 4,6;
4) 2,2,6;
5) 2,4,4;
6) 2,2,2,4;
7) 2,2,2,2,2.

Тип 1 содержит 396 существенно различных ЛК. Из них 98 имеют чистые симметрий, то есть они уже были проверены раньше при проверке соответствующих чистых симметрий. Оставшиеся 298 ЛК имеют группу автоморфизмов порядка два, с единственным нетривиальным автоморфизмом — транспонированием. Марьяжных ДЛК они не имеют.

Загруженные файлы:
  • Вам нужно войти, чтобы просматривать прикрепленные файлы..
Array

Тут меня попросили прокомментировать пост

https://boinc.progger.info/odlk/forum_thread.php?id=130&postid=4844

Сразу замечу, что утверждение:

Как я понимаю, это оценка количества вариантов заполнения 9 строк СН ДЛК.
Количество вариантов заполнения 10 строк по идее должно быть таким же, потому что при заполненных 9 строках квадрата вариант заполнения 10-й строки всего один.

неверно. В действительности, 9-строчных заполнений больше чем 10-строчных, так как не всякое 9-строчное заполнение может быть расширено до 10-строчного, но если такое расширение возможно, то, действительно, вариант расширения только один. Убедиться в этом можно "поигравшись" с программой counter_var_row, приведённой в третьем посте данной темы.

Следовательно, число СН ДЛК линейки 51 можно оценить числом 1,548e+18, а число нормализованных ДЛК линейки 51 — числом 1,189e+21. Число же КФ ДЛК линейки 51 можно оценить числом 7,74e+16.

Array

Выполним подобную оценку для всех 67 линеек ДЛК10 при размере выборки 10000. Результат под спойлером:
- первая колонка — номер линейки;
- вторая колонка — оценка числа СНДЛК;
- третья колонка — оценка числа нормализованных ДЛК;
- четвёртая колонка — оценка нижней границы числа главных классов ДЛК.

Спойлер
1 1.253E+018 4.009E+020 2.61E+016
2 1.511E+018 1.161E+022 7.556E+017
3 1.217E+018 1.169E+021 7.609E+016
4 2.568E+018 9.862E+021 6.421E+017
5 2.567E+018 9.857E+021 6.417E+017
6 2.428E+018 1.865E+021 1.214E+017
7 2.212E+018 8.493E+021 5.529E+017
8 2.384E+018 9.156E+021 5.961E+017
9 2.217E+018 1.703E+022 1.108E+018
10 1.917E+018 7.36E+021 4.792E+017
11 2.548E+018 9.783E+021 6.369E+017
12 2.538E+018 9.746E+021 6.345E+017
13 2.505E+018 9.617E+021 6.261E+017
14 2.289E+018 1.758E+022 1.144E+018
15 1.251E+018 4.002E+020 2.605E+016
16 1.506E+018 1.157E+022 7.532E+017
17 2.499E+018 1.919E+022 1.25E+018
18 2.668E+018 1.024E+022 6.67E+017
19 1.294E+018 9.938E+021 6.47E+017
20 1.475E+018 1.133E+022 7.374E+017
21 2.404E+018 1.846E+022 1.202E+018
22 2.163E+018 8.305E+021 5.407E+017
23 2.205E+018 1.693E+022 1.102E+018
24 2.31E+018 1.774E+022 1.155E+018
25 2.368E+018 9.095E+021 5.921E+017
26 2.476E+018 1.901E+022 1.238E+018
27 2.675E+018 1.027E+022 6.688E+017
28 2.426E+018 1.863E+022 1.213E+018
29 2.473E+018 1.899E+022 1.236E+018
30 2.426E+018 1.863E+022 1.213E+018
31 2.494E+018 1.916E+022 1.247E+018
32 2.406E+018 9.238E+021 6.014E+017
33 2.406E+018 9.237E+021 6.014E+017
34 2.325E+018 8.926E+021 5.811E+017
35 2.346E+018 9.009E+021 5.865E+017
36 2.894E+018 9.262E+020 6.03E+016
37 2.841E+018 2.727E+021 1.775E+017
38 1.203E+018 3.851E+020 2.507E+016
39 1.416E+018 1.088E+022 7.082E+017
40 2.506E+018 9.621E+021 6.264E+017
41 2.555E+018 1.962E+022 1.277E+018
42 2.561E+018 9.836E+021 6.404E+017
43 3.066E+018 2.355E+022 1.533E+018
44 3.025E+018 2.323E+022 1.512E+018
45 3.103E+018 2.383E+022 1.552E+018
46 3.059E+018 2.349E+022 1.53E+018
47 2.645E+018 2.032E+022 1.323E+018
48 1.981E+018 1.522E+022 9.907E+017
49 1.533E+018 5.885E+021 3.832E+017
50 2.569E+018 3.946E+021 2.569E+017
51 1.511E+018 1.161E+021 7.557E+016
52 2.245E+018 8.619E+021 5.611E+017
53 1.332E+018 5.114E+021 3.329E+017
54 2.34E+018 1.797E+022 1.17E+018
55 2.278E+018 1.75E+022 1.139E+018
56 1.744E+018 1.34E+022 8.721E+017
57 1.531E+018 2.352E+022 1.531E+018
58 2.25E+018 3.456E+022 2.25E+018
59 2.41E+018 3.701E+022 2.41E+018
60 2.433E+018 3.737E+022 2.433E+018
61 2.082E+018 3.197E+022 2.082E+018
62 2.429E+018 3.73E+022 2.429E+018
63 2.392E+018 3.674E+022 2.392E+018
64 2.454E+018 1.885E+022 1.227E+018
65 2.498E+018 3.838E+022 2.498E+018
66 1.548E+018 2.377E+022 1.548E+018
67 2.43E+018 1.866E+022 1.215E+018
--------------------------------------------------
Всего: 1.496E+020 9.932E+023 6.466E+019

Так как почти все ДЛК имеют тривиальную группу автоморфизмов, то число главных классов ДЛК весьма близко к оценке нижней границе. Например, для порядка 9 имеется 5056994653507584 нормализованных ДЛК, поэтому нижняя граница числа главных классов ДЛК9 равна 3292314227544, что составляет 99,9996% от точного их числа (3292326155394).

Следовательно, число главных классов ДЛК10 (число КФ) можно оценить числом 6,47e+19.

Array

Кто бы еще оценил, сколько будет считать проект ODLK1? Точность ответа не важна - возраст земли меньше.

Про TBEG вообще мрак. Взята одна линейка (51), а на выходе все, причем в каждой линейке получается больше, чем в исходной.

Array

TBEG — это что?

Array

T.Brada Experimental Grid

https://boinc.tbrada.eu

 

Array
12