Database CF ODLS of order n

Message boards : Science : Database CF ODLS of order n
Message board moderation

To post messages, you must log in.

1 · 2 · 3 · Next

AuthorMessage
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 12852
Credit: 0
RAC: 0
Message 6711 - Posted: 1 Nov 2020, 16:02:04 UTC
Last modified: 1 Nov 2020, 16:13:29 UTC

Количество КФ ДЛК порядка n определяется количеством главных классов.
Смотрите последовательность OEIS https://oeis.org/A287764.

Не все КФ ДЛК для данного порядка имеют ОДЛК.
Так например, для ДЛК порядка n=8 существует 4873096 КФ ДЛК (по кличеству главных классов).
По результатам, приведённым Белышевым, имеется только 1105 КФ ОДЛК порядка 8.
Результаты были выложены Белышевым на форуме boinc.ru.
К сожалению, на этом форуме данных результатов сейчас нет, они пропали вместе с предыдущей версией форума.
Результаты были сохранены мной.
Цитата
Выполнил проверку. Результат следующий:

mate[1] = 786
mate[2] = 94
mate[3] = 24
mate[4] = 111
mate[5] = 6
mate[6] = 5
mate[7] = 11
mate[8] = 2
mate[9] = 2
mate[10] = 2
mate[11] = 2
mate[12] = 4
mate[13] = 1
mate[14] = 5
mate[16] = 9
mate[18] = 3
mate[19] = 3
mate[20] = 5
mate[22] = 3
mate[24] = 2
mate[28] = 10
mate[40] = 1
mate[45] = 3
mate[48] = 1
mate[50] = 2
mate[108] = 3
mate[116] = 2
mate[128] = 1
mate[131] = 1
mate[824] = 1
Всего КФ ОДЛК: 1105
Время работы: 702.422 сек

Я нашла программой 972 КФ ДЛК 7-го порядка и пропустила их через программу Белышева ortogon_u.
Смотрите сообщение
https://boinc.progger.info/odlk/forum_thread.php?id=162&postid=6191
Таким образом, БД КФ ОДЛК 7-го порядка состоит из 5 КФ ОДЛК

0 2 3 6 5 4 1
3 1 0 5 6 2 4
1 3 2 4 0 6 5
4 6 5 3 2 1 0
2 5 6 1 4 0 3
6 4 1 0 3 5 2
5 0 4 2 1 3 6

0 2 4 5 3 6 1
3 1 5 4 6 2 0
4 3 2 6 0 1 5
2 6 1 3 5 0 4
1 5 6 0 4 3 2
6 4 0 2 1 5 3
5 0 3 1 2 4 6

0 2 4 5 3 6 1
6 1 0 4 5 2 3
1 5 2 6 0 3 4
4 6 5 3 1 0 2
2 3 6 0 4 1 5
3 4 1 2 6 5 0
5 0 3 1 2 4 6

0 2 4 6 5 3 1
6 1 0 5 3 2 4
1 5 2 4 0 6 3
4 6 5 3 1 0 2
3 0 6 2 4 1 5
2 4 3 1 6 5 0
5 3 1 0 2 4 6

0 2 5 4 3 6 1
4 1 0 6 5 2 3
1 6 2 5 0 3 4
6 5 4 3 2 1 0
2 3 6 1 4 0 5
3 4 1 0 6 5 2
5 0 3 2 1 4 6

БД КФ ОДЛК 4-го порядка состоит из одной КФ ОДЛК

[DLK(1):1]
0 2 3 1
3 1 0 2
1 3 2 0
2 0 1 3

Этот ДЛК является SODLS.

КФ ДЛК 5-го порядка существует две

0 2 3 4 1
2 1 4 0 3
4 3 2 1 0
1 4 0 3 2
3 0 1 2 4

0 3 4 2 1
2 1 3 4 0
1 4 2 0 3
4 0 1 3 2
3 2 0 1 4

Но ортогональный соквадрат имеет только одна КФ ДЛК

[DLK(1):1]
0 3 4 2 1
2 1 3 4 0
1 4 2 0 3
4 0 1 3 2
3 2 0 1 4

Этот ДЛК является SODLS.
Поэтому БД КФ ОДЛК 5-го порядка состоит из одной КФ ОДЛК.

PS. Как известно, ДЛК 6-го порядка не имеют ортогональных соквадратов.
My new article "SOLS and SODLS"
in Russian
https://yadi.sk/d/nvdI6TgBrKv72A
in English https://yadi.sk/d/VeY9bx6_q6CcZg
ID: 6711 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 12852
Credit: 0
RAC: 0
Message 6712 - Posted: 1 Nov 2020, 16:27:13 UTC
Last modified: 1 Nov 2020, 16:48:42 UTC

Составлению БД КФ ОДЛК 9-го порядка посвящён мой ручной проект
https://boinc.progger.info/odlk/forum_thread.php?id=44

Смотрите также
https://boinc.progger.info/odlk/forum_thread.php?id=165

На данный момент найдено 53844 КФ ОДЛК.
My new article "SOLS and SODLS"
in Russian
https://yadi.sk/d/nvdI6TgBrKv72A
in English https://yadi.sk/d/VeY9bx6_q6CcZg
ID: 6712 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 12852
Credit: 0
RAC: 0
Message 6713 - Posted: 1 Nov 2020, 16:30:26 UTC
Last modified: 1 Nov 2020, 17:02:27 UTC

В OEIS есть последовательность
https://oeis.org/A330391
Цитирую
Number of main classes of diagonal Latin squares of order n with at least one orthogonal diagonal mate.
1, 0, 0, 1, 1, 0, 5, 1105

Можно пока сказать, что a(9)>53844.

PS. Уже найдено ещё несколько КФ ОДЛК, поэтому неравенство строгое.
My new article "SOLS and SODLS"
in Russian
https://yadi.sk/d/nvdI6TgBrKv72A
in English https://yadi.sk/d/VeY9bx6_q6CcZg
ID: 6713 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 12852
Credit: 0
RAC: 0
Message 6714 - Posted: 1 Nov 2020, 17:19:59 UTC
Last modified: 1 Nov 2020, 18:51:03 UTC

БД КФ ОДЛК порядка 8 (в первом формате) выложена автором последовательности https://oeis.org/A330391
E. I. Vatutin, List of all main classes of orthogonal diagonal Latin squares of orders 1-8.

Скачала и пропустила через программу Белышева ortogon_u.
Показываю несколько первых и последних КФ ОДЛК

[DLK(1):1]
0 1 2 3 4 5 6 7
1 2 0 5 7 6 3 4
7 6 3 4 1 2 0 5
4 5 6 7 0 1 2 3
5 3 7 1 6 0 4 2
3 7 5 6 2 4 1 0
2 4 1 0 3 7 5 6
6 0 4 2 5 3 7 1

[DLK(4):2]
0 1 2 3 4 5 6 7
1 2 3 0 7 4 5 6
3 5 4 7 0 6 1 2
6 7 5 1 3 2 4 0
5 3 0 4 6 7 2 1
7 6 1 2 5 3 0 4
4 0 6 5 2 1 7 3
2 4 7 6 1 0 3 5

[DLK(1):6]
0 1 2 3 4 5 6 7
1 2 0 4 7 6 3 5
5 3 7 1 6 0 4 2
7 6 3 5 1 2 0 4
6 4 5 2 3 1 7 0
3 0 6 7 5 4 2 1
2 5 4 6 0 7 1 3
4 7 1 0 2 3 5 6

[DLK(1):7]
0 1 2 3 4 5 6 7
1 2 3 0 7 4 5 6
3 7 4 2 5 6 1 0
6 5 0 1 3 7 4 2
7 3 5 4 6 2 0 1
5 6 1 7 0 3 2 4
4 0 6 5 2 1 7 3
2 4 7 6 1 0 3 5

[DLK(1):8]
0 1 2 3 4 5 6 7
1 2 0 5 7 6 3 4
7 6 3 4 1 2 0 5
4 5 6 7 0 1 2 3
5 3 7 1 6 0 4 2
2 7 5 6 3 4 1 0
3 4 1 0 2 7 5 6
6 0 4 2 5 3 7 1

[DLK(4):9]
0 1 2 3 4 5 6 7
1 2 3 0 6 7 4 5
4 0 6 2 7 3 5 1
3 5 1 7 0 4 2 6
6 3 4 1 5 2 7 0
7 4 5 6 2 1 0 3
5 6 7 4 1 0 3 2
2 7 0 5 3 6 1 4

[DLK(1):13]
0 1 2 3 4 5 6 7
2 3 0 1 7 6 5 4
5 6 1 7 3 4 0 2
6 5 3 4 1 7 2 0
7 4 5 2 6 0 3 1
4 7 6 0 5 2 1 3
1 0 4 5 2 3 7 6
3 2 7 6 0 1 4 5

[DLK(19):14]
0 1 2 3 4 5 6 7
1 2 3 0 7 4 5 6
6 0 4 2 5 3 7 1
3 5 1 7 0 6 2 4
7 3 5 1 6 2 4 0
4 7 6 5 2 1 0 3
5 4 7 6 1 0 3 2
2 6 0 4 3 7 1 5

[DLK(1):33]
0 1 2 3 4 5 6 7
1 2 5 0 3 7 4 6
3 7 4 6 1 2 5 0
4 5 6 7 0 1 2 3
2 4 3 5 6 0 7 1
5 6 1 4 7 3 0 2
7 3 0 2 5 6 1 4
6 0 7 1 2 4 3 5

[DLK(45):34]
0 1 2 3 4 5 6 7
2 3 0 1 6 7 4 5
4 2 6 0 7 1 5 3
1 5 3 7 0 4 2 6
6 0 4 2 5 3 7 1
7 4 5 6 1 2 3 0
5 6 7 4 3 0 1 2
3 7 1 5 2 6 0 4
. . . . . . 

[DLK(4):4521]
0 1 2 3 4 5 6 7
1 2 3 0 7 6 5 4
5 6 4 7 2 0 3 1
6 4 7 5 1 3 0 2
3 0 1 2 6 7 4 5
7 5 6 4 3 1 2 0
2 3 0 1 5 4 7 6
4 7 5 6 0 2 1 3

[DLK(4):4525]
0 1 2 3 4 5 6 7
2 3 0 1 6 7 4 5
4 5 7 6 3 2 0 1
6 7 5 4 1 0 2 3
3 2 1 0 5 4 7 6
1 0 3 2 7 6 5 4
7 6 4 5 2 3 1 0
5 4 6 7 0 1 3 2

[DLK(4):4529]
0 1 2 3 4 5 6 7
2 3 0 1 6 7 4 5
4 7 6 5 0 3 2 1
6 5 4 7 2 1 0 3
3 2 1 0 5 4 7 6
7 4 5 6 1 2 3 0
5 6 7 4 3 0 1 2
1 0 3 2 7 6 5 4

[DLK(1):4533]
0 1 2 3 4 5 6 7
1 2 3 0 5 7 4 6
6 3 5 1 7 0 2 4
2 4 0 7 3 6 5 1
4 0 7 2 6 1 3 5
3 5 1 6 0 4 7 2
7 6 4 5 2 3 1 0
5 7 6 4 1 2 0 3

[DLK(2):4534]
0 1 2 3 4 5 6 7
2 3 0 1 6 7 4 5
4 5 7 6 0 1 3 2
6 7 5 4 2 3 1 0
3 2 1 0 5 4 7 6
1 0 3 2 7 6 5 4
7 6 4 5 1 0 2 3
5 4 6 7 3 2 0 1

[DLK(2):4536]
0 1 2 3 4 5 6 7
2 3 0 1 6 7 4 5
4 7 6 5 0 3 2 1
6 5 4 7 2 1 0 3
3 4 1 0 5 6 7 2
7 0 5 4 1 2 3 6
5 6 7 2 3 4 1 0
1 2 3 6 7 0 5 4

[DLK(1):4538]
0 1 2 3 4 5 6 7
1 2 3 0 7 6 5 4
5 7 4 6 2 0 1 3
7 4 6 5 3 1 0 2
6 5 7 4 1 3 2 0
3 0 1 2 6 7 4 5
4 6 5 7 0 2 3 1
2 3 0 1 5 4 7 6

[DLK(2):4539]
0 1 2 3 4 5 6 7
1 2 6 5 7 3 0 4
3 7 4 2 0 1 5 6
6 0 1 7 5 4 2 3
7 3 5 6 1 2 4 0
4 5 3 0 2 6 7 1
5 4 7 1 6 0 3 2
2 6 0 4 3 7 1 5

[DLK(1):4541]
0 1 2 3 4 5 6 7
1 2 3 0 6 7 4 5
5 4 7 6 0 1 2 3
7 6 5 4 3 0 1 2
3 0 1 2 5 4 7 6
2 3 0 1 7 6 5 4
4 5 6 7 1 2 3 0
6 7 4 5 2 3 0 1

[DLK(1):4542]
0 1 2 3 4 5 6 7
1 2 3 0 6 7 4 5
5 4 7 6 0 3 2 1
7 6 5 4 1 0 3 2
3 0 1 2 5 4 7 6
2 3 0 1 7 6 5 4
4 5 6 7 3 2 1 0
6 7 4 5 2 1 0 3

[DLK(2):4543]
0 1 2 3 4 5 6 7
1 2 6 5 7 4 0 3
4 7 3 0 2 1 5 6
7 6 5 4 3 2 1 0
5 4 7 6 1 0 3 2
3 0 4 7 5 6 2 1
6 5 1 2 0 3 7 4
2 3 0 1 6 7 4 5

[DLK(1):4545]
0 1 2 3 4 5 6 7
1 2 3 5 7 6 0 4
3 7 1 0 2 4 5 6
7 6 5 4 3 2 1 0
5 3 7 1 6 0 4 2
4 0 6 7 5 3 2 1
6 5 4 2 0 1 7 3
2 4 0 6 1 7 3 5

45-ка тут есть.
А это рекордная КФ ОДЛК, имеет 824 ортогональных диагональных соквадрата

[DLK(824):236]
0 1 2 3 4 5 6 7
2 3 0 1 6 7 4 5
4 5 6 7 0 1 2 3
6 7 4 5 2 3 0 1
3 2 1 0 7 6 5 4
1 0 3 2 5 4 7 6
7 6 5 4 3 2 1 0
5 4 7 6 1 0 3 2

О рекордных КФ ОДЛК разных порядков смотрите последовательность https://oeis.org/A287695
My new article "SOLS and SODLS"
in Russian
https://yadi.sk/d/nvdI6TgBrKv72A
in English https://yadi.sk/d/VeY9bx6_q6CcZg
ID: 6714 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 12852
Credit: 0
RAC: 0
Message 6715 - Posted: 1 Nov 2020, 17:25:31 UTC
Last modified: 1 Nov 2020, 17:31:56 UTC

Всего одна 128-ка

[DLK(128):1470]
0 1 2 3 4 5 6 7
2 3 0 1 6 7 4 5
1 5 4 0 7 3 2 6
5 4 7 6 1 0 3 2
3 7 6 2 5 1 0 4
7 6 5 4 3 2 1 0
4 0 1 5 2 6 7 3
6 2 3 7 0 4 5 1

и всего одна 131-ка
[DLK(131):1127]
0 1 2 3 4 5 6 7
2 3 0 1 6 7 4 5
1 6 5 4 7 2 3 0
7 4 3 6 1 0 5 2
6 7 4 5 2 3 0 1
4 5 6 7 0 1 2 3
5 0 1 2 3 4 7 6
3 2 7 0 5 6 1 4

Ну, остальные группы ОДЛК смотрите в таблице Белышева, приведённой выше.
Правда, там нет живых квадратов, а только количества.
My new article "SOLS and SODLS"
in Russian
https://yadi.sk/d/nvdI6TgBrKv72A
in English https://yadi.sk/d/VeY9bx6_q6CcZg
ID: 6715 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 12852
Credit: 0
RAC: 0
Message 6716 - Posted: 1 Nov 2020, 17:38:54 UTC
Last modified: 1 Nov 2020, 18:01:57 UTC

Несколько живых КФ ОДЛК 8-го порядка (дающих крупные группы ОДЛК) показано здесь
https://boinc.progger.info/odlk/forum_thread.php?id=162&postid=6190
https://boinc.progger.info/odlk/forum_thread.php?id=162&postid=6200
https://boinc.progger.info/odlk/forum_thread.php?id=162&postid=6211
My new article "SOLS and SODLS"
in Russian
https://yadi.sk/d/nvdI6TgBrKv72A
in English https://yadi.sk/d/VeY9bx6_q6CcZg
ID: 6716 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 12852
Credit: 0
RAC: 0
Message 6717 - Posted: 1 Nov 2020, 17:59:28 UTC

Как известно, над составлением БД КФ ОДЛК 10-го порядка работают два BOINC-проекта.

Проект ОДЛК
https://boinc.progger.info/odlk/

Проект ODLK1
https://boinc.multi-pool.info/latinsquares/

Результатов получено много (более 10 миллионов КФ ОДЛК).
К сожалению, они пока не все собраны в единую БД.

Вот здесь
https://boinc.multi-pool.info/latinsquares/forum_thread.php?id=54&postid=920
вы можете посмотреть "Result of BOINC project ODLK1 from 2017-11 to 2020-02"

Результаты проекта ОДЛК публикуются здесь
https://boinc.progger.info/odlk_results/odlk3/
https://boinc.progger.info/odlk_results/odlkmax/
https://boinc.progger.info/odlk_results/odlkmin/
My new article "SOLS and SODLS"
in Russian
https://yadi.sk/d/nvdI6TgBrKv72A
in English https://yadi.sk/d/VeY9bx6_q6CcZg
ID: 6717 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 12852
Credit: 0
RAC: 0
Message 6721 - Posted: 2 Nov 2020, 2:17:59 UTC

Читайте моё исследование о MODLS порядка 9
https://boinc.progger.info/odlk/forum_thread.php?id=171

Интересно выполнить такое исследование о MODLS порядков 7 и 8.
My new article "SOLS and SODLS"
in Russian
https://yadi.sk/d/nvdI6TgBrKv72A
in English https://yadi.sk/d/VeY9bx6_q6CcZg
ID: 6721 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 12852
Credit: 0
RAC: 0
Message 6723 - Posted: 2 Nov 2020, 8:33:05 UTC
Last modified: 2 Nov 2020, 8:38:57 UTC

Вопрос о MODLS - интересный вопрос.
Для порядка 7 можно увидеть MODLS, состоящую из 4 взаимно ортогональных ДЛК, в полной системе MOLS



Иллюстрация из моей статьи
http://www.natalimak1.narod.ru/grolk.htm

Есть ли другая (не изоморфная) группа MODLS 7-го порядка из 4-х взаимно ортогональных ДЛК?
Я думаю, что нет.

Выполнила маленький эксперимент.
Взяла полную БД КФ ОДЛК 7-го порядка, состоящую из 5 ОДЛК (отсюда), нашла к этим ОДЛК все ортогональные ДЛК; в полученной группе ОДЛК образовала все ортогональные пары.
Таблица ортогональных пар, выданная утилитой Harry White

6:  1
7:  2
8:  3
9:  3 8
10:  3 8 9
11:  4
12:  5

Здесь есть группа MODLS из 4-х взаимно ортогональных ДЛК, она единственная; это ДЛК 3, 8, 9, 10.
Думаю, что эта группа MODLS изоморфна той, что мы видим в полной системе MOLS.
My new article "SOLS and SODLS"
in Russian
https://yadi.sk/d/nvdI6TgBrKv72A
in English https://yadi.sk/d/VeY9bx6_q6CcZg
ID: 6723 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 12852
Credit: 0
RAC: 0
Message 6724 - Posted: 2 Nov 2020, 9:06:41 UTC
Last modified: 2 Nov 2020, 9:37:02 UTC

Нарисовала группу ОДЛК 7-го порядка из предыдущего поста в Gephi



Понятно, что группа MODLS, состоящая из 4-х взаимно ортогональных ДЛК, это четырёхугольник на иллюстрации.

Сейчас я канонизирую обе группы MODLS (из полной системы MOLS и рассмотренную мной) и сравню их.

Канонизировала и сравнила:
4 ДЛК первой группы MODLS и 4 ДЛК второй группы MODLS имеют одну и ту же КФ

0 2 4 5 3 6 1
6 1 0 4 5 2 3
1 5 2 6 0 3 4
4 6 5 3 1 0 2
2 3 6 0 4 1 5
3 4 1 2 6 5 0
5 0 3 1 2 4 6

My new article "SOLS and SODLS"
in Russian
https://yadi.sk/d/nvdI6TgBrKv72A
in English https://yadi.sk/d/VeY9bx6_q6CcZg
ID: 6724 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 12852
Credit: 0
RAC: 0
Message 6729 - Posted: 2 Nov 2020, 15:20:42 UTC
Last modified: 2 Nov 2020, 15:52:05 UTC

Кстати, о группах MODLS смотрите последовательность в OEIS
https://oeis.org/A328873

Для порядка 8 существует группа MODLS, состоящая из 6 взаимно ортогональных ДЛК; эти ДЛК входят в полную систему MOLS данного порядка.
Вы можете посмотреть полную систему MOLS 8-го порядка в моей статье
http://www.natalimak1.narod.ru/grolk.htm

Я нарисовала группу MODLS из 6 взаимно ортогональных ДЛК в Gephi (только для порядка 9 рисовала, но для порядка 8 будет точно так же)



Однако интересный вопрос: единственная ли (не изоморфная) группа MODLS 8-го порядка, состоящая из 6 взаимно ортогональных ДЛК?
Тут так просто не получится исследовать, как для порядка 7 выше исследовано.

PS. Для порядка 9 в указанной последовательности член не указан, а указана только оценка a(9)>=6.
Эта оценка предполагает, что может существовать группа MODLS 9-го порядка, состоящая более чем из 6 взаимно ортогональных ДЛК.
Я такую группу не знаю.
Кто знает, покажите, пожалуйста, или дайте ссылку на публикацию.
My new article "SOLS and SODLS"
in Russian
https://yadi.sk/d/nvdI6TgBrKv72A
in English https://yadi.sk/d/VeY9bx6_q6CcZg
ID: 6729 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 12852
Credit: 0
RAC: 0
Message 6730 - Posted: 2 Nov 2020, 16:35:11 UTC
Last modified: 2 Nov 2020, 16:35:56 UTC

Первый маленький эксперимент.
Беру самую большую группу ОДЛК 8-го порядка

[DLK(824)]
0 2 5 7 6 4 3 1
3 1 6 4 5 7 0 2
7 5 2 0 1 3 4 6
4 6 1 3 2 0 7 5
2 0 7 5 4 6 1 3
1 3 4 6 7 5 2 0
5 7 0 2 3 1 6 4
6 4 3 1 0 2 5 7

Образую группу: основной ДЛК + 824 ОДЛК, нахожу в этой группе все ортогональные пары.
С помощью утилиты Harry White легко увидеть в этой группе MODLS, состоящую из 6 взаимно ортогональных ДЛК; она единственная в данной группе ОДЛК.
Это квадраты: 1, 85, 95, 261, 417, 822.
Сейчас я их покажу.
Ну, квадрат 1 уже показан, это основной ДЛК, порождающий группу.
My new article "SOLS and SODLS"
in Russian
https://yadi.sk/d/nvdI6TgBrKv72A
in English https://yadi.sk/d/VeY9bx6_q6CcZg
ID: 6730 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 12852
Credit: 0
RAC: 0
Message 6731 - Posted: 2 Nov 2020, 16:46:23 UTC
Last modified: 2 Nov 2020, 16:52:08 UTC

Итак, встречайте: группа MODLS 8-го порядка, состоящая из 6 взаимно ортогональных ДЛК

0 2 5 7 6 4 3 1
3 1 6 4 5 7 0 2
7 5 2 0 1 3 4 6
4 6 1 3 2 0 7 5
2 0 7 5 4 6 1 3
1 3 4 6 7 5 2 0
5 7 0 2 3 1 6 4
6 4 3 1 0 2 5 7

0 1 2 3 4 5 6 7
2 3 0 1 6 7 4 5
5 4 7 6 1 0 3 2
7 6 5 4 3 2 1 0
6 7 4 5 2 3 0 1
4 5 6 7 0 1 2 3
3 2 1 0 7 6 5 4
1 0 3 2 5 4 7 6

0 1 2 3 4 5 6 7
3 2 1 0 7 6 5 4
7 6 5 4 3 2 1 0
4 5 6 7 0 1 2 3
2 3 0 1 6 7 4 5
1 0 3 2 5 4 7 6
5 4 7 6 1 0 3 2
6 7 4 5 2 3 0 1

0 1 2 3 4 5 6 7
4 5 6 7 0 1 2 3
6 7 4 5 2 3 0 1
2 3 0 1 6 7 4 5
7 6 5 4 3 2 1 0
3 2 1 0 7 6 5 4
1 0 3 2 5 4 7 6
5 4 7 6 1 0 3 2

0 1 2 3 4 5 6 7
5 4 7 6 1 0 3 2
4 5 6 7 0 1 2 3
1 0 3 2 5 4 7 6
3 2 1 0 7 6 5 4
6 7 4 5 2 3 0 1
7 6 5 4 3 2 1 0
2 3 0 1 6 7 4 5

0 1 2 3 4 5 6 7
7 6 5 4 3 2 1 0
1 0 3 2 5 4 7 6
6 7 4 5 2 3 0 1
5 4 7 6 1 0 3 2
2 3 0 1 6 7 4 5
4 5 6 7 0 1 2 3
3 2 1 0 7 6 5 4

Осталось канонизировать и сравнить с классической группой MODLS из полной системы MOLS.

Для показанной группы канонизировала ДЛК.
Все они изоморфные; основной ДЛК является КФ.
Позже канонизирую ДЛК классической группы MODLS.
My new article "SOLS and SODLS"
in Russian
https://yadi.sk/d/nvdI6TgBrKv72A
in English https://yadi.sk/d/VeY9bx6_q6CcZg
ID: 6731 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 12852
Credit: 0
RAC: 0
Message 6732 - Posted: 2 Nov 2020, 17:18:53 UTC

Покажу классическую группу MODLS 8-го порядка из полной системы MOLS

0 1 2 3 4 5 6 7
2 3 0 1 6 7 4 5
4 5 6 7 0 1 2 3
6 7 4 5 2 3 0 1
5 4 7 6 1 0 3 2
7 6 5 4 3 2 1 0
1 0 3 2 5 4 7 6
3 2 1 0 7 6 5 4

0 1 2 3 4 5 6 7
3 2 1 0 7 6 5 4
6 7 4 5 2 3 0 1
5 4 7 6 1 0 3 2
1 0 3 2 5 4 7 6
2 3 0 1 6 7 4 5
7 6 5 4 3 2 1 0
4 5 6 7 0 1 2 3

0 1 2 3 4 5 6 7
4 5 6 7 0 1 2 3
5 4 7 6 1 0 3 2
1 0 3 2 5 4 7 6
7 6 5 4 3 2 1 0
3 2 1 0 7 6 5 4
2 3 0 1 6 7 4 5
6 7 4 5 2 3 0 1

0 1 2 3 4 5 6 7
5 4 7 6 1 0 3 2
7 6 5 4 3 2 1 0
2 3 0 1 6 7 4 5
3 2 1 0 7 6 5 4
6 7 4 5 2 3 0 1
4 5 6 7 0 1 2 3
1 0 3 2 5 4 7 6

0 1 2 3 4 5 6 7
6 7 4 5 2 3 0 1
1 0 3 2 5 4 7 6
7 6 5 4 3 2 1 0
2 3 0 1 6 7 4 5
4 5 6 7 0 1 2 3
3 2 1 0 7 6 5 4
5 4 7 6 1 0 3 2

0 1 2 3 4 5 6 7
7 6 5 4 3 2 1 0
3 2 1 0 7 6 5 4
4 5 6 7 0 1 2 3
6 7 4 5 2 3 0 1
1 0 3 2 5 4 7 6
5 4 7 6 1 0 3 2
2 3 0 1 6 7 4 5

Все эти ДЛК изоморфны друг другу, все получаются друг из друга перестановкой строк.
И КФ этих ДЛК та же самая, что и у рассмотренной выше группы MODLS.
Следовательно, эти две группы MODLS изоморфные.

Есть ли ещё группы MODLS 8-го порядка, состоящие из 6 взаимно ортогональных ДЛК, но существенно другие (не изоморфные классической группе)?
My new article "SOLS and SODLS"
in Russian
https://yadi.sk/d/nvdI6TgBrKv72A
in English https://yadi.sk/d/VeY9bx6_q6CcZg
ID: 6732 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 12852
Credit: 0
RAC: 0
Message 6734 - Posted: 3 Nov 2020, 8:29:23 UTC
Last modified: 3 Nov 2020, 9:26:46 UTC

Эксперимент посложнее

Беру БД КФ ОДЛК 8-го порядка, 1105 КФ ОДЛК.
Нахожу программой Белышева ortogon_u все ОДЛК к ним, получаю 4545 ОДЛК.
Объединяю эти два множества ОДЛК, получаю 5650 ОДЛК.
Нахожу в этой группе ОДЛК все ортогональные пары с помощью утилиты Harry White
Order? 8

Enter the name of the squares file: inp
..output file inpPairs_6.txt
..output file inpPairNos_6.txt
squares 5650 orthogonal pairs 16675

Найдено 16675 ортогональных пар! Круто!
Вот тут, наверное, есть все группы MODLS, состоящие из 6 взаимно ортогональных ДЛК.
Как вы думаете, господа?

Однако... визуально найти их в этой таблице ортогональных пар нереально.
А как можно найти по-другому?
Ваши идеи?

Таблицу ортогональных пар сейчас выложу на Яндекс.Диск.
Здесь
https://yadi.sk/d/44yMmWPLZ8et0g
My new article "SOLS and SODLS"
in Russian
https://yadi.sk/d/nvdI6TgBrKv72A
in English https://yadi.sk/d/VeY9bx6_q6CcZg
ID: 6734 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 12852
Credit: 0
RAC: 0
Message 6737 - Posted: 4 Nov 2020, 3:32:36 UTC

Взяла небольшой фрагмент из таблицы ортогональных пар

1401:  166 167 168 169 171 172 203 1067 1069 1070
1401:  1154 1158 1266 1284 1287 1305 1307
1402:  166 167 168 169 171 172 203 1067 1069 1070
1402:  1154 1158 1266 1284 1287 1305 1307
1403:  166 167 168 169 171 172 203 1067 1069 1070
1403:  1154 1158 1266 1284 1287 1305 1307
1404:  166 167 168 169 171 172 203 1067 1069 1070
1404:  1154 1158 1266 1284 1287 1305 1307
1406:  166 167 168 169 171 172 203 1067 1069 1070
1406:  1154 1158 1266 1284 1287 1305 1307
1407:  166 167 168 169 171 172 203 1067 1069 1070
1407:  1154 1158 1266 1284 1287 1305 1307
1817:  166 167 168 169 171 172 203 1067 1069 1070
1817:  1154 1158 1266 1284 1287 1305 1307
5270:  166 167 168 169 171 172 203 1067 1069 1070
5270:  1154 1158 1266 1284 1287 1305 1307 1976 2066 2150
5270:  2151 2152 2153 2197 2214 2270 2281 2344 2420 2473
5270:  2492 2698 2711 2725 3075 3076 3115 3117 3136 3137
5270:  3142 3249 3251 3252 3257 3258 3260 3263 3368 3371
5270:  3784 3791 4218 4228 4370 4691 4730 4835 4895 4964
5270:  4969 4970 4971 4974 4975 4976 4978 4979 4980 4984
5281:  166 167 168 169 171 172 203 1067 1069 1070
5281:  1154 1158 1266 1284 1287 1305 1307 1976 2066 2150
5281:  2151 2152 2153 2197 2214 2270 2281 2344 2420 2473
5281:  2492 2698 2711 2725 3075 3076 3115 3117 3136 3137
5281:  3142 3249 3251 3252 3257 3258 3260 3263 3368 3371
5281:  3784 3791 4218 4228 4370 4691 4730 4835 4895 4964
5281:  4969 4970 4971 4974 4975 4976 4978 4979 4980 4984
5365:  166 167 168 169 171 172 203 1067 1069 1070
5365:  1154 1158 1266 1284 1287 1305 1307 1976 2066 2150
5365:  2151 2152 2153 2197 2214 2270 2281 2344 2420 2473
5365:  2492 2698 2711 2725 3075 3076 3115 3117 3136 3137
5365:  3142 3249 3251 3252 3257 3258 3260 3263 3368 3371
5365:  3784 3791 4218 4228 4370 4691 4730 4835 4895 4964
5365:  4969 4970 4971 4974 4975 4976 4978 4979 4980 4984

(У продолжения строки номер узла повторен, иначе Gephi не понимает.)

Нарисовала



Не нашла здесь даже треугольник, то есть тройку MODLS.
Может плохо искала.
Ну, нам вообще-то шестёрка MODLS нужна.
My new article "SOLS and SODLS"
in Russian
https://yadi.sk/d/nvdI6TgBrKv72A
in English https://yadi.sk/d/VeY9bx6_q6CcZg
ID: 6737 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 12852
Credit: 0
RAC: 0
Message 6738 - Posted: 4 Nov 2020, 3:36:54 UTC

Вводить в Gephi надо в таком формате

1401;166;167;168;169;171;172;203;1067;1069;1070
1401;1154;1158;1266;1284;1287;1305;1307
1402;166;167;168;169;171;172;203;1067;1069;1070
1402;1154;1158;1266;1284;1287;1305;1307
1403;166;167;168;169;171;172;203;1067;1069;1070
1403;1154;1158;1266;1284;1287;1305;1307
1404;166;167;168;169;171;172;203;1067;1069;1070
1404;1154;1158;1266;1284;1287;1305;1307
1406;166;167;168;169;171;172;203;1067;1069;1070
1406;1154;1158;1266;1284;1287;1305;1307
1407;166;167;168;169;171;172;203;1067;1069;1070
1407;1154;1158;1266;1284;1287;1305;1307
1817;166;167;168;169;171;172;203;1067;1069;1070
1817;1154;1158;1266;1284;1287;1305;1307
5270;166;167;168;169;171;172;203;1067;1069;1070
5270;1154;1158;1266;1284;1287;1305;1307;1976;2066;2150
5270;2151;2152;2153;2197;2214;2270;2281;2344;2420;2473
5270;2492;2698;2711;2725;3075;3076;3115;3117;3136;3137
5270;3142;3249;3251;3252;3257;3258;3260;3263;3368;3371
5270;3784;3791;4218;4228;4370;4691;4730;4835;4895;4964
5270;4969;4970;4971;4974;4975;4976;4978;4979;4980;4984
5281;166;167;168;169;171;172;203;1067;1069;1070
5281;1154;1158;1266;1284;1287;1305;1307;1976;2066;2150
5281;2151;2152;2153;2197;2214;2270;2281;2344;2420;2473
5281;2492;2698;2711;2725;3075;3076;3115;3117;3136;3137
5281;3142;3249;3251;3252;3257;3258;3260;3263;3368;3371
5281;3784;3791;4218;4228;4370;4691;4730;4835;4895;4964
5281;4969;4970;4971;4974;4975;4976;4978;4979;4980;4984
5365;166;167;168;169;171;172;203;1067;1069;1070
5365;1154;1158;1266;1284;1287;1305;1307;1976;2066;2150
5365;2151;2152;2153;2197;2214;2270;2281;2344;2420;2473
5365;2492;2698;2711;2725;3075;3076;3115;3117;3136;3137
5365;3142;3249;3251;3252;3257;3258;3260;3263;3368;3371
5365;3784;3791;4218;4228;4370;4691;4730;4835;4895;4964
5365;4969;4970;4971;4974;4975;4976;4978;4979;4980;4984

Запишите это в любой текстовый файл и присвойте ему расширение csv, например: input.csv
My new article "SOLS and SODLS"
in Russian
https://yadi.sk/d/nvdI6TgBrKv72A
in English https://yadi.sk/d/VeY9bx6_q6CcZg
ID: 6738 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 12852
Credit: 0
RAC: 0
Message 6741 - Posted: 4 Nov 2020, 8:30:18 UTC
Last modified: 4 Nov 2020, 8:34:06 UTC

Тэк-с, найти нам нужно клику, точнее - все клики размера 6.

https://ru.wikipedia.org/wiki/Задача_о_клике
Кликой в неориентированном графе называется подмножество вершин, каждые две из которых соединены ребром графа. Иными словами, это полный подграф первоначального графа. Размер клики определяется как число вершин в ней. Задача о клике существует в двух вариантах: в задаче распознавания требуется определить, существует ли в заданном графе G клика размера k, в то время как в вычислительном варианте требуется найти в заданном графе G клику максимального размера.

А вот и алгоритм поиска
https://ru.wikipedia.org/wiki/Алгоритм_Брона_—_Кербоша
Алгоритм Брона — Кербоша — метод ветвей и границ для поиска всех клик (а также максимальных по включению независимых множеств вершин) неориентированного графа. Разработан голландскими математиками Броном и Кербошем в 1973 году и до сих пор является одним из самых эффективных алгоритмов поиска клик.

Алгоритм использует тот факт, что всякая клика в графе является его максимальным по включению полным подграфом. Начиная с одиночной вершины (образующей полный подграф), алгоритм на каждом шаге пытается увеличить уже построенный полный подграф, добавляя в него вершины из множества кандидатов. Высокая скорость обеспечивается отсечением при переборе вариантов, которые заведомо не приведут к построению клики, для чего используется дополнительное множество, в которое помещаются вершины, которые уже были использованы для увеличения полного подграфа.
. . . . .

ПРОЦЕДУРА extend (candidates, not):
ПОКА candidates НЕ пусто И not НЕ содержит вершины, СОЕДИНЕННОЙ СО ВСЕМИ вершинами из candidates,
ВЫПОЛНЯТЬ:
1 Выбираем вершину v из candidates и добавляем её в compsub
2 Формируем new_candidates и new_not, удаляя из candidates и not вершины, не СОЕДИНЕННЫЕ с v
3 ЕСЛИ new_candidates и new_not пусты
4 ТО compsub – клика
5 ИНАЧЕ рекурсивно вызываем extend (new_candidates, new_not)
6 Удаляем v из compsub и candidates, и помещаем в not

Господа!
Всё уже придумано до нас :)
Осталось взять готовую процедуру и написать программу.
Кто смелый? :)
My new article "SOLS and SODLS"
in Russian
https://yadi.sk/d/nvdI6TgBrKv72A
in English https://yadi.sk/d/VeY9bx6_q6CcZg
ID: 6741 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 12852
Credit: 0
RAC: 0
Message 6742 - Posted: 4 Nov 2020, 8:54:02 UTC
Last modified: 4 Nov 2020, 14:40:50 UTC

А вот здесь
https://moluch.ru/archive/107/25826/

Илларионов, Р. Е. Двухфазный алгоритм решения задачи о клике для разреженных графов большой размерности / Р. Е. Илларионов. — Текст : непосредственный // Молодой ученый. — 2016. — № 3 (107). — С. 4-8. — URL: https://moluch.ru/archive/107/25826/ (дата обращения: 04.11.2020).

У нас разреженный граф?
Если да, то алгоритм нам подходит.

PS. Точнее поставлю вопрос: то, что я представила таблицей ортогональности - это вообще граф?
Я ведь тёмная в отношении графов :)
Это сейчас графы в школе изучают (на информатике в 11 классе), а когда я училась, их даже в университете не преподавали.
Итак: у нас имеется 5650 узлов (вершин) и 16675 рёбер.
Если это граф, можно в нём искать клики размером 6.
My new article "SOLS and SODLS"
in Russian
https://yadi.sk/d/nvdI6TgBrKv72A
in English https://yadi.sk/d/VeY9bx6_q6CcZg
ID: 6742 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 12852
Credit: 0
RAC: 0
Message 6743 - Posted: 4 Nov 2020, 14:56:26 UTC
Last modified: 4 Nov 2020, 15:00:44 UTC

По поводу разреженных и плотных графов
https://ru.wikipedia.org/wiki/Плотный_граф

Пло́тный граф — граф, в котором число рёбер E близко к максимально возможному у полного графа с числом V вершин:

E= V(V-1)/2

Граф, имеющий малое число рёбер, принято называть разреженным графом.
Вообще говоря, разница между разреженным и плотным графом условна и зависит от контекста.

Получается, что у нас граф разреженный (если это вообще граф), так как в нём количество рёбер далеко от максимально возможного.
Ну вот и хорошо: можно применить указанный выше алгоритм для разреженных графов.
My new article "SOLS and SODLS"
in Russian
https://yadi.sk/d/nvdI6TgBrKv72A
in English https://yadi.sk/d/VeY9bx6_q6CcZg
ID: 6743 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
1 · 2 · 3 · Next

Message boards : Science : Database CF ODLS of order n


©2024 (C) Progger