Лучший способ проверить полную достижимость

У меня есть набор узлов, каждый из которых подключен как минимум к одному другому узлу. Я хотел бы знать, таковы ли соединения, что каждый узел доступен из любого другого. Например:

1--2
   |
3--4

Против:

1--2

3--4

Я убежден, что такое тестирование достижимости можно спроецировать с точки зрения проблемы с точным покрытием, однако Никак не могу сообразить, как это сделать. Есть ли у кого-нибудь указатели, документация, веб-сайты и т. д. о том, как это сделать? Примеры были бы чрезвычайно ценны.

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


projection graph-theory language-agnostic reachability
person fbrereto    schedule 12.12.2009    source источник
comment
Я не понимаю. Проверка связности графа является полиномиальной. Почему вы хотите свести ее к NP-полной задаче о точном покрытии?   -  person Pascal Cuoq    schedule 12.12.2009
comment
@Pascal - это даже линейно в E   -  person Yuval Adam    schedule 12.12.2009
comment
@Андреас Андреас нет, они ненаправлены.   -  person fbrereto    schedule 12.12.2009

Ответы (2)


arrow_upward
3
arrow_downward

  • начать с любого узла и выполнить обход в глубину/ширину
  • подсчитайте количество посещенных узлов (конечно, не посещайте ни один узел дважды!)
  • сравнить подсчитанное число с общим числом
person akuhn    schedule 12.12.2009
comment
+1 Но я думаю, что этот алгоритм требует, чтобы граф был неориентированным? - person Andreas Brinck; 12.12.2009
comment
Должно быть прямо преобразовано направленный граф в неориентированный, если это то, что вам нужно. - person akuhn; 12.12.2009

arrow_upward
0
arrow_downward

Существует также быстрый (но довольно сложный) алгоритм для динамического поддержания связности (т. е. при вставке/удалении ребер), показанный в этой статье: Полилогарифмические детерминированные полностью динамические алгоритмы для связности, минимального остовного дерева, 2-х ребер и двусвязности

Основная идея заключается в поддержке связующего дерева. Простыми случаями являются вставка ребра и удаление ребра неостовного дерева. Проблема при удалении ребра связующего дерева, потому что теперь нет гарантированной связности — приходится эффективно искать альтернативный маршрут для соединения разорванных частей, иначе граф разъединяется.

person Dimitris Andreou    schedule 12.01.2010