MAXimal | |
добавлено: 26 Mar 2012 1:00 Содержание [скрыть] Код Прюфера. Формула Кэли. Количество способов сделать граф связнымВ данной статье мы рассмотрим так называемый код Прюфера, который представляет из себя способ однозначного кодирования помеченного дерева с помощью последовательности чисел. С помощью кодов Прюфера демонстрируется доказательство формулы Кэли (задающей количество остовных деревьев в полном графе), а также решение задачи о количестве способов добавить в заданный граф рёбра, чтобы превратить его в связный. Примечание. Мы не будем рассматривать деревья, состоящие из единственной вершины, — это особый случай, на котором многие утверждения вырождаются. Код ПрюфераКод Прюфера — это способ взаимно однозначного кодирования помеченных деревьев с Хотя использовать код Прюфера для хранения и оперирования с деревьями нецелесообразно из-за специфичности представления, коды Прюфера находят применения в решении комбинаторных задач. Автор — Хейнц Прюфер (Heinz Prüfer) — предложил этот код в 1918 г. как доказательство формулы Кэли (см. ниже). Построение кода Прюфера для данного дереваКод Прюфера строится следующим образом. Будем Таким образом, код Прюфера для заданного дерева — это последовательность из Алгоритм вычисления кода Прюфера легко реализовать с асимптотикой const int MAXN = ...; int n; vector<int> g[MAXN]; int degree[MAXN]; bool killed[MAXN]; vector<int> prufer_code() { set<int> leaves; for (int i=0; i<n; ++i) { degree[i] = (int) g[i].size(); if (degree[i] == 1) leaves.insert (i); killed[i] = false; } vector<int> result (n-2); for (int iter=0; iter<n-2; ++iter) { int leaf = *leaves.begin(); leaves.erase (leaves.begin()); killed[leaf] = true; int v; for (size_t i=0; i<g[leaf].size(); ++i) if (!killed[g[leaf][i]]) v = g[leaf][i]; result[iter] = v; if (--degree[v] == 1) leaves.insert (v); } return result; } Впрочем, построение кода Прюфера можно реализовать и за линейное время, что описывается в следующем разделе. Построение кода Прюфера для данного дерева за линейное времяПриведём здесь простой алгоритм, имеющий асимптотику Суть алгоритма заключается в хранении движущегося указателя На первый взгляд, такое невозможно, ведь в процессе построения кода Прюфера номера листьев могут как увеличиваться, так и уменьшаться. Однако легко заметить, что уменьшения происходят только в единственном случае: кода при удалении текущего листа его предок имеет меньший номер (этот предок станет минимальным листом и удалится из дерева на следующем же шаге кода Прюфера). Таким образом, случаи уменьшения можно обработать за время const int MAXN = ...; int n; vector<int> g[MAXN]; int parent[MAXN], degree[MAXN]; void dfs (int v) { for (size_t i=0; i<g[v].size(); ++i) { int to = g[v][i]; if (to != parent[v]) { parent[to] = v; dfs (to); } } } vector<int> prufer_code() { parent[n-1] = -1; dfs (n-1); int ptr = -1; for (int i=0; i<n; ++i) { degree[i] = (int) g[i].size(); if (degree[i] == 1 && ptr == -1) ptr = i; } vector<int> result; int leaf = ptr; for (int iter=0; iter<n-2; ++iter) { int next = parent[leaf]; result.push_back (next); --degree[next]; if (degree[next] == 1 && next < ptr) leaf = next; else { ++ptr; while (ptr<n && degree[ptr] != 1) ++ptr; leaf = ptr; } } return result; } Прокомментируем этот код. Основная функция здесь — Как легко видно по коду, асимптотика алгоритма действительно составляет Некоторые свойства кодов Прюфера
Восстановление дерева по его коду ПрюфераДля восстановления дерева достаточно заметить из предыдущего пункта, что степени всех вершин в искомом дереве мы уже знаем (и можем посчитать и сохранить в некотором массиве Таким образом, мы нашли первое ребро, удалённое кодом Прюфера. Добавим это ребро в ответ, затем уменьшим степени Будем повторять эту операцию, пока не просмотрим весь код Прюфера: искать минимальную вершину с В конце концов у нас останется только две вершины с Алгоритм завершён, искомое дерево построено. Реализовать этот алгоритм легко за время Приведём соответствующую реализацию (где функция vector < pair<int,int> > prufer_decode (const vector<int> & prufer_code) { int n = (int) prufer_code.size() + 2; vector<int> degree (n, 1); for (int i=0; i<n-2; ++i) ++degree[prufer_code[i]]; set<int> leaves; for (int i=0; i<n; ++i) if (degree[i] == 1) leaves.insert (i); vector < pair<int,int> > result; for (int i=0; i<n-2; ++i) { int leaf = *leaves.begin(); leaves.erase (leaves.begin()); int v = prufer_code[i]; result.push_back (make_pair (leaf, v)); if (--degree[v] == 1) leaves.insert (v); } result.push_back (make_pair (*leaves.begin(), *--leaves.end())); return result; } Восстановление дерева по коду Прюфера за линейное времяДля получения алгоритма с линейной асимптотикой можно применить тот же самый приём, что применялся для получения линейного алгоритма вычисления кода Прюфера. В самом деле, для нахождения листа с наименьшим номером необязательно заводить структуру данных для извлечения минимума. Вместо этого можно заметить, что, после того как мы находим и обрабатываем текущий лист, он добавляет в рассмотрение только одну новую вершину. Следовательно, мы можем обойтись одним движущимся указателем вместе с переменной, хранящей в себе текущий минимальный лист: vector < pair<int,int> > prufer_decode_linear (const vector<int> & prufer_code) { int n = (int) prufer_code.size() + 2; vector<int> degree (n, 1); for (int i=0; i<n-2; ++i) ++degree[prufer_code[i]]; int ptr = 0; while (ptr < n && degree[ptr] != 1) ++ptr; int leaf = ptr; vector < pair<int,int> > result; for (int i=0; i<n-2; ++i) { int v = prufer_code[i]; result.push_back (make_pair (leaf, v)); --degree[leaf]; if (--degree[v] == 1 && v < ptr) leaf = v; else { ++ptr; while (ptr < n && degree[ptr] != 1) ++ptr; leaf = ptr; } } for (int v=0; v<n-1; ++v) if (degree[v] == 1) result.push_back (make_pair (v, n-1)); return result; } Взаимная однозначность соответствия между деревьями и кодами ПрюфераС одной стороны, для каждого дерева существует ровно один код Прюфера, соответствующий ему (это следует из определения кода Прюфера). С другой стороны, из корректности алгоритма восстановления дерева по коду Прюфера следует, что любому коду Прюфера (т.е. последовательности из Таким образом, все деревья и все коды Прюфера образуют взаимно однозначное соответствие. Формула КэлиФормула Кэли гласит, что количество остовных деревьев в полном помеченном графе из Имеется много доказательств этой формулы, но доказательство с помощью кодов Прюфера наглядно и конструктивно. В самом деле, любому набору из Количество способов сделать граф связнымМощь кодов Прюфера заключается в том, что они позволяют получить более общую формулу, чем формулу Кэли. Итак, дан граф из Выведем готовую формулу для решения этой задачи. Обозначим через Таким образом, для подсчёта количества способов оказывается важным, какие степени имеют все Пусть Если С учётом того, что каждое ребро, смежное с Для получения ответа на задачу надо просуммировать эту формулу по всевозможным допустимым наборам Для свёртывания этой формулы воспользуемся определением мультиномиального коэффициента: Сравнивая эту формулу с предыдущей, получаем, что если ввести обозначение то после сворачивания ответ на задачу равен: (Эта формула верна и при Задачи в online judgesЗадачи в online judges, в которых применяются коды Прюфера:
|