Имя пользователя:
Пароль:  
Помощь | Регистрация | Забыли пароль?  | Правила  

Компьютерный форум OSzone.net » Программирование, базы данных и автоматизация действий » Программирование и базы данных » Графы

Ответить
Настройки темы
Графы

Студент


Сообщения: 445
Благодарности: 8

Профиль | Отправить PM | Цитировать


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

-------
*Origin: Lots of people talking, few of them - no... (2:5020/****.**)


Отправлено: 12:56, 09-12-2001

 

редкий гость


Сообщения: 1696
Благодарности: 44

Профиль | Сайт | Отправить PM | Цитировать


Цитирую свою любимую книжку по алгоритмам( "Алгоритмы: построение и анализ" ) :
Цитата:
Пусть G = (V,E) -- связный неориентированный граф. Точка раздела ( articulation point ) графа G -- это вершина, при удалении которой граф G перестаёт быть связанным. Мост ( bridge ) -- это ребро с аналогичным свойством. Двусвязная компонента ( biconnected component ) -- это максимальный набор рёбр, любые два ребра которого принадлежат общему простому циклу( см. картинку ). Точки раздела, мосты и двусвязные компоненты можно найти с помощью поиска в глубину.
Так как у меня нет сканнера я нарисовал картинку в Paint`е -- http://ivank.hut.ru/pictures/biconnected_component.gif.

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

-------
http://ivank.ru


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



Для отключения данного рекламного блока вам необходимо зарегистрироваться или войти с учетной записью социальной сети.

Если же вы забыли свой пароль на форуме, то воспользуйтесь данной ссылкой для восстановления пароля.


Студент


Сообщения: 445
Благодарности: 8

Профиль | Отправить PM | Цитировать


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

-------
*Origin: Lots of people talking, few of them - no... (2:5020/****.**)


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


редкий гость


Сообщения: 1696
Благодарности: 44

Профиль | Сайт | Отправить PM | Цитировать


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

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

-------
http://ivank.ru


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


Студент


Сообщения: 445
Благодарности: 8

Профиль | Отправить PM | Цитировать


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

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

-------
*Origin: Lots of people talking, few of them - no... (2:5020/****.**)


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


редкий гость


Сообщения: 1696
Благодарности: 44

Профиль | Сайт | Отправить PM | Цитировать


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

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

Псевдокод на C++( паскаля не знаю ), надеюсь поймёшь что там написано.
Код: Выделить весь код
Код, который здесь был не верен.
И по сему злобно удолён.
Завтра постараюсь проверить работает или нет


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

-------
http://ivank.ru


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


редкий гость


Сообщения: 1696
Благодарности: 44

Профиль | Сайт | Отправить PM | Цитировать


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

-------
http://ivank.ru


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


Студент


Сообщения: 445
Благодарности: 8

Профиль | Отправить PM | Цитировать


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

-------
*Origin: Lots of people talking, few of them - no... (2:5020/****.**)


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


редкий гость


Сообщения: 1696
Благодарности: 44

Профиль | Сайт | Отправить PM | Цитировать


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

-------
http://ivank.ru


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


Студент


Сообщения: 445
Благодарности: 8

Профиль | Отправить PM | Цитировать


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

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

-------
*Origin: Lots of people talking, few of them - no... (2:5020/****.**)


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



Компьютерный форум OSzone.net » Программирование, базы данных и автоматизация действий » Программирование и базы данных » Графы

Участник сейчас на форуме Участник сейчас на форуме Участник вне форума Участник вне форума Автор темы Автор темы Шапка темы Сообщение прикреплено




 
Переход