Cтраница 2
Теперь сформулируем обобщение теоремы Андерсона, предложенное Вудоллом. Как отмечает сам Вудолл, его доказательство этого обобщения абсолютно аналогично доказательству Андерсона и отличается только тем, что вместо теоремы Татта в одном месте используется формула Бержа. Доказательство оставляем читателю в качестве упражнения. [16]
Сейчас мы представим результат, следствия из которого в теории паросочетаний так же значительны, как и теорема Татта, но он не является широко известным. Как было уже отмечено, теорема Татта дает нам хорошую характеризацию для графов, не имеющих совершенного паросочетания. А именно, чтобы явно продемонстрировать, что граф G не имеет совершенного паросочетания, мы можем указать конкретное множество S вершин и не менее чем 5 1 нечетных компонент в графе G - S. Такое разделяющее множество S часто называют множеством Татта. Конечно, таких множеств Татта может быть много. [17]
Это доказательство теоремы о пересечении матроидов является не очень изящным, особенно если учесть, что мы применили теорему 11.2.7, доказательство которой было достаточно сложным. Однако важно здесь увидеть, что даже в некотором смысле общие результаты о паросочетаниях полиматроидов могут быть использованы для решения задачи о пересечении матроидов. Читатель, который решал упражнение 3.1.4, вспомнит, что получение теоремы о свадьбах из теоремы Татта тоже не совсем прямое; поучительно сравнить с нашим доказательством рассуждения, потребовавшиеся там. [18]
Для недвудольных графов ситуация совершенно иная. Известные алгоритмы для нахождения наибольшего паросочетания в общем графе, выполняемые за полиномиальное время, занимают место среди самых сложных комбинаторных алгоритмов. Многие из них базируются на процедуре пополнения, осуществляемой с использованием чередующихся цепей, - как в большинстве доказательств теоремы Татта и формулы Бержа. Но чтобы превратить эти минимаксные результаты в выполняемые за полиномиальное время алгоритмы, требуются принципиально новые идеи. В его алгоритме в качестве ключевой была использована идея сжатия или стягивания определенных нечетных циклов. Вплоть до наших дней большинство алгоритмов построения паросочетаний ( и даже самые удачные из них) базируются - явно или неявно - на этой идее. [19]