А




Абсолют корневого дерева(Absolute of a rooted tree)
- некорневое дерево с теми же вершинами и ребрами, что и исходное корневое.
Литература:[Харари-Палмер]

Абсолютная медиана(Absolute median)
- точка на ребре (не обязательно совпадающая с вершиной графа) графа G = (V,E), на которой достигается минимум функции

[Formula-1]
где [xi][_j] - вес вершины v[_j], d(y,v) - расстояние между вершинами y и v.

Литература:[Кристофидес]

Абсолютный внешний радиус(Absolute outer radius)
- число

[Formula-2]
где [xi](v) - вес вершины v, d(v,y) - расстояние между вершинами v и y.
Литература:[Кристофидес]

Абсолютный внешний центр(Absolute outcentre)
- точка на дуге (не обязательно совпадающая с вершиной), на которой достигается минимум величины

[Formula-3]
где [xi](v) - вес вершины v, d(v,y) - расстояние между вершинами v и y.
Литература:[Кристофидес]

Абсолютный внутренний радиус(Absolute inner radius)
- число

[Formula-4]
где [xi](v) - вес вершины v, d(v,y) - расстояние между вершинами v и y.
Литература:[Кристофидес]

Абсолютный внутренний центр(Absolute incentre)
- точка на дуге (не обязательно совпадающая с вершиной), на которой достигается минимум величины

[Formula-5]
где [xi](v) - вес вершины v, d(v,y) - расстояние между вершинами v и y.
Литература:[Кристофидес]

Абсолютный гиперграф(Absolute hypergraph)
- гиперграф, для любых двух вершин u и v которого существует ребро e = (u,v).
Литература:[Лекции]

Абсолютный центр - см. Абсолютный внешний центр, Абсолютный внутренний центр.

Абстрактный граф(Abstract graph)
- класс изоморфных графов.
Другое название - непомеченный граф.
Литература:[Лекции]

АВЛ-дерево(AVL-tree)
- бинарное дерево, для любой вершины которого разность высот левого и правого поддеревьев не превышает единицы. Название дано в честь Г.М.Адельсона-Вельского и Е.М.Ландиса, которые ввели в рассмотрение этот тип деревьев (1962). Другое название - балансированные по высоте деревья.
Литература:[Кнут], [Евстигнеев], [Евстигнеев-Касьянов]

Автоматная грамматика - см. Порождающая грамматика.

Автоморфизм графа(Automorphism of a graph)
- произвольная подстановка [phi] на множестве вершин графа, сохраняющая отношение смежности; т.е. [phi] такова, что образы [phi](u) и [phi](v) вершин u и v смежны тогда и только тогда, когда смежны сами вершины u и v. Иными словами, автоморфизм графа - это изоморфизм графа на себя. См. Группа автоморфизмов графа.
Литература:[Харари], [Лекции]

А-граф - см. Иерархия вложенных альтов.

Алгоритм(Algorithm)
- точное предписание, которое задает вычислительный процесс (называемый в этом случае алгоритмическим), начинающийся с произвольного исходного данного (из некоторой совокупности возможных для данного А. исходных данных и направленный на получение полностью определяемым этим исходным данным результата (Математическая энциклопедия, т.1. С.202). Алгоритмический процесс есть процесс последовательного преобразования конструктивных объектов, проходящий дискретными шагами; каждый шаг состоит в смене одного конструктивного объекта другим. Алгоритмы характеризуются вычислительной сложностью и емкостной сложностью. По виду используемой вычислительной модели алгоритмы делятся на последовательные (или детерминированные), параллельные (или недетерминированные), распределенные и пр. Подробнее об алгоритмах см. Математическая энциклопедия, статьи Алгоритм, Алгоритм локальный, Алгоритма сложность, Алгоритмическая проблема, Алгоритмическая сводимость, Алгоритмов теория и др., а также литературу, указанную в конце каждой статьи. Алгоритмы на графах представляют собой частный случай общего понятия алгоритма; исходными данными для них служат абстрактные или помеченные графы. В процессе работы алгоритма могут создаваться новые графы или может изменяться система меток. Результатом работы алгоритма может быть граф, помеченный граф или конструктивный объект иной природы (число, слово или строка символов и т.д.).
Литература:[Успенский-Семенов], [Ахо-Хопкрофт-Ульман], [Евстигнеев-Касьянов], [Касьянов], [Рейнгольд-Нивергельт-Део]}

Алгоритм венгерский - см. Венгерский алгоритм.

Алгоритм Дейкстры(E.Dijkstra)
- алгоритм отыскания кратчайшего пути (цепи) во взвешенном орграфе (графе) без контуров (циклов) отрицательной длины с трудоемкостью [Ou](|V|[^2]), предложенный Э.Дейкстрой в 1959 г.
Литература:[Ахо-Хопкрофт-Ульман], [Кристофидес]

Алгоритм жадный - см. Жадный алгоритм.

Алгоритм Кнута-Бендикса(D.Knuth, P.Bendix)
- алгоритм построения полной системы переписывания термов.
Литература:[Евстигнеев-Касьянов]

Алгоритм Краскала(J.B.Kruskal)
- 1. Алгоритм построения каркаса графа путем последовательного удаления в соответствии с некоторой упорядоченностью ребер графа без нарушения связности получаемой части графа. 2. Алгоритм построения каркаса наименьшего веса описанным выше методом, но с предварительным упорядочением ребер в порядке неубывания весов. На основе А.К. созданы многочисленные модификации.
Литература:[Кристофидес], [Евстигнеев-Касьянов]

Алгоритм Патерсона-Вегмана(M.S.Paterson, M.N.Wegman)
- алгоритм построения наибольшего общего унификатора двух термов, представленных бесконтурными графами (дэгами), за линейное относительно суммарного числа вершин и дуг графа время.
Литература:[Евстигнеев-Касьянов]

Алгоритм Прима(R.C.Prim)
- алгоритм нахождения каркаса наименьшего веса графа путем наращивания поддерева (фрагмента каркаса) за счет присоединения граничного ребра (т.е. ребра, только один конец которого принадлежит фрагменту каркаса) с наименьшим весом. На основе А.П. созданы многочисленные модификации.
Литература:[Кристофидес], [Евстигнеев-Касьянов]

Алгоритм Робертса-Флореса(S.M.Roberts, B.Flores)
- алгоритм построения гамильтонова цикла, использующий технику поиска с возвратом.
Литература:[Кристофидес]

Алгоритм Уоршалла(S.Warshall)
- матричный алгоритм построения транзитивного замыкания орграфа.
Литература:[Ахо-Хопкрофт-Ульман], [Евстигнеев]

Алгоритм Уэ(G.Huet)
- алгоритм построения наибольшего общего унификатора двух термов, представленных бесконтурными графами (дэгами), за линейное относительно суммарного числа вершин и дуг графа время.
Литература:[Евстигнеев-Касьянов]

Алгоритм Флери(Fleury)
- алгоритм построения эйлерова цикла.
Литература:[Кристофидес]

Алгоритм Флойда(R.W.Floyd)
- матричный алгоритм определения кратчайших расстояний между всеми парами вершин в графе.
Литература:[Ахо-Хопкрофт-Ульман]

Алгоритм Хакими(S.L.Hakimi)
- алгоритм нахождения абсолютных центров в графе.
Литература:[Кристофидес]

Алгоритм Хопкрофта-Карпа(J.Hopcroft, R.M.Karp)
- алгоритм построения наибольшего паросочетания в двудольном графе.
Литература:[Липский]

Алфавит(Alphabet)
- непустое конечное множество символов, элементы которого называются буквами или знаками алфавита. См. также Язык, порожденный грамматикой.
Литература:[Касьянов], [Касьянов-Поттосин]

Альт(Alt)
- фрагмент управляющего графа с единственной начальной вершиной, т.е. выделенной вершиной, которая либо совпадает с входом управляющего графа, либо имеет заходящую дугу с началом вне данного фрагмента. См. также Гамак, Интервал, Иерархия вложенных альтов.
Литература:[Евстигнеев-Касьянов], [Касьянов], [Касьянов-Поттосин]

Альт внешний - см. Иерархия вложенных альтов.

Альт внутренний - см. Иерархия вложенных альтов.

Альт непосредственно вложенный - см. Иерархия вложенных альтов.

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

Антибаза(Contrabasis)
- такое минимально возможное множество [B^~] вершин орграфа G, что из любой вершины G достижима некоторая вершина в [B^~]. См. База орграфа.
Литература:[Кристофидес]

Антисимметрический граф(Anti-symmetric graph)
- орграф, для которого выполнено следующее условие: если дуга (v[_i],v[_j]) принадлежит орграфу, то в нем нет противоположно ориентированной дуги (v[_j],v[_i]). Очевидно, что в А.г. нет петель.
Литература:[Берж]

А-представление - см. Иерархия вложенных альтов.

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

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

Асимметрический граф(Asymmetric graph)
- граф, группа автоморфизмов которого состоит из одного тождественного автоморфизма.
Литература:[Харари]

Ассоциативный поиск(Associative search, keyed access method)
- поиск по ключу элемента в информационном множестве.
Литература:[Касьянов-Поттосин]

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

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

Ациклическая раскраска(Acyclic coloring)
- правильная раскраска вершин графа, при которой ни один двуцветный подграф не содержит циклов.
Литература:[Toft]

Ациклический граф(Acyclic graph, DAG)
- для неориентированных графов то же самое, что лес для ориентированных графов то же самое, что бесконтурный орграф. Иногда используется термин "дэг".
Литература:[Харари], [Лекции]

Ациклическое хроматическое число(Acyclic chromatic number)
- наименьшее число цветов, при котором возможна ациклическая раскраска графа.
Литература:[Toft]