LINUX.ORG.RU

найти точки деления графа

 


1

1

Не знаю, как точно сказать, но надо найти точки деления на графе. Т.е. такие узлы, которые делят граф на несвязанные подграфы. Вот пример графа, где хочется найти точкой деления узел, выделенный жирным: https://pasteboard.co/Hv23hxM.png (Граф рисовал примерный, реальные графы будут на сотни тысяч узлов)

Собственно, прошу подсказать - в какую сторону копать? Если подграфы представляют собой деревья, то я понимаю как быть (начинать с узлов и двигаться «вверх»). А тут мысль останавливается.

Добавлю, что решение достаточно найти «примерно». Т.е. достаточно будет найти не все «точки деления», а только некоторые, но за приемлемое время.


Если подграфы представляют собой деревья, то я понимаю как быть (начинать с узлов и двигаться «вверх»). А тут мысль останавливается.

Мысль вслух: сперва найти все циклы, и идти вверх отталкиваясь от соседних с ними вершин, по аналогии с деревьями?

vladimir-vg ★★ ()
Ответ на: комментарий от jcdr

Правильно ли я понимаю, что надо искать на графе мосты (https://en.wikipedia.org/wiki/Bridge_(graph_theory))?

Не похоже. Тебя же интересуют вершины, а не рёбра.

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

Т.е. достаточно будет найти не все «точки деления», а только некоторые, но за приемлемое время.

Ещё ссылочка по теме: https://en.wikipedia.org/wiki/K-vertex-connected_graph

Crocodoom ★★★★ ()
Ответ на: комментарий от anonymous

Т.е. те которые не участвуют в циклах.

anonymous ()
Ответ на: комментарий от Crocodoom

Не похоже. Тебя же интересуют вершины, а не рёбра.

Его интересует вершина из которой исходит как минимум один мост.

slovazap ★★★★★ ()
Ответ на: комментарий от anonymous

Ну, как бы решение я нашел сам (выше была ссылка на мосты). Но все равно спасибо анониму за участие

jcdr ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.