Расширения: структура двудольных графов без идеального паросочетания

С алгоритмической точки зрения мы уже знаем, как найти идеальное паросоче- тание: нужно использовать приведенный выше алгоритм для нахождения мак- симального паросочетания, а потом проверить, является ли это паросочетание идеальным.

Но пока зададимся чуть менее алгоритмическим вопросом. Не во всех двудоль- ных графах существуют идеальные паросочетания. Как выглядит двудольный граф без идеального паросочетания? Существует ли простой способ определить, что двудольный граф не имеет идеального паросочетания — или по крайней мере убе- дить кого-то в том, что граф не имеет идеального паросочетания, после выполнения алгоритма? А если говорить конкретнее, было бы хорошо, если бы алгоритм после принятия решения об отсутствии идеального паросочетания мог выдать короткий «сертификат», подтверждающий его отсутствие. С таким сертификатом любой желающий мог бы быстро убедиться в отсутствии идеального паросочетания без отслеживания всего хода выполнения алгоритма.

Чтобы понять идею такого сертификата, на происходящее можно было бы взглянуть так, чтобы решить, имеет ли граф G идеальное паросочетание, мы могли бы проверить, что величина максимального потока в графе G' не ниже n. Согласно теореме о максимальном потоке и минимальном разрезе, разрез s-t с пропускной способностью ниже n существует в том случае, если величина максимального потока в G' ниже n. Итак, разрез с пропускной способностью ниже n мог бы по- служить таким сертификатом. Однако нам нужен сертификат, обладающий есте- ственным смыслом в контексте исходного графа G.

Как мог бы выглядеть такой сертификат? Например, если существуют узлы x1, x2 ^ X, каждый из которых имеет только одно инцидентное ребро, а другим концом каждого ребра является один и тот же узел у, очевидно, такой граф не имеет идеального паросочетания: и x1 и x2 должны будут оказаться в паре с одним узлом у. На более общем уровне рассмотрим подмножество узлов A !Ξ X; пусть Г(A) !Ξ Yобозначает множество всех узлов, смежных с узлами вA. Если граф имеет идеальное паросочетание, то все узлы в A должен находиться в парах с разными узлами в Г(A), так что множество Г(A) должно быть по крайней мере не меньшеA. Мы приходим к следующему факту.

(7.39) Если двудольный граф G = (V, E) с двумя сторонами X и Y имеет иде- альное паросочетание, то для всех A !Ξ X должно выполняться условие |Г(A)| > |A|.

Это утверждение подсказывает, какой сертификат мог бы демонстрировать отсутствие идеального паросочетания у графа: множество A !Ξ X, для которого |Г(A)| < |A|. Но будет ли истинным также условие, обратное (7.39)? Действительно ли в любой ситуации при отсутствии идеального паросочетания существует по- добное множество A, которое это доказывает? Ответ на этот вопрос оказывается по- ложительным, если добавить очевидное условие | X | = | Y | (без которого идеального паросочетания, конечно, быть не может). Это утверждение известно в литературе как теорема Холла, хотя его разновидности были независимо открыты несколькими учеными (вероятно, первым был Кёниг) в начале 1900-х годов. Из доказательства утверждения также вытекает способ нахождения такого подмножества A за по- линомиальное время.

(7.40) Предположим, в двудольном графе G = (V,E) имеются две стороныX и Y, для которых |X | = | Y |.

В этом случае граф G либо имеет идеальное паросочетание, либо существует такое подмножество A !Ξ X, что |Г(A)| < | A |. Идеальное паросоче- тание или соответствующее подмножество A могут быть найдены за время O(mn).

Доказательство. Воспользуемся тем же графом G', что и в (7.37). Будем считать, что |X | = | Y| = n. Согласно (7.37) граф G имеет максимальное паросочетание в том и только в том случае, если величина максимального потока в G' равна n.

Необходимо показать, что если величина максимального потока меньше n, то существует подмножество A, для которого |Г(A)| < |A|, как указано в утверждении. По теореме о максимальном потоке и минимально разрезе (7.12), если величина максимального потока меньше n, то существует разрез (A', B') с пропускной способ- ностью менее n в G'. МножествоA' содержит s, и может содержать узлы как изX, так и из Y, как показано на рис. 7.11. Утверждается, что множество A = X ∩ A' обладает заявленным свойством. Если нам удастся это доказать, то тем самым будут доказа- ны обе части утверждения, так как в (7.11) было показано, что минимальный разрез (A', B') также может быть найден выполнением алгоритма Форда-Фалкерсона.

Начнем с того, что минимальный разрез (A', B') можно изменить так, чтобы га- рантировать выполнение условия Г(A) !Ξ A'(как и прежде,A = X ∩ A'). Для этого рассмотрим узел у Г(A), принадлежащий B', как показано на рис. 7.11, а. Утверж- дается, что перемещение y из B' в A' не увеличивает емкость разреза. Действитель- но, что происходит при перемещении y из B' в A'? Ребро (у, t) теперь пересекает разрез, увеличивая пропускную способность на 1. Но ранее было по крайней мере одно ребро (x, у) с x A, так как y Г(A); разрез пересекали все ребра из A и у,

а теперь ситуация изменилась, поэтому общая пропускная способность разреза не может возрасти. (Обратите внимание: нам не нужно беспокоиться об узлах x X,

не входящих в A. Два конца ребра (x, у) будут находиться на разных сторонах раз- реза, но само ребро не увеличивает пропускную способность разреза, потому что проходит из B' в A'.)

а


Рис. 7.11. a — минимальный разрез из доказательства (7.40); b — тот же разрез после перемещения узла у на сторону A'. Ребра, пересекающие разрез, выделены жирными линиями


Теперь рассмотрим пропускную способность минимального разреза (A', B'), у которого Г(A) !Ξ A' (рис. 7.11, b). Так как все соседи A принадлежат A', мы видим, что из A' выходят только ребра, либо выходящие из источника s, либо входящие в сток t. Следовательно, пропускная способность разреза равна в точности



Сравнивая первую и последнюю части, получаем требуемое неравенство

Al > |г(А)|.

7.6.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Расширения: структура двудольных графов без идеального паросочетания:

  1. БЕЗ СЛЕДОВ, БЕЗ ТЕНИ, БЕЗ ЭГО
  2. 2. Всестороннее развитие без детской любви – ничто. Гармония с самим собой немыслима без гармонических отношений с другими
  3. ИДЕАЛЬНОЕ
  4. ВАРИКОЗНОЕ РАСШИРЕНИЕ ВЕН
  5. Я ИДЕАЛЬНОЕ
  6. Расширение графического метода
  7. Идеальные условия
  8. Расширение внутреннего кругозора
  9. Самовоспитание как "расширение" сознания
  10. 3.1. РАСШИРЕНИЕ НЕЙРОЛОГИЧЕСКОГО КОНТАКТА
  11. 3.12.2. Техника расширенного восприятия
  12. 7.2.2. Расширение полноты ответа
  13. 7.2.2. Расширение полноты ответа