Метод двойного подсчёта: как доказать, что сумма степеней вершин равна удвоенному числу рёбер?
На разборе сказали «по двойному подсчёту сумма степеней вершин = 2E». Я проверил на примерах — работает, но не понимаю самого приёма «двойного подсчёта». Можете объяснить идею метода и показать ещё пару применений в комбинаторных задачах?
2 ответа
Двойной подсчёт — это посчитать одну и ту же величину двумя способами и приравнять результаты. Формально: считаем число элементов некоторого множества пар двумя разными перечислениями.
Для графа берём множество пар (вершина, инцидентное ей ребро). С одной стороны, каждая вершина v вносит deg(v) таких пар → сумма равна Σ deg(v). С другой стороны, каждое ребро имеет ровно 2 конца → вносит 2 пары → всего 2E. Приравниваем: Σ deg(v) = 2E. Отсюда сразу следствие: число вершин нечётной степени всегда чётно (лемма о рукопожатиях).
Другой пример — биномиальное тождество n·2^{n−1} = Σ k·C(n,k): считаем пары (подмножество, выделенный в нём элемент). Слева: выбираем элемент (n способов), потом любое подмножество остальных (2^{n−1}). Справа: фиксируем подмножество размера k и выбираем в нём элемент (k способов), суммируем по k. Две формулы для одного множества пар — значит равны.
Кода как такового нет — это метод доказательства. Но он постоянно нужен, чтобы обосновать корректность формулы перед тем, как считать её в коде, и чтобы вывести нужное тождество прямо на контесте.
Третий частый пример — счёт «уголков»/треугольников: число путей длины 2 (центр которых — вершина v) равно Σ C(deg(v), 2). Этот же приём лежит в основе многих оценок: считаешь множество специальных конфигураций по «центрам», а потом сравниваешь с другим способом подсчёта, получая неравенство или точную формулу.