MAX-CUT: вероятностное округление/Задачи/ex-maxcut-trivial-greedy-1-2 — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
Larisa (обсуждение | вклад) |
||
Строка 5: | Строка 5: | ||
Прав ли студент? | Прав ли студент? | ||
− | [[Category: | + | [[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> |
Версия 19:03, 12 декабря 2014
Студент предлагает для задачи MAX-CUT приближенный алгоритм с точностью ½:
- положить первую вершину в одну часть, последнюю — в другую,
- затем по-очереди добавлять оставшиеся вершины, к множеству, с которым у этой вершины меньше ребер-связей.
Прав ли студент?