Из графа получить граф-дерево, удалив заданное кол-во вершин

[FasterHarder]

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

Есть такая задача.
Задан граф, состоящий из k вершин. Известно, что этот заданный граф не является деревом. Затем с клавиатуры вводится натуральное число n – кол-во вершин ( не превосходящее k ). И нужно проверить, а можно ли из заданного графа получить дерево, удалив ровно n вершин вместе с инцидентными им ребрами.

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

Также, как я понимаю, граф может быть как ор так и неор – вроде непринципиально. Буду отталкиваться от неориентированных графов. Веса ребер роли не играют.
Вот парочка визуальных примеров графов-деревьев:

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

Видно, что степени вершин могут абсолютно различными: для висячих вершин степень = 1, но у остальных может быть и 2, и 3, и –цать. То есть в алгоритме, скорее всего, нельзя будет информацию о степенях как-то использовать.
Допустим задан такой граф ( и n = 1 ):

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

Проверил его на связность. Кстати, думаю, что через DFS ( хотя много примеров на BFS, а через DFS нельзя что ли? – да вроде можно ).
Дальше запускаю поиск цикла ( опять через DFS, наверное ). В итоге цикл найден.

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

И что мне это дает? Ну я буду знать, что я попал в вершину №2 из нее же, но не буду знать, какие вершины входят в сам цикл.
Допустим, каким-то образом узнал, что цикл образуют вершины 2 – 3 – 4 – 2. Надо что-то удалять. А что именно?? И вот тут начинаются колоссальные проблемы! Тут ведь неоднозначность. Можно удалить вершину 3 и инцидентные ей ребра или вершину №4:

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

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

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

Он содержит цикл. Чтобы избавиться от цикла – надо что-то дропать из него. С какой вершины начать? В данном случае удаление любой вершины кроме №2 приводит граф к дереву.

Еще такой момент, как я понял, результирующее граф-дерево должно получатся на последней итерации, когда удаляется последняя n-я по номеру вершина. Иначе, если граф-дерево получен раньше, то на оставшихся итерациях достаточно будет удалять только концевые вершины ( степень таких вершин = 1 ), т к их удаление не меняет тип графа ( он остается деревянным ), а лишь сокращается кол-во вершин в нем.

В итоге, к чему пришел ( приполз ), что нужно искать цикл и каким-то перебором пробовать удалять из него вершины, пока цикл не испарится. Кажется, что последовательность удаления вершин может быть очень важна, но здесь у меня понимания 0.0. Т к циклов может быть несколько + они могут быть взаимопроникающими, то вообще муть получается и непонятка...

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

И есть 2ой подход – тупо перебором. Например, задан граф, у него k = 20, а n = 6. И просто перебирать удаление последовательно вершин + проверка на связность и циклы после каждого удаления. По сути, это комбинаторика размещения из 20 по 6 ( вроде бы она ) и получается всего примерно 27 миллионов вариантов…

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

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

[Akina]

Односвязный ациклический ненаправленный граф всегда является деревом.

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

Сообщение отредактировано: Akina - 25.11.23, 18:52

[FasterHarder]

Цитата Akina @ 25.11.23, 18:48

выявляем все циклы

Все? вроде пишут, что это не совсем тривиально

Цитата Akina @ 25.11.23, 18:48

Если количество удалённых меньше заданного, удаляем недостающее количество листьев. Все. Ибо задание никоим образом не фиксирует номер шага, на котором граф становится деревом - это ты зачем-то сам придумал

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

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

вот рассмотрим такой граф:

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

он содержит 2 ( вроде 2 всего ) цикла: синий и зеленый

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

примечание: если запустить DFS из вершины №0, то будет такой массив предков:
// -1 0 1 2 3 4 5 3 7 8 - предок вершины
// 0 1 2 3 4 5 6 7 8 9 - номер вершины

итак, запускаем DFS( 0 ): 0 -> 1 -> 2 -> 3 -> 4 -> 5 и ломаная замыкается на 1, т е найден 1ый цикл. У меня была идея ( как мне показалась шикарной, но потом оказалось, что глуповатой)) ) такая, удалить сразу эту вершину, на которой замыкается цикл, т е вершину #5. Если это сделать, что граф становится несвязным, т к вершина #6 становится изолированной.
Akina, вот скажи, на этом этапе, как идентифицирован ПЕРВЫЙ цикл, можно применять какие-то действия по удалению?? Или нужно обязательно искать ВСЕ циклы?

и еще такой момент: чтобы пройтись по всем циклам, ведь вроде ДОСТАТОЧНО запустить DFS из ЛЮБОЙ вершины ОДИН раз и нет необходимости dfs-ить все вершины с самого начала?? Речь просто про циклы без какого-либо удаления чего-либо

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

Сообщение отредактировано: FasterHarder - 26.11.23, 00:35

[Akina]

Цитата FasterHarder @ 26.11.23, 00:31

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

?? как-то даже представить себе такое не могу. Пример есть?

Цитата FasterHarder @ 26.11.23, 00:31

Все? вроде пишут, что это не совсем тривиально

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

Сообщение отредактировано: Akina - 26.11.23, 07:05

[FasterHarder]

Цитата Akina @ 26.11.23, 07:01

?? как-то даже представить себе такое не могу. Пример есть?

ну вот что такое вроде ( но я не уверен )

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

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

Из этого можно вроде делать вывод, что нет гарантий, что удаление вершин надо начинать с цикловой. С другой стороны, если сначала дропнуть вершину #3 + еще есть вершины, которые можно удалить, то можно и #9 удалить. Но это приводит к огромному кол-ву вариаций, куча всяких проверок и пр. пр.

Цитата Akina @ 26.11.23, 07:01

Вероятно, имеется в виду, что выявление всех циклов избыточно?

это бы я хотел у тебя узнать) ( в посте #3 красным цветом выделил вопрос, примерно об этом )

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

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

Добавлено 26.11.23, 09:59
Вот еще ответ некого подобия ChatGPT:

Скрытый текст

ChatGPT
Для того чтобы из заданного графа получить дерево, необходимо удалить ровно n вершин с инцидентными им ребрами и при этом сохранить связность графа.

Проверяем, является ли заданный граф деревом. Для этого проверяем два условия:

a) Количество ребер в графе равно n-1, где n - количество вершин. Если это не так, то граф не является деревом и невозможно получить дерево, удалив ровно n вершин. b) Граф связный. Для этого можно использовать алгоритм поиска в глубину или поиск в ширину, чтобы проверить, что из любой вершины можно достичь все остальные вершины. Если граф не связный, то невозможно получить дерево, удалив ровно n вершин.

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

a) Найти все компоненты связности графа. Для этого можно использовать алгоритм поиска в глубину или поиск в ширину из каждой вершины, которая еще не входит в компоненту связности. b) После нахождения всех компонент связности, выбрать самую маленькую компоненту и удалить все вершины и инцидентные им ребра этой компоненты до того момента, пока не будут удалены n вершин. c) Если после удаления вершин из самой маленькой компоненты связности графа остались другие компоненты, то повторить шаги b) и c) для каждой оставшейся компоненты до тех пор, пока не будут удалены ровно n вершин. d) Если после выполнения шагов b) и c) все компоненты связности удалены и в графе остались только ребра, то полученное множество ребер является деревом.

Если после выполнения этих шагов в графе остались вершины или не удалось удалить ровно n вершин, то получить дерево из данного графа, удалив ровно n вершин, невозможно.

[Akina]

Цитата FasterHarder @ 26.11.23, 09:50

ну вот что такое вроде

А, блин, там же не рёбра, а вершины удалять надо!!!

[FasterHarder]

насчет того, что прописал чатЖПТ ( в целом он многое хорошо написал, но есть НО...)

Цитата chatGPT @ 26.11.23, 09:50

a) Найти все компоненты связности графа. Для этого можно использовать алгоритм поиска в глубину или поиск в ширину из каждой вершины, которая еще не входит в компоненту связности. b) После нахождения всех компонент связности, выбрать самую маленькую компоненту и удалить все вершины и инцидентные им ребра этой компоненты до того момента, пока не будут удалены n вершин. c) Если после удаления вершин из самой маленькой компоненты связности графа остались другие компоненты, то повторить шаги b) и c) для каждой оставшейся компоненты до тех пор, пока не будут удалены ровно n вершин. d) Если после выполнения шагов b) и c) все компоненты связности удалены и в графе остались только ребра, то полученное множество ребер является деревом.

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

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

в итоге решил БРУТ-форсом эту задачу
например, в графе 10 вершин и удаляется n = 3 вершины
тупо удаляю последовательно все возможные ТРОЙКИ: 1 2 3, 1 2 4, ..., 1 2 10, 2 3 4, 2 3 5, ..., 8, 9, 10 т е по формуле сочетаний без повторений, т к вроде комбинация вершин 1 2 3 и 2 3 1 вроде бы тождественна равные
после удаления каждой тройки проверяю:
1. количество ребер = количество вершин - 1
2. 1 компонента связности ( через DFS )

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

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

[Akina]

Цитата FasterHarder @ 26.11.23, 22:16

тупо удаляю последовательно все возможные ТРОЙКИ

Если брутфорсить - то имеет смысл ограничиться (на первом этапе) только теми узлами, которые входят в хотя бы один из циклов (если циклов меньше, чем окончательно надо удалить вершин - то удалять столько вершин, сколько в графе циклов). И, если вариант удаления превратил граф в дерево, а удалено недостаточное количество вершин, то добирать до заданного удалением листьев.

[FasterHarder]

Цитата Akina @ 27.11.23, 04:56

Если брутфорсить - то имеет смысл ограничиться (на первом этапе) только теми узлами, которые входят в хотя бы один из циклов (если циклов меньше, чем окончательно надо удалить вершин - то удалять столько вершин, сколько в графе циклов). И, если вариант удаления превратил граф в дерево, а удалено недостаточное количество вершин, то добирать до заданного удалением листьев.

ок, это интересная мысль
в целом спс за обсуждение

[Majestio]

Чуйка мне подсказывает вот какой подход:

1) Временно отойти от анализа вершин графа, а сформировать вектор множеств вершин, образующих петли
2) Сформировать набор правил, которые будут определять, что делать дальше при анализе пересечения i-го и j-го множеств из ранее сформированного вектора
3) По сформированным правилам осуществлять анализ путём поиска в ширину/глубину по вкусу

Естественно, формируя правила, нужно стараться предусмотреть разные варианты топологии графа. Просто надеяться побыстрее удалить вершину, общую для двух петель - не всегда будет комильфо.
Вот пример, когда вершину (4) удалять нельзя, т.к. граф "разорвется":

   (1)
  /   \
 (2)  (3)
  \   /
   (4)
  /   \
 (5)  (6)
  \   /
   (7)

А вот так удалить (4) прокатит:

    (1)
   /   \
 (2)   (3)
  |     |
 (4) - (5)
  |     |
 (6)   (7)
   \   /
    (8)

Ну, в общем - это чисто намёк на идею. Ибо во многих ЯП операции с множествами имеют хорошую поддержку. Хотя, я HZ, может я наоборот предлагаю вам тупиковую идею Решайте сами.