Венгерское дерево
Cтраница 1
 |
Венгерское дерево. [1] |
Венгерское дерево - это такое альтернирующее дерево в графе, что каждое ребро графа, имеющее внешнюю вершину дерева в качестве концевой, имеет другой концевой вершиной внутреннюю вершину этого дерева. [2]
В случае ( III) вершины венгерского дерева и инцидентные им ребра совсем удаляются из графа ( в соответствии с теоремой 4) и алгоритм применяется к оставшемуся подграфу. [3]
 |
Наибольшее паросочетание в примере. [4] |
Заметим, что вершина х19 удалена ранее вместе с венгерским деревом. Получающееся паросочетание, изображенное на рис. 12.14, будет, таким образом, наибольшим паросочетанием. [5]
О частично строится из паросочетания в Н, оставляющего экспонированным корень дерева Н, и поэтому существование венгерского дерева означает, что в О нет никакого совершенного паросочетания. Таким образом, при обнаружении такого дерева следует изменить вектор весов [ яг, Яг ], чтобы получить новый специальный остовный подграф О в графе О и подвергнуть его проверке. Ниже будет описано, как вычисляется такой весовой вектор. [6]
Вообще говоря, может оказаться, что в G совершенное паросочетание найти нельзя, а алгоритм для ЗНПС обнаружит венгерское дерево. Как уже отмечалось в разд. [7]
Вообще говоря, может оказаться, что в С совершенное паросочетание найти нельзя, а алгоритм для ЗНПС обнаружит венгерское дерево. Как уже отмечалось в разд. [8]
Если это не так, то удалим из G вершины Т и все ребра, инцидентные с этими вершинами, и повторим шаги 1 - 3 для оставшегося графа. Таким образом, мы постепенно удаляем одно венгерское дерево за другим до тех пор, пока не получим совершенное паросочетание в оставшейся части графа или оставшаяся часть графа оказывается венгерским деревом. [9]
Для доказательства достаточно рассмотреть определения и найти ребро е графа G, относительно которого Т является расширяющимся или цветущим деревом. Если такого ребра не существует и Т не может быть увеличено, то Т является венгерским деревом. [10]
Рассмотрим теорему, очень важную для понимания алгоритма поиска максимального паросочетания в графе. Теорема 6.10. Растущее дерево Т в G может быть увеличено до расширяющегося дерева, до цветущего дерева, либо до венгерского дерева. [11]
Естественно одно и то же растущее дерево может удовлетворять нескольким из этих условий относительно различных ребер. Если оно не удовлетворяет ни одному из названных условий при рассмотрении любого ребра, инцидентного любой внешней вершиной, то мы приходим к понятию венгерского дерева. Таким образом, Т не является расширяемым или цветущим деревом относительно произвольного ребра е графа G и его нельзя увеличить, как делалось в предыдущем абзаце. [12]
Если это не так, то удалим из G вершины Т и все ребра, инцидентные с этими вершинами, и повторим шаги 1 - 3 для оставшегося графа. Таким образом, мы постепенно удаляем одно венгерское дерево за другим до тех пор, пока не получим совершенное паросочетание в оставшейся части графа или оставшаяся часть графа оказывается венгерским деревом. [13]
Там этой породе давно уже придают большее значение, чем большинству местных, и, по словам проф. Вадаса, белая акация с полным правом может быть названа венгерским деревом. [14]
Два расширения ( на основе ребер 8 и 9) образуют дерево, показанное на рис. 6.32, д, которое является венгерским. Его внешние вершины ( С, Н и /) связаны только с внутренними вершинами дерева. Теперь временно удалим дерево из рассмотрения и выделим подграф GJ, полученный удалением вершин венгерского дерева и всех ребер, инцидентных его вершинам. Это паросочетание является, очевидно, максимальным ( точнее, совершенным) в GJ. [15]
Страницы: 1