Аноним

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

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