Достижимость

Материал из WikiGrapp
Перейти к:навигация, поиск

Достижимость (Reachability) — бинарное отношение R на множестве вершин графа такое, что aRb тогда и только тогда, когда в графе существует путь из a в b. См. Достижимая вершина. От одной вершины к другой может быть несколько различных путей, кратчайший из них называется геодезической линией. Множество вершин, достижимых из данной вершины v, называется множеством достижимости вершины v. Орграф является односвязным, если в любой паре вершин по крайней мере одна из них является достижимой из другой.

Литература

  • Кристофидес Н. Теория графов. Алгоритмический подход. — М.: Мир, 1978.
  • Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.