Математика · объяснение и практика
Разрез графа: почему можно разделить хотя бы половину рёбер
Доказываем существование разреза через среднее число пересекающих рёбер и строим его последовательным выбором доли; отличаем гарантию от максимума и от полной двудольности.

В теме Доказательства и комбинаторные модели · Учебная карта
Главная мысль
В любом конечном неориентированном графе без петель можно разделить вершины на две доли так, чтобы между ними проходило не меньше половины всех рёбер. Случайный независимый выбор доли даёт это число в среднем, а последовательное помещение вершины напротив большинства её уже размещённых соседей строит подходящее разделение.
Среднее по всем разделениям даёт существование одного
Назовём разрезом рёбра, концы которых оказались в разных долях. Сами доли содержат все вершины и не пересекаются, но не обязаны иметь одинаковый размер. Для каждого ребра независимо от других рассуждений посмотрим на два его конца. Если каждый конец независимо выбирает долю с вероятностью половина, два из четырёх равновероятных назначений разделяют концы.
Индикатор пересечения данного ребра имеет ожидание половина. Складывая индикаторы по m рёбрам, получаем средний размер разреза m/2. Индикаторы соседних рёбер не требуется объявлять независимыми: для сложения ожиданий это условие не нужно. Среди конечного числа разделений хотя бы одно имеет результат не ниже среднего. Иначе все результаты были бы строго меньше среднего, и их взвешенная сумма тоже была бы меньше него.
Последовательный выбор превращает существование в построение
Разместим вершины в любом фиксированном порядке. Перед помещением очередной посчитаем её соседей среди уже размещённых: a в первой доле и b во второй. Если a≥b, поместим вершину во вторую, иначе в первую. Тогда она создаёт max(a,b) пересекающих рёбер, не меньше (a+b)/2. При равенстве подходит любая доля.
Учитываем каждое ребро ровно однажды, когда размещён его более поздний конец. В этот момент второй конец уже имеет долю, а будущие решения их не изменят. Поэтому суммы a+b по всем шагам дают m, а число созданных пересекающих рёбер не меньше m/2. Связи с ещё не размещёнными вершинами пока не участвуют в счёте, но не теряются: их проверят на соответствующем будущем шаге. Эта привязка к позднему концу доказывает общую гарантию локального выбора.
Пример
В графе с вершинами А,Б,В,Г есть рёбра АБ,АВ,АГ,БВ,ВГ. Примените последовательный выбор в порядке А,Б,В,Г, помещая первую вершину в первую долю.
После А вершину Б ставим во вторую долю и пересекаем АБ. У В уже есть по одному соседу в каждой доле; выберем первую, пересечётся БВ. У Г два прежних соседа А и В в первой доле, поэтому Г идёт во вторую и пересекает оба ребра. Всего четыре из пяти. Гарантия требовала хотя бы три; фактический результат может быть больше округлённой половины.
Нижняя гарантия не равна максимальному разрезу
Полученное разделение может не быть лучшим: порядок вершин и выбор при равенствах меняют конкретный результат. Доказательство гарантирует достаточное качество, а не точный максимум. Если m нечётно, целочисленный размер разреза не меньше округлённой вверх половины. В треугольнике можно пересечь два из трёх рёбер, хотя все три пересечь двумя долями невозможно.
Условие отсутствия петель существенно: петля никогда не соединяет разные доли. Для графа только из петель половинная гарантия по всем его рёбрам ложна. Изолированные вершины, наоборот, можно поместить куда угодно. Теорема не утверждает равенства численностей долей и не решает задачу выбора двух групп заданного размера. Дополнительные ограничения меняют пространство допустимых разделений и требуют отдельного доказательства.
От чтения к действию
А теперь — вы
Частые вопросы
Каждое ребро разреза должно быть независимо от остальных?
Нет. Линейность ожидания не требует независимости индикаторов. Независимый выбор долей концами нужен для расчёта вероятности пересечения одного обычного ребра.
Теорема делает весь граф двудольным?
Нет. Она находит большой набор пересекающих рёбер. Внутри долей могут остаться другие рёбра; двудольность требует отсутствия всех таких рёбер.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Почему нечётный цикл мешает раскрасить граф в два цвета
Раскрасьте граф двумя цветами по соседям, найдите конфликт на нечётном цикле и проверьте каждую компоненту вместо одной красивой части рисунка.
Открыть темуКак один набор пар даёт два способа подсчёта
Как доказать равенство двух сумм через один набор пар, выбрать учитываемую связь и проверить, что каждая сторона действительно считает те же объекты.
Открыть темуПочему математические ожидания складываются даже без независимости
Складываем ожидаемые значения зависимых величин, используем индикаторы для подсчёта событий и отделяем линейность суммы от правил для произведений и дисперсий.
Открыть тему