Альтернирующее дерево

Cтраница 2

Если в G уже существует альтернирующее дерево, то продолжать его построение. [16]

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

Как отмечалось выше, срезание цветка приводит к дереву Т с корректной структурой альтернирующего дерева, так что Т можно сохранить и продолжать процесс роста дерева. [19]

В легко получить паросочетание из q ребер, как это показано на рис. 12.15. После того как цветок В распустился, он разбивает текущее альтернирующее дерево на две компоненты, одна из которых касается цветка в вершин arlt а другая - в вершине хг. Новое альтернирующее дерево можно затем расширять до тех пор, пока опять не возникнут приведенные выше случаи А, Б или В. [20]

Для этих новых весов [ яь Лг ] новый специальный остовный подграф графа С2 изображен на рис. 12.24. После введения нового ребра ( я12, хг1) альтернирующее дерево на рис. 12.22 становится аугментальным, так что новое ребро входит в паросочетание. В любом случае ребро ( о в, х10) сразу же попадает в паросочетание и получается совершенное паросочетание. Чтобы найти соответствующее паросочетание в С0, мы сначала распустим цветок Ъ2 и построим в нем совершенное паросочетание, как показано на рис. 12.25 ( б), а затем распустим цветок &. Так как в соответствии с теорией линейного программирования максимум величины 2 из (12.11) равен минимуму величины и из (12.16), то можно сделать проверку. [21]

Для этих новых весов [ nt, Кг ] новый специальный остовный подграф графа G2 изображен на рис. 12.24. После введения нового ребра ( z12, zn) альтернирующее дерево на рис. 12.22 становится аугментальным, так что новое ребро входит в паросочетание. В любом случае ребро ( х9, xw) сразу же попадает в паросочетание и получается совершенное паросочетание. Так как в соответствии с теорией линейного программирования максимум величины z из (12.11) равен минимуму величины и из (12.16), то можно сделать проверку. [22]

В этом случае цветок срезается, получается новый граф Gf и его специальный остовный подграф G / I - Как отмечалось выше, срезание цветка приводит к дереву Т с корректной структурой альтернирующего дерева, так что Т можно сохранить и продолжать процесс роста дерева. [23]

Специальный остовный подграф графа G0 есть G [ в этом графе строится альтернирующее дерево, как это делалось в алгоритме для ЗНПС. [25]

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

Дерево с цветком. [27]

Когда цветок Б срезан, получающаяся псевдовершина считается внешней вершиной. Но когда псевдовершина, получающаяся после срезания цветка, помечается как внешняя, структура остающегося альтернирующего дерева все еще будет корректной - как это вытекает из определения альтернирующего дерева. Таким образом, после срезания цветка альтернирующее дерево в получившемся графе сохраняется. [28]

Дерево с цветком. [29]

Когда цветок В срезан, получающаяся псевдовершина считается внешней вершиной. Но когда псевдовершина, получающаяся после срезания цветка, помечается как внешняя, структура остающегося альтернирующего дерева все еще будет корректной - как это вытекает из определения альтернирующего дерева. Таким образом, после срезания цветка альтернирующее дерево в получившемся графе сохраняется. [30]

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