Глава 2. ДОСТИЖИМОСТЬ И СВЯЗНОСТЬ

1. Введение

В предыдущей главе отмечалось, что систему связи любой организации можно интерпретировать как граф, в котором люди представлены вершинами, а каналы связи дугами. Естественно при рассмотрении такой системы поставить вопрос, может ли информация от одного лица быть передана другому лицу существует ли путь, идущий от вершины к вершине . Если такой путь существует, то говорят, что вершина достижима из Можно интересоваться достижимостью вершины из вершины только на таких путях, длины которых не превосходят заданной величины. Целью этой главы является обсуждение некоторых фундаментальных понятий, касающихся достижимости и свойств связности графов, а также введение ряда весьма важных алгоритмов.

На языке графов, представляющих организации, в настоящей главе рассматриваются следующие вопросы:

(i) Каково наименьшее число сотрудников, для которых каждый другой сотрудник в этой организации может быть достижим?

(ii) Каково наибольшее число сотрудников, которые взаимно достижимы?

(iii) Как между собой связаны вопросы (i) и (ii)?