2.3. Венгерские деревья

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

Рис. 12.10. Венгерское дерево.

На рис. 12.10 сплошными линиями показано венгерское дерево, причем жирными линиями изображены ребра, входящие в паросочетание, а светлыми — остальные. Ребра графа, не принадлежащие дереву, показаны пунктиром.

Важность венгерских деревьев для ЗМП объясняется следующим их свойством.

Теорема 4 [10]. Пусть венгерское дерево в графе и порожденный подграф графа «исключающий» из множество вершин дерева Если — паросочетание в дереве наибольшее паросочетание в то множество ребер является наибольшим паросочетанием в

Доказательство. Пусть множество А ребер графа разбито на три подмножества:

Если произвольное паросочетание в то может быть разбито аналогичным образом, так что

По определению паросочетания мы имеем

Рассмотрим теперь граф состоящий из ребер и их концевых вершин. По отношению к Мн все вершины являющиеся концевыми для ребер из будут экспонированными. Альтернирующая цепь, начинающаяся в экспонированной вершине (или начинающаяся в корне дерева который также является экспонированной вершиной), может только тогда быть аугментальной, когда она оканчивается в другой вершине Но аугментальная цепь должна содержать нечетное число ребер, а это означает, что если первое ребро этой цепи идет из экспонированной вершины во внутреннюю, то последнее ребро должно идти из внешней вершины в экспонированную. Так как по определению дерева все ребра в АНвп лежат между внутренними вершинами и вершинами из то в графе нет никакой аугментальной цепи и, следовательно, Мн является наибольшим паросочетанием в т. е.

Из (12.8) и (12.9) получаем

Таким образом, Мн является наибольшим паросочетанием в