|
|
| Строка 22: |
Строка 22: |
| | | | |
| | | | |
| − | [[Category:На проверку]] | + | [[Category:Решенные задачи]] |
| | <!--Вообще-то, решения уже есть--> | | <!--Вообще-то, решения уже есть--> |
| − |
| |
| − | <!--[[Файл:Celyh-max-cut.pdf|Celyh-max-cut]]-->
| |
| − | <latex>
| |
| − | Решение (Целых Влада, 974 группа):
| |
| − | Дан неориентированный граф $G = (V,E)$ с весами $w_e>0$. Необходимо найти
| |
| − | разрез $(S,T)$ с максимальным весом $R(S,T)$.
| |
| − | Детерминированный 2-приближенный полиномиальный алгоритм: сначала $S = \{v_1\}, T = \{v_2\}$.
| |
| − | Каждую следующую вершину относим ко множеству, сумма весов ребер до вершин которого минимальна, т.е.
| |
| − | если $\sum_{e\in E(S,v)} w_e > \sum_{e\in E(T,v)} w_e$, то $T=T\cup \{v\}$, иначе $S=S\cup \{v\}$.
| |
| − |
| |
| − | На каждой итерации работы алгоритма выполняется:
| |
| − | \begin{align}
| |
| − | \sum_{e\in E(S,T)} w_e \geq \sum_{e\in E(S,S)} w_e + \sum_{e\in E(T,T)} w_e \label{feat}
| |
| − | \end{align}
| |
| − | в силу того, что в начале работы алгоритма это верно ($w_{(v_1,v_2)} \geq 0$), а
| |
| − | добавление вершины, например, ко множеству $S$ приводит к:
| |
| − | \begin{align*}
| |
| − | &\sum_{e\in E(S\cup \{v\},T)} w_e = \sum_{e\in E(S,T)} w_e + \sum_{e\in E(v,T)} w_e \geq
| |
| − | \sum_{e\in E(S,S)} w_e + \sum_{e\in E(T,T)} w_e +\\
| |
| − | &+ \sum_{e\in E(v,S)} w_e = \sum_{e\in E(S\cup v,S \cup v)} w_e + \sum_{e\in E(T,T)} w_e,
| |
| − | \end{align*}
| |
| − | что и утверждалось.
| |
| − |
| |
| − | Из~(\ref{feat}) следует, что
| |
| − | $$
| |
| − | 2 \cdot \sum_{e\in E(S,T)} w_e \geq \sum_{e\in E(S,T)} w_e + \sum_{e\in E(S,S)} w_e + \sum_{e\in E(T,T)} w_e = \sum_{e\in E} w_e \geq OPT,
| |
| − | $$
| |
| − | где OPT-оптимальное решение задачи. Таким образом, предложенный алгоритм является 2-приближенным.
| |
| − | </latex>
| |