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