Достижимость: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
 
Строка 1: Строка 1:
'''Достижимость''' (''[[Reachability]]'') - бинарное отношение <math>R</math> на множестве [[вершина|вершин]] [[граф|графа]] такое, что <math>aRb</math> тогда и только тогда, когда в графе существует [[путь]] из <math>a</math> в <math>b</math>. См. ''[[Достижимая вершина]]''. От одной вершины к другой может быть несколько различных путей, [[кратчайший путь|кратчайший]] из них называется ''[[геодезическая линия|геодезической линией]]''. Множество вершин, достижимых из данной вершины <math>v</math>, называется множеством достижимости вершины <math>v</math>. [[Орграф]] является ''[[односвязный орграф|односвязным]]'', если в любой паре вершин по крайней мере одна из них является достижимой из другой.
'''Достижимость''' (''[[Reachability]]'') бинарное отношение <math>R</math> на множестве [[вершина|вершин]] [[граф|графа]] такое, что <math>aRb</math> тогда и только тогда, когда в графе существует [[путь]] из <math>a</math> в <math>b</math>. См. ''[[Достижимая вершина]]''. От одной вершины к другой может быть несколько различных путей, [[кратчайший путь|кратчайший]] из них называется ''[[геодезическая линия|геодезической линией]]''. Множество вершин, достижимых из данной вершины <math>v</math>, называется множеством достижимости вершины <math>v</math>. [[Орграф]] является ''[[односвязный орграф|односвязным]]'', если в любой паре вершин по крайней мере одна из них является достижимой из другой.
==Литература==
==Литература==
[Лекции],  
* Кристофидес Н. Теория графов. Алгоритмический подход. — М.: Мир, 1978.


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

Текущая версия от 16:21, 7 февраля 2011

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

Литература

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