Теорема кэли деревья доказательство

Содержание

§ 9. Формула Кэли
Теорема Кэли о числе помеченных деревьев с р вершинами
§ 9. Формула Кэли
Art of Math

§ 9. Формула Кэли

Рассмотренная ниже теорема была доказана Кэли, который исследовал деревья в связи с химическими структурными формулами.

Теорема 3.6 (Кэли). Число различных деревьев, которые можно построить на n данных вершинах, равно: t_n= n n  2 .

 Чтобы вывести эту формулу, воспользуемся методом Прюфера. Обозначим элементы данного множества вершин V, расположенные в некотором фиксированном порядке, числами

Установим теперь взаимно однозначное соответствие между множеством всех деревьев с n вершинами и множеством всех векторов (со значениями компонент от 1 до n) длиной (n2).

Согласно третьему свойству, в дереве Т найдутся хотя бы две концевые вершины. Обозначим через b₁ первую концевую вершину в последовательности (*), а через e₁=(a₁,b₁) — соответствующее концевое ребро. Удалив из дерева Т ребро e₁ и вершину b₁, мы получим новое дерево T₁. Для T₁ найдётся первая в последовательности (*) концевая вершина b₂ с ребром e₂=(a₂,b₂), удалив которое, получим дерево T₂ и т.д. Наконец, после удаления ребра e_n_₂=(a_n_₂,b_n_₂) останется единственное ребро e_n_₁=(a_n_₁,b_n_₁), соединяющее две оставшиеся вершины. Тогда вектор (a₁,a₂. a_n_₂) однозначно определяется деревом Т и двум различным деревьям соответствуют разные векторы.

Пример. Составить вектор для данного дерева (см. рис. 3.19, а).

Решение.. Концевая вершина с самым маленьким номером — 3, а соответствующее ей концевое ребро — (2,3); поэтому принимаем a₁=2 и отсекаем это ребро.

Концевая вершина с самым маленьким номером из оставшихся  4, а соответствующее ей концевое ребро — (2,4). Принимаем a₂=2 и отсекаем ребро. Дальше действуем аналогично.

Требуемый вектор имеет вид: (2,2,2,1,6,6).

Покажем теперь, что, наоборот, каждое дерево Т однозначно определяется вектором

Выполним обратное построение. Если дан вектор (**), то в последовательности (*) находится первая вершина b₁, которая не содержится в (**). Это определяет ребро e₁=(a₁,b₁).

Рис. 3.19.

Далее следует удалить вершины a₁ из (**) и b₁ из (*) и продолжить построение аналогичным образом.

Пример. Восстановить дерево Т, если соответствующий ему вектор имеет вид: (1, 2, 2, 1, 4, 4, 4). (’’)

Решение. Данный вектор содержит 7 компонент, значит, дерево Т должно иметь 7+2=9 вершин. Выпишем последовательность номеров этих вершин:

1. В (’) находим первое число, которое не содержится в (’’), — 3. Получаем ребро (1,3).

Зачёркиваем 1 в (’’), 3 в (’); остаётся:

(2, 2, 1, 4, 4, 4), (’’) 1, 2, 4, 5, 6, 7, 8, 9. (’)

2. Первое число в (’), которое не содержится в (’’), — это 5. Получаем следующее ребро — (2,5). Зачёркиваем 2 в (’’), 5 в (’); остаётся:

Повторяя эту процедуру ещё 3 раза, получим рёбра (2,6), (1,2), (4,1), (4,7), (4,8). После этого в последовательности (’) останутся два числа — 4 и 9. Они определяют последнее ребро (4,9). Так как все рёбра известны, восстанавливаем дерево Т, схема которого приведена на рис. 3.19, б.

Итак, нам удалось установить взаимно однозначное соответствие между множеством всех деревьев с n вершинами и множеством всех векторов (со значениями компонент от 1 до n) длиной (n2). Из взаимно однозначного соответствия этих множеств следует их равномощность.

В векторе (a₁, a₂. a_n_₂) каждая компонента может принимать любое из n значений (от 1 до n), а всего таких компонент n. По следствию из теоремы о мощности прямого произведения можно составить n n  2 различных векторов вида (a₁,a₂. a_n_₂), а значит, и различных деревьев с n вершинами будет столько же. 

Источник

Теорема Кэли о числе помеченных деревьев с р вершинами

Дерево есть связный подграф без циклов.
Индукцией по числу вершин можно показать, что (p,q) дерево имеет q = p-1 рёбер.
Теорема Кэли: Число помеченных деревьев (tp) с p вершинами равно: р р-2 , то есть t_p = p p-2 .

Доказательство Прюфера: Пусть Т – помеченное дерево с р вершинами. V = . Сопоставим дереву Т единственный набор (а₁,… ,а_р-2) из V p-2 следующим образом: выберем в Т висячую вершину v с наименьшей пометкой а₁. Аналогично найдём наименьшую пометку а₂ для висячей вершины в дереве Т-v (Т без v и без принадлежащих v ребер). И так далее… Остается одно ребро из Т. Набор А=(а₁,…,а_р-2) построен для дерева Т. Так как каждое a_i было единственно, то набор а единственный. Так как каждое помеченное дерево с р вершинами связано с единственным набором длины (р-2) из р элементов и так как число таких наборов равно р р-2 , то число помеченных деревьев t_p ≤ p p-2 . Продолжим Доказательство теоремы следующим утверждением.

Утверждение: Каждому набору длины (р-2) из 1,2,…,р можно единственным образом сопоставить помеченное дерево с р вершинами 1,2,…,р

Доказательство: Индукция по р.
Базис: р=2. V = . p p-2 = 2 2-2 = 2 0 = 1. Набор а пуст. Для пустого набора существует только одно помеченное дерево.
Предположение индукции: предположим, что каждому набору длины (р-3) из 1,2,….,р-1 можно единственным образом сопоставить помеченное дерево с (р-1) вершинами 1,2,…,р-1.
Шаг: Пусть а= длины (р-2) составлен из элементов 1,2,…,р. Пусть b₁ есть наименьшее натуральное число не из набора a и пусть с=2,…,c_p-2> есть набор длины (р-3), полученный из а уменьшением всех его координат, больших чем b₁, на единицу, тогда набор с состоит из чисел, принадлежащих множеству V_P-1=. Так как набор с состоит из (р-3) элементов, то по предположению индукции набору с соответствует единственное помеченное дерево Т_р-1 с (р-1) вершинами из V_p-1. Прибавим в дерево Т_р-1 по единице к каждой пометке вершины, превосходящей (b₁-1), затем введём вершину р с пометкой b₁ и соединим её с вершиной, помеченной числом а₁ в дереве Т_р-1. Однозначно получено дерево с р вершинами, соответствующее набору а. чтд.

Продолжим доказательство теоремы Кэли. Так как каждому из р р-2 наборов длины (р-2) однозначно соответствует помеченное дерево с р вершинами, то t_p ≥ p p-2 . Получили: t_p ≤ p p-2 и t_p ≥ p p-2 , следовательно t_p = p p-2 . чтд.

Перечисление графов. Производящая функция для числа помеченных графов с р вершинами
Матричная теорема Кирхгофа о деревьях
Функции алгебры логики
Раскрашивание планарных графов. Теорема о пяти красках. Теорема о четырех красках
Многочлен циклов (цикловой индекс), теорема Пойа
Лемма Бернсайда о числе орбит группы подстановок
Подсчет числа размещений, перестановок, сочетаний без повторов и с повторами
Теорема Поста о функциональной полноте
Деревья, их характеристика, каркасы (остовы)
Двойственные функции. Теорема о суперпозиции двойственных функций. Принцип двойственности
Теорема Форда-Фалкерсона о максимальном потоке
Двудольные и бихроматические графы
Теорема об устойчивости. Теорема об неустойчивости
Системы различных представителей, теорема Холла о совершенном паросочетании в двудольном графе
Класс монотонных функций и его замкнутость относительно суперпозиции
Сравнение мощностей. Теорема Кантора-Бернштейна.
Формула Эйлера

Источник

§ 9. Формула Кэли

Теорема 3.6 (Кэли). Число различных деревьев, которые можно построить на n данных вершинах, равно: t_n= n n  2 .

Пример. Составить вектор для данного дерева (см. рис. 3.19, а).

Требуемый вектор имеет вид: (2,2,2,1,6,6).

Покажем теперь, что, наоборот, каждое дерево Т однозначно определяется вектором

Рис. 3.19.

Далее следует удалить вершины a₁ из (**) и b₁ из (*) и продолжить построение аналогичным образом.

Пример. Восстановить дерево Т, если соответствующий ему вектор имеет вид: (1, 2, 2, 1, 4, 4, 4). (’’)

1. В (’) находим первое число, которое не содержится в (’’), — 3. Получаем ребро (1,3).

Зачёркиваем 1 в (’’), 3 в (’); остаётся:

(2, 2, 1, 4, 4, 4), (’’) 1, 2, 4, 5, 6, 7, 8, 9. (’)

Источник

Art of Math

Начнем с определений.
Определение 10. Дерево — связный граф, в котором нет циклов.
Определение 11. Висячая вершина — это вершина, локальная степень которой равна 1.

В доказательстве теоремы Кэли нам поможет небольшая лемма.

Лемма (Теорема 5). В любом дереве найдутся по-крайней мере две висячие вершины.

Доказательство. Выберем произвольную вершину дерева. Если ее степень 1, лемма доказана, иначе будем идти из нее по дереву, отмечая при обходе пройденные вершины, постоянно направляясь только в неотмеченные вершины. Понятно, что этот процесс кончится, тогда мы окажемся в вершине, из которой можно попасть либо только в помеченные вершины, либо совсем никуда. Если мы можем попасть в помеченные вершины, значит в графе есть цикл, что невозможно, значит степень вершины, в которой мы оказались равна 1. То есть, одну висячую вершину мы получили. Теперь снова сделаем все вершины непомеченными и повторим процесс для полученной нами висячей вершины, получив вторую висячую вершину. Лемма доказана.

Теорема 6 (Кэли). Число различных деревьев, которые можно построить на множестве V из N вершин, равно N^(N-2).

Доказательство.
Пронумеруем вершины от 1 до N. Рассмотрим произвольное дерево T такое, что множество его вершин совпадает с V. Выберем в нем висячую вершину с наименьшим номером, которая соединена с вершиной b1, удалим ее вместе с ребром из T, получив дерево T1. Будем вновь проделывать такие же операции с получающимися деревьями, пока оставшийся граф не будет представлять из себя две вершины при ребре. Таким образом, мы получим последовательность bi=.
Докажем теперь, что каждая такая последовательность однозначно задает дерево. Просто приведем алгоритм, который однозначно восстанавливает дерево. Алгоритм рекуррентный, докажем его по индукции.
Для N=3, восстановление очевидно.
Скажем сперва, что достаточно очевидно, что те числа от 1 до N, которых нет в bi, являются висячими вершинами изначального дерева T. Тогда возьмем самое маленькое такое число А. Понятно, что в изначальном дереве Т оно соединено ребром с вершиной b1. Проведем такое ребро. Теперь рассмотрим весь наш граф без вершины А и ребра (A, b1). Далее по индукции. Заметим, что минимальную вершину следует выбирать из тех, которые подходят по описанному условию и еще не были выбраны.Таким образом, мы установили, что каждая такая последовательность однозначно задает дерево. Количество таких последовательностей равно N^(N-2), что очевидно.
Теорема доказана.

Источник