Жадные алгоритмы и матроиды
Жадными (градиентными) называют алгоритмы, действующие по принципу
"максимальный выигрыш на каждом шаге". Такая стратегия не всегда
ведет
к конечному успеху - иногда выгоднее сделать не наилучший, казалось бы,
выбор на очередном шаге с тем, чтобы в итоге получить оптимальное решение.
Но для некоторых задач применение жадных алгоритмов оказывается
оправданным. Одной из самых известных задач такого рода является задача об
оптимальном каркасе. Существует общая теория, обосновывающая применимость
жадных алгоритмов к задачам определенного типа, к которому относится и
рассмотренный в предыдущей лекции алгоритм Крускала. В этой лекции будет дан набросок этой теории. Затем будет рассмотрено применение жадного
алгоритма в сочетании с методом увеличивающих путей для решения задачи
о паросочетании наибольшего веса в двудольном графе со взвешенными
вершинами.
Матроиды
Когда возник вопрос о том, каковы обстоятельства, при которых жадный
алгоритм результативен, или иначе - что особенного в тех задачах, для
которых он дает точное решение, оказалось, что математическая теория,
с помощью которой что-то в этом можно прояснить, уже существует. Это теория
матроидов, основы которой были заложены Уитни в работе 1935 г. Целью
создания теории матроидов было изучение комбинаторного аспекта линейной
независимости, а в дальнейшем обнаружились разнообразные применения
понятия матроида, первоначально совсем не имевшиеся в виду.
Определение. Матроидом называется
пара $$M=(E,\Phi)$$, где $$E$$ -
конечное непустое множество, $$\Phi$$ - семейство
подмножеств множества $$E$$, удовлетворяющее условиям:
(1) если $$X\in \Phi$$ и $$Y\subseteq X$$,
то $$Y\in \Phi$$ ;
(2) если $$X\in \Phi$$, $$Y\in \Phi$$ и $$|X| < |Y|$$, то существует
такой элемент $$a\in Y-X$$, что $$X\cup (a)\in \Phi$$.
Элементы множества $$E$$ называются элементами матроида,
а множества из семейства $$\Phi$$ - независимыми множествами
матроида. Максимальное по включению независимое множество называют базой матроида. Из аксиомы (2)
следует,
что все базы матроида состоят из одинакового количества элементов.
Если $$E$$ - множество строк некоторой матрицы,
а $$\Phi$$ состоит
из всех линейно независимых множеств строк этой матрицы,
то пара $$(E,\Phi)$$ образует матроид,
называемый матричным
матроидом.
Другим важным типом матроидов являются графовые матроиды. Пусть $$G=(V,E)$$ - обыкновенный граф. Подмножество множества $$E$$ назовем ациклическим, если подграф,
образованный ребрами этого подмножества,
не содержит циклов, т.е. является лесом.
Теорема 1. Если $$G=(V,E)$$ - обыкновенный граф, $$\Phi$$ - семейство всех ациклических подмножеств
множества $$E$$, то
пара $$M_{G} =(E,\Phi )$$ является матроидом.
Доказательство. Аксиома (1) выполняется, так как всякое
подмножество ациклического множества, очевидно, является ациклическим.
Докажем, что выполняется и (2). Пусть $$X$$ и $$Y$$ -
два
ациклических множества и $$|X| \lt |Y|$$. Допустим, что не существует
такого
ребра $$e\in Y$$, что множество $$X\cup \{ e\}$$ является
ациклическим. Тогда при добавлении любого ребра из множества $$Y$$
к множеству $$X$$ образуется цикл. Это означает, что концы каждого
такого ребра принадлежат одной компоненте связности остовного подграфа,
образованного ребрами множества $$Y$$. Тогда каждая область связности
подграфа $$X$$ содержится в какой-нибудь области связности
подграфа $$Y$$.
Но компоненты связности каждого из этих подграфов - деревья,
а дерево с $$k$$ вершинами содержит ровно $$k-1$$ ребер.
Следовательно, в этом случае число ребер в $$Y$$ не превосходило бы
числа ребер в $$X$$, что противоречит
условию $$|X| < |Y|$$.
Базами графового матроида являются все каркасы графа. Для связного графа
это будут все его остовные деревья.
Теорема Радо-Эдмондса
Рассмотрим общий тип оптимизационных задач, формулируемых следующим
образом. Дано произвольное конечное множество $$E$$ и некоторое
семейство $$\Phi$$ его подмножеств. Для каждого элемента $$x\in
E$$
задан его вес - положительное число $$w(x)$$. Вес множества $$X\subseteq E$$ определяется как сумма весов его элементов. Требуется
найти множество наибольшего веса, принадлежащее $$\Phi$$.
В эту схему укладываются многие известные задачи,
например задача о независимом множестве графа ( $$E$$ -
множество вершин графа, вес каждой вершины равен 1,
а $$\Phi$$ состоит из всех независимых множеств) или
задача о паросочетании ( $$E$$ - множество ребер графа, вес
каждого
ребра равен 1, $$\Phi$$ состоит из всех паросочетаний). В задаче об
оптимальном каркасе, рассмотренной в предыдущей лекции, требуется найти
каркас минимального, а не максимального веса, ее можно свести к задаче на
максимум. Действительно, пусть $$w$$ - заданная весовая функция
на
множестве ребер графа и требуется найти каркас минимального веса. Пусть $$a$$ - число, большее, чем веса всех ребер в данном графе.
Рассмотрим
новую весовую функцию $$w'$$, полагая что $$w'(e)=a-w(e)$$
для каждого
ребра $$e$$. Очевидно, что ациклическое множество наибольшего веса
относительно весовой функции $$w'$$ будет каркасом наименьшего веса
относительно весовой функции $$w$$ и обратно. Таким образом, задача об
оптимальном каркасе эквивалентна задаче построения ациклического множества
максимального веса. Последнюю будем называть задачей об оптимальном
каркасе на максимум. Она тоже является задачей рассматриваемого общего
типа: $$E$$ - множество ребер графа, $$\Phi$$
состоит из всех
ациклических множеств. К этой задаче применимы рассмотреннные в предыдущей лекции алгоритмы Прима и Крускала, если в первом из них на каждом шаге
выбирать ребро не минимального, а максимального веса, а во втором
упорядочивать ребра не по возрастанию, а по убыванию весов.
Модифицированный таким образом алгоритм Крускала будем называть
максимизирующим алгоритмом Крускала.
Сформулируем теперь жадный алгоритм для решения этой общей задачи.
Чтобы отличать этот алгоритм от других жадных алгоритмов, назовем его СПО
(Сортировка и Последовательный Отбор).
Алгоритм 1. Алгоритм СПО
Упорядочить элементы множества $$E$$ по убыванию весов: $$E=\{e_1,e_2\ldots e_{m}\}$$, $$w(e_{1} )\ge w(e_{2})\ge \ldots \ge w(e_{m} )$$.
$$A:=\varnothing$$
for $$i:=1$$ to $$m$$ do
if $$A\cup \{e_{i}\} \in
\Phi$$ then $$A:=A\cup \{e_{i}\}$$
Максимизирующий алгоритм Крускала является примером алгоритма этого типа.
Уместен вопрос: каким условиям должно удовлетворять семейство $$\Phi$$
для того, чтобы при любой весовой функции $$w$$ алгоритм СПО находил
оптимальное решение? Исчерпывающий ответ дает следующая теорема
Радо-Эдмондса.
Теорема 2. Если $$M=(E,\Phi)$$ - матроид, то для
любой весовой функции $$w\colon E\texto R^{+}$$ множество $$A$$, найденное
алгоритмом СПО, будет множеством наибольшего веса из $$\Phi$$.
Если же $$M=(E,\Phi )$$ не является матроидом, то найдется такая
функция $$w\colon E\texto R^{+}$$, что $$A$$ не будет множеством
наибольшего веса из $$\Phi$$.
Доказательство. Предположим, что $$M=(E,\Phi)$$ является матроидом
и $$A=\{a_{1},a_{2}\ldots a_{n}\}$$ - множество, построенное
алгоритмом СПО, причем $$w(a_{1})\ge w(a_{2})\ge \ldots \ge
w(a_{n})$$.
Очевидно, $$A$$ является базой матроида.
Пусть $$B=\{b_{1},b_{2}\ldots
b_{k} \}$$ - любое другое независимое множество
и $$w(b_{1} )\ge w(b_{2})\ge \ldots \ge w(b_{k})$$.
Так как $$A$$ - база, то $$k\le n$$.
Покажем, что $$w(a_{i} )\ge w(b_{i} )$$
для каждого $$i\in \{1\ldots k\}$$.
Действительно, положим $$X=\{a_{1}\ldots a_{i-1} \}$$, $$Y=\{ b_{1}\ldots b_{i-1},b_{i}\}$$ для некоторого $$i$$.
Согласно условию (2) определения матроида, в множестве $$Y$$
имеется такой элемент $$b_{j}$$, что $$b_{j} \notin X$$ и
множество $$X\cup \{b_{j}\}$$ - независимое. В соответствии с алгоритмом,
элементом наибольшего веса, который может быть добавлен к $$X$$ так,
чтобы получилось независимое множество, является $$a_{i}$$.
Следовательно, $$w(a_{i} )\ge w(b_{j} )\ge w(b_{i})$$.
Теперь предположим, что $$M=(E,\Phi)$$ не является матроидом.
Допустим
сначала, что нарушается условие (1), т.е. существуют такие подмножества $$X$$ и $$Y$$ множества $$E$$, что $$X\in
\Phi$$, $$Y\subset X$$ и $$Y\notin \Phi$$. Определим
функцию $$w$$
следующим образом:
$$w(x)=\left\{\begin{aligned} 1, \text{если } x\in Y, \\ 0,
\text{если } x \notin Y.
\end{aligned}\right.$$
Алгоритм СПО сначала будет рассматривать все элементы
множества $$Y$$.
Так как $$Y\notin \Phi$$, то не все они войдут в построенное
алгоритмом
множество $$A$$. Следовательно, w(A) < |Y|. В то же
время имеется
множество $$X\in \Phi$$, такое, что $$w(X)=|Y|$$. Таким
образом,
в этом случае алгоритм СПО строит не оптимальное множество. Если же
условие (1) выполнено, а не выполняется условие (2), то существуют такие
подмножества $$X$$ и $$Y$$ множества $$E$$,
что $$X\in \Phi$$, $$Y\in \Phi$$, |X| < |Y|
и $$X\cup \{ x\} \notin \Phi$$
для каждого $$x\in Y$$. Выберем такое $$\varepsilon$$,
что $$0 < \varepsilon < \frac{|Y|}{|X|} -1$$, и определим
функцию $$w$$
следующим образом:
$$w(x)=\left\{\begin{aligned} 1+\varepsilon, \text{если } x\in X, \\
1, \text{если } x\in Y-X, \\ 0, \text{если } x\notin
X\cup Y.
\end{aligned}\right.$$
Алгоритм СПО сначала выберет все элементы множества $$X$$, а затем
отвергнет все элементы из $$Y-X$$. В результате будет построено
множество $$A$$ с весом $$w(A)=(1+\varepsilon )|X| < |Y|$$,
которое не
является оптимальным, так как $$W(Y)=|Y|$$.
Максимизирующий алгоритм Крускала - это алгоритм СПО, применяемый к
семейству ациклических множеств ребер графа. Из теорем 1 и 2 следует, что
он действительно решает задачу об оптимальном каркасе. В то же время
существует много жадных алгоритмов, не являющихся алгоритмами типа СПО.
Примером может служить алгоритм Прима. Эти алгоритмы не попадают под
действие теоремы Радо-Эдмондса, для их обоснования нужна иная
аргументация.
Если для некоторой конкретной задачи удалось установить применимость
к ней
алгоритма СПО, это не значит, что все проблемы позади. Этот алгоритм
внешне очень прост, но он включает операцию проверки принадлежности
множества семейству $$\Phi$$, эффективное выполнение которой может
потребовать дополнительных усилий. В алгоритме Крускала, например, для
этого применяются специальные структуры данных. Ниже рассмотрим еще один
пример, когда для успешного решения задачи алгоритм СПО комбинируется
с методом увеличивающих путей для задачи о паросочетании, рассмотренным в
лекции 12.
Взвешенные паросочетания
Рассмотрим следующую задачу. Дан двудольный граф $$G=(A,B,E)$$ и
для
каждой вершины $$x\in A$$ задан положительный
вес $$w(x)$$. Требуется
найти такое паросочетание в этом графе, чтобы сумма весов вершин
из доли $$A$$, инцидентных ребрам паросочетания, была максимальной.
Эту задачу иногда интерпретируют следующим образом. $$A$$ - это множество работ, а $$B$$ - множество
работников.
Ребро в графе $$G$$ соединяет
вершину $$a\in A$$ с вершиной $$b\in B$$, если
квалификация
работника $$b$$ позволяет ему выполнить работу $$a$$. Каждая
работа
выполняется одним работником. Выполнение работы $$a$$ принесет
прибыль $$w(a)$$. Требуется так распределить обязанности работников, чтобы
максимизировать общую прибыль. Покажем, что эта задача может быть решена
алгоритмом СПО в сочетании с методом чередующихся цепей.
Множество $$X\subseteq A$$ назовем отображаемым, если в графе $$G$$
существует паросочетание $$M$$, насыщающее все вершины из $$X$$. $$M$$ в этом случае будем называть отображением для $$X$$.
Пусть $$\Phi$$ - семейство всех отображаемых множеств.
Теорема 3. Пара $$(A,\Phi)$$ является матроидом.
Доказательство. Условие (1) определения матроида, очевидно,
выполняется. Докажем, что выполняется и условие (2).
Пусть $$X\in \Phi$$, $$Y\in \Phi$$, $$|X| < |Y|$$.
Рассмотрим подграф $$H$$ графа $$G$$, порожденный всеми
вершинами из $$X\cup Y$$ и всеми смежными
с ними вершинами из доли $$B$$.
Пусть $$M_{X}$$ - отображение для $$X$$.
Так как $$M_{X}$$ не является наибольшим паросочетанием
в графе $$H$$, то по теореме 6 относительно
него в этом графе существует увеличивающая цепь. Одним из концов этой цепи
является свободная относительно $$M_{X}$$ вершина $$a\in
Y$$. После
увеличения паросочетания $$M_{X}$$ с использованием этой цепи, как
было
описано выше, получим паросочетание $$M'$$, отображающее множество $$X\cup \{a\}$$. Следовательно, $$X\cup \{a\} \in
\Phi$$.
Даже если бы в задаче требовалось найти только отображаемое множество
наибольшего веса, проверка принадлежности множества семейству $$\Phi$$
требовала бы и нахождения соответствующего отображения, т.е.
паросочетания. На самом же деле построение паросочетания входит в условие
задачи. Комбинируя СПО с алгоритмом поиска увеличивающих цепей, получаем
следующий алгоритм.
Алгоритм 2. Построение паросочетания наибольшего
веса в двудольном графе $$G=(A,B,E)$$ с заданными весами
вершин доли $$A$$.
Упорядочить элементы множества $$A$$ по убыванию весов: $$A=\{a_{1},a_2,\ldots, a_{k}\}$$, $$w(a_{1} )\ge w(a_{2} )\ge \ldots \ge w(a_{k})$$
$$X:=\varnothing$$
$$M:=\varnothing$$
for $$i:=1$$ to $$k$$ do
if в $$G$$ существует
увеличивающая
цепь $$P$$ относительно $$M$$,
начинающаяся в вершине $$a_{i}$$
then $${ X:=X\cup \{
a_{i}\}$$ ; $$M:=M\otimes P}$$
Если для поиска увеличивающей цепи применить метод поиска в ширину, как
описано выше, то время поиска будет пропорционально числу ребер. Общая
трудоемкость алгоритма будет $$O(mk)$$, где $$k$$ -
число ребер
в доле $$A$$.
Жадные алгоритмы и матроиды
Жадными (градиентными) называют алгоритмы, действующие по принципу
"максимальный выигрыш на каждом шаге". Такая стратегия не всегда
ведет
к конечному успеху - иногда выгоднее сделать не наилучший, казалось бы,
выбор на очередном шаге с тем, чтобы в итоге получить оптимальное решение.
Но для некоторых задач применение жадных алгоритмов оказывается
оправданным. Одной из самых известных задач такого рода является задача об
оптимальном каркасе. Существует общая теория, обосновывающая применимость
жадных алгоритмов к задачам определенного типа, к которому относится и
рассмотренный в предыдущей лекции алгоритм Крускала. В этой лекции будет дан набросок этой теории. Затем будет рассмотрено применение жадного
алгоритма в сочетании с методом увеличивающих путей для решения задачи
о паросочетании наибольшего веса в двудольном графе со взвешенными
вершинами.
Матроиды
Когда возник вопрос о том, каковы обстоятельства, при которых жадный
алгоритм результативен, или иначе - что особенного в тех задачах, для
которых он дает точное решение, оказалось, что математическая теория,
с помощью которой что-то в этом можно прояснить, уже существует. Это теория
матроидов, основы которой были заложены Уитни в работе 1935 г. Целью
создания теории матроидов было изучение комбинаторного аспекта линейной
независимости, а в дальнейшем обнаружились разнообразные применения
понятия матроида, первоначально совсем не имевшиеся в виду.
Определение. Матроидом называется
пара $$M=(E,\Phi)$$, где $$E$$ -
конечное непустое множество, $$\Phi$$ - семейство
подмножеств множества $$E$$, удовлетворяющее условиям:
(1) если $$X\in \Phi$$ и $$Y\subseteq X$$,
то $$Y\in \Phi$$ ;
(2) если $$X\in \Phi$$, $$Y\in \Phi$$ и $$|X| < |Y|$$, то существует
такой элемент $$a\in Y-X$$, что $$X\cup (a)\in \Phi$$.
Элементы множества $$E$$ называются элементами матроида,
а множества из семейства $$\Phi$$ - независимыми множествами
матроида. Максимальное по включению независимое множество называют базой матроида. Из аксиомы (2)
следует,
что все базы матроида состоят из одинакового количества элементов.
Если $$E$$ - множество строк некоторой матрицы,
а $$\Phi$$ состоит
из всех линейно независимых множеств строк этой матрицы,
то пара $$(E,\Phi)$$ образует матроид,
называемый матричным
матроидом.
Другим важным типом матроидов являются графовые матроиды. Пусть $$G=(V,E)$$ - обыкновенный граф. Подмножество множества $$E$$ назовем ациклическим, если подграф,
образованный ребрами этого подмножества,
не содержит циклов, т.е. является лесом.
Теорема 1. Если $$G=(V,E)$$ - обыкновенный граф, $$\Phi$$ - семейство всех ациклических подмножеств
множества $$E$$, то
пара $$M_{G} =(E,\Phi )$$ является матроидом.
Доказательство. Аксиома (1) выполняется, так как всякое
подмножество ациклического множества, очевидно, является ациклическим.
Докажем, что выполняется и (2). Пусть $$X$$ и $$Y$$ -
два
ациклических множества и $$|X| \lt |Y|$$. Допустим, что не существует
такого
ребра $$e\in Y$$, что множество $$X\cup \{ e\}$$ является
ациклическим. Тогда при добавлении любого ребра из множества $$Y$$
к множеству $$X$$ образуется цикл. Это означает, что концы каждого
такого ребра принадлежат одной компоненте связности остовного подграфа,
образованного ребрами множества $$Y$$. Тогда каждая область связности
подграфа $$X$$ содержится в какой-нибудь области связности
подграфа $$Y$$.
Но компоненты связности каждого из этих подграфов - деревья,
а дерево с $$k$$ вершинами содержит ровно $$k-1$$ ребер.
Следовательно, в этом случае число ребер в $$Y$$ не превосходило бы
числа ребер в $$X$$, что противоречит
условию $$|X| < |Y|$$.
Базами графового матроида являются все каркасы графа. Для связного графа
это будут все его остовные деревья.
Теорема Радо-Эдмондса
Рассмотрим общий тип оптимизационных задач, формулируемых следующим
образом. Дано произвольное конечное множество $$E$$ и некоторое
семейство $$\Phi$$ его подмножеств. Для каждого элемента $$x\in
E$$
задан его вес - положительное число $$w(x)$$. Вес множества $$X\subseteq E$$ определяется как сумма весов его элементов. Требуется
найти множество наибольшего веса, принадлежащее $$\Phi$$.
В эту схему укладываются многие известные задачи,
например задача о независимом множестве графа ( $$E$$ -
множество вершин графа, вес каждой вершины равен 1,
а $$\Phi$$ состоит из всех независимых множеств) или
задача о паросочетании ( $$E$$ - множество ребер графа, вес
каждого
ребра равен 1, $$\Phi$$ состоит из всех паросочетаний). В задаче об
оптимальном каркасе, рассмотренной в предыдущей лекции, требуется найти
каркас минимального, а не максимального веса, ее можно свести к задаче на
максимум. Действительно, пусть $$w$$ - заданная весовая функция
на
множестве ребер графа и требуется найти каркас минимального веса. Пусть $$a$$ - число, большее, чем веса всех ребер в данном графе.
Рассмотрим
новую весовую функцию $$w'$$, полагая что $$w'(e)=a-w(e)$$
для каждого
ребра $$e$$. Очевидно, что ациклическое множество наибольшего веса
относительно весовой функции $$w'$$ будет каркасом наименьшего веса
относительно весовой функции $$w$$ и обратно. Таким образом, задача об
оптимальном каркасе эквивалентна задаче построения ациклического множества
максимального веса. Последнюю будем называть задачей об оптимальном
каркасе на максимум. Она тоже является задачей рассматриваемого общего
типа: $$E$$ - множество ребер графа, $$\Phi$$
состоит из всех
ациклических множеств. К этой задаче применимы рассмотреннные в предыдущей лекции алгоритмы Прима и Крускала, если в первом из них на каждом шаге
выбирать ребро не минимального, а максимального веса, а во втором
упорядочивать ребра не по возрастанию, а по убыванию весов.
Модифицированный таким образом алгоритм Крускала будем называть
максимизирующим алгоритмом Крускала.
Сформулируем теперь жадный алгоритм для решения этой общей задачи.
Чтобы отличать этот алгоритм от других жадных алгоритмов, назовем его СПО
(Сортировка и Последовательный Отбор).
Алгоритм 1. Алгоритм СПО
Упорядочить элементы множества $$E$$ по убыванию весов: $$E=\{e_1,e_2\ldots e_{m}\}$$, $$w(e_{1} )\ge w(e_{2})\ge \ldots \ge w(e_{m} )$$.
$$A:=\varnothing$$
for $$i:=1$$ to $$m$$ do
if $$A\cup \{e_{i}\} \in
\Phi$$ then $$A:=A\cup \{e_{i}\}$$
Максимизирующий алгоритм Крускала является примером алгоритма этого типа.
Уместен вопрос: каким условиям должно удовлетворять семейство $$\Phi$$
для того, чтобы при любой весовой функции $$w$$ алгоритм СПО находил
оптимальное решение? Исчерпывающий ответ дает следующая теорема
Радо-Эдмондса.
Теорема 2. Если $$M=(E,\Phi)$$ - матроид, то для
любой весовой функции $$w\colon E\texto R^{+}$$ множество $$A$$, найденное
алгоритмом СПО, будет множеством наибольшего веса из $$\Phi$$.
Если же $$M=(E,\Phi )$$ не является матроидом, то найдется такая
функция $$w\colon E\texto R^{+}$$, что $$A$$ не будет множеством
наибольшего веса из $$\Phi$$.
Доказательство. Предположим, что $$M=(E,\Phi)$$ является матроидом
и $$A=\{a_{1},a_{2}\ldots a_{n}\}$$ - множество, построенное
алгоритмом СПО, причем $$w(a_{1})\ge w(a_{2})\ge \ldots \ge
w(a_{n})$$.
Очевидно, $$A$$ является базой матроида.
Пусть $$B=\{b_{1},b_{2}\ldots
b_{k} \}$$ - любое другое независимое множество
и $$w(b_{1} )\ge w(b_{2})\ge \ldots \ge w(b_{k})$$.
Так как $$A$$ - база, то $$k\le n$$.
Покажем, что $$w(a_{i} )\ge w(b_{i} )$$
для каждого $$i\in \{1\ldots k\}$$.
Действительно, положим $$X=\{a_{1}\ldots a_{i-1} \}$$, $$Y=\{ b_{1}\ldots b_{i-1},b_{i}\}$$ для некоторого $$i$$.
Согласно условию (2) определения матроида, в множестве $$Y$$
имеется такой элемент $$b_{j}$$, что $$b_{j} \notin X$$ и
множество $$X\cup \{b_{j}\}$$ - независимое. В соответствии с алгоритмом,
элементом наибольшего веса, который может быть добавлен к $$X$$ так,
чтобы получилось независимое множество, является $$a_{i}$$.
Следовательно, $$w(a_{i} )\ge w(b_{j} )\ge w(b_{i})$$.
Теперь предположим, что $$M=(E,\Phi)$$ не является матроидом.
Допустим
сначала, что нарушается условие (1), т.е. существуют такие подмножества $$X$$ и $$Y$$ множества $$E$$, что $$X\in
\Phi$$, $$Y\subset X$$ и $$Y\notin \Phi$$. Определим
функцию $$w$$
следующим образом:
$$w(x)=\left\{\begin{aligned} 1, \text{если } x\in Y, \\ 0,
\text{если } x \notin Y.
\end{aligned}\right.$$
Алгоритм СПО сначала будет рассматривать все элементы
множества $$Y$$.
Так как $$Y\notin \Phi$$, то не все они войдут в построенное
алгоритмом
множество $$A$$. Следовательно, w(A) < |Y|. В то же
время имеется
множество $$X\in \Phi$$, такое, что $$w(X)=|Y|$$. Таким
образом,
в этом случае алгоритм СПО строит не оптимальное множество. Если же
условие (1) выполнено, а не выполняется условие (2), то существуют такие
подмножества $$X$$ и $$Y$$ множества $$E$$,
что $$X\in \Phi$$, $$Y\in \Phi$$, |X| < |Y|
и $$X\cup \{ x\} \notin \Phi$$
для каждого $$x\in Y$$. Выберем такое $$\varepsilon$$,
что $$0 < \varepsilon < \frac{|Y|}{|X|} -1$$, и определим
функцию $$w$$
следующим образом:
$$w(x)=\left\{\begin{aligned} 1+\varepsilon, \text{если } x\in X, \\
1, \text{если } x\in Y-X, \\ 0, \text{если } x\notin
X\cup Y.
\end{aligned}\right.$$
Алгоритм СПО сначала выберет все элементы множества $$X$$, а затем
отвергнет все элементы из $$Y-X$$. В результате будет построено
множество $$A$$ с весом $$w(A)=(1+\varepsilon )|X| < |Y|$$,
которое не
является оптимальным, так как $$W(Y)=|Y|$$.
Максимизирующий алгоритм Крускала - это алгоритм СПО, применяемый к
семейству ациклических множеств ребер графа. Из теорем 1 и 2 следует, что
он действительно решает задачу об оптимальном каркасе. В то же время
существует много жадных алгоритмов, не являющихся алгоритмами типа СПО.
Примером может служить алгоритм Прима. Эти алгоритмы не попадают под
действие теоремы Радо-Эдмондса, для их обоснования нужна иная
аргументация.
Если для некоторой конкретной задачи удалось установить применимость
к ней
алгоритма СПО, это не значит, что все проблемы позади. Этот алгоритм
внешне очень прост, но он включает операцию проверки принадлежности
множества семейству $$\Phi$$, эффективное выполнение которой может
потребовать дополнительных усилий. В алгоритме Крускала, например, для
этого применяются специальные структуры данных. Ниже рассмотрим еще один
пример, когда для успешного решения задачи алгоритм СПО комбинируется
с методом увеличивающих путей для задачи о паросочетании, рассмотренным в
лекции 12.
Взвешенные паросочетания
Рассмотрим следующую задачу. Дан двудольный граф $$G=(A,B,E)$$ и
для
каждой вершины $$x\in A$$ задан положительный
вес $$w(x)$$. Требуется
найти такое паросочетание в этом графе, чтобы сумма весов вершин
из доли $$A$$, инцидентных ребрам паросочетания, была максимальной.
Эту задачу иногда интерпретируют следующим образом. $$A$$ - это множество работ, а $$B$$ - множество
работников.
Ребро в графе $$G$$ соединяет
вершину $$a\in A$$ с вершиной $$b\in B$$, если
квалификация
работника $$b$$ позволяет ему выполнить работу $$a$$. Каждая
работа
выполняется одним работником. Выполнение работы $$a$$ принесет
прибыль $$w(a)$$. Требуется так распределить обязанности работников, чтобы
максимизировать общую прибыль. Покажем, что эта задача может быть решена
алгоритмом СПО в сочетании с методом чередующихся цепей.
Множество $$X\subseteq A$$ назовем отображаемым, если в графе $$G$$
существует паросочетание $$M$$, насыщающее все вершины из $$X$$. $$M$$ в этом случае будем называть отображением для $$X$$.
Пусть $$\Phi$$ - семейство всех отображаемых множеств.
Теорема 3. Пара $$(A,\Phi)$$ является матроидом.
Доказательство. Условие (1) определения матроида, очевидно,
выполняется. Докажем, что выполняется и условие (2).
Пусть $$X\in \Phi$$, $$Y\in \Phi$$, $$|X| < |Y|$$.
Рассмотрим подграф $$H$$ графа $$G$$, порожденный всеми
вершинами из $$X\cup Y$$ и всеми смежными
с ними вершинами из доли $$B$$.
Пусть $$M_{X}$$ - отображение для $$X$$.
Так как $$M_{X}$$ не является наибольшим паросочетанием
в графе $$H$$, то по теореме 6 относительно
него в этом графе существует увеличивающая цепь. Одним из концов этой цепи
является свободная относительно $$M_{X}$$ вершина $$a\in
Y$$. После
увеличения паросочетания $$M_{X}$$ с использованием этой цепи, как
было
описано выше, получим паросочетание $$M'$$, отображающее множество $$X\cup \{a\}$$. Следовательно, $$X\cup \{a\} \in
\Phi$$.
Даже если бы в задаче требовалось найти только отображаемое множество
наибольшего веса, проверка принадлежности множества семейству $$\Phi$$
требовала бы и нахождения соответствующего отображения, т.е.
паросочетания. На самом же деле построение паросочетания входит в условие
задачи. Комбинируя СПО с алгоритмом поиска увеличивающих цепей, получаем
следующий алгоритм.
Алгоритм 2. Построение паросочетания наибольшего
веса в двудольном графе $$G=(A,B,E)$$ с заданными весами
вершин доли $$A$$.
Упорядочить элементы множества $$A$$ по убыванию весов: $$A=\{a_{1},a_2,\ldots, a_{k}\}$$, $$w(a_{1} )\ge w(a_{2} )\ge \ldots \ge w(a_{k})$$
$$X:=\varnothing$$
$$M:=\varnothing$$
for $$i:=1$$ to $$k$$ do
if в $$G$$ существует
увеличивающая
цепь $$P$$ относительно $$M$$,
начинающаяся в вершине $$a_{i}$$
then $${ X:=X\cup \{
a_{i}\}$$ ; $$M:=M\otimes P}$$
Если для поиска увеличивающей цепи применить метод поиска в ширину, как
описано выше, то время поиска будет пропорционально числу ребер. Общая
трудоемкость алгоритма будет $$O(mk)$$, где $$k$$ -
число ребер
в доле $$A$$.
