Лес обхода: различия между версиями
Перейти к навигации
Перейти к поиску
KEV (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Лес обхода''' (''[[Search forest]]'') | '''Лес обхода''' (''[[Search forest]]'') — | ||
для данного ''[[обход графа|обхода]] <math>H</math>'' графа <math>G = (X,U)</math> такая его часть <math>(X,Z)</math>, | для данного ''[[обход графа|обхода]] <math>\,H</math>'' графа <math>\,G = (X,U)</math> такая его часть <math>\,(X,Z)</math>, | ||
что <math>Z</math> содержит каждое такое [[ребро]] <math>u \in U</math>, что среди [[вершина|вершин]], | что <math>\,Z</math> содержит каждое такое [[ребро]] <math>u \in U</math>, что среди [[вершина|вершин]], | ||
расположенных в <math>H</math> между вершинами <math>p = H(i)</math> и <math>q = H(j)</math>, где <math>i | расположенных в <math>\,H</math> между вершинами <math>\,p = H(i)</math> и <math>\,q = H(j)</math>, где <math>\,i | ||
\leq j</math> и <math>u = (p,q)</math>, нет вершин, соединенных ребром с вершиной | \leq j</math> и <math>\,u = (p,q)</math>, нет вершин, соединенных ребром с вершиной | ||
<math>H(j)</math>. | <math>\,H(j)</math>. | ||
==Литература== | ==Литература== | ||
* Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994. | |||
Текущая версия от 13:14, 29 апреля 2011
Лес обхода (Search forest) — для данного обхода [math]\displaystyle{ \,H }[/math] графа [math]\displaystyle{ \,G = (X,U) }[/math] такая его часть [math]\displaystyle{ \,(X,Z) }[/math], что [math]\displaystyle{ \,Z }[/math] содержит каждое такое ребро [math]\displaystyle{ u \in U }[/math], что среди вершин, расположенных в [math]\displaystyle{ \,H }[/math] между вершинами [math]\displaystyle{ \,p = H(i) }[/math] и [math]\displaystyle{ \,q = H(j) }[/math], где [math]\displaystyle{ \,i \leq j }[/math] и [math]\displaystyle{ \,u = (p,q) }[/math], нет вершин, соединенных ребром с вершиной [math]\displaystyle{ \,H(j) }[/math].
Литература
- Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994.