Формула Кэли

Сколько разных сетей можно натянуть на n городов, соединив их без циклов и без изолированных точек? На языке графов: сколько остовных деревьев у полного графа $K_n$? Малые случаи прозаичны: для $K_2$ — единственная дорога, для $K_3$ — три «вилки», для $K_4$ — уже 16. Закономерность на глаз не видна, а ответ красив: формула Кэли даёт ровно $n^{n-2}$. Показатель $n-2$ выглядит загадочно — и в этом вся прелесть.

Главная улика — код Прюфера (1918). Каждому дереву на n помеченных вершинах сопоставим последовательность длины n−2 из номеров вершин: найди минимальный лист, запиши номер его соседа, откуси лист — и так, пока не останутся две вершины. Строку можно однозначно развернуть обратно в дерево, а вариантов строки ровно $n^{n-2}$, каждый учтён один раз. Биекция закрыла вопрос подсчёта одним махом — и заодно объяснила странный показатель: дереву остаётся «что сказать» ровно n−2 раза, потому что у дерева всегда есть листья.

Зачем считать деревья. Масштаб: для $K_{10}$ формула даёт $10^8$ — сто миллионов остовных деревьев, и на этом фоне почти чудом выглядят жадные алгоритмы Прима и Крускала, находящие минимальный остов за секунды, не перебирая и тысячной доли вариантов. Химия: изомеры углеводородов — это непомеченные деревья, и Кэли пришёл к подсчёту деревьев именно от молекул. Олимпиадная практика: через код Прюфера доказывают, например, что в случайном дереве ожидаемое число листьев около $n/e$. Полный контекст остовов — в уроке деревья и алгоритмы.

Быстрая проверка руками — любимое задание семинаров: перечислите деревья $K_4$ (четыре звезды плюс двенадцать путей), затем возьмите $K_5$ и выписывайте коды Прюфера — строки из цифр 1–5 длины 3, всего $5^3=125$. Напомнить, чем дерево отличается от «просто графа», поможет термин дерево, стартовая точка по теме — урок графы: основы, а все формулы графов на одном листе — в шпаргалке по графам и алгоритмам.