Поиск всех графов-заготовок для выращивания конечного графа

[FasterHarder]

Всем хай! Сходу к делу!

Задан обыкновенный граф вида { A, A + B }, где А - кол-во вершин, A + B - количество ребер, причем B = { 2, 3, 4 }. Этот граф назовем целевым. Надо получить все возможные сжатые графы ( пресс-графы ), из которых можно получить целевой граф, используя пореберное разбиение ( по сути - это добавление новой вершины ). Главное требование к сжатому графу - имеет минимально возможное кол-во вершин в своем составе.

===============================================
Сразу скажу, что есть колоссальное подозрение, что для разных B = { 2, 3, 4 } может кардинально отличаться алгоритм и его сложность ( например, для B = 2 - квадратичная, а уже для B = 4 - факториальная ). Но не факт. Также есть подозрение, что при увеличении B, например, если взять B = 17 - задача становится неразрешимой за разумное время, поэтому ограничение лишь до B = 4. Но в этом ни на йоту не уверен...

Рассмотрим тривиальнейший пример. Граф помечен числами от 1 до A
1 -- 2 -- 3 - целевой граф
Что из себя может представлять сжатый граф? Вроде вариант единственный
1 -- 3. Чтобы получить целевой, нужно разбить ребро { 1, 3 }, добавив вершину №2.
1 -- +2+ -- 3 - ГОТОВО!
Примечание: очевидно, что степень добавленной вершины ВСЕГДА = 2, вроде бы...
В этом примере нарушено условие по кол-ву ребер - их должно быть НЕ меньше 5ти ( т к 3 вершины ). Но я это сделал нарочно, чтобы показать суть реберной разбивки.

Как мне кажется, в алгоритме нужна привязка к вершинам, имеющие степени = 2 - ну это так, черная мысль)

==============================================

И я хотел поинтересоваться, а как это вообще все делать-то?)) От чего отталкиваться, к чему стремиться? Тут, кстати, может быть замешан индекс Хосойи, но это неточно. Или тут какой-то абсолютно полный перебор всех возможных сжатых графов с последовательной разбивкой ребра + сравнение с целевым.

Если потребуется, то готов отрисовать любой граф и провести его пошаговый анализ + сюда картинки повыкладывать.

Подскажите, как быть-то? Буду сильно признателен)

Сообщение отредактировано: FasterHarder - 28.04.25, 15:53

[FasterHarder]

допустим, что дан такой целевой граф:

Прикреплённая картинка

он подчиняется всем требованиям: 5 вершин и 7 ребер

можно ли его вырастить из пресс-графа 1 -- 2, например? Невозможно, т к при первой же разбивке ребра связь между вершинами 1 и 2 будет потеряна, вроде бы НАВСЕГДА...

получается, что нужно обращать внимание ТОЛЬКО на вершины, имеющих степень = 2. Такая вершина единственная - это вершина №3. Кстати, а не означает ли это, что сжатый граф может быть только единственным в этом случае ( раз только одна вершина со степенью = 2 )? Наверное, нет...

Соседи вершины №3 - это №2 и №5, следовательно, можно удалить вершину №3 и добавить связь между №2 и №5. Как понимаю, здесь важно, чтобы в целевом графе изначально не должно быть связи между №2 и №5, иначе будет нарушение на этом этапе свойство обыкновенности графа ( возникнет мультиграф ).

Затем дальше продолжаем искать вершину со степенью = 2. Таких больше нет - все, сжать больше НЕ получится) Ответ готов.

В итоге нужно просто перебрать все возможные варианты УДАЛЕНИЯ вершин со степенью = 2?? Тут возможно, что при переборе всех вариантов где-то будут возникать проблемы с изоморфностью сжатых графов, но это так, черная мысль...

[Akina]

Цитата FasterHarder @ 28.04.25, 15:46

Задан обыкновенный граф

Сразу возникает вопрос - как именно задан. На мой взгляд, оптимальным для решаемой задачи является задание в виде матрицы связности. Простой список рёбер тоже подходит.

Цитата FasterHarder @ 28.04.25, 15:46

Надо получить все возможные сжатые графы

Ну уже правильно замечено, что степень сжимаемой вершины всегда 2. Кроме того, вершины нумерованы, и, следовательно, различимы. То есть в итоге задача сводится к тривиальной генерации всех возможных сочетаний вершин степени 2.

[FasterHarder]

Цитата Akina @ 28.04.25, 16:37

Сразу возникает вопрос - как именно задан. На мой взгляд, оптимальным для решаемой задачи является задание в виде матрицы связности. Простой список рёбер тоже подходит.

любой удобный формат для решения подойдет

Цитата Akina @ 28.04.25, 16:37

То есть в итоге задача сводится к тривиальной генерации всех возможных сочетаний вершин степени 2.

то есть мои рассуждения из поста №2 в принципе норм?)

еще прошу тебя обратить внимание на изоморфность сжатых графов, которые получены разной траекторией генерации, так сказать, а также, что думаешь, по этому поводу?

Цитата FasterHarder @ 28.04.25, 15:46

Сразу скажу, что есть колоссальное подозрение, что для разных B = { 2, 3, 4 } может кардинально отличаться алгоритм и его сложность ( например, для B = 2 - квадратичная, а уже для B = 4 - факториальная ). Но не факт. Также есть подозрение, что при увеличении B, например, если взять B = 17 - задача становится неразрешимой за разумное время, поэтому ограничение лишь до B = 4. Но в этом ни на йоту не уверен...

[Akina]

Цитата FasterHarder @ 28.04.25, 16:42

еще прошу тебя обратить внимание на изоморфность сжатых графов, которые получены разной траекторией генерации, так сказать, а также, что думаешь, по этому поводу?

Вот исходный граф и два сжатых от него после удаления ОДНОЙ вершины.

Прикреплённая картинка

Это один и тот же сжатый граф, или это разные сжатые графы?

[macomics]

Если вершину не убирать (3 или 4), а дополнять информацией (3+4), тогда графы одинаковые. Иначе восстановить исходный граф будет сложно.

Но, судя по вашему примеру, его еще можно свернуть по примеру FasterHarder. Тогда будет граф с 2+3+4 или граф с 3+4+5. И вот тогда они станут двумя разными.

ADD: Какой количество вершин в графе предполагается? Может будет проще, если номера вершин будут заменены битовыми позициями? т.е. нумерация будет не 1,2,3,..,N. А 1,2,4,..,2^N.
Так можно будет проще сворачивать вершины графа.

Сообщение отредактировано: macomics - 28.04.25, 20:09

[FasterHarder]

Akina, спс, что потратил время и привел пример графа

Цитата Akina @ 28.04.25, 19:53

Это один и тот же сжатый граф, или это разные сжатые графы?

с тз помеченности - разные, а с тз изоморфности - одинаковые, но я пока не могу на твой вопрос однозначно ответить, т к нужно понять, а графы вообще помеченные должны быть или нет. Я с этим буду разбираться.

Цитата macomics @ 28.04.25, 20:04

Иначе восстановить исходный граф будет сложно.

по условию восстановление не требуется, но это я еще буду выяснять

Цитата macomics @ 28.04.25, 20:04

Какой количество вершин в графе предполагается?

тоже попробую понять, но, скорее всего, как обычно 10⁹ или около того...

когда искал какую-либо инфу для алгоритма этой задачи, то попалась ПДФ-ка забугорная из 20-25 стр. и там что-то было про графы вида ( N, N+2 ). Текст из этой ПДФ я понял на 1-2%, не больше) ( хотя пробовал понять раз 5 ) и там что-то было про индекс Хосойи + там все оч.сложно было как-то и постоянно встречалось слово cycle ( цикл ). А вот этот сжатый граф дословно переводился как стягиваемый граф. И там вроде на рисунках графы были непомеченные, хм...

в общем мне нужно время, чтобы погрузиться поглубже в эту задачу, подготовить примеры + ответы на вопросы) но к этой задаче я вернусь в ближайшее время - 100%

[Akina]

Цитата FasterHarder @ 28.04.25, 23:28

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

Всё, мысль остановилась. Нет чёткого и однозначного задания - нет и обсуждения/решения. Рассматривать все 4 варианта - это перебор.

[FasterHarder]

разобрался с постановкой задачи - все оказалось не так, как предполагалось изначально - все резко усложнилось сейчас, имхо

Заданы обыкновенные графы вида { A, A + B }, где А - кол-во вершин, A + B - количество ребер, причем B = { 1, 2, 3, 4 }. Количество вершин на вход программе НЕ подается, а только значения B, т е одно число на вход: 1, 2, 3 или 4. То есть рассматривается не какой-то конкретный граф, а целый КЛАСС графов одновременно ( привязки к кол-ву вершин как бы нет ).

Сжатый ( стягиваемый граф ) - связный псевдограф ( допустимы петли и мультиребра ). Имеет A' вершин и C' ребер ( C' = A' + B ). Степень каждой вершины НЕ меньше 3. Число вершин A' лежит на отрезке [ 1.. 2B ].

Надо получить все возможные сжатые графы неизоморфные друг другу для заданного значения B. Известно, что их кол-во ограниченно.

Примечание: все графы непомеченные ( вершины не имеют уникальных меток )

=====================================================================

а это вообще как исследовать? или входных данных ( только одно значение B = { 1, 2, 3, 4 } ) явно недостаточно

подскажите как быть-то? буду признателен...

[FasterHarder]

нашел в сети еще такую картинку

Прикреплённая картинка

тут полный перечень сжатых графов для класса графов вида ( A, A + 2 ), т е абсолютно ЛЮБОЙ обыкновенный граф вида ( A, A + 2 ) можно стянуть в один из тех, что на картинке...

[macomics]

Т.е. задача сводится к последовательному увеличению количества вершин и попыткам построить с ними все графы на N + B ребер, а потом проверка их на совпадение и возможность свертывания в один из уже сохраненных. Увеличивать будем вершины до тех пор пока не будет встречено количество вершин для которого все графы свернутся в уже сохраненные.

Жуткий переборчик получится и явно не быстрый. Но это если в лоб решать.

[FasterHarder]

macomics, считаю, что правильная мысль и она оч.похожа на ту, что я читал где-то на забугорном сайте, поняв на 1-2%. После твоих слов - понимание увеличилось)

[macomics]

Но это логично и вообще то изображено на картинке. Только они там как-то хаотично упорядочены. Графы скорее размещали по принципу расхода места, а не упорядочили по количеству вершин. Но там явно видно: 1 граф с одной вершиной, 4 с двумя, 5 с тремя, а нижний ряд с 4-я вершинами и их 5 штук.

Добавлено 02.05.25, 12:00
С другой стороны. Математически можно задачу упростить до: разложить 2*(N+B) (N+B черных и N+B белых - белый + черный шар символизируют разные концы грани, но на цвет в задаче можно внимания не обращать т.к. допустимы петли) по N коробкам так, чтобы в каждой было не меньше 3-х шаров.

Сообщение отредактировано: macomics - 02.05.25, 12:01

[FasterHarder]

Буду отталкиваться от B = 2 ( это графы вида { A, A + 2 } ), т к для этого случая есть пример всех возможных сжатых графов ( пост №10 ). Планирую потихоньку публиковать сюда рассуждения + задавать уточняющие вопросы.

Немного порисовал обыкновенные графы и получил их сжатие

Прикреплённая картинка

в целом вроде понятно, как это все работает. Как понимаю, в программе при любом раскладе потребуется вот этот кусок алгоритма, который текущий обыкновенный граф стягивает

псевдокод

ПОКА (ИСТИНА)
    флаг = ЛОЖЬ
 
    перебрать все вершины от 1 до A
        если степень текущий вершины = 2
            удалить ее из графа
            степень соседних вершин увеличить на +1
 
            флаг = ИСТИНА
 
     если флаг = ЛОЖЬ
         выход из цикла, т к не осталось ни одной вершины со степенью = 2
КОНЕЦ ПОКА

то есть при стягивании графа идет привязка исключительно к степени вершины и проверки на 2. Надеюсь, что это правильный подход)

[FasterHarder]

дальше, как понимаю, однозначно потребуется подалгоритм - проверка на изоморфизм двух псевдографов ( допустимы петли и кратные ребра! ), пока без привязки к структурам данных. Вроде постановка четко локализована, но, после 5-10мин. гугления стало понятно, что это не оч.простая задача - на форумах много обсуждают, спорят и пр., даже приводят алгоритмы, где проще доказать НЕизоморфизм и т.п.

в итоге нашел вот такой алгоритм (хорошо, что речь там про мультиграфы), насколько он корректен - понятия не имею

Прикреплённая картинка

есть еще какие-то варианты, типа подключить хеширование и для каждого псевдографа получать некий хеш, т е иметь коллекцию хешей. И когда будет получен очередной сжатый граф, то просто проверить его хеш на совпадение хешей из коллекции...Тут вопрос: а какую ХФ можно использовать, которая гарантирует исключение коллизий?

[AVA12]

Ну, то, что у изоморфных графов матрицы смежности можно получить друг из друга корректной перестановкой (т.е. переставить i-тую и j-тую строки И i-тый и j-тый столбец) интуитивно понятно. Хэш-функция для матрицы, не зависящая от корректных перестановок, давно известна - это определитель, он же детерминант. Но использовать его для сравнения матриц - не очень хорошая идея (слишком много коллизий). Даже если вместо матрицы смежности использовать более хитрую матрицу (например, элемент равен взвешенной сумме весов самой вершины, смежных с ней, смежных со смежными и т.д.), то идея все равно сомнительная. И вообще, мучиться с генерацией огромного числа матриц, чтобы в итоге выкинуть почти все результаты, как-то неправильно.

Лучше придумать способ упорядочивания всех корректных перестановок конкретной матрицы. Например, линеаризовать матрицу в список значений и для определения взаимного порядка двух перестановок сравнивать эти списки поэлементно. И для проверки генерировать только наибольшую (или наименьшую) из перестановок для каждого варианта.

По условию задачи для каждого B нужно получить матрицы смежности для графов из V вершин и E ребер, в которых E = V + B и сумма элементов каждой строки (или, что то же самое, каждого столбца) >= 3. Для предварительной отбраковки вариантов можно заметить, что в матрице каждое ребро (за исключением петель, т.е. главной диагонали) учитывается дважды, т.е. сумма элементов матрицы равна (2*E - D) (где D - сумма главной диагонали), и сумма всех строк должна быть >= 3*V,
=> 2*E - D >= 3*V
=> 2*V + 2*B - D >= 3*V
=> 2*B - D >= V

А вот над деталями алгоритма генерации матриц для проверки нужно еще подумать.

Сообщение отредактировано: AVA12 - 03.05.25, 17:18

[FasterHarder]

хотел бы внести небольшую ( а может даже и большую! ) поправку в псевдокод из поста №14. Есть такое утверждение, что из любого обыкновенного графа можно получить сжатый и он будет единственным. Это означает, что вершины обыкновенного графа можно просматривать в произвольном порядке, причем достаточно будет всего одного раза. При удалении вершины степень его соседей увеличивается на 1, а в исходном графе минимальная степень = 2 ( изолированные или висячие вершины обыкновенный граф вроде как по определению НЕ имеет ), поэтому любое удаление приводит минимум степень соседних вершин = 3, после чего они уже физически не участвуют в последующей обработке...
Если в стартовом обыкновенном графе K вершин, имеющих степень = 2, то не важно, с какой начинать обработку, т к в итоге полученные стягиваемые графы все равно будут изоморфны друг другу, что делает их совпадающими по условию задачи. Но в этом я не уверен на 100%.
Получается, что внешний бесконечный цикл WHILE как бы лишний, достаточно просто одного перебора всех вершин для получения сжатого графа...

=============================================================

На вход подается только 1 число, в данном примере это число = 2. Все, ничего больше нет - пустота. Как раньше писал macomics, надо иметь хранилище сжатых графов ( вопрос по их хешам остается открытым, но в любом случае только одного хеша недостаточно, т к в оконцовке программа должна вывести в какой-то форме информацию о сжатых графах как таковых ).

Работа идет с КЛАССОМ графов вида ( A, A + 2). Очевидно, что таких обыкновенных графов БЕСКОНЕЧНОЕ множество, т к A можно увеличивать до бесконечности)
Надо бы понять, а какое наименьшее значение А?
1. Может ли А = 1? Нет, т к в этом случае будет 2 петли, что нарушает свойство обыкновенного графа.
2. Может ли А = 2? Нет, т к в этом случае будут кратные ребра, что нарушает...
3. Может ли А = 3? Нет, опять будут петли или мультиребра
4. Может ли А = 4? Да, это ромб с обеими диагоналями, например. Кстати, это один из вариантов сжатого графа из коллекции. То есть, когда А = 4 стягивать нечего, но этот граф обыкновенный. Кстати, это единственный сжатый граф, не имеющий петель и кратных ребер!
Вывод: запускать генерацию обыкновенных графов стоит от 4рех вершин. Получается так или нет?


==========================================================

Ядро алгоритма - генерация всех возможных обыкновенных графов до определенного предела с формированием коллекции сжатых графов.
об этом попозже напишу)

[macomics]

Цитата FasterHarder @ 03.05.25, 14:28

то есть при стягивании графа идет привязка исключительно к степени вершины и проверки на 2. Надеюсь, что это правильный подход)

А если у вас идут две вершины рядом со степенью 2 как у Akina в #5. Тогда нельзя просто увеличивать на 1. Надо считать новые вершины по стяжкам.

Но, вроде, у них не увеличится количество соединений вовсе (степень)?

Добавлено 03.05.25, 17:35

Цитата FasterHarder @ 03.05.25, 15:08

Тут вопрос: а какую ХФ можно использовать, которая гарантирует исключение коллизий?

Смотря какие данные вы будете подвергать ей. Если данные не очень длинные, то пойдет что-то быстрое и короткое типа CRC32. А вот если представление графа будет размерами кратными МБ и более, тогда нужны более точные, но медленные MD5, SHA и тд.

[AVA12]

Гм, я забыл учесть, что петля прибавляет к степени вершины 2, а не 1. Тогда для сжатого графа сумма элементов строки плюс диагональный элемент >= 3, а для предварительной отбраковки сжатых кандидатов считать 2*E >= 3*V
=> 2*V + 2*B >= 3*V
=> 2*B >= V

FasterHarder:
На всякий случай уточняю: я говорил про генерацию уже сжатых графов, генерировать исходные графы и что-то хранить не нужно.

Цитата

При удалении вершины степень его соседей увеличивается на 1

С чего вдруг? Сосед был связан с ныне удаленной вершиной, теперь связан с кем-то другим. Одна связь исчезла, другая появилась, ничего не поменялось.

[AVA12]

Кстати, FasterHarder, насчет запрета висячих вершин и того, что в сжатом графе степень вершин >= 3: это действительно часть условия или просто наблюдение? Если в исходном графе есть висячие вершины, то они могут остаться висячими в сжатом графе, и тогда алгоритм проверки заметно усложняется.

[FasterHarder]

macomics, AVA12, вы, конечно же правы относительного того, что, степень соседей НЕ нужно увеличивать на +1 при удалении вершины, тут я прогнал дико, конечно). Ну тогда внешний бесконечный цикл нужен в псевдокоде, ок...

Цитата AVA12 @ 03.05.25, 18:18

насчет запрета висячих вершин и того, что в сжатом графе степень вершин >= 3: это действительно часть условия или просто наблюдение? Если в исходном графе есть висячие вершины, то они могут остаться висячими в сжатом графе, и тогда алгоритм проверки заметно усложняется.

тут дело в том, что обработке подвергаются ТОЛЬКО обыкновенные графы, а это, как минимум:
1. нет петель
2. нет кратных ребер
3. нет изолированных и висячих вершин
таково определение обыкновенного графа...

=================================================

еще у меня есть неточность, когда были примеры сжатия в посте №14. Паттерн "лепесток" будет чуть другим )( сейчас там есть кратные ребра, что недопустимо! ), а именно:

Прикреплённая картинка

вроде это минимальный обыкновенный граф, который можно сжать до графа-точки с 3мя петлями.

==================================================

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

[FasterHarder]

По генерации всех возможных графов класса ( А, А + 2 ) при заданном А есть лютые проблемы.
Будет полный перебор всех возможных комбинаций ребер между вершинами. То есть из каждой текущей вершины будет попытка перейти в ЛЮБУЮ другую вершину.
Рассмотрим вариант для А = 4 - это минимальное кол-во вершин, с которого стоит запускать генерацию. Несмотря на то, что графы по условию непомеченные, но в коде к ним все равно нужно как-то обращаться, поэтому нумерация какая-то нужна, ну я буду нумеровать их натуральными от 1 до А.

Вот заготовка для генерации графов, состоящего из 4рех вершин:

Прикреплённая картинка

правило построения: от вершины с наименьшим номером к наибольшей. Ребра маркирую латинскими буквами по алфавиту в порядке появления. Графы формируются рекурсивно ( вроде на спуске будет ).

на 5ом уровне рекурсивного спуска будет такая ситуация:

Прикреплённая картинка

поскольку это НЕ Эйлеровый граф, то при переходе из вершины 4 во 2ую попадаем в ТУПИК. Тупик - это такая вершина, что все смежные с ней вершины уже посещены. Любое дальнейшее продвижение из тупика приводит к появлению кратных ребер, что недопустимо.

Понятно, что при достижении тупика закрывается текущий уровень рекурсии и делается откат на уровень выше, т е переход к вершине №4 и затем уже последнее ребро инсталлируется к вершине №3 и все готово.

Прикреплённая картинка

Как я понимаю, на каждом уровне рекурсивного вызова нужно знать:
1. сколько ребер осталось вставить
2. состояние графа (его текущая структура)
3. номер вершины, из которой будет выходить ребро
это навскидку, черновой вариант того, что минимум нужно пока что...

Откат рекурсивного спуска на уровень выше делается в 2 случаях:
- достижение тупика
- кол-во вставляемых ребер стало равно 0 (граф сформирован!)

Мне не очень понятно по поводу п.2 (про состояние графа). Вроде считается, что каждый более нижний уровень вызова рекурсии должен учитывать и рассчитываться на основании вызовов более верхних уровней, но здесь это не прокатывает как бы...

Пусть для примера ( только для примера! ) граф описывается матрицей смежности. Она передается по значению в качестве параметра, не по ссылке, хотя может надо и по ссылке, чтобы отражались изменения на любом рекурсивном вызове.
В итоге, когда достигли тупика (на уровне №5) делаем откат на уровень №4:

Прикреплённая картинка

ну и в итоге ребро e =(4,2) потеряно. То есть нужно его каким-то образом запоминать, либо передавать матрицу смежности по ссылке, но это вроде приведет к лютым проблемам при стирании траектории при новой генерации.

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

Вот пример рекурсивного спуска с запоминаем всех посещенных вершин:

Прикреплённая картинка

граф на 5ых уровнях работает независимо друг от друга, как и писал выше, нижние уровни учитывают только более верхние, а не равные и более нижние им...
в итоге, когда текущий граф сформирован его нужно отдать на проверку обыкновенности, ведь генерация всех возможных вариантов будет давать и брак:
1. будет генерация с висячими вершинами
2. будет генерация с изолированными вершинами (больше одной компоненты связности)
кстати, проверку на обыкновенность графа вроде сделать несложно: достаточно посчитать степень КАЖДОЙ вершины и она должна быть У КАЖДОЙ вершины не меньше 2 (если будет 0 - изоляция - брак, если будет 1 - висячая - брак)

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

так, стоп, а я вообще правильно мыслю или все совсем не так должно быть?
кстати, алгоритмическая сложность такой генерации вроде будет (A + 2)^A - это, конечно, ужасно, хуже только факториальная сложность вроде ))

====================================
еще есть вариант, типа, например для A = 10, рассмотреть матрицу смежностей - квадрат 10 на 10, вычеркнуть элементы гл.диагонали и рассмотреть нижнетреугольную матрицу, которую надо забить всеми возможными комбинациями 1 в кол-ве 12 штук