Формула Кэли и коды Прюфера: n^(n−2) деревьев и как выбрать одно наугад

Если ты умеешь строить код Прюфера и восстанавливать дерево по коду и понимаешь, почему отсюда следует n^(n−2), листай до «Теперь сам».

Как думаешь, сколько деревьев на пяти вершинах

Пять пронумерованных серверов надо соединить кабелями без циклов так, чтобы все были связаны, - это дерево. Сколько существует разных схем? Перебрать четыре ребра из десяти возможных - 210 наборов, и часть из них содержит цикл.

Прежде чем читать дальше, попробуй угадать формулу по маленьким n: на двух вершинах одно дерево, на трёх - три (любая вершина в середине), на четырёх - шестнадцать. Что дальше?

На что это похоже

Разборка мебели с подписью деталей. Каждый раз снимаешь самую маленькую по номеру деталь, которая держится только за одну другую, и записываешь, к чему она крепилась. Запись получается короткой - по числу на каждую снятую деталь, кроме двух последних, - и по ней однозначно собирается та же мебель: сборщик знает, сколько раз каждая деталь встречается в записи, а значит, сколько к ней крепится.

Механизм: отрезать наименьший лист

КОДИРОВАНИЕ (дерево → код длины n − 2)
повторить n − 2 раза:
    лист = наименьший по номеру лист
    записать его соседа, удалить лист

ДЕКОДИРОВАНИЕ (код → дерево)
степень(v) = 1 + сколько раз v встречается в коде
для каждого x в коде по порядку:
    лист = наименьшая вершина со степенью 1
    ребро лист – x;  степень(x) −= 1 (лист больше не участвует)
последние две вершины со степенью 1 соединить ребром

Почему соответствие взаимно однозначное. Лист никогда не попадает в код, пока он лист: вершина встречается в коде ровно (степень − 1) раз - столько её соседей удалят до неё самой. Значит, по коду восстанавливаются степени, а по степеням - какая вершина на каждом шаге была наименьшим листом, и, следовательно, всё дерево. Каждая последовательность длины n − 2 декодируется в дерево, разные коды - в разные деревья. Последовательностей n^(n−2) - столько и деревьев.

С кучей для наименьшего листа оба направления работают за O(n log n).

Правило

Деревьев на n пронумерованных вершинах ровно n^(n−2) (формула Кэли). Код Прюфера сопоставляет дереву последовательность из n − 2 чисел: отрезать наименьший лист и записать его соседа. Обратно: степень = 1 + число появлений в коде, и рёбра восстанавливаются правилом «наименьший лист - к очередному числу кода». Случайный код даёт равномерно случайное дерево.

Разбор: туда и обратно на шести вершинах

рёбра: 0–3, 1–3, 2–3, 3–4, 4–5

КОДИРОВАНИЕ
листья {0, 1, 2, 5}:  наименьший 0, сосед 3 → код 3
листья {1, 2, 5}:     1 → 3
листья {2, 5}:        2 → 3;  теперь 3 - лист (остался сосед 4)
листья {3, 5}:        3 → 4
код: 3 3 3 4

ДЕКОДИРОВАНИЕ
степени: 3 встречается трижды → 4;  4 один раз → 2;  остальные 1
x = 3: наименьший лист 0 → ребро 0–3, степень 3 стала 3
x = 3: лист 1 → 1–3, степень 3 → 2
x = 3: лист 2 → 2–3, степень 3 → 1 - теперь 3 лист
x = 4: наименьший лист 3 → 3–4, степень 4 → 1
остались листья 4 и 5 → ребро 4–5

Дерево восстановилось полностью. Вершина 3 со степенью четыре встретилась в коде трижды, листья 0, 1, 2, 5 - ни разу: это всегда так, и по коду сразу видно, какие вершины - листья.

Разбор: проверка формулы перебором

Программа перебирает все наборы из n − 1 ребра полного графа, считает среди них деревья для n от 2 до 7 и сравнивает с n^(n−2), затем проверяет, что все 1296 кодов длины 4 дают 1296 РАЗНЫХ деревьев на шести вершинах.

import heapq
import itertools
import random


def v_kod(n, rebra):                  # дерево → код Прюфера
    sosedi = {v: set() for v in range(n)}
    for u, v in rebra:
        sosedi[u].add(v)
        sosedi[v].add(u)
    listya = [v for v in range(n) if len(sosedi[v]) == 1]
    heapq.heapify(listya)
    kod = []
    for _ in range(n - 2):
        list_ = heapq.heappop(listya)  # наименьший лист
        otec = sosedi[list_].pop()
        kod.append(otec)               # записать его соседа
        sosedi[otec].discard(list_)
        if len(sosedi[otec]) == 1:
            heapq.heappush(listya, otec)
    return kod


def iz_koda(n, kod):                  # код Прюфера → дерево
    stepen = [1] * n
    for x in kod:
        stepen[x] += 1                # степень = 1 + появлений в коде
    listya = [v for v in range(n) if stepen[v] == 1]
    heapq.heapify(listya)
    rebra = []
    for x in kod:
        list_ = heapq.heappop(listya)
        rebra.append((list_, x))
        stepen[x] -= 1
        if stepen[x] == 1:
            heapq.heappush(listya, x)
    rebra.append(tuple(listya))        # два последних листа
    return rebra


def derevo_li(n, rebra):               # n − 1 ребро и связность
    kto = list(range(n))
    def koren(x):
        while kto[x] != x:
            x = kto[x]
        return x
    for u, v in rebra:
        a, b = koren(u), koren(v)
        if a == b:
            return False
        kto[a] = b
    return True


for n in range(2, 8):                  # перебор: остовы полного графа
    vse_rebra = list(itertools.combinations(range(n), 2))
    derevev = sum(derevo_li(n, r)
                  for r in itertools.combinations(vse_rebra, n - 1))
    print(f"n={n}: деревьев {derevev}, n^(n−2) = {n ** (n - 2)}")

n = 6                                  # код ↔ дерево - биекция
vidennye = set()
for kod in itertools.product(range(n), repeat=n - 2):
    d = iz_koda(n, list(kod))
    assert derevo_li(n, d) and v_kod(n, d) == list(kod)
    vidennye.add(frozenset(frozenset(e) for e in d))
print(f"n=6: кодов {n ** (n - 2)}, разных деревьев {len(vidennye)}")

rng = random.Random(29)
kod = [rng.randrange(10) for _ in range(8)]
print("дерево на 10 вершинах из кода", kod)
print(sorted(tuple(sorted(e)) for e in iz_koda(10, kod)))

n=2: деревьев 1, n^(n−2) = 1
n=3: деревьев 3, n^(n−2) = 3
n=4: деревьев 16, n^(n−2) = 16
n=5: деревьев 125, n^(n−2) = 125
n=6: деревьев 1296, n^(n−2) = 1296
n=7: деревьев 16807, n^(n−2) = 16807
n=6: кодов 1296, разных деревьев 1296
дерево на 10 вершинах из кода [8, 1, 5, 9, 9, 4, 1, 8]
[(0, 8), (1, 2), (1, 4), (1, 8), (3, 5), (4, 7), (5, 9), (6, 9), (8, 9)]

Перебор подтвердил формулу до семи вершин (на семи - 16 807 деревьев из 54 264 наборов рёбер), а 1296 кодов дали 1296 разных деревьев - соответствие взаимно однозначно. Последняя строка - дерево, полученное из случайного кода: так генерируют тестовые деревья, равномерные по всем возможным.

Что ломается без этого

Первая ошибка - генерировать «случайное дерево», присоединяя каждую новую вершину к случайной старой: получаются в основном неглубокие деревья, и распределение далеко от равномерного; тесты на таких деревьях пропускают ошибки, проявляющиеся на длинных цепочках. Вторая - в кодировании брать не наименьший лист, а любой: код перестаёт быть однозначным, и декодирование вернёт другое дерево. Третья - путать пронумерованные деревья с непомеченными формами: форм на пяти вершинах всего три (цепочка, звезда, «вилка»), а пронумерованных деревьев - 125. Четвёртая - считать остовы произвольного графа по Кэли: формула верна только для полного графа.

Зачем это в работе

Генерация тестов для алгоритмов на деревьях: случайный код Прюфера даёт по-настоящему равномерное дерево, в том числе длинные цепочки и звёзды. Компактное хранение и передача деревьев: n − 2 числа вместо n − 1 пары. Подсчёт вариантов в задачах проектирования сетей: сколько всего способов связать n узлов без избыточных связей. А для числа остовов произвольного графа есть матричная теорема о деревьях Кирхгофа - определитель, обобщающий формулу Кэли.

Теперь сам

Восстанови дерево на пяти вершинах 0..4 по коду 1 1 3. Какие вершины - листья?