Мирзаянов М. Р. Паросочетания и смежные задачи определения и вводные понятия
 Скачать 1.13 Mb.
|
§2. Четыре основные задачиПервая основная задача была фактически уже сформулирована, и звучит она следующим образом: в графе  найдите максимальное паросочетание. В этой и остальных задачах какого-либо поиска следует считать, что если ответов несколько, то следует найти любой из них. Максимальное паросочетание будем обозначать символом  или просто  , если контекст это позволяет (сокращение – аббревиатура от английского maximummatching).Подмножество ребер графа называется реберным покрытием, если любая вершина графа инцидентна хотя бы одному ребру данного подмножества. Очевидно, интерес представляют минимальные в некотором смысле реберные покрытия. Реберное покрытие называется минимальным, если количество ребер в любом реберном покрытии не меньше, чем в данном. Минимальное реберное покрытие будем обозначать как  или просто  (от англ. minimumedgecovering). Заметим, что если в графе есть изолированные вершины, то реберного покрытия для такого графа не существует. Поэтому, везде ниже если ведется речь о реберном покрытии, предполагается, что в графе нет изолированных вершин.Вторая основная задача: в графе найдите . Подмножество вершин графа называется независимым, если не существует ребра в графе, оба конца которого принадлежат этому подмножеству. Независисимое подмножество вершин называется максимальным, если не существует другого независимого подмножества в котором больше вершин. Максимальное независимое подмножество обозначается символом  или просто  (от англ. maximumindependentvertexsubset).Третья основная задача: в графе найдите . Подмножество вершин графа называется вершинным покрытием, если для любого ребра хотя бы один его конец инцидентен какой-то вершине подмножества. Вершинное покрытие называется минимальным, если количество вершин в любом вершинном покрытии не меньше, чем в данном. Минимальное вершинное покрытие будем обозначать как  или просто  (от англ. minimumvertexcovering).Напомним, что на рис.1 изображен пример решения первой основной задачи. На рис. 2, рис.3, рис. 4 изображены примеры решения задач 2, 3, 4 соответственно.  Следует заметить, что все эти четыре задачи являются классическими задачами алгоритмической теории графов, и зачастую возникают в приложениях. §3. Эквивалентность задач: MM и MEC, MIVS и MVCВ этом параграфе будет показано, что задачи нахождения максимального паросочетания и минимального реберного покрытия являются эквивалентными. Решив любую из них, легко получить решение другой задачи. Аналогично, решив задачу нахождения максимального независимого подмножества вершин, немедленно следует решение задачи нахождения минимального вершинного покрытия. Теорема 2. Для любого графа выполняется равенство: .Доказательство. Докажем более сильное утверждение: дополнение максимального независимого подмножества вершин является минимальным вершинным покрытием (разумеется, верно и обратное). Рассмотрим произвольное максимальное независимое подмножество вершин   . Из определения независимого подмножества вершин следует, что любое ребро соединяет либо вершину из и  , либо вершины множества . Таким образом, каждое ребро инцидентно некоторой вершине множества , то есть является некоторым вершинным покрытием. Следовательно: ,или:  Рассмотрим произвольное минимальное вершинное покрытие . Так как каждое ребро инцидентно хотя бы одной вершине из , то  является независимым подмножеством вершин. Тогда: ,или:  Таким образом, из неравенств и следует, что:  Следовательно, является минимальным вершинным покрытием, а является максимальным независимым подмножеством вершин.  В следующей теореме будет установлена эквивалентность задач нахождения максимального паросочетания и минимального реберного покрытия. Теорема 3. Для любого графа выполняется равенство: .Доказательство. Докажем два неравенства. 1. Рассмотрим некоторое максимальное паросочетание . Очевидно, что оно насыщает  вершин, и не насыщает  . Каждая из ненасыщенных вершин смежна только с насыщенными вершинами, так как в противном случае паросочетание можно было бы дополнить соответствующим ребром. Если к множеству добавить ребер так, что каждое из добавленных ребер инцидентно своей ненасыщенной вершине, то получившееся множество будет некоторым реберным покрытием. В этом множестве будет    ребер. То есть 2. Пусть – некоторое минимальное реберное покрытие. Рассмотрим граф  . Очевидно, что  не содержит циклов, то есть – лес (более того, можно показать, что каждое дерево в имеет диаметр не более 2). Так как в любом дереве количество вершин на единицу больше количества ребер, то: ,где  – количество компонент связности графа . Cконструируем множество  , выбрав из каждого дерева графа по одному ребру. Очевидно, что является паросочетанием и  . Так как  , то Из неравенств и следует, что  . Из конструктивного доказательства теоремы 3 непосредственно следуют алгоритмы построения максимального паросочетания по минимальному реберному покрытию и наоборот. |