Достижимость: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Создана новая страница размером '''Достижимость''' (''Reachability'') - бинарное отношение <math>R</math> на множестве верши...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 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>. Орграф является ''односвязным'', | |||
если в любой паре вершин по крайней мере одна из них | |||
является достижимой из другой. | |||
==Литература== | ==Литература== | ||
[Лекции], | [Лекции], | ||
[Кристофидес] | [Кристофидес] | ||
Версия от 16:30, 15 октября 2009
Достижимость (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]. Орграф является односвязным, если в любой паре вершин по крайней мере одна из них является достижимой из другой.
Литература
[Лекции],
[Кристофидес]