Форум на Исходниках.RU

Форум на Исходниках.RU https://forum.sources.ru Форум на Исходниках.RU Форум на Исходниках.RU https://forum.sources.ru/index.php?showtopic=460420&view=findpost&p=3921756 Sun, 04 May 2025 01:48:06 +0000 Поиск всех графов-заготовок для выращивания конечного графа https://forum.sources.ru/index.php?showtopic=460420&view=findpost&p=3921756 Будет полный перебор всех возможных комбинаций ребер между вершинами. То есть из каждой текущей вершины будет попытка перейти в ЛЮБУЮ другую вершину.
Рассмотрим вариант для А = 4 - это минимальное кол-во вершин, с которого стоит запускать генерацию. Несмотря на то, что графы по условию непомеченные, но в коде к ним все равно нужно как-то обращаться, поэтому нумерация какая-то нужна, ну я буду нумеровать их натуральными от 1 до А.

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

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

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

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

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

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

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

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

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

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

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

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

====================================
еще есть вариант, типа, например для A = 10, рассмотреть матрицу смежностей - квадрат 10 на 10, вычеркнуть элементы гл.диагонали и рассмотреть нижнетреугольную матрицу, которую надо забить всеми возможными комбинациями 1 в кол-ве 12 штук]]> FasterHarder Алгоритмы https://forum.sources.ru/index.php?showtopic=460420&view=findpost&p=3921754 Sat, 03 May 2025 19:55:44 +0000 Поиск всех графов-заготовок для выращивания конечного графа https://forum.sources.ru/index.php?showtopic=460420&view=findpost&p=3921754 macomics, AVA12, вы, конечно же правы относительного того, что, степень соседей НЕ нужно увеличивать на +1 при удалении вершины, тут я прогнал дико, конечно). Ну тогда внешний бесконечный цикл нужен в псевдокоде, ок...

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

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

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

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

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

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

еще было интересно узнать, а являются ли эти обыкновенные графы Эйлеровыми, которые можно сжать - нет, т к паттерн "виселица" (самый правый) не имеет Эйлерового пути. Возможно, что это сильно помешает рекурсивному спуску/подъему (бэктрекинг) при генерации всех возможных обыкновенных графов для обработки...]]> FasterHarder Алгоритмы https://forum.sources.ru/index.php?showtopic=460420&view=findpost&p=3921752 Sat, 03 May 2025 18:18:12 +0000 Поиск всех графов-заготовок для выращивания конечного графа https://forum.sources.ru/index.php?showtopic=460420&view=findpost&p=3921752 FasterHarder, насчет запрета висячих вершин и того, что в сжатом графе степень вершин >= 3: это действительно часть условия или просто наблюдение? Если в исходном графе есть висячие вершины, то они могут остаться висячими в сжатом графе, и тогда алгоритм проверки заметно усложняется.]]> AVA12 Алгоритмы https://forum.sources.ru/index.php?showtopic=460420&view=findpost&p=3921751 Sat, 03 May 2025 18:11:52 +0000 Поиск всех графов-заготовок для выращивания конечного графа https://forum.sources.ru/index.php?showtopic=460420&view=findpost&p=3921751 плюс диагональный элемент >= 3, а для предварительной отбраковки сжатых кандидатов считать 2*E >= 3*V
=> 2*V + 2*B >= 3*V
=> 2*B >= V

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

Цитата

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

С чего вдруг? Сосед был связан с ныне удаленной вершиной, теперь связан с кем-то другим. Одна связь исчезла, другая появилась, ничего не поменялось.]]> AVA12 Алгоритмы https://forum.sources.ru/index.php?showtopic=460420&view=findpost&p=3921750 Sat, 03 May 2025 17:31:17 +0000 Поиск всех графов-заготовок для выращивания конечного графа https://forum.sources.ru/index.php?showtopic=460420&view=findpost&p=3921750 Цитата 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 и тд.]]> macomics Алгоритмы https://forum.sources.ru/index.php?showtopic=460420&view=findpost&p=3921749 Sat, 03 May 2025 17:23:21 +0000 Поиск всех графов-заготовок для выращивания конечного графа https://forum.sources.ru/index.php?showtopic=460420&view=findpost&p=3921749 из любого обыкновенного графа можно получить сжатый и он будет единственным. Это означает, что вершины обыкновенного графа можно просматривать в произвольном порядке, причем достаточно будет всего одного раза. При удалении вершины степень его соседей увеличивается на 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рех вершин. Получается так или нет?

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

Ядро алгоритма - генерация всех возможных обыкновенных графов до определенного предела с формированием коллекции сжатых графов.
об этом попозже напишу)]]> FasterHarder Алгоритмы https://forum.sources.ru/index.php?showtopic=460420&view=findpost&p=3921748 Sat, 03 May 2025 17:11:45 +0000 Поиск всех графов-заготовок для выращивания конечного графа https://forum.sources.ru/index.php?showtopic=460420&view=findpost&p=3921748
Лучше придумать способ упорядочивания всех корректных перестановок конкретной матрицы. Например, линеаризовать матрицу в список значений и для определения взаимного порядка двух перестановок сравнивать эти списки поэлементно. И для проверки генерировать только наибольшую (или наименьшую) из перестановок для каждого варианта.

По условию задачи для каждого 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 Алгоритмы https://forum.sources.ru/index.php?showtopic=460420&view=findpost&p=3921747 Sat, 03 May 2025 15:08:49 +0000 Поиск всех графов-заготовок для выращивания конечного графа https://forum.sources.ru/index.php?showtopic=460420&view=findpost&p=3921747 псевдографов ( допустимы петли и кратные ребра! ), пока без привязки к структурам данных. Вроде постановка четко локализована, но, после 5-10мин. гугления стало понятно, что это не оч.простая задача - на форумах много обсуждают, спорят и пр., даже приводят алгоритмы, где проще доказать НЕизоморфизм и т.п.

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

есть еще какие-то варианты, типа подключить хеширование и для каждого псевдографа получать некий хеш, т е иметь коллекцию хешей. И когда будет получен очередной сжатый граф, то просто проверить его хеш на совпадение хешей из коллекции...Тут вопрос: а какую ХФ можно использовать, которая гарантирует исключение коллизий?]]> FasterHarder Алгоритмы https://forum.sources.ru/index.php?showtopic=460420&view=findpost&p=3921746 Sat, 03 May 2025 14:28:32 +0000 Поиск всех графов-заготовок для выращивания конечного графа https://forum.sources.ru/index.php?showtopic=460420&view=findpost&p=3921746
Немного порисовал обыкновенные графы и получил их сжатие
________________________________________.png (, : 343)
в целом вроде понятно, как это все работает. Как понимаю, в программе при любом раскладе потребуется вот этот кусок алгоритма, который текущий обыкновенный граф стягивает

псевдокод

ПОКА (ИСТИНА)

флаг = ЛОЖЬ

перебрать все вершины от 1 до A

если степень текущий вершины = 2

удалить ее из графа

степень соседних вершин увеличить на +1

флаг = ИСТИНА

если флаг = ЛОЖЬ

выход из цикла, т к не осталось ни одной вершины со степенью = 2

КОНЕЦ ПОКА

то есть при стягивании графа идет привязка исключительно к степени вершины и проверки на 2. Надеюсь, что это правильный подход)]]> FasterHarder Алгоритмы https://forum.sources.ru/index.php?showtopic=460420&view=findpost&p=3921738 Fri, 02 May 2025 11:57:10 +0000 Поиск всех графов-заготовок для выращивания конечного графа https://forum.sources.ru/index.php?showtopic=460420&view=findpost&p=3921738
Добавлено 02.05.25, 12:00
С другой стороны. Математически можно задачу упростить до: разложить 2*(N+B) (N+B черных и N+B белых - белый + черный шар символизируют разные концы грани, но на цвет в задаче можно внимания не обращать т.к. допустимы петли) по N коробкам так, чтобы в каждой было не меньше 3-х шаров.]]> macomics Алгоритмы https://forum.sources.ru/index.php?showtopic=460420&view=findpost&p=3921737 Fri, 02 May 2025 11:25:05 +0000 Поиск всех графов-заготовок для выращивания конечного графа https://forum.sources.ru/index.php?showtopic=460420&view=findpost&p=3921737 macomics, считаю, что правильная мысль и она оч.похожа на ту, что я читал где-то на забугорном сайте, поняв на 1-2%. После твоих слов - понимание увеличилось)]]> FasterHarder Алгоритмы https://forum.sources.ru/index.php?showtopic=460420&view=findpost&p=3921736 Fri, 02 May 2025 11:18:29 +0000 Поиск всех графов-заготовок для выращивания конечного графа https://forum.sources.ru/index.php?showtopic=460420&view=findpost&p=3921736
Жуткий переборчик получится и явно не быстрый. Но это если в лоб решать.]]> macomics Алгоритмы https://forum.sources.ru/index.php?showtopic=460420&view=findpost&p=3921735 Fri, 02 May 2025 10:20:30 +0000 Поиск всех графов-заготовок для выращивания конечного графа https://forum.sources.ru/index.php?showtopic=460420&view=findpost&p=3921735 _______________________.png (, : 365)
тут полный перечень сжатых графов для класса графов вида ( A, A + 2 ), т е абсолютно ЛЮБОЙ обыкновенный граф вида ( A, A + 2 ) можно стянуть в один из тех, что на картинке...]]> FasterHarder Алгоритмы https://forum.sources.ru/index.php?showtopic=460420&view=findpost&p=3921734 Fri, 02 May 2025 10:10:55 +0000 Поиск всех графов-заготовок для выращивания конечного графа https://forum.sources.ru/index.php?showtopic=460420&view=findpost&p=3921734
Заданы обыкновенные графы вида { 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 Алгоритмы https://forum.sources.ru/index.php?showtopic=460420&view=findpost&p=3921577 Tue, 29 Apr 2025 04:30:00 +0000 Поиск всех графов-заготовок для выращивания конечного графа https://forum.sources.ru/index.php?showtopic=460420&view=findpost&p=3921577 Цитата FasterHarder @ 28.04.25, 23:28

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

Всё, мысль остановилась. Нет чёткого и однозначного задания - нет и обсуждения/решения. Рассматривать все 4 варианта - это перебор.]]> Akina Алгоритмы https://forum.sources.ru/index.php?showtopic=460420&view=findpost&p=3921575 Mon, 28 Apr 2025 23:28:30 +0000 Поиск всех графов-заготовок для выращивания конечного графа https://forum.sources.ru/index.php?showtopic=460420&view=findpost&p=3921575 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%]]> FasterHarder Алгоритмы https://forum.sources.ru/index.php?showtopic=460420&view=findpost&p=3921573 Mon, 28 Apr 2025 20:04:20 +0000 Поиск всех графов-заготовок для выращивания конечного графа https://forum.sources.ru/index.php?showtopic=460420&view=findpost&p=3921573
Но, судя по вашему примеру, его еще можно свернуть по примеру FasterHarder. Тогда будет граф с 2+3+4 или граф с 3+4+5. И вот тогда они станут двумя разными.

ADD: Какой количество вершин в графе предполагается? Может будет проще, если номера вершин будут заменены битовыми позициями? т.е. нумерация будет не 1,2,3,..,N. А 1,2,4,..,2^N.
Так можно будет проще сворачивать вершины графа.]]> macomics Алгоритмы https://forum.sources.ru/index.php?showtopic=460420&view=findpost&p=3921572 Mon, 28 Apr 2025 19:53:51 +0000 Поиск всех графов-заготовок для выращивания конечного графа https://forum.sources.ru/index.php?showtopic=460420&view=findpost&p=3921572 Цитата FasterHarder @ 28.04.25, 16:42

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

Вот исходный граф и два сжатых от него после удаления ОДНОЙ вершины.
84.png (, : 383)
Это один и тот же сжатый граф, или это разные сжатые графы?]]> Akina Алгоритмы https://forum.sources.ru/index.php?showtopic=460420&view=findpost&p=3921569 Mon, 28 Apr 2025 16:42:02 +0000 Поиск всех графов-заготовок для выращивания конечного графа https://forum.sources.ru/index.php?showtopic=460420&view=findpost&p=3921569 Цитата 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. Но в этом ни на йоту не уверен...

]]> FasterHarder Алгоритмы https://forum.sources.ru/index.php?showtopic=460420&view=findpost&p=3921568 Mon, 28 Apr 2025 16:37:56 +0000 Поиск всех графов-заготовок для выращивания конечного графа https://forum.sources.ru/index.php?showtopic=460420&view=findpost&p=3921568 Цитата FasterHarder @ 28.04.25, 15:46

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

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

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

Ну уже правильно замечено, что степень сжимаемой вершины всегда 2. Кроме того, вершины нумерованы, и, следовательно, различимы. То есть в итоге задача сводится к тривиальной генерации всех возможных сочетаний вершин степени 2.]]> Akina Алгоритмы https://forum.sources.ru/index.php?showtopic=460420&view=findpost&p=3921567 Mon, 28 Apr 2025 16:37:03 +0000 Поиск всех графов-заготовок для выращивания конечного графа https://forum.sources.ru/index.php?showtopic=460420&view=findpost&p=3921567 ___________________.png (, : 435)
он подчиняется всем требованиям: 5 вершин и 7 ребер

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

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

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

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

В итоге нужно просто перебрать все возможные варианты УДАЛЕНИЯ вершин со степенью = 2?? Тут возможно, что при переборе всех вариантов где-то будут возникать проблемы с изоморфностью сжатых графов, но это так, черная мысль...]]> FasterHarder Алгоритмы https://forum.sources.ru/index.php?showtopic=460420&view=findpost&p=3921565 Mon, 28 Apr 2025 15:46:52 +0000 Поиск всех графов-заготовок для выращивания конечного графа https://forum.sources.ru/index.php?showtopic=460420&view=findpost&p=3921565
Задан обыкновенный граф вида { 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 Алгоритмы