Внешняя вершина

Cтраница 2

Допустим, что лес F имеет в одной связной компоненте две внешние вершины х и у, смежные в графе G. Тогда обозначим через С цикл, образованный ребром ху и ху-цепью в F. Пусть Р обозначает ( единственную) цепь в F, соединяющую цикл С с корнем леса F. Цикл С может проходить и через корень, в этом случае цепь Р состоит из одной вершины. [16]

Заметьте, что если бы внутренняя вершина не была покрыта, то две внешние вершины тоже оказались бы непокрытыми, так как каждое ребро соединяет внутреннюю вершину с внешней. [17]

Альтернирующее дерево. / - внутренние вершины, Ф - внешние вершины. [18]

Степень любой внутренней вершины альтернирующего дерева равна 2, в то время как степень внешней вершины может быть любым целым положительным числом. [19]

При малых расстояниях между трещинами ( К 2 5) k всегда больший для внешних вершин, чем для внутренних. Коэффициент интенсивности k2 при малых р больший для внутренних, а при значениях ( 3, близких к я / 2, - для внешних вершин. Взаимодействие между трещинами приводит к увеличению ( при малых углах Р) или уменьшению ( при Р, близких к п / 2) коэффициента интенсивности k по сравнению со случаем изолированной трещины. [20]

Заметим, что перекрывающимися расходимостями называются расходимости в собственно-энергетических частях, в которых часть внешних вершин заменена на вершинные части. [21]

В двоичном дереве левый путь определяется как путь, ведущий из корня в некоторую внешнюю вершину, при этом на каждом уровне путь идет по ссылке на левого сына. Правый путь определяется симметричным образом. [22]

Здесь мы будем подразумевать под двоичным деревом поиска полное двоичное дерево, в котором каждая внешняя вершина содержит элемент, выбранный из некоторого полностью упорядоченного универсума, причем порядок следования внешних вершин согласуется с общей упорядоченностью этого универсума. Каждая внутренняя вершина дерева содержит ключ, который также является элементом универсума. [23]

Венгерское дерево. [24]

Венгерское дерево - это такое альтернирующее дерево в графе, что каждое ребро графа, имеющее внешнюю вершину дерева в качестве концевой, имеет другой концевой вершиной внутреннюю вершину этого дерева. [25]

Аугменталъное дерево - это альтернирующее дерево относительно данного паросочетания, удовлетворяющее условию: существует ребро от какой-нибудь внешней вершины дерева х0, до некоторой экспонированной вершины хе, не принадлежащей дереву. Единственная цепь, идущая от корня дерева до вершины х0 и далее - по ребру ( х0, ее), будет тогда аугментальной цепью. [26]

Лемма 4.1. Пусть & - связный подкомплекс граничного комплекса простого d - многогранника М, и пусть & имеет по крайней мере одну внешнюю вершину. [27]

Безотносительно к значению А все ребра из старого графа 6 г, образующие текущее дерево Т, остаются в новом графе С, так как веса яг всех внутренних и внешних вершин дерева Т увеличиваются и уменьшаются на одну и ту же величину, а значит равенство в выражении (12.17) по-прежнему сохраняется. Таким образом, если псевдовершина из 0 - г была помечена как внешняя в альтернирующем дереве Т в старом графе С), то для некоторого ребра а ( х, х), входящего в цветок, после срезания которого образовалась эта псевдовершина, веса Я; и яй уменьшатся на А. [28]

Безотносительно к значению Д все ребра из старого графа G r, образующие текущее дерево Т, остаются в новом графе G r, так как веса я - всех внутренних и внешних вершин дерева Т увеличиваются и уменьшаются на одну и ту же величину, а значит равенство в выражении (12.17) по-прежнему сохраняется. [30]

Страницы: 1 2 3 4