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

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


Строка 7: Строка 7:


==Литература==
==Литература==
[Евстигнеев/85],  
* Евстигнеев В.А. Применение теории графов в программировании. — М.: Наука, 1985.
* Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994.


[Евстигнеев-Касьянов/94],  
* Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988.
 
[Касьянов/88],  
* Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.
 
[Лекции]

Навигация