Внешняя вершина
Cтраница 4
Чередующееся дерево - это дерево, вершины которого разбиты на два класса ( называемые внутренними и внешними вершинами ] так, что каждая внутренняя вершина имеет степень 2 и каждое ребро соединяет внутреннюю вершину с внешней. [46]
Наконец, если каждая внешняя вершина имеет соседями только внутренние вершины, то мы можем утверждать, что паросочетание М уже само является наибольшим. Чтобы убедиться в этом, предположим, что лес F содержит m внутренних и п внешних вершин. Далее, если мы удалим все внутренние вершины леса F из графа G, то получившийся граф будет содержать все внешние вершины леса F как изолированные вершины. Но паросочетание М пропускает в точности 5 вершин, и поэтому оно должно быть наибольшим паросочетанием. [47]
Естественно одно и то же растущее дерево может удовлетворять нескольким из этих условий относительно различных ребер. Если оно не удовлетворяет ни одному из названных условий при рассмотрении любого ребра, инцидентного любой внешней вершиной, то мы приходим к понятию венгерского дерева. Таким образом, Т не является расширяемым или цветущим деревом относительно произвольного ребра е графа G и его нельзя увеличить, как делалось в предыдущем абзаце. [48]
Аналогично величины Si, П и Я можно представить неприводимыми диаграммами. Собственная энергия Si ( l z) есть сумма всех связанных топологически неэквивалентных неприводимых диаграмм с двумя внешними вершинами, которые не распадаются на две отдельные части при разрыве одной линии, отвечающей функции Грина свободных частиц. Аналогично поляризационный оператор П ( 7, о) дается суммой всех связанных топологически неэквивалентных неприводимых диаграмм с двумя внешними вершинами ( возникающими при отсечении линий VQ), которые не распадаются на две отдельные части при разрыве одной линии кулоновского взаимодействия. [49]
 |
Красно-черное дерево. Закрашенные вершины имеют черный цвет, а незакрашенные - красный. ( На рисунке показаны лишь цвета. [50] |
Чтобы вставить новый элемент в красно-черное дерево, мы сначала ищем в нем наибольший элемент, меньший вставляемого. Достигнув в процессе поиска внешней вершины, мы заменяем ее внутренней вершиной, имеющей двух сыновей ( потомков): старую внешнюю вершину и новую внешнюю вершину, содержащую вставляемый элемент. Новая внутренняя вершина содержите качестве ключа наименьший из двух элементов, содержащихся в вершинах-сыновьях этой вершины. Эта новая внутренная вершина окрашивается в красный цвет. Это может привести к нарушению условия ( 3), которое должно выполняться для красных вершин. Чтобы это условие вновь выполнялось, применим следующую процедуру перекраски вершин. Двигаясь снизу вверх по пути, пройденному при поиске, изменяем цвета вершин по правилам, показанным на рис. 20, а. [51]
На, начальное паросочетание в котором показана жирными линиями. Мы применим алгоритм предыдущего раздела с тем правилом, что на шаге 3 внешние вершины просматриваются в порядке увеличения их индексов и если дана внешняя вершина, то ребра, ведущие из нее, просматриваются в порядке увеличения индексов их вторых концевых вершин. [52]
На, начальное паросочетание в котором показано жирными линиями. Мы применим алгоритм предыдущего раздела с тем правилом, что на шаге 3 внешние вершины просматриваются в порядке увеличения их индексов и если дана внешняя вершина, то ребра, ведущие из нее, просматриваются в порядке увеличения индексов их вторых концевых вершин. [53]
При малых расстояниях между трещинами ( К 2 5) k всегда больший для внешних вершин, чем для внутренних. Коэффициент интенсивности k2 при малых р больший для внутренних, а при значениях ( 3, близких к я / 2, - для внешних вершин. Взаимодействие между трещинами приводит к увеличению ( при малых углах Р) или уменьшению ( при Р, близких к п / 2) коэффициента интенсивности k по сравнению со случаем изолированной трещины. [54]
 |
Красно-черное дерево. Закрашенные вершины имеют черный цвет, а незакрашенные - красный. ( На рисунке показаны лишь цвета. [55] |
Чтобы вставить новый элемент в красно-черное дерево, мы сначала ищем в нем наибольший элемент, меньший вставляемого. Достигнув в процессе поиска внешней вершины, мы заменяем ее внутренней вершиной, имеющей двух сыновей ( потомков): старую внешнюю вершину и новую внешнюю вершину, содержащую вставляемый элемент. Новая внутренняя вершина содержите качестве ключа наименьший из двух элементов, содержащихся в вершинах-сыновьях этой вершины. Эта новая внутренная вершина окрашивается в красный цвет. Это может привести к нарушению условия ( 3), которое должно выполняться для красных вершин. Чтобы это условие вновь выполнялось, применим следующую процедуру перекраски вершин. Двигаясь снизу вверх по пути, пройденному при поиске, изменяем цвета вершин по правилам, показанным на рис. 20, а. [56]
Страницы: 1 2 3 4