5. Задачи, связанные с ограниченной достижимостью
В предыдущем разделе при определении базы мы исходили из неограниченных достижимых множеств. Если рассматривать ограниченную достижимость, т. е. использовать пути ограниченной длины (как упоминалось ранее в разд. 2), и определять, ограниченную базу, опираясь на ограниченную достижимость, то возникают осложнения двух типов.
(а) Понятия сильной компоненты и конденсации, которые упрощают решение задачи определения баз в случае неограниченной достижимости, теперь использоваться не могут. Распространение этих понятий на случай ограниченной достижимости не дает существенного упрощения задачи.
В случае когда достижимость ограничена путями единичной длины (просто дугами), ограниченные базы называют минимальными доминирующими множествами. Мы подробно рассматриваем их в гл. 3. В случае когда достижимость ограничена, скажем, 
дугами, граф 
может быть определен как граф, множество вершин которого то же самое, что и у графа 
а дуга 
существует в 
тогда и только тогда, когда в 
найдется путь между вершинами 
длины, не больше чем 
(см. соотношение 2.1). Ограниченная матрица достижимостей графа 
соответствует тогда матрице смежности графа 
граф 
может быть назван ограниченным транзитивным замыканием графа 
(в соответствии с определением транзитивного замыкания, приведенным в разд. 2). Задача определения ограниченных баз графа 
эквивалентна задаче нахождения минимальных доминирующих множеств графа G.
(б) В неограниченном случае различные базы имеют одно и то же число элементов; оно равно числу таких вершин в конденсации графа, которые имеют нулевые полустепени захода. В
ограниченном случае, однако, разные базы могут иметь различное число элементов, и тогда возникает, в частности, задача нахождения базы с наименьшим числом элементов. Еще один подход: если не наложено ограничение на достижимость, то можно искать такую ограниченную базу, которая содержит, например, ровно 
вершин и, кроме того, из вершин этой базы все остальные вершины графа 
могут быть достигнуты с минимально возможной ограниченностью достижимости. Эти задачи тесно связаны с задачей нахождения 
-центра и более детально рассматриваются в гл. 4.
6. Задачи
(см. скан)
