Глубинное остовное дерево: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
Строка 2: Строка 2:
на четыре класса: [[древесная дуга|''древесные'' --- дуги]], принадлежащие [[дерево|дереву]]; [[обратная дуга|''обратные'' --- дуги]], ведущие от [[потомок вершины|потомков]] к [[предок вершины|предкам]] (возможно, от вершин в себя); [[прямая дуга|''прямые'' --- дуги]], идущие от предков к потомкам, но не являющиеся древесными; [[поперечная дугая|''поперечные'' --- дуги]], соединяющие вершины, которые не являются ни предками, ни потомками относительно друг друга.
на четыре класса: [[древесная дуга|''древесные'' --- дуги]], принадлежащие [[дерево|дереву]]; [[обратная дуга|''обратные'' --- дуги]], ведущие от [[потомок вершины|потомков]] к [[предок вершины|предкам]] (возможно, от вершин в себя); [[прямая дуга|''прямые'' --- дуги]], идущие от предков к потомкам, но не являющиеся древесными; [[поперечная дугая|''поперечные'' --- дуги]], соединяющие вершины, которые не являются ни предками, ни потомками относительно друг друга.
'''2.''' [[Каркас]], построенный поиском в глубину в неориентированном [[граф|графе]].
'''2.''' [[Каркас]], построенный поиском в глубину в неориентированном [[граф|графе]].
[[Файл:Depth-first spanning tree.png|950px]]
==Литература==
==Литература==
[Евстигнеев/85],  
[Евстигнеев/85],  

Версия от 16:14, 8 октября 2009

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

Depth-first spanning tree.png

Литература

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

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

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

[Лекции]