Графы

[noname00.pas]

Кто-нибудь может мне поведать, что такое компоненты двусвязности, как их выделять, и как выделять компоненты рёберной двусвязности? В моей книжке это прокомментировано слишком коротко. "Описанное разбиение графа может быть осуществлено с помощью обхода вглубину, аналогично поиску обычных компонент двусвязности графа [Липский 88, п. 2.6]."

[ivank]

Цитирую свою любимую книжку по алгоритмам( "Алгоритмы: построение и анализ" ) :

Пусть G = (V,E) -- связный неориентированный граф. Точка раздела ( articulation point ) графа G -- это вершина, при удалении которой граф G перестаёт быть связанным. Мост ( bridge ) -- это ребро с аналогичным свойством. Двусвязная компонента ( biconnected component ) -- это максимальный набор рёбр, любые два ребра которого принадлежат общему простому циклу( см. картинку ). Точки раздела, мосты и двусвязные компоненты можно найти с помощью поиска в глубину.

Так как у меня нет сканнера я нарисовал картинку в Paint`е -- http://ivank.hut.ru/pictures/biconnected_component.gif.

Точки раздела и мосты изображены тёмно серым. Двусвязные компоненты -- наборы рёбер в пределах одной серой области ( внутри которой указан номер двусвязной компоненты ).

[noname00.pas]

ivank
Допустим с определениями ясно, а как насчёт алгоритмов? Как же именно обходом в глубину ищутся такие компоненты двусвязности?

[ivank]

noname00.pas
Честно говоря, не знаю -- в книге нет, сам никогда этим не интересовался. Поэксперементирую на досуге. О результатах доложу.

(Отредактировал(а) ivank - 21:43 - 9 Дек., 2001)

[noname00.pas]

ivank
А-а-а... Ну-ну -:)

У тебя Липский есть?

[ivank]

noname00.pas
У тебя Липский есть?
Нет.

Зато я кажись нашёл как можно находить двусвязные компоненты:

Псевдокод на C++( паскаля не знаю ), надеюсь поймёшь что там написано.

Код, который здесь был не верен.
И по сему злобно удолён.


Завтра постараюсь проверить работает или нет


(Отредактировал(а) ivank - 0:37 - 11 Дек., 2001)

[ivank]

Забыл сказать: вызывать надо find_biconnected_components.

[noname00.pas]

ivank
Спасибо, разберусь когда время будет...

[ivank]

noname00.pas
Не. Там есть ошибка. Сейчас работаю над её устранением...

[noname00.pas]

ivank
Так... А вот теперь я зашёл в тупик. Чем отличается двусвязность от рёберной двусвязности? Компонента двусвязности - максимальный набор рёбер, такой, что любые два входят в простой цикл. Компонента рёберной двусвязности - максимальный набор вершин и рёбер, причем не содержащий ни одного моста. Если есть какой-то набор рёбер, удовлетворяющий первому определению, то понятно, что мостов в нём быть не может. С другой стороны понятно, что если в каком-то наборе нет мостов, то между любыми двумя вершинами есть по крайней мере два пути, а значит по двум рёбрам одной компоненты ребёрной двусвязности можно провести простой цикл. А в чём тогда разница между двусвязностью и рёберной двусвязностью? Или дело всё в том, что компоненты рёберной двусвязности вотличии от компоненты двусвязности содержат ещё и вершины? Но ведь любому ребру из компоненты двусвязности можно взаимооднозначно сопоставить набор рёбер... А зачем тогда два различных понятия?

Или я что-то напутал?

[ivank]

noname00.pas
По моему, ты прав, т.е. это одно и тоже.

Кстати, откуда эти определения? Из одной книги, или из разных?

[noname00.pas]

ivank
Ну вот... Значит всё не так плохо, как я думал, т.к. у меня в принципе есть решение этой задачи (в которой компоненты рёберной двусвязности надо искать). :)

Спасибо

[ivank]

noname00.pas
Не за что :D

А ты мог бы то свое решение сюда запостить? Интересно...

[noname00.pas]

ivank
Только это не моё решение, это решение авторов книги... И оно уже есть в и-нете.
http://www.informatics.ru/variousdocs/onzi/archiv/z3_2.zip

Я вот склоняюсь к мысли, что при данных ограничениях пройдёт простая проверка для каждого ребра, не приводит ли его удаление к увеличению компонент связности. Сложность - O(N*M). Или может это и имелось ввиду под обходом в глубину?

[ivank]

noname00.pas
Каких ограничениях?

[noname00.pas]

ivank
Не более 100 вершин.