Это цикл статей о том, как распознавать задачи, решаемые жадными алгоритмами, писать строгие доказательства корректности этих алгоритмов, а также о том, как распознавать задачи для которых жадные алгоритмы не применимы.
О жадных алгоритмах многие знают ещесо школы с университета. В любом курсе по алгоритмам выделена хотя бы одна небольшая глава посвященная жадным алгоритмам. В частности, в книге Томаса Кормена «Алгоритмы. Построение и анализ» освящается эта тема.
В данной статье будет одна задача, для которой будет приведено строгое доказательство на почти формальном математическом языке.
Пусть задан неориентированный граф $inline$G=(V, E)$inline$. Нужно найти максимальный подграф $inline$G^* = (V^*, E^*) \subset G $inline$ такой, чтобы выполнялось условие:
$$display$$\forall v \in V^*: 2 \le deg(v) \le |V^*|-2$$display$$
Первое, что приходит на ум — итеративно исключать на каждом шаге вершину
$$display$$v_n: deg(v_n) < 2 \vee deg(v_n) > |V_n|-2 $$display$$
Здесь следует пояснить, что на $inline$n$inline$-ом шаге рассматривается граф $inline$G_n = (V_n, E_n)$inline$, который отличается от исходного графа тем, что в нем отсутствуют вершины $inline$ \{ v_1, v_2, ..., v_{n-1} \} $inline$.
Данную процедуру мы можем повторять до тех пор пока в графе есть хоть какие-нибудь вершины и пока можно хоть какую-нибудь вершину удалить из графа, поэтому такой алгоритм работает за конечное число шагов.
В результате, мы получим граф $inline$G_N=(V_N,E_N)$inline$, который удовлетворяет нашим условиям, но будет ли такой граф максимальным?
В данной задаче ответ на последний вопрос положительный. Указанный граф действительно будет максимальным из всех существующих. Чтобы строго доказать это, сформулируем лемму:
Определение:
Множеством всех решений данной задачи $inline$Sol(G)$inline$ назовем множество всех графов, которые подходят под ограничения, т.е.
$$display$$Sol(G) \stackrel{def}{=} \{\dot G = (\dot V,\dot E) \subset G\ |\ \forall v \in \dot V: 2 \le deg(v) \le |\dot V|-2 \}$$display$$
Лемма:
Не существует $inline$ \dot G \in Sol(G_n)\ \exists v \in V_n: deg(v) < 2 \vee deg(v) > |V_n|-2 $inline$
Доказательство:
Пусть лемма не верна. Тогда предположим, что существует решение $inline$ \dot G $inline$, включающее в себя вершину $inline$ v $inline$
$$display$$v \in \dot V: deg(v) < 2 \vee deg(v) > |\dot V|-2 $$display$$
По определению $inline$ \dot G \subset G_n $inline$, следовательно $inline$ \forall v \in V_n: deg(v) $inline$ не меньше, чем $inline$ deg(v) $inline$ в его подграфе $inline$ \dot G $inline$. Поэтому первое неравенство выполняться не может.
Аналогичное рассуждение можно провести со вторым неравенством: В исходном графе $inline$ V_n $inline$ не может быть меньше вершин не инидентных с данной, чем в его подграфе. Следовательно, мы получили противоречие, наше предположение не верно и такого решения действительно не существует.
Ч.т.д.
Тогда, в силу леммы, на каждом шаге алгоритма, мы можем выкидывать вершины графа, не подходящие под начальные ограничения, тем самым не теряя решений. Жадность алгоритма доказана!
В следующих статьях я постараюсь привести еще больше задач в решении которых имеют место жадные алгоритмы. Надеюсь данная тема будет интересна определенному кругу читателей хабра. Буду рад вашим замечаниям и конструктивным предложениям по улучшению данного материала.
Вступление
О жадных алгоритмах многие знают еще
В данной статье будет одна задача, для которой будет приведено строгое доказательство на почти формальном математическом языке.
Задача
Пусть задан неориентированный граф $inline$G=(V, E)$inline$. Нужно найти максимальный подграф $inline$G^* = (V^*, E^*) \subset G $inline$ такой, чтобы выполнялось условие:
$$display$$\forall v \in V^*: 2 \le deg(v) \le |V^*|-2$$display$$
Решение:
Первое, что приходит на ум — итеративно исключать на каждом шаге вершину
$$display$$v_n: deg(v_n) < 2 \vee deg(v_n) > |V_n|-2 $$display$$
Здесь следует пояснить, что на $inline$n$inline$-ом шаге рассматривается граф $inline$G_n = (V_n, E_n)$inline$, который отличается от исходного графа тем, что в нем отсутствуют вершины $inline$ \{ v_1, v_2, ..., v_{n-1} \} $inline$.
Данную процедуру мы можем повторять до тех пор пока в графе есть хоть какие-нибудь вершины и пока можно хоть какую-нибудь вершину удалить из графа, поэтому такой алгоритм работает за конечное число шагов.
В результате, мы получим граф $inline$G_N=(V_N,E_N)$inline$, который удовлетворяет нашим условиям, но будет ли такой граф максимальным?
Доказательство жадности:
В данной задаче ответ на последний вопрос положительный. Указанный граф действительно будет максимальным из всех существующих. Чтобы строго доказать это, сформулируем лемму:
Определение:
Множеством всех решений данной задачи $inline$Sol(G)$inline$ назовем множество всех графов, которые подходят под ограничения, т.е.
$$display$$Sol(G) \stackrel{def}{=} \{\dot G = (\dot V,\dot E) \subset G\ |\ \forall v \in \dot V: 2 \le deg(v) \le |\dot V|-2 \}$$display$$
Лемма:
Не существует $inline$ \dot G \in Sol(G_n)\ \exists v \in V_n: deg(v) < 2 \vee deg(v) > |V_n|-2 $inline$
Доказательство:
Пусть лемма не верна. Тогда предположим, что существует решение $inline$ \dot G $inline$, включающее в себя вершину $inline$ v $inline$
$$display$$v \in \dot V: deg(v) < 2 \vee deg(v) > |\dot V|-2 $$display$$
По определению $inline$ \dot G \subset G_n $inline$, следовательно $inline$ \forall v \in V_n: deg(v) $inline$ не меньше, чем $inline$ deg(v) $inline$ в его подграфе $inline$ \dot G $inline$. Поэтому первое неравенство выполняться не может.
Аналогичное рассуждение можно провести со вторым неравенством: В исходном графе $inline$ V_n $inline$ не может быть меньше вершин не инидентных с данной, чем в его подграфе. Следовательно, мы получили противоречие, наше предположение не верно и такого решения действительно не существует.
Ч.т.д.
Тогда, в силу леммы, на каждом шаге алгоритма, мы можем выкидывать вершины графа, не подходящие под начальные ограничения, тем самым не теряя решений. Жадность алгоритма доказана!
Заключение
В следующих статьях я постараюсь привести еще больше задач в решении которых имеют место жадные алгоритмы. Надеюсь данная тема будет интересна определенному кругу читателей хабра. Буду рад вашим замечаниям и конструктивным предложениям по улучшению данного материала.