Глубинное остовное дерево

Материал из WEGA
Версия от 15:57, 6 октября 2009; Glk (обсуждение | вклад) (Создана новая страница размером '''Глубинное остовное дерево''' (''Depth-first spanning tree'') - '''1.''' Ор-каркас в виде раст...)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

Глубинное остовное дерево (Depth-first spanning tree) - 1. Ор-каркас в виде растущего ордерева, образованный древесными дугами при реализации поиска в глубину в орграфе; корень ордерева совпадает с началом поиска в глубину. Все множество дуг орграфа разбивается относительно его Г.о.д. на четыре класса: древесные --- дуги, принадлежащие дереву; обратные --- дуги, ведущие от потомков к предкам (возможно, от вершин в себя); прямые --- дуги, идущие от предков к потомкам, но не являющиеся древесными; поперечные --- дуги, соединяющие вершины, которые не являются ни предками, ни потомками относительно друг друга. 2. Каркас, построенный поиском в глубину в неориентированном графе.

Литература

[Евстигнеев/85],

[Евстигнеев-Касьянов/94],

[Касьянов/88],

[Лекции]