LINUX.ORG.RU

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

 


1

1

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

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

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



Последнее исправление: jcdr (всего исправлений: 1)

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

Читал. Вы на что-то конкретно намекаете?

jcdr
() автор топика

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

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

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
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.