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

Cтраница 3

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

Затем третий по порядку элемент исходного списка сравнивается либо с первым, либо со вторым элементом; на этом совпадение дерева на рис. 2.2 с деревом на рис. 2.1 заканчивается. Внешние вершины усеченного дерева на рис. 2.2 представляют правильно упорядоченные последовательности элементов, обозначенных своими порядковыми номерами в исходном списке, получаемые после A ( k) парных сравнений. С увеличением числа ранжируемых элементов дерево быстро разрастается. На схеме все его элементы показаны только для k & 4, следующие уровни дерева представлены фрагментами. При некоторых значениях k несовпадающие последовательности парных сравнений могут приводить к одним и тем же наиболее благоприятным упорядочениям. Такой случай имеет место при k 5; в представленном на рис. 2.2 фрагменте из восьми упорядочений, каждое из которых получено при дЛ ( 5) 2, только пять различных. Повторяющиеся упорядочения этого фрагмента заштрихованы. [32]

Два расширения ( на основе ребер 8 и 9) образуют дерево, показанное на рис. 6.32, д, которое является венгерским. Его внешние вершины ( С, Н и /) связаны только с внутренними вершинами дерева. Теперь временно удалим дерево из рассмотрения и выделим подграф GJ, полученный удалением вершин венгерского дерева и всех ребер, инцидентных его вершинам. Это паросочетание является, очевидно, максимальным ( точнее, совершенным) в GJ. [33]

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

Корневая вершина ( нулевой уровень) отображает сравнение первой пары элементов исходного списка. Первый уровень содержит две внешние вершины. Второй уровень содержит четыре внутренние вершины, так как третий по порядку элемент исходного списка можно сравнивать в соответствии с алгоритмом III как с первым элементом, полученной последовательности, так и со вторым. Дерево, отображающее проце - ДУРУ ранжирования трех элементов, показано на рис. 2.1. Двенадцать внешних вершин представляют получаемые последователъности из трех элементов, обозначенных своими порядковыми номерами в исходном списке. На третьем уровне представлены упорядочения, для получения которых достаточно выполнения двух парных сравнений; в каждом случае третье парное сравнение было бы избыточным в силу транзитивности бинарного отношения линейного строгого порядка. Вершины четвертого уровня представляют упорядочения, для получения каждого из которых необходимо выполнить три парных сравнения. Отметим, что каждое упорядочение встречается дважды. Для получения двух из них безразличен порядок выполнения двух последних парных сравнений - это последовательности 2 3, 1 и 1 3, 2, тогда как для остальных этот порядок имеет значение, поскольку эти последовательности могут быть получены в результате либо двух, либо трех парных сравнений. [35]

Красно-черное дерево. Закрашенные вершины имеют черный цвет, а незакрашенные - красный. ( На рисунке показаны лишь цвета. [36]

Чтобы вставить новый элемент в красно-черное дерево, мы сначала ищем в нем наибольший элемент, меньший вставляемого. Достигнув в процессе поиска внешней вершины, мы заменяем ее внутренней вершиной, имеющей двух сыновей ( потомков): старую внешнюю вершину и новую внешнюю вершину, содержащую вставляемый элемент. Новая внутренняя вершина содержите качестве ключа наименьший из двух элементов, содержащихся в вершинах-сыновьях этой вершины. Эта новая внутренная вершина окрашивается в красный цвет. Это может привести к нарушению условия ( 3), которое должно выполняться для красных вершин. Чтобы это условие вновь выполнялось, применим следующую процедуру перекраски вершин. Двигаясь снизу вверх по пути, пройденному при поиске, изменяем цвета вершин по правилам, показанным на рис. 20, а. [37]

Альтернирующее дерево Т с корнем в экспонированной вершине х1 показано сплошными линиями, а все другие ребра графа, не входящие в дерево Т - пунктиром. Так как между двумя внешними вершинами х12 и х13 существует ребро, то добавление к дереву вышеупомянутого последнего ребра дает цветок. [38]

Альтернирующее дерево Т с корнем в экспонированной вершине хг показано сплошными линиями, а все другие ребра графа, не входящие в дерево Г - пунктиром. Так как между двумя внешними вершинами х12 и х13 существует ребро, то добавление к дереву вышеупомянутого последнего ребра дает цветок. [39]

Красно-черное дерево. Закрашенные вершины имеют черный цвет, а незакрашенные - красный. ( На рисунке показаны лишь цвета. [40]

Исключение элемента производится аналогичным образом. При удалении элемента сначала ищется внешняя вершина, содержащая этот элемент. Затем вершина-родитель этой вершины заменяется братом удаляемой вершины. Это может привести к нарушению условия ( 2) для черных вершин, а именно может появиться так называемая короткая вершина, определяемая тем, что все пути, проходящие через нее к внешним вершинам, содержат на одну черную вершину меньше, чем пути, проходящие через ее брата. [41]

Можно обозначить ранжируемые элементы их порядковыми номерами в конечном списке, т.е. правильными рангами, и указать те исходные последовательности, из которых получается правильное упорядочение за Л ( Ю парных сравнений. На рис. 2.2 имеется 16 внешних вершин, представляющих правильные упорядочения четырех элементов. Эту последовательность можно описать так: первый по порядку элемент занимает в исходном списке четвертое место, второй - третье, третий - первое и четвертый элемент - второе место. Ветвь рассматриваемого дерева, образующая последовательность 4 3 1 2, показана на рис. 2.3 а, а на рис. 2.3 6 представлена та же ветвь, где ранжируемые элементы обозначены соответствующими номерами конечного списка Аналогичным способом можно представить другие наиболее благоприятные последовательности, элементы которых обозначены порядковыми номерами конечного списка. [42]

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

На, начальное паросочетание в котором показана жирными линиями. Мы применим алгоритм предыдущего раздела с тем правилом, что на шаге 3 внешние вершины просматриваются в порядке увеличения их индексов и если дана внешняя вершина, то ребра, ведущие из нее, просматриваются в порядке увеличения индексов их вторых концевых вершин. [44]

На, начальное паросочетание в котором показано жирными линиями. Мы применим алгоритм предыдущего раздела с тем правилом, что на шаге 3 внешние вершины просматриваются в порядке увеличения их индексов и если дана внешняя вершина, то ребра, ведущие из нее, просматриваются в порядке увеличения индексов их вторых концевых вершин. [45]

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