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

Компьютерный форум 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 | Цитировать


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

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

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


Отправлено: 03:43, 11-12-2001 | #11



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

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


Студент


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

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


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

Спасибо

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


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


редкий гость


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

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


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

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

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


Отправлено: 14:22, 11-12-2001 | #13


Студент


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

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


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

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

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


Отправлено: 19:29, 11-12-2001 | #14


редкий гость


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

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


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

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


Отправлено: 23:19, 11-12-2001 | #15


Студент


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

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


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

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


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



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

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




 
Переход