Аннотация. Рассматривается распределенная сеть, в основе которой лежит сильно связный ориентированный нумерованный корневой граф без кратных ребер и петель, в котором дуги, исходящие из вершины, перенумерованы от 1 до полустепени исхода вершины. Ставится задача обеспечения передачи сообщений из каждой вершины в каждую по кратчайшим путям. Для этого предлагается построить в каждой вершине a графа отображение, которое каждой вершине с номером b ставит в соответствие номер дуги, с которой начинается кратчайший путь из a в b. Такое отображение полезно для решения многих задач, в частности, задачи самонастройки программно-конфигурируемой сети. Сетевой коммутатор (switch) хранит в программно-настраиваемых таблицах отображение адреса целевого хоста в номер выходного порта. Время передачи пакетов минимально, если в отображении использованы кратчайшие пути.  Другая задача – симуляция распределенных алгоритмов, разработанных для сетей с неориентированным графом связей, на классе сетей с ориентированным графом связей. Здесь приходится решать проблему отката (backtracking problem): вместо передачи сообщения из конца дуги a®b в ее начало сообщение передается по ориентированному пути b®...®a. Предполагается, что алгоритм построения отображения должен начинаться и заканчиваться в корне графа. Предлагаются два алгоритма построения отображения: «быстрый» алгоритм с оценками T=O(n) и N=O(n) и «экономный» алгоритм с оценками T=O(n2) и N=O(1), где T – время (в тактах) работы алгоритма, N – число сообщений, одновременно передаваемых по дуге, n – число вершин графа. Доказано, что эти оценки являются нижними оценками на классе алгоритмов, которые правильно работают на классе всех рассматриваемых графов.

Ключевые слова: ориентированный граф; корневой граф; нумерованный граф; распределенные алгоритмы; задачи на графах; кратчайшие пути.