Guest
Новичок
|
    
Есть очень важная задача. Пожалуйста помогите решить.
Суть состоит в следующем:
Необходимо найти бинарную (элементы 1 или 0) матрицу следующего вида:
1. Размер матрицы 12(строк)на9(столбцов)
2. В каждой строке 3 единицы
3. В каждом столбце 4 единицы
4. У каждой пары строк не может быть больше 1 общей единицы
5. У каждой пары столбцов не может быть больше 1 общей единицы
Необходимо доказать наличие решения найти его или
доказать отсутсвие решения.
Необходимо найти общий алгоритм поиска таких матриц
Размерность матрицы задается и может быть:
12х9 (единиц 4 и 3 соответственно) (решение найдено перебором)
20х12 (единиц 3 и 5 соответственно) (решение найдено перебором)
26х13 (единиц 6 и 3 соответственно) (решение найдено перебором)
35х15 (единиц 7 и 3 соответственно) решение пока не найдено
56х21 (единиц 8 и 3 соответственно) решение пока не найдено
63х21 (единиц 9 и 3 соответственно) решение пока не найдено
есть еще и большее количество матриц, но вся проблема состоит в том, что
поиск перебором не позволяет находить решения.
Прошу помочь в поиске алгоритма решения и построения таких матриц.
Спасибо.
|
Всего сообщений: Нет | Присоединился: Never | Отправлено: 19 нояб. 2007 13:38 | IP
|
|
llorin1
Участник
|
35х15 (единиц 7 и 3 соответственно) решение пока не найдено
56х21 (единиц 8 и 3 соответственно) решение пока не найдено
63х21 (единиц 9 и 3 соответственно) решение пока не найдено
У каждой пары столбцов или строк не может быть больше 1 общей единицы
__________________________________________________________
Искомая матрица может интерпретироваться как матрица инцидентности уравновешенной (сбалансированной) неполной блок-схемы D(b, v , r, k, L) –
- размещение v различных элементов по b блокам, причем:
1) каждый блок содержит ровно k различных элементов;
2) каждый элемент принадлежит ровно r различным блокам;
3) каждая пара различных элементов принадлежит точно L блокам.
В нашем случае даны блок-схемы с конфигурациями
(35, 15, 7, 3, 1), (56, 21, 8, 3, 1) , (63, 21, 9, 3, 1).
При k=3 и L=1, (b, v , r, 3, 1) - конфигурация называется системой троек Штейнера.
Система троек Штейнера (см. [1], [2]) существует тогда и только тогда, когда
v=1(mod 6) либо v=3(mod 6).
А так как параметры блок-схемы D связаны соотношениями
b k= v r, r(k-1)=L(v-1),
то существует только (35, 15, 7, 3, 1) – конфигурация.
Для ее построения (см. [2]) используются орбиты элементов (0,x,y) и (0,m,2m) аддитивной группы классов вычетов по модулю v (группа автоморфизмов блок-схемы D):
Если v=6t+3=3m, причем m=2t+1<>0(mod 3), то x,y определяются из условий
x=1(mod 3), y=1(mod 3);
x<>0(mod m), y<>0(mod m); (*)
x+y=0(mod m).
Заданные таким способом, орбиты элементов (0,x,y) периода v и (0,m,2m) периода m, образуют
(b=(3t+1)(2t+1), v=6t+3, r=3t+1, k=3, L=1) – конфигурацию.
В нашем случае, решение системы (*) при m=5, есть (x=1,y=4) или (x=7,y=13).
Орбита каждого элемента выписывается как вычет по mod v (группа аддитивна):
(0,x,y), (1,x+1,y+1) (mod v), (2,x+2,y+2) (mod v), …, (v-1,x+v-1,y+v-1) (mod v).
Таким образом, выписав по 15 троек, образованных из (0,1,4) и (0,7,13) , и 5 троек – из (0,5,10), всего получим семейство из 35 троек.
Теперь, если везде заменить число 0 на число 15, то семейство
{15, 1, 4},
{1, 2, 5},
{2, 3, 6},
{3, 4, 7},
{4, 5, 8},
{5, 6, 9},
{6, 7, 10},
{7, 8, 11},
{8, 9, 12},
{9, 10, 13},
{10, 11, 14},
{11, 12, 15},
{12, 13, 1},
{13, 14, 2},
{14, 15, 3},
---
{15, 7, 13},
{1, 8, 14},
{2, 9, 15},
{3, 10, 1},
{4, 11, 2},
{5, 12, 3},
{6, 13, 4},
{7, 14, 5},
{8, 15, 6},
{9, 1, 7},
{10, 2, 8},
{11, 3, 9},
{12, 4, 10},
{13, 5, 11},
{14, 6, 12},
---
{15, 5, 10},
{1, 6, 11},
{2, 7, 12},
{3, 8, 13},
{4, 9, 14}
можно рассматривать, как номера единиц в строках матрицы инцидентности блок-схемы D(35, 15, 7, 3, 1).
[1]: Сачков В.Н. Введение в комбинаторные методы дискретной математики, М.: Наука, 1982.
[2]: Холл М. Комбинаторика, М.: Мир, 1970.
|
Всего сообщений: 147 | Присоединился: июнь 2006 | Отправлено: 23 нояб. 2007 0:47 | IP
|
|
Guest
Новичок
|
Спасибо большое!
Вы чрезвычайно помогли! Если появятся вопросы, обязательно
зададим... Пока проверяем ранее найденные матрицы...
Спасибо!
|
Всего сообщений: Нет | Присоединился: Never | Отправлено: 23 нояб. 2007 2:05 | IP
|
|
|
Форум
задача Чернышева
