В


Валентность вершины - то же, что и степень вершины.

Веер - то же, что и звездный граф.

Вектор-каркас(Spanning tree's vector)
- вектор длины m (где m - число ребер в графе), i-я координата которого равна 1 или 0, если ребро e[_i] входит или не входит в данный каркас T соответственно.
Литература:[Евстигнеев-Касьянов]

Вектор-коцикл(Cocycle vector)
- (для неориентированных графов) 0-1-вектор [w^] длины m (где m - число ребер в графе), i-я координата которого равна 1 или 0, если ребро e[_i] входит или не входит в данный коцикл, соответственно; (для ориентированных графов) вектор [wvect], где m - число дуг в орграфе и w[^i] равна 0, если дуга e[_i] не принадлежит коциклу, равна 1, если e[_i] принадлежит коциклу и ее ориентация совпадает с направлением коцикла, и равна -1 в противном случае.
Литература:[Berge]

Вектор-цикл(Cycle vector)
- вектор

[c0vect]
m-мерного пространства R[^m], где m - число ребер в графе, сопоставляемый циклу [mu] по следующему правилу: придадим каждому ребру графа произвольную ориентацию и положим c[^k]=r[_k]-s[_k], если цикл [mu] проходит через ребро e[_k] r[_k] раз в направлении его ориентации и s[_k] в противоположном направлении.
Литература:[Берж]

Величина потока(Value of a flow)
- сумма дуговых потоков на дугах, исходящих из входа сети. Равна сумме дуговых потоков на дугах, заходящих в выход сети.
Литература:[Берж], [Кристофидес]

Величина разреза(Value of a cut)
- сумма пропускных способностей дуг разреза. Другое название - пропускная способность разреза.
Литература:[Берж], [Кристофидес]

Величина рассечения - см. Рассечение.

Венгерский алгоритм(Hungarian method)
- алгоритм решения задачи о максимальном паросочетании для двудольных графов и задачи о назначениях как частного случая ее.
Литература:[Берж], [Кристофидес]

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

Вершина бинарная - см. Бинарная вершина.

Вершина висячая - см. Висячая вершина.

Вершина внутренняя - см. Внутренняя вершина.

Вершина входная - см. Входная вершина.

Вершина выходная - см. Выходная вершина.

Вершина гиперграфа - см. Гиперграф.

Вершина голая(Naked vertex, isolated vertex)
- изолированная вершина без петель.
Литература:[Зыков,а]

Вершина граничная - см. Граничная вершина.

Вершина дефицитная - см. ??? Дефицитная вершина.

Вершина доминирующая - см. Доминирующая вершина.

Вершина, достижимая из a(Reachible from a vertex)
- вершина в орграфе, для которой существует путь из a в нее.
Литература:[Оре]

Вершина изолированная(Isolated vertex)
- вершина (возможно с петлями), но без инцидентных ей дуг или ребер. В случае графа без петель вершина степени 0.
Литература:[Зыков], [Харари]

Вершина, инцидентная ребру(Vertex incident to an edge)
- одна из концевых вершин ребра.
Литература:[Берж]

Вершина конечная - см. Конечная вершина.

Вершина концевая(Terminal vertex)
- одна из вершин a и b, соединенных ребром e = (a,b); для орграфа вершина b дуги e = (a,b); иногда концевые вершины ребра определяются с помощью инцидентора. В [Харари] - то же, что и висячая.
Литература:[Берж], [Зыков,а]

Вершина критическая(Critical vertex)
- вершина, удаление которой уменьшает некоторую числовую характеристику графа, например число вершинного покрытия, хроматическое число.
Литература:[Харари]

Вершина начальная - см. Начальная вершина.

Вершина неподвижная(Immovable vertex)
- вершина, не являющаяся подобной никакой другой вершине; другими словами, вершина неподвижна, если любой автоморфизм оставляет ее на месте.
Литература:[Харари]

Вершина, непосредственно предшествующая b - см. Непосредственный обязательный предшественник.

Вершина, непосредственно следующая за a - см. Непосредственный обязательный преемник.

Вершина обратно дефицитная - см. ??? Обратно дефицитная вершина.

Вершина орграфа - см. Вершина.

Вершина переменная - см. Переменная вершина.

Вершина периферийная(Periphery vertex)
- вершина, эксцентриситет которой равен диаметру графа.
Литература:[Лекции]

Вершина разделяющая - то же, что и точка сочленения.

Вершина разрезающая - см. Разрезающая вершина.

Вершина свободная(Noncoved vertex, unsaturated vertex)
- вершина, не принадлежащая ни одному ребру паросочетания.
Литература:[Липский]

Вершина стартовая - см. Стартовая вершина.

Вершина финишная - см. ??? Финишная вершина.

Вершина функциональная - см. Функциональная вершина.

Вершина центральная(Central vertex)
- вершина, эксцентриситет которой равен радиусу графа; множество центральных вершин образует центр графа. См. Бицентр, Центр.
Литература:[Харари], [Лекции]

Вершина центроидная(Centroidal vertex)
- вершина дерева, имеющая наибольший вес, вычисляемый как сумма ребер всех поддеревьев с корнем в данной вершине. См.также Ветвь к вершине v .
Литература:[Харари]

Вершинная база - то же, что и база.

Вершинная группа графа - см. Группа автоморфизмов графа.

Вершинная связность(Vertex connectivity)
- наибольшее k, для которого граф k-вершинно связен.
Литература:[Оре]

Вершинно-критический граф(Vertex critical graph.)
- граф, в котором каждая вершина критическая.
Литература:[Харари]

Вершинно непересекающиеся графы (подграфы)(Vertex disjoint graphs(subgraphs))
- графы (подграфы), не имеющие общих вершин.
Литература:[Лекции]

Вершинно-порожденный подграф - см. Подграф.

Вершинно-реберное инцидентное паросочетание(Vertex-edge incidence matching)
- взаимно однозначное отображение множества вершин графа в множество его ребер v [rarr] e[_v], для которого v и e[_v] инцидентны.
Литература:[Оре]

k-вершинно-связный граф(k-vertex connected graph)
- граф, ???вершинная связность которого равна k.
Литература:[Лекции]

Вершинно-симметрический граф(Vertex symmetrical graph)
- граф, у которого любая пара вершин подобна, т.е. вершины из этой пары переводятся друг в друга автоморфизмом.
Литература:[Харари], [Оре]

Вершинного покрытия число - см. Число вершинного покрытия.

Вершинное покрытие(Vertex covering, transversal set)
- множество вершин, покрывающее все ребра графа; другими словами, множество вершин такое, что любое ребро инцидентно хотя бы одной вершине этого множества.
Литература:[Берж], [Харари]

Вершинное число независимости(Stability number)
- наибольшая мощность множества независимых вершин в графе.
Литература:[Берж], [Харари]

Вершинное ядро(Vertex kernel)
- подграф, порожденный объединением всех независимых множеств графа, мощность которых равна числу реберного покрытия графа. Граф содержит В.я. тогда и только тогда, когда он имеет реберное ядро.
Литература:[Харари]

Вершины бисвязные - см. Бисвязные вершины.

Вершины взаимосвязанные - то же, что и бисвязные вершины.

Вершины независимые - см. Независимые вершины.

Вершины несравнимые - см. Несравнимые вершины.

Вершины подобные - см. Подобные вершины.

Вершины ориентированно-циклически-реберно связанные - см. Ориентированно-циклически-реберно связанные вершины.

Вершины связанные - см. Связанные вершины.

Вершины сильно связанные - то же, что и Бисвязные вершины.

Вершины сильно циклически связанные - см. Сильно циклически связанные вершины.

Вершины смежные - см. Смежные вершины.

Вершины соцветные - см. Соцветные вершины.

Вершины сравнимые - см. Сравнимые вершины.

Вершины циклически-реберно связанные - см. Циклически-реберно связанные вершины.

Вес вершины(Weight of a vertex)
- число, приписанное вершине; действия, производимые над ними, зависят от конкретной интерпретации, но чаще всего предполагается, что веса вершин образуют какую-нибудь алгебраическую структуру (например, решетку или полурешетку). См. также Метка вершины.
Литература:[Лекции]

Вес дуги(Weight of an arc)
- число, приписанное дуге и играющее, например, роль длины дуги. В общем случае смысл веса должен оговариваться особо. См. для сравнения Пропускная способность дуги.
Литература:[Лекции]

Вес контура(Weight of a cycle)
- функция от весов дуг (реже вершин) контура; чаще всего это - сумма весов дуг контура. См. Вес цепи.
Литература:[Лекции]

Вес подграфа(Weight of a subgraph)
- числовая функция от множества весов ребер (дуг) подграфа; чаще всего - сумма весов ребер.
Литература:[Лекции]

Вес пути(Weight of a path)
- функция, определенная на множестве дуг пути; чаще всего это - сумма весов дуг пути.
Другое название - длина пути.
Литература:[Лекции]

Вес ребра - то же, что и Вес дуги.

Вес цепи(Weight of a chain)
- 1. В неориентированном графе функция, определенная на множестве ребер цепи; чаще всего это - сумма весов ребер. 2. В орграфе алгебраическая сумма весов дуг цепи, вычисляемая по правилу: вес дуги берется со знаком +, если дуга проходится в направлении ее ориентации, и со знаком - в противном случае.
Литература:[Лекции]

Вес цикла - см. Вес цепи.

Ветвь к вершине v(Branch of a tree relative to a vertex v)
- в дереве максимальное поддерево, содержащее v в качестве висячей вершины; таким образом, число ветвей к v равно ее степени.
Литература:[Харари]

Взаимно простые пути(Simply related paths)
- пути из a в b, не имеющие общих вершин, отличных от a и b.
Литература:[Оре]

Взаимно связный граф - см. Сильно связный орграф.

Взаимные паросочетания(Mutual matchings)
- в двудольном графе G = (V [u] V',E) паросочетания из V в V' и из V' в V.
Литература:[Оре]

Взвешенное корневое дерево - см. Взвешенный граф.

Взвешенный граф(Weighted graph)
- граф (орграф), ребрам (дугам) которого приписаны веса. Иногда изображается в виде пары (G,w), где w - весовая функция, определенная на множестве ребер графа.
Литература:[Лекции]

Взвешенный массив - см. Информационный массив.

Висячая вершина(Terminal(pendant) vertex)
- 1. В неориентированном графе вершина степени 1.
2. В орграфе вершина с полустепенью захода, равной 1, и полустепенью исхода, равной 0.
Другое название - лист.
Литература:[Берж]

Висячее ребро(Terminal pendant edge)
- ребро, одна из концевых вершин которого имеет степень 1.
Литература:[Берж]

Внешнепланарный граф(Outerplanar graph)
- планарный граф, который имеет укладку на плоскости такую, что все его вершины принадлежат одной грани. См. Внешнеплоский граф.
Литература:[Харари]

Внешнеплоский граф(Outerplane graph)
- граф, допускающий внешнепланарную реализацию.
Литература:[Харари]

Внешне устойчивое множество(Absorbant set, external stability set)
- множество вершин X такое, что любая вершина графа или принадлежит X или смежна с вершиной из X.
Другое название - доминирующее множество.
Литература:[Берж]

Внешней устойчивости число - см. Число внешней устойчивости.

Внешний радиус(Outradius)
- число внешнего разделения вершины, являющейся внешним центром.
Литература:[Кристофидес]

Внешний радиус абсолютный - см. Абсолютный внешний радиус.

Внешний центр(Outcentre)
- вершина, на которой число внешнего разделения достигает минимума.
Литература:[Кристофидес]

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

Внешность цикла(Exterior of a cycle)
- подграф, порожденный вершинами, не принадлежащими данному циклу.
Литература:[Харари]

Внешняя грань - см. Грань.

Внутренне устойчивое множество(Stable set)
- множество попарно несмежных вершин графа.
Другое название - независимое множество.
Литература:[Берж]

Внутреннего разделения число - см. Число внутреннего разделения.

Внутренней устойчивости число - см. Число внутренней устойчивости.

Внутренний порядок обхода дерева(Tree traversal inorder)
- обход ордерева в соответствии со следующими рекурсивными правилами:
1) посетить во внутреннем порядке левое поддерево корня (если оно существует),
2) посетить корень,
3) посетить во внутреннем порядке правое поддерево корня (если оно существует).
Другое название - инфиксный порядок.
Литература:[Ахо-Хопкрофт-Ульман], [Евстигнеев-Касьянов]

Внутренний радиус(Inradius)
- число внутреннего разделения вершины, являющейся внутренним центром.
Литература:[Кристофидес]

Внутренний радиус абсолютный - см. Абсолютный внутренний радиус.

Внутренний центр(Incentre)
- вершина, на которой число внутреннего разделения достигает минимума.
Литература:[Кристофидес]

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

Внутренняя вершина(Inner vertex)
- вершина дерева, имеющая сыновей, т.е. не являющаяся листом.
Литература:[Касьянов-Поттосин]

Внутренняя грань - см. Грань.

Возвратный ход - см. Поиск в глубину.

Вполне несвязный граф(Fully disconnected graph)
- граф без ребер. Другие названия - регулярный степени 0 граф, пустой граф.
Литература:[Харари]

Вращение двойное(Double rotation)
- преобразование балансированного (по высоте или по весу) дерева для восстановления его структуры. См. Вращение простое.
Литература:[Кнут], [Евстигнеев], [Евстигнеев-Касьянов]

Вращение простое(Simple rotation)
- преобразование балансированного (по высоте или по весу) дерева для восстановления его структуры. См. Вращение двойное.
Литература:[Кнут], [Евстигнеев], [Евстигнеев-Касьянов]

Временная сложность(Time complexity)
- основной параметр, характеризующий алгоритм; определяется как число шагов, выполняемых алгоритмом в худшем случае, обычно рассматривается как функция размерности задачи, представленной входными данными. Обычно под размерностью теоретико-графовой задачи понимается число вершин графа n, число дуг m или пара (n,m). Под шагом алгоритма понимается выполнение одной из команд некоторой гипотетической машины. Поскольку при таком определении шага сложность алгоритма зависит от конкретного вида машинных команд, во внимание принимается асимптотическая сложность, т.е. асимптотическая скорость увеличения числа шагов алгоритма, когда размерность задачи неограниченно растет. Ясно, что при двух произвольных "разумных" способах перевода алгоритма в последовательность машинных команд соответствующие сложности различаются не более чем на мультипликативную константу, а их скорость роста одинакова.
При сравнении скорости роста двух функций f(n) и g(n) используются следующие обозначения:
f(n) = O(g(n)) [LeftRightDoubleArrow] существуют константы C, N > 0, такие что f(n) [leq] C [cdot] g(n) для всех n [geq] N
f(n) = [omega](g(n)) [LeftRightDoubleArrow] существуют константы C, N > 0, такие что f(n) [geq] C [cdot] g(n) для всех n [geq] N

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

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

Втягивание вершины(Vertex involving)
- преобразование орграфа, состоящее в отождествлении вершин a и b, связанных дугой (a,b), причем эта дуга - единственная заходящая в b дуга.
Другое название - слияние двух вершин. См. также Разборный граф.
Литература:[Евстигнеев], [Евстигнеев-Касьянов], [Касьянов]

Вход(Source, input, entry)
- вершина в орграфе, полустепень захода которой равна 0, а полустепень исхода отлична от нуля; в общем случае - произвольная выделенная вершина, служащая точкой начала отсчета при решении прикладной задачи.
Литература:[Евстигнеев], [Евстигнеев-Касьянов], [Касьянов]

Входная вершина подграфа(Entry vertex of a subgraph)
- вершина, через которую проходит любой путь извне подграфа в произвольную вершину подграфа.
Литература:[Касьянов], [Евстигнеев-Касьянов]

Входная вершина фрагмента(Entry vertex of a fragment)
- вершина фрагмента, для которой существует путь из начальной вершины уграфа, не содержащий дуг фрагмента.
Литература:[Евстигнеев-Касьянов], [Касьянов]

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

Входящий оркаркас(Input directed spanning tree)
- суграф орграфа в виде входящего дерева.
Литература:[Евстигнеев-Касьянов], [Майника]

Вывод цепочки - см. Язык, порожденный грамматикой.

Выпуклый прямолинейный граф(Convex linear graph)
- плоский граф, у которого граница каждой грани есть выпуклый многоугольник.
Литература:[Лекции]

Выровненное дерево(Justified tree)
- ордерево, у которого все листья расположены на одном уровне. См. 2-3-дерево, Дерево братства, Дерево соседства, B-дерево.
Литература:[Евстигнеев], [Евстигнеев-Касьянов], [Касьянов-Поттосин]

Высота вершины (в ордереве)(Height of vertex)
- длина самого длинного пути из рассматриваемой вершины в какой-нибудь лист.
Литература:[Ахо-Хопкрофт-Ульман], [Евстигнеев]

Высота дерева(Height of tree)
- высота корня дерева (ордерева).
Литература:[Ахо-Хопкрофт-Ульман], [Евстигнеев], [Евстигнеев-Касьянов]

Выход(Output, sink, exit)
- вершина в орграфе, полустепень исхода которой равна 0, а полустепень захода больше нуля.
Литература:[Берж], [Евстигнеев], [Касьянов]

Выходная вершина подграфа(Output vertex of subgraph)
- вершина подграфа, через которую проходит любой путь из вершин подграфа в произвольную вершину графа, не принадлежащую подграфу.
Литература:[Евстигнеев]

Выходная вершина фрагмента(Exit vertex of fragment)
- вершина фрагмента, которая либо является конечной вершиной уграфа, либо из нее исходит дуга уграфа, не принадлежащая фрагменту.
Литература:[Евстигнеев-Касьянов], [Касьянов]

Выходящее дерево(Output tree)
- ордерево (в частности оркаркас), все дуги которого ориентированы так, что любая вершина достижима из корня (ориентированы от корня).
Литература:[Евстигнеев]

Выходящий оркаркас(Output directed spanning tree)
- суграф орграфа в виде выходящего дерева.
Литература:[Евстигнеев-Касьянов], [Майника]

Вычислительная сложность алгоритма - то же, что и временная сложность.