Вопрос 31 из 42

Практика: доказательства и комбинаторные модели

Разрез графа: почему можно разделить хотя бы половину рёбер

От чтения к действию

А теперь — вы

У очередной вершины три уже размещённых соседа в первой доле и один во второй. Куда её помещает доказанный алгоритм и сколько нынешних рёбер пересекается?

Разберёмся в теме

В любом конечном неориентированном графе без петель можно разделить вершины на две доли так, чтобы между ними проходило не меньше половины всех рёбер. Случайный независимый выбор доли даёт это число в среднем, а последовательное помещение вершины напротив большинства её уже размещённых соседей строит подходящее разделение.

Объяснение и примеры

Частые вопросы

Где найти подробное решение?

Перейдите по ссылке «Объяснение и примеры» над этим блоком. Там разобрана тема текущего вопроса.

Можно ли попробовать снова?

Да. После проверки можно изменить ответ. Переход к следующему вопросу не блокируется результатом, а личный счёт не сохраняется.