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

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


[Кристофидес]
[Кристофидес]

Навигация