Для любого графа G = (V,E) существует разрез размера не меньше |E|/2. Знаю доказательство через вероятностный метод, а есть что попроще?

задан 17 Июл '15 23:06

Мне кажется, вероятностное доказательство со случайным распределением вершин на две группы по принципу "бросания монетки" как раз удовлетворяет критерию максимальной простоты (а заодно и краткости). Может быть, имелось в виду что-то другое? Типа доказательства, до которого "проще додуматься" (пусть и более длинного)?

(17 Июл '15 23:39) falcao

Не могу судить о простоте других методов, так как знаю только вероятностный. Но да, интересно именно наиболее естественный, до которого проще додуматься и который использует минимальный инструментарий

(18 Июл '15 0:12) sapere aude

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

(18 Июл '15 0:22) falcao
10|600 символов нужно символов осталось
2

Рассмотрим произвольный разрез. Допустим, что имеется вершина, у которой менее половины исходящих из неё рёбер принадлежит разрезу. Тогда переведём её в другое множество. При этом число рёбер разреза увеличится. Будем так делать, пока есть вершины с указанным свойством. За число шагов, не превышающее количество рёбер, этот процесс окончится. Поскольку у каждой вершины не менее половины исходящих рёбер будет принадлежать разрезу, общее число рёбер, входящих в разрез, составит не меньше половины от общего числа рёбер.

ссылка

отвечен 18 Июл '15 0:26

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,231
×164

задан
17 Июл '15 23:06

показан
341 раз

обновлен
18 Июл '15 0:26

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru