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 приближенный алгоритм с точностью ½:
- положить первую вершину в одну часть, последнюю — в другую,
- затем по-очереди добавлять оставшиеся вершины, к множеству, с которым у этой вершины меньше ребер-связей.
Прав ли студент?