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

[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мин. гугления стало понятно, что это не оч.простая задача - на форумах много обсуждают, спорят и пр., даже приводят алгоритмы, где проще доказать НЕизоморфизм и т.п.

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

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

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