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

[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 штук