Cтраница 4
Мы завершаем этот раздел рассмотрением еще одной из эквивалентных теорем о двудольном паросочетании, также принадлежащей Кенигу ( ср. Напомним, что реберное покрытие графа G - это множество ребер, покрывающих ( в совокупности) каждую вершину в G, и что p ( G есть наименьшая из мощностей реберных покрытий графа G. Как и раньше, через a ( G) обозначается ( вершинное) число независимости. Тождества Галлаи ( см. 1.0.1 и 1.0.2) вместе с теоремой Кенига позволяют нам легко установить следующий результат. [46]
Было замечено, что если нас интересует, скажем, число наибольших паросочетаний, то следует решать сначала соответствующую задачу для более специального класса графов, а именно графов с совершенными паросочетаниями. Подграф C ( G) из декомпозиции Галлаи - Эдмондса является как раз таким графом, а для графов с совершенными паросочетаниями выполняется равенство: C ( G) G. Следовательно, в этом случае теорема Галлаи - Эдмондса ничего интересного нам не дает. Поэтому нужно заняться специально изучением графов, обладающих совершенными паросочетаниями, что и будет предпринято в данной и следующей главах. В настоящей главе рассматриваются двудольные графы. [47]
В последнем разделе настоящей главы мы рассматриваем задачу о реализации наборов целых положительных чисел наборами степеней вершин графов. Эту задачу мы будем называть проблемой ( или задачей) о наборах степеней ( вершин) графов. Она представляет собой частный случай задачи об / - факторе, относящийся к ситуации, когда заданный граф является полным. Однако имеется несколько более прямых подходов для установления фундаментального результата Эрдеша и Галлаи ( 1960), дающего характеризацию реализуемых наборов степеней, а также для получения различных обобщений этого результата. Мы также рассматриваем здесь проблему реализации набора степеней графом, обладающим совершенным паросочетанием. [48]
Естественным обобщением задачи о нахождении паросочетания является так называемая задача об / - факторе. Если нет, то насколько хорошо можно аппроксимировать / степенями остовного подграфа. Последнюю ( менее четкую) проблему принято называть задачей о подграфе с ограниченными степенями. Цель данной главы состоит в том, чтобы дать ответы на эти вопросы посредством декомпозиции множества V ( G), аналогичной декомпозиции Галлаи - Эдмондса, описанной в гл. [49]
Поскольку ни одно ребро не соединяет D и С, эти компоненты разбивают множество D. G, индуцированный множеством С. Из равенств (3.2.2) следует, что всякое наибольшее паросочетание графа G - А покрывает подграф Н, но каждая вершина из D не покрывается каким-то одним из таких паросочетаний. Таким образом, подграф Я имеет совершенное паросочетание. Далее, так как каждая вершина в G - не покрывается каким-нибудь наибольшим паросочетанием графа d, то, применяя лемму Галлаи, немедленно получаем, что каждый граф Gt факторно-критический. [50]
Теорема Фробениуса дает характеризацию двудольных графов, обладающих совершенным паросочетанием. Теорема Холла содержит характеризацию двудольных графов, имеющих паросочетание из А в В. Теорема Кенига дает формулу для числа паросочетания в двудольном графе. Часто возникают задачи, начинающиеся словами охарактеризуем эти... Если мы найдем необходимое и достаточное условие, то как нам узнать, не является ли оно только вновь объявленным, возможно замаскированным, свойством определения. И теорема Кенига ( см. теорему 1.1.1), и тождество Галлаи ( см. лемму 1.0.2) дают формулы для v ( G), но чувствуется, однако, что теорема Кенига - более глубокий результат. [51]