вершиной следующей. Простой
вершиной следующей.
Простой путь - это путь, в котором каждая дуга используется не более одного раза.
Элементарный путь - это путь, в котором каждая вершина используется не более одного раза.
Если существует путь из вершины графа v в вершину u, то говорят, что u достижима из v. Матрицу достижимостей R определим следующим образом:
R[v,u]=
Множество R(v) - это множество таких вершин графа G, каждая из которых может быть достигнута из вершины v. Обозначим через Г(v) множество таких вершин графа G, которые достижимы из v с использованием путей длины 1. Г2(v) - это Г(Г(v)), то есть с использованием путей длины 2 и так далее. В этом случае:
R(v)={v}?Г(v)?Г2(v)?...?Гp(v).
При этом p - некоторое конечное значение, возможно, достаточно большое.
Пример(для рисунка). R(1)={1}?{2,5}?{1,6}?{2,5,4}?{1,6,7}={1,2,4,5,6,7}
Выполняя эти действия для каждой вершины графа, мы получаем матрицу достижимостей R.
procedure Reach; {формирование матрицы R, глобальной переменной}
{исходные
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
