Графы

ivank · Отправлено: **16:07, 09-12-2001** | #2

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

Цитата:

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

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

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

noname00.pas · Отправлено: **17:19, 09-12-2001** | #3

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

ivank · Отправлено: **00:42, 10-12-2001** | #4

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

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

noname00.pas · Отправлено: **01:16, 10-12-2001** | #5

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

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

ivank · Отправлено: **01:50, 10-12-2001** | #6

noname00.pas

Цитата:

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

Нет.

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

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

Код:

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

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

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

ivank · Отправлено: **01:52, 10-12-2001** | #7

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

noname00.pas · Отправлено: **18:27, 10-12-2001** | #8

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

ivank · Отправлено: **23:53, 10-12-2001** | #9

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

noname00.pas · Отправлено: **01:40, 11-12-2001** | #10

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

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