Начнем с определений.
Определение 10. Дерево - связный граф, в котором нет циклов.
Определение 11. Висячая вершина - это вершина, локальная степень которой равна 1.
В доказательстве теоремы Кэли нам поможет небольшая лемма.
Лемма (Теорема 5). В любом дереве найдутся по-крайней мере две висячие вершины.
Доказательство. Выберем произвольную вершину дерева. Если ее степень 1, лемма доказана, иначе будем идти из нее по дереву, отмечая при обходе пройденные вершины, постоянно направляясь только в неотмеченные вершины. Понятно, что этот процесс кончится, тогда мы окажемся в вершине, из которой можно попасть либо только в помеченные вершины, либо совсем никуда. Если мы можем попасть в помеченные вершины, значит в графе есть цикл, что невозможно, значит степень вершины, в которой мы оказались равна 1. То есть, одну висячую вершину мы получили. Теперь снова сделаем все вершины непомеченными и повторим процесс для полученной нами висячей вершины, получив вторую висячую вершину. Лемма доказана.
Теорема 6 (Кэли). Число различных деревьев, которые можно построить на множестве V из N вершин, равно N^(N-2).
Доказательство.
Пронумеруем вершины от 1 до N. Рассмотрим произвольное дерево T такое, что множество его вершин совпадает с V. Выберем в нем висячую вершину с наименьшим номером, которая соединена с вершиной b1, удалим ее вместе с ребром из T, получив дерево T1. Будем вновь проделывать такие же операции с получающимися деревьями, пока оставшийся граф не будет представлять из себя две вершины при ребре. Таким образом, мы получим последовательность bi={b1, b2, b3, ...., b(N-2)}.
Докажем теперь, что каждая такая последовательность однозначно задает дерево. Просто приведем алгоритм, который однозначно восстанавливает дерево. Алгоритм рекуррентный, докажем его по индукции.
Для N=3, восстановление очевидно.
Скажем сперва, что достаточно очевидно, что те числа от 1 до N, которых нет в bi, являются висячими вершинами изначального дерева T. Тогда возьмем самое маленькое такое число А. Понятно, что в изначальном дереве Т оно соединено ребром с вершиной b1. Проведем такое ребро. Теперь рассмотрим весь наш граф без вершины А и ребра (A, b1). Далее по индукции. Заметим, что минимальную вершину следует выбирать из тех, которые подходят по описанному условию и еще не были выбраны.Таким образом, мы установили, что каждая такая последовательность однозначно задает дерево. Количество таких последовательностей равно N^(N-2), что очевидно.
Теорема доказана.
Определение 10. Дерево - связный граф, в котором нет циклов.
Определение 11. Висячая вершина - это вершина, локальная степень которой равна 1.
В доказательстве теоремы Кэли нам поможет небольшая лемма.
Лемма (Теорема 5). В любом дереве найдутся по-крайней мере две висячие вершины.
Доказательство. Выберем произвольную вершину дерева. Если ее степень 1, лемма доказана, иначе будем идти из нее по дереву, отмечая при обходе пройденные вершины, постоянно направляясь только в неотмеченные вершины. Понятно, что этот процесс кончится, тогда мы окажемся в вершине, из которой можно попасть либо только в помеченные вершины, либо совсем никуда. Если мы можем попасть в помеченные вершины, значит в графе есть цикл, что невозможно, значит степень вершины, в которой мы оказались равна 1. То есть, одну висячую вершину мы получили. Теперь снова сделаем все вершины непомеченными и повторим процесс для полученной нами висячей вершины, получив вторую висячую вершину. Лемма доказана.
Теорема 6 (Кэли). Число различных деревьев, которые можно построить на множестве V из N вершин, равно N^(N-2).
Доказательство.
Пронумеруем вершины от 1 до N. Рассмотрим произвольное дерево T такое, что множество его вершин совпадает с V. Выберем в нем висячую вершину с наименьшим номером, которая соединена с вершиной b1, удалим ее вместе с ребром из T, получив дерево T1. Будем вновь проделывать такие же операции с получающимися деревьями, пока оставшийся граф не будет представлять из себя две вершины при ребре. Таким образом, мы получим последовательность bi={b1, b2, b3, ...., b(N-2)}.
Докажем теперь, что каждая такая последовательность однозначно задает дерево. Просто приведем алгоритм, который однозначно восстанавливает дерево. Алгоритм рекуррентный, докажем его по индукции.
Для N=3, восстановление очевидно.
Скажем сперва, что достаточно очевидно, что те числа от 1 до N, которых нет в bi, являются висячими вершинами изначального дерева T. Тогда возьмем самое маленькое такое число А. Понятно, что в изначальном дереве Т оно соединено ребром с вершиной b1. Проведем такое ребро. Теперь рассмотрим весь наш граф без вершины А и ребра (A, b1). Далее по индукции. Заметим, что минимальную вершину следует выбирать из тех, которые подходят по описанному условию и еще не были выбраны.Таким образом, мы установили, что каждая такая последовательность однозначно задает дерево. Количество таких последовательностей равно N^(N-2), что очевидно.
Теорема доказана.
Комментариев нет:
Отправить комментарий