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