Математический форум Math Help Planet
http://mathhelpplanet.com/

Ортогональные латинские квадраты 10-го порядка
http://mathhelpplanet.com/viewtopic.php?f=57&t=46638
Страница 60 из 421

Автор:  Nataly-Mak [ 01 мар 2016, 10:39 ]
Заголовок сообщения:  Re: Ортогональные латинские квадраты 10-го порядка

Avgust
проверила. Увы! Диагональных ОЛК нет к этому ДЛК.

Автор:  whitefox [ 01 мар 2016, 20:39 ]
Заголовок сообщения:  Re: Ортогональные латинские квадраты 10-го порядка

Восстановил по памяти свою программу проверки ДЛК на изоморфизм.

Эта программа любой ДЛК10 приводит к канонической форме. Все ДЛК, принадлежащие одному и тому же классу изоморфизма (изоморфы), имеют одну и туже каноническую форму, а ДЛК, принадлежащие разным классам изоморфизма, имеют разные канонические формы.

Для проверки двух ДЛК на изоморфизм, нужно их привести к канонической форме и сравнить. ДЛК изморфны тогда и только тогда, когда из канонические формы равны.

Сейчас у меня нет доступа к нормальному компилятору, поэтому выкладываю исходик. Его нужно скопировать, вставить в какой-нибудь онлайн-компилятор, например http://ideone.com/, и кликнуть Run.

Исходный ДЛК прописан в программе, для проверки другого ДЛК, замените код:

int isxodn[10][10] = {
{0,1,2,3,4,5,6,7,8,9},
{9,8,7,6,5,4,3,2,1,0},
{6,4,9,8,7,2,1,0,5,3},
{5,0,1,7,3,6,2,8,9,4},
{3,5,0,1,2,7,8,9,4,6},
{4,9,8,2,6,3,7,1,0,5},
{1,2,3,5,9,0,4,6,7,8},
{7,6,4,9,1,8,0,5,3,2},
{2,3,5,0,8,1,9,4,6,7},
{8,7,6,4,0,9,5,3,2,1}};

нужным.

Текс программы в оффтопе.
#include <iostream>

using namespace std;

const int chprst = 120;
const int chkrtzh = 32;
const int prst[chprst] = {
3,2,1,0,3,0,1,2,3,1,3,2,1,0,1,0,1,2,3,2,3,2,1,0,
1,0,1,2,3,1,3,2,1,0,3,0,1,2,3,0,3,2,1,0,3,0,1,2,
3,1,3,2,1,0,1,0,1,2,3,2,3,2,1,0,1,0,1,2,3,1,3,2,
1,0,3,0,1,2,3,0,3,2,1,0,3,0,1,2,3,1,3,2,1,0,1,0,
1,2,3,2,3,2,1,0,1,0,1,2,3,1,3,2,1,0,3,0,1,2,3,0};
const int krtzh[chkrtzh] = {
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4};

int isxodn[10][10] = {
{0,1,2,3,4,5,6,7,8,9},
{9,8,7,6,5,4,3,2,1,0},
{6,4,9,8,7,2,1,0,5,3},
{5,0,1,7,3,6,2,8,9,4},
{3,5,0,1,2,7,8,9,4,6},
{4,9,8,2,6,3,7,1,0,5},
{1,2,3,5,9,0,4,6,7,8},
{7,6,4,9,1,8,0,5,3,2},
{2,3,5,0,8,1,9,4,6,7},
{8,7,6,4,0,9,5,3,2,1}};

int kanon[100] = {10};

void rabota();
void vvod(int izomorf[][10][10]);

inline void preobr_4(int x, int izomorf[10][10]){
for(int i = 0; i < 10; i++){
swap(izomorf[i][x], izomorf[i][x + 1]);
swap(izomorf[i][9 - x], izomorf[i][8 - x]);
}
for(int i = 0; i < 10; i++){
swap(izomorf[x][i], izomorf[x + 1][i]);
swap(izomorf[9 - x][i], izomorf[8 - x][i]);
}
}

inline void preobr_2(int x, int izomorf[10][10]){
for(int i = 0; i < 10; i++) swap(izomorf[x][i], izomorf[9 - x][i]);
for(int i = 0; i < 10; i++) swap(izomorf[i][x], izomorf[i][9 - x]);
}

int main(){
rabota();
for(int i = 0; i < 10; i++) for(int j = 0; j < 10; j++)
cout << kanon[i * 10 + j] << (j != 9 ? ' ' : '\n');
cout << endl;
return 0;
}

void rabota(){
int izomorf[4][10][10];
int temp[10][10];
int kraska[10];
vvod(izomorf);
for(int kvadrat = 0; kvadrat < 4; kvadrat++) for(int i = 0; i < chprst; i++){
for(int j = 0; j < chkrtzh; j++){
for(int k = 0; k < 10; k++) kraska[izomorf[kvadrat][0][k]] = k;
for(int k = 0; k < 10; k++) for(int l = 0; l < 10; l++){
temp[k][l] = kraska[izomorf[kvadrat][k][l]];
}
for(int k = 0; k < 100; k++){
if(kanon[k] > temp[k / 10][k % 10]){
for(int l = 0; l < 100; l++) kanon[l] = temp[l / 10][l % 10];
break;
}
else if(kanon[k] < temp[k / 10][k % 10]) break;
}
preobr_2(krtzh[j], izomorf[kvadrat]);
}
preobr_4(prst[i], izomorf[kvadrat]);
}
}

void vvod(int izomorf[][10][10]){
for(int i = 0; i < 10; i++) for(int j = 0; j < 10; j++){
izomorf[0][i][j] = isxodn[i][j];
izomorf[1][j][i] = izomorf[0][i][j];
}
for(int i = 0; i < 10; i++) for(int j = 0; j < 10; j++){
izomorf[2][i][j] = izomorf[0][i][9 - j];
izomorf[3][i][j] = izomorf[1][i][9 - j];
}
}

Автор:  Nataly-Mak [ 01 мар 2016, 21:52 ]
Заголовок сообщения:  Re: Ортогональные латинские квадраты 10-го порядка

whitefox писал(а):
Восстановил по памяти свою программу проверки ДЛК на изоморфизм.

Эта программа любой ДЛК10 приводит к канонической форме. Все ДЛК, принадлежащие одному и тому же классу изоморфизма (изоморфы), имеют одну и туже каноническую форму, а ДЛК, принадлежащие разным классам изоморфизма, имеют разные канонические формы.

whitefox
здорово! Важнейшая программа классификации всех изоморфов ДЛК. Она даёт надежду на получение всей БД ДЛК.

Тестирую программу. Первый ДЛК для проверки - основной ДЛК Брауна:

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

Программа выдала следующую какноническую форму для данного ДЛК:

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

Теперь беру один из ДЛК, полученных по матрице Avgust:

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

Программа выдала такую каноническую форму для этого ДЛК:

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

Как видим, кононическая форма такая же, как в первом примере, значит, эти два ДЛК принадлежат одному классу изоморфизма (это все ДЛК, получаемые переобозначением элементов, в этом классе 10! изоморфов).

Третий ДЛК для тестирования - полученный мной М-преобразованием изоморф основного ДЛК Брауна:

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

Для этого ДЛК программа выдала следующую каноническую форму:

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

Как видим, получилась другая каноническая форма, потому что это другой класс изоморфизма (ДЛК, получаемые М-преобразованиями).

whitefox
всё правильно поняла?
Если мы возьмём любой из 10! изоморфов основного ДЛК Брауна из класса изоморфизма - переобозначение элементов, получим для него одну и ту же каноническую форму. Так?
Точно так же для класса изоморфизма - М-преобразования.
А какие ещё будут классы изоморфизма?

Автор:  Avgust [ 01 мар 2016, 21:57 ]
Заголовок сообщения:  Re: Ортогональные латинские квадраты 10-го порядка

Nataly-Mak
Вот теперь нужно тщательно рассмотреть две канонические формы и понять, как производить другие виды.

Автор:  Nataly-Mak [ 01 мар 2016, 22:01 ]
Заголовок сообщения:  Re: Ортогональные латинские квадраты 10-го порядка

Четвёртый тест - нормализованный основной ДЛК Брауна

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


Выданная программой каноническая форма:

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

Всё правильно: первый класс изоморфизма.

Автор:  Nataly-Mak [ 01 мар 2016, 22:05 ]
Заголовок сообщения:  Re: Ортогональные латинские квадраты 10-го порядка

Avgust писал(а):
Вот теперь нужно тщательно рассмотреть две канонические формы и понять, как производить другие виды.

Совершенно верно. Только канонических форм, наверное, будет не две, а больше (?). Это нам whitefox расскажет. Хотя я пока не знаю других классов изоморфизма для ДЛК.

Вот смотрите: мой генератор генерирует ДЛК тысячами, но среди этих тысяч принципиально разных (не изоморфных) ДЛК раз-два и ... нету. Значит, надо генерировать сразу различные ДЛК, то есть при генерации проверять все получаемые ДЛК по канонической форме всех классов изоморфизма. Вот тогда в принципе возможно получить полную базу данных (БД) всех ДЛК. А сейчас их многие миллионы и разобраться в этой куче невозможно.

whitefox
а основные преобразования ЛК - повороты и отражения - у вас вошли в класс М-преобразований?
По идее вроде бы не должны, это отдельный класс изоморфизма.

Автор:  Nataly-Mak [ 01 мар 2016, 22:26 ]
Заголовок сообщения:  Re: Ортогональные латинские квадраты 10-го порядка

Повернула на 90 градусов нормализованный ДЛК Брауна и проверила его по программе.

Это проверяемый ДЛК (повёрнутый ДЛК Брауна в нормализованном виде):

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

Программа выдала каноническую форму:

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

Это класс изоморфизма - М-преобразования.
Получается, что и основные преобразования, и М-преобразования в одном классе изоморфизма, и всего изоморфов в этом классе 15360.
Так?

Автор:  Avgust [ 01 мар 2016, 22:30 ]
Заголовок сообщения:  Re: Ортогональные латинские квадраты 10-го порядка

Пока что опять только две канонические формы (КФ). А желательно 5-6 КФ, чтобы
понять свойства.

Автор:  Nataly-Mak [ 01 мар 2016, 22:43 ]
Заголовок сообщения:  Re: Ортогональные латинские квадраты 10-го порядка

Avgust
вы молодец!
Я сначала немного не так поняла количество канонических форм (КФ). Это количество совсем не равно количеству классов изоморфизма. КФ позволяет определить всех изоморфов для данной группы ДЛК.

Я нашла третью КФ!
Взяла нормализованный ДЛК Гергели

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

и проверила его по программе. Выдалась совсем другая КФ:

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

В-о-о-о-о-т! Значит, ДЛК Гергели - совсем новый ДЛК, не имеющий никакого отношения к ДЛК Брауна, не получающийся из него никакими преобразованиями.

Итак, три КФ у нас уже есть. Сколько же их будет всего?
Для этого надо генерировать ДЛК и проверять их программой whitefox на КФ.

Автор:  whitefox [ 01 мар 2016, 22:51 ]
Заголовок сообщения:  Re: Ортогональные латинские квадраты 10-го порядка

Nataly-Mak писал(а):
Получается, что и основные преобразования, и М-преобразования в одном классе изоморфизма, и всего изоморфов в этом классе 15360.
Так?
Всего имеется [math]15360\cdot 10!=55\ 738\ 368\ 000[/math] изоморфизмов ДЛК. В это число входят и повороты и отражения и М-преобразования и переобозначения элементов. И все ДЛК, которые любым из этих [math]55\ 738\ 368\ 000[/math] способов приводятся к одной и той же канонической форме, принадлежат одному классу изоморфизма.
Nataly-Mak писал(а):
Третий ДЛК для тестирования - полученный мной М-преобразованием изоморф основного ДЛК Брауна:
Какое именно преобразование вы применили?

Страница 60 из 421 Часовой пояс: UTC + 3 часа [ Летнее время ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/