Д

Двоичный n-мерный куб(Binary n-dimensional cube)
- граф, вершины которого соответствуют бинарным последовательностям длины n и две вершины которого соединены ребром, если соответствующие последовательности отличаются в точности в одной позиции.
Литература: [Липский]

Двойное вращение - см. Вращение двойное.

Двойственный гиперграф - (Dual hypergraph)
- для данного гиперграфа H = (V,E) без изолированных вершин Д.г. есть гиперграф H[^*] = (V[^*],E[^*]), в котором V[^*] = E, а E[^*] - семейство всех множеств E(v), где v [include] V и E(v) есть множество всех инцидентных v ребер.
Литература: [Лекции]

Двойственный граф(Dual graph)
- для данного плоского графа (геометрически) двойственный граф есть снова плоский граф, вершины которого суть грани исходного графа и две вершины смежны, если соответствующие грани имеют общее ребро. (Абстрактно) двойственный граф - это граф, у которого подмножество ребер образует простой цикл тогда и только тогда, когда соответствующее ему (при некоторой биекции) подмножество ребер исходного графа образует простой разрез и наоборот. Справедливо утверждение: граф, геометрически двойственный к плоскому графу, является абстрактно двойственным к нему.
Литература: [Лекции]

Двудольный граф(Bipartite graph)
- граф, у которого существует такое разбиение множества вершин на две части (доли), что концы каждого ребра принадлежат разным долям. Если при этом любые две вершины, входящие в разные доли, смежны, то граф называется полным двудольным. См. также Веер, Звезда,
Литература: [Лекции]

Двудольный матроид(Bipartite matroid)
- матроид, все циклы которого имеют четную длину.
Литература: [Свами-Тхуласираман]

Двумерная целочисленная решетка - то же, что и Граф решетки.

Двусторонне бесконечный маршрут(Two-way infinite sequence)
- цепь (необязательно простая) в бесконечном графе, не имеющая ни начальной, ни конечной вершины.
Литература: [Оре]

Двуцветный подграф(Bicoloured subgraph)
- подграф правильно раскрашенного графа, порожденный вершинами, окрашенными в два заданных цвета.
Литература: [Харари]

Двусторонний граф - то же, что и Двудольный граф.

Декартова сумма графов(Cartesian sum of graphs)
- граф [sigma] = H[_1] [oplus] H[_2] [oplus] ... [oplus] H[_k], множество вершин которого есть декартово произведение множеств вершин графов H[_i] и в [sigma] существует ребро (v,w), где v = (v[_1], ... , v[_k]) и w = (w[_1], ... , w[_k]), тогда и только тогда, когда хотя бы в одном графе H[_i] найдется ребро (v[_i], w[_i]).
Литература: [Оре]

Декартово произведение графов(Cartesian product of graphs)
- граф [pi] = H[_1] [times] H[_2] [times] ... [times] H[_k], множество вершин которого есть декартово произведение множеств вершин графов H[_i] и в [pi] существует ребро (v,w), где v = (v[_1], ... , v[_k]) и w = (w[_1], ... , w[_k]), тогда и только тогда, когда существует семейство ребер

E[_1] = (v[_1], w[_1]),..., E[_k] = (v[_k], w[_k]), E[_i] [subset] H[_i].

Литература: [Оре]

Дерево(Tree)
- связный граф без циклов.
Литература: [Лекции], [Евстигнеев-Касьянов]

Дерево m-арное(m-ary tree)
- ордерево, каждая вершина которого имеет не менее m/2 и не более m потомков.
Другое название - сильно ветвящееся дерево.
Литература: [Евстигнеев], [Евстигнеев-Касьянов]

Дерево асимметричное - см. ?????Асимметричное дерево.

Дерево балансированное по весу то же, что и BB-дерево.

Дерево балансированное по высоте то же, что и АВЛ-дерево.

Дерево бесконечное см. ?????Бесконечное дерево.

Дерево бинарное см. Бинарное дерево.

Дерево бинарное сортировки см. Бинарное дерево сортировки.

Дерево бицентральное см. Бицентральное дерево.

Дерево блоков и точек сочленения то же, что и Граф блоков и точек сочленения.

Дерево братскоесм. Братское дерево.

Дерево 1-2-братскоесм. 1-2-братское дерево.

Дерево братствато же, что и Братское дерево.

Дерево входящеесм. Входящее дерево.

Дерево вывода(Derivation tree)
- графическое представление класса всех эквивалентных выводов заданной цепочки в контекстно-свободной грамматике в виде дерева, висячие вершины которого помечены терминалами и символом e.
Другое название - дерево разбора.
Литература: [Касьянов-Поттосин], [Евстигнеев-Касьянов]

Дерево выровненноесм. Выровненное дерево.

Дерево вырожденное(Degenerate tree)
- дерево с одной вершиной. Другие названия - тривиальное дерево, пустое дерево.
Литература: [Евстигнеев-Касьянов]

Дерево выходящеесм. Выходящее дерево.

Дерево глубинное остовное - см. Глубинное остовное дерево.

Дерево гомеоморфно несводимое - см. Гомеоморфно несводимое дерево.

Дерево двоичное - то же, что и Бинарное дерево.

Дерево двоичного-поиска - то же, что и Бинарное дерево сортировки.

Дерево доминаторов(Dominator tree)
- корневое ордерево, вершины которого суть вершины исходного графа и в котором дуга (v,w) существует в том и только том случае, когда v есть непосредственный предшественник (доминатор) вершины w.
Литература: [Свами-Тхуласираман], [Ахо-Хопкрофт-Ульман]

Дерево конечное - см. Конечное дерево.

Дерево корневое - см. Корневое дерево.

Дерево левосторонее - см. Левостороннее дерево.

Дерево линейное - см. Линейное дерево.

Дерево максимальное - то же, что и Каркас.

Дерево левых выводов(Left-derivation tree)
- дерево, определяемое для контекстно-свободной грамматики следующим образом: корню дерева сопоставлена цепочка, состоящая из единственного начального символа; если цепочка [alpha] сопоставлена некоторой вершине p дерева, то для каждой цепочки [beta], получаемой левой подстановкой из [alpha], заводится вершина дерева и объявляется преемником вершины p.
Литература: [Касьянов-Поттосин], [Евстигнеев-Касьянов]

Дерево ориентированное - см. Ориентированное дерево.

Дерево остовное - то же, что и Каркас.

Дерево позиций(Position tree)
- для цепочки [alpha] в алфавите I такое I-дерево, что в нем ровно k листьев, помеченных числами 1,2,...,k, где k - длина цепочки [alpha], и для любого i последовательность реберных меток, расположенных на пути из корня в лист с меткой I, является кратчайшей цепочкой, идентифицирующей позицию i в [alpha].
Литература: [Ахо-Хопкрофт-Ульман]

Дерево поиска в глубину(Depth-first search tree)
- оркаркас графа, образуемый в результате поиска в глубину.
Другое название - глубинное остовное дерево.
Литература: [Ахо-Хопкрофт-Ульман]

Дерево поиска в ширину(Width-first search tree)
- оркаркас графа, образуемый в результате поиска в ширину.
Литература: [Свами-Тхуласираман]

Дерево поисковое - см. Поисковое дерево.

Дерево плоское - см. Плоское дерево.

Дерево r-плотное - см. r-плотное дерево.

Дерево пустое - то же, что и Дерево вырожденное.

Дерево разбора - см. Дерево вывода.

Дерево растущее - см. Выходящее дерево.

Дерево редукций(Reduction tree)
- дерево, определяемое для заданных цепочки [alpha] и контекстно-свободной грамматики следующим образом: корню дерева соответствует цепочка [alpha]; если некоторой вершине p сопоставлена цепочка [beta], то для каждой возможной редукции [beta] заводится новая вершина - преемник вершины p, которой и ставится в соответствие цепочка, получаемая в результате этой редукции.
Литература: [Касьянов-Поттосин], [Евстигнеев-Касьянов]

Дерево свободное - см. Свободное дерево.

Дерево сильно ветвящееся - то же, что и Дерево m-арное.

Сильно плотные деревья - см. Сильно плотное дерево.

Дерево слабо плотное - см. Слабо плотное дерево.

Дерево сливаемое - см. Сливаемое дерево.

Дерево сортировки(Sorting tree)
- дерево для организации хранения информации в виде слов, для которых определен лексикографический порядок; слова хранятся во всех вершинах или только в висячих (см. выровненное дерево), причем размещение слов производится по специальным правилам, учитывающим отношение порядка. Деревья сортировки имеют то или иное строение, обеспечивающее логарифмическую трудоемкость поиска; для поддержания этой структуры используются специальные преобразования. См. Балансированное по весу дерево, Балансированное по высоте дерево, АВЛ-дерево, бинарное дерево сортировки, многомерное дерево сортировки, B-дерево, H-дерево, HB-дерево, HS-дерево, 2-3-дерево.
Литература: [Евстигнеев], [Евстигнеев-Касьянов]

Дерево сортировки многомерное - см. Многомерное дерево сортировки.

Дерево соседства(Neighbourhood tree)
- бинарное выровненное дерево, у которого каждая вершина с единственным потомком имеет правого соседа с двумя потомками.
Другое название - H-дерево.
Литература: [Евстигнеев], [Евстигнеев-Касьянов]

Дерево стягивающее - то же, что и Каркас.

Дерево тривиальное - то же, что и Дерево вырожденное.

Дерево упорядоченное - см. Упорядоченное дерево.

Дерево Фиббоначи(Fibonaсci tree)
- бинарное дерево, определяемое следующим образом: пустое дерево есть дерево Фиббоначи F[_0], вырожденное дерево есть дерево Фиббоначи F[_1], дерево Фиббоначи F[_i] есть корневое дерево, у которого левое поддерево корня - дерево F[_i-2], а правое - дерево F[_i-1].
Литература: [Евстигнеев], [Евстигнеев-Касьянов]

Дерево Хусими(Husimi tree)
- граф, в котором каждый блок представляет собой простой цикл.
Литература: [Оре]

Дерево Штейнера(Steiner tree)
- частичный связный граф в виде дерева минимального веса, множество вершин которого содержит выделенное множество вершин исходного графа. Нахождение дерева Штейнера составляет проблему Штейнера на графах; какие-либо эффективные алгоритмы, решающие ее, неизвестны. См. Задача Штейнера на графах, Евклидова задача Штейнера.
Литература: [Лекции], [Кристофидес]

B-дерево(B-tree)
- B-дерево порядка m есть m-арное выровненное дерево, у которого каждая вершина (страница) содержит не более m и не менее m/2 слов, корень имеет не менее 2 потомков, каждая страница либо представляет собой висячую вершину, либо имеет k+1 потомков, где k - число слов на этой странице. B-дерево представляет собой структуру данных для двухуровневой памяти.
Литература: [Кнут], [Евстигнеев], [Евстигнеев-Касьянов]

B-дерево многомерное - см. Многомерное B-дерево.

B-дерево сильное - см. Сильное B-дерево.

B-дерево симметричное бинарное - см. Симметричное бинарное дерево.

B-дерево слабое - см. Слабое B-дерево.

BB-дерево(BB-tree)
- дерево T[_n] = (T[_l], r, T[_r]) с корнем r называется BB-деревом с балансом [alpha], 0 [leq] [alpha] [leq] 1/2, если:
а) для корневого баланса [rho](T[_n]) выполняется условие [alpha] [leq] [rho](T[_n]) [leq] 1-[alpha];
б) T[_l] и T[_r] - BB-деревья с балансом [alpha].
Другое название - балансированное по весу дерево.
Литература: [Рейнгольд-Нивергельт-Део], [Евстигнеев-Касьянов]

H-дерево - то же, что и Дерево соседства.

HB-дерево - то же, что и Братское дерево.

HS-дерево(HS-tree)
- бинарное выровненное дерево, у которого каждый единственный потомок любой вершины либо сам является листом, либо сам имеет двух потомков. Класс HS-деревьев является расширением класса HB-деревьев.
Литература: [Евстигнеев], [Евстигнеев-Касьянов]

I-дерево(I-tree)
- для некоторого алфавита I такое дерево T, ребра которого помечены символами из I, что попарно различны метки ребер, выходящих из любой его вершины.
Литература: [Ахо-Хопкрофт-Ульман]

k-дерево малой высоты(k-tree with small height)
- бинарное выровненное дерево, у которого вершина с одним потомком имеет по крайней мере одного правого соседа и первые k правых соседей (или все правые соседи, если их число меньше k) этой вершины имеют двух потомков. 1-дерево малой высоты есть в точности H-дерево. Имеет место следующее утверждение: для любого [epsil] > 0 существует такое k, что класс k-деревьев малой высоты есть класс выровненных бинарных деревьев высоты h [leq] (1 + [epsil]) log n + 1, где n - число листьев.
Литература: [Евстигнеев], [Евстигнеев-Касьянов]

kB-дерево(kB-tree)
- обобщение B-дерева для хранения многомерных данных. См. также Многомерное B-дерево.
Литература: [Евстигнеев-Касьянов]

k-d-дерево(k-d-tree)
- обобщение бинарного дерева сортировки, ориентированное на многомерные данные.
Литература: [Евстигнеев-Касьянов]

1-дерево(1-tree)
- связный граф, содержащий в точности один цикл.
Литература: [Лекции]

2-3-дерево(2-3-tree)
- выровненное дерево, каждая вершина которого имеет двух или трех потомков. Информация в таких деревьях хранится в листьях, а остальные вершины содержат вспомогательную информацию для организации поиска.
Литература: [Ахо-Хопкрофт-Ульман], [Евстигнеев-Касьянов]

Дефицит двудольного графа(Deficiency of a bipartite graph)
- для двудольного графа G = (X,Y,E) наибольшая из величин [delta](A) = |A| - |N(A)|, где A - произвольное подмножество X, а N(A) - подмножество вершин из Y, смежных с вершинами из A. Говорят, что множество A является множеством без дефицита, если никакое его подмножество не имеет положительного дефицита. Понятие дефицита используется при доказательстве теорем о паросочетаниях для двудольных графов.
Литература: [Лекции], [Оре]

Диагональ блока(Diagonal of a block)
- ребро, соединяющее две вершины цикла и не принадлежащее циклу.
Литература: [Харари]

Диаграмма конечно-автоматная - см. Конечно-автоматная диаграмма.

Диаграмма синтаксическая - см. Синтаксическая диаграмма.

Диаграмма Хассе(Hasse diagram)
- графическое представление частично упорядоченного множества (чу-множества) P = (X, [leq]), в котором каждой точке из X сопоставляется точка плоскости таким образом, что меньшая точка всегда располагается ниже большей точки. Две точки x и y в Д.Х. соединены тогда и только тогда, когда x [leq] y и не существует такой точки z, что x [leq] z [leq] y.
Литература: [Харари], [Берж]

Диаметр(Diameter)
- наибольшее расстояние между вершинами графа.
Литература: [Лекции]

Дизъюнктное объединение графов(Disjunct union of graphs)
- объединение графов с непересекающимися множествами вершин.
Литература: [Лекции]

Дисперсия графа(Variance of a graph)
- величина, равная минимуму по всем вершинам v суммы

[Formula-7]
где n - число вершин в графе. См. также центр тяжести графа.
Литература: [Оре]

Длина дуги(Length of an arc)
- вес дуги, рассматриваемый как расстояние между вершинами.
Литература: [Кристофидес]

Длина контура(Length of a cycle)
- (в невзвешенном орграфе) число дуг в контуре; (во взвешенном орграфе) сумма длин дуг. См. также вес контура.
Литература: [Кристофидес]

Длина пути - то же, что и Длина контура.

Длина ребра - см. Длина дуги.

Длина цепи(Length of a chain)
- (в невзвешенном графе) число ребер в цепи; (во взвешенном графе) сумма длин ребер. См. также Вес цепи.
Литература: [Кристофидес]

Добавление ребра(Edge adding)
- операция над графами, состоящая в соединении ребром e двух несмежных вершин графа G, порождая граф G + e.
Литература: [Лекции]

k-дольный граф(k-partite graph)
- граф, у которого существует такое разбиение множества вершин на k долей, что концы каждого ребра принадлежат разным долям. Если при этом любые две вершины, входящие в разные доли, смежны, то граф называется полным k-дольным и обозначается K[_n1_nk].
Литература: [Лекции]

Доминатор - то же, что и Обязательный предшественник.

Доминаторное дерево - то же, что и Дерево доминаторов.

Доминирующая вершина(Dominating vertex)
- вершина графа, смежная с каждой другой его вершиной.
Литература: [Лекции]

Доминирующее множество - то же, что и Внешне устойчивое множество.

Доминирующее число - то же, что и Число внешней устойчивости.

Дополнение графа(Complementary graph)
- граф [G^~], имеющий то же множество вершин, что и G, но в котором две несовпадающие вершины смежны тогда и только тогда, когда они не смежны в G.
Литература: [Лекции]

Дополнительный граф - то же, что и Дополнение графа.

Достижимая вершина(Reachable vertex)
- вершина w достижима из вершины v, если в орграфе существует путь из v в w.
Литература: [Лекции]

Достижимое множество(Reaching set)
- множество вершин, достижимое из заданной вершины. См. Достижимость, Контрадостижимое множество, Матрица достижимости.
Литература: [Кристофидес]

Достижимость(Reachability)
- бинарное отношение R на множестве вершин графа такое, что aRb тогда и только тогда, когда в графе существует путь из a в b. См. Достижимая вершина.
Литература: [Лекции], [Кристофидес]

Древесная дуга(Tree arc)
- дуга, принадлежащая дереву поиска в глубину.
Литература: [Евстигнеев], [Евстигнеев-Касьянов], [Касьянов]

Древесность - то же, что и Ориентированное дерево.

Древесность графа(Arboricity of a graph)
- наименьшее число непересекающихся по ребрам остовных лесов, на которые можно разложить граф.
Литература: [Харари]

Древесность линейная графаlinear arboricity of a graph
- наименьшее число непересекающихся по ребрам остовных лесов с максимальной степенью не более двух, на которые можно разложить граф.
Литература: [Харари]

Дуга(Arc)
- фундаментальное понятие теории графов; определяется как упорядоченная пара (v,w) вершин, графически изображается отрезком непрерывной кривой со стрелкой, направленной от вершины v - начала дуги к вершине w - концу дуги.
Литература: [Лекции]

Дуга вперед(Forward arc)
- дуга аранжируемого графа, которая является F-прямой дугой для любой его аранжировки F.
Литература: [Касьянов], [Евстигнеев-Касьянов]

Дуга древесная - см. Древесная дуга.

Дуга назад(Backward arc)
- дуга аранжируемого графа, которая является F-обратной дугой для любой его аранжировки F.
Литература: [Евстигнеев-Касьянов], [Касьянов]

Дуга обратная - см. Обратная дуга.

Дуга поперечная - см. Поперечная дуга.

Дуга прямая - см. Прямая дуга.

F-дуга - то же, что и F-прямая дуга.

Дэг(DAG)
- аббревиатура от directed acyclic graph.
Литература: [Евстигнеев-Касьянов]