MAX-CUT: вероятностное округление/Задачи/ex-maxcut-trivial-greedy-1-2 — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
(Массовая правка: замена :Нерешенные задачи]] на :Решенные задачи]])
(не показано 13 промежуточных версий этого же участника)
Строка 1: Строка 1:
Студент предлагает для задачи [[MAX-CUT]] приближенный алгоритм с точностью ½:
+
Студент предлагает для невзвешенной задачи [[MAX-CUT]] приближенный алгоритм с точностью ½:
 
* положить первую вершину в одну часть, последнюю — в другую,
 
* положить первую вершину в одну часть, последнюю — в другую,
 
* затем по-очереди добавлять оставшиеся вершины, к множеству, с которым у этой вершины меньше ребер-связей.
 
* затем по-очереди добавлять оставшиеся вершины, к множеству, с которым у этой вершины меньше ребер-связей.
Строка 5: Строка 5:
 
Прав ли студент?
 
Прав ли студент?
  
[[Category:На проверку]]
 
  
<latex>
+
<!--Вообще-то, решения уже есть-->
Покажем, что алгоритм строит максимальный разрез f графа G(V, E) с точностью 1/2.                                 
+
 
\\1. Процесс завершаемый, поскольку на каждом шаге алгоритм добавляет либо в T, либо в S одну вершину, а количество вершин в графе конечна.
+
[[Категория:Решенные задачи]]
\\2. Для $\forall u \in V$, обозначим $in(u) = \{(u, v)$, где $v \in S$, если $u \in S$; или $v \in T$, если $u \in T\}$ и
+
$out(u) = \{(u, v)$, где $v \in S$, если $u \in T$; или $v \in T$, если $u \in S\}$
+
\\$\forall u \in V, |in(u)| < |out(u)|$ (по построению)
+
\\Следовательно, количество внутренних рёбер меньше чем количество наружных рёбер.
+
Значит, количество наружных ребер, которые и образуют разрез построенный алгоритмом > m/2 , где m -  
+
количество ребер в графе. Так как оптимальный разрез opt не может быть больше чем m, то получаем
+
\\$f ≥ \frac{m}{2} ≥ \frac{opt}{2}$ => $f ≥ \frac{opt}{2}$
+
\\Студент прав.
+
</latex>
+

Версия 15:49, 20 мая 2020

Студент предлагает для невзвешенной задачи MAX-CUT приближенный алгоритм с точностью ½:

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

Прав ли студент?