Студопедия  
Главная страница | Контакты | Случайная страница

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Деревья

Читайте также:
  1. В это время дети-Деревья окружают его, не дают уйти.
  2. Деревья
  3. Деревья
  4. Если мы срубаем деревья, или убиваем насекомых и червей во Вриндаване, думая, что они подобны деревьям, насекомым и червям других мест, мы совершаем апарадху.
  5. Если мы срубаем деревья, или убиваем насекомых и червей во Вриндаване, думая, что они подобны деревьям, насекомым и червям других мест, мы совершаем апарадху.
  6. Живущие на деревьях
  7. Не менее одной четверти площади каждого Поместья должно быть занято дикорастущими деревьями.
  8. РУНЫ И ДЕРЕВЬЯ
  9. Саймон стал рядом и смотрел на горизонт из-за плеча Ральфа. Штаны Мориса вздохнули и треснули, он скинул их, побежал за деревья и тотчас вернулся.

Деревом называется связный граф, не имеющий циклов. Известно, что всякое нетривиальное дерево имеет не менее двух висящих вершин (вершины степени 1). Это Следует из того, что если T – дерево с p вершинами и q ребрами, то

q=p-1.

Теорема. (Кэли 1897). Число tp помеченных деревьев порядка p равно

tp=pp-2.

Доказательство.

Первый подход (Кэли) Установим соответствие между помеченными деревьями и функциями, отображающими множество из p-2 объектов в множество из p объектов. Например, если p=5, то существует 53 функций из {a,b,c} в {v1, v2, v3, v4, v5}. Эти функции перечисляются многочленом

(v1+ v2+ v3+ v4+ v5)3. (16)

Слагаемые этого многочлена сопоставляются функциям естественным образом. Например, соответствует постоянной функции f(x)=v4, слагаемое отвечает трем функциям, которые отображают только один элемент в v1, два других – в v3, 6v2v3v5 дает шесть функций, отображающих по одному элементу в v2, v3 и v5. Теперь, умножая многочлен на v1v2v3v4v5 и получая

(v1+ v2+ v3+ v4+ v5)3 v1v2v3v4v5 (17)

устанавливаем тем самым соответствие между слагаемыми из этого произведения и помеченными деревьями порядка 5. Это соответствие с использованием слагаемого = v1v2v3v4v5) выглядит так

 
 


 

Заметим, что в деревьях, соответствующих слагаемому , степень вершины, помеченной числом k, равна показателю степени у vk. Справедливость этого высказывания может быть установлена и в общем случае. Следовательно, число помеченных деревьев, у которых вершины, помеченные числом k, имеют степень dk, равно полиномиальному коэффициенту

. (18)

Кэли проиллюстрировал это соответствие для p=6 и не стал рассатривать другие случаи, заметив: “Сразу видно, что доказательство, данное для этого частного случая, применимо при любом значении p”.

Второй подход (Прюфер 1917). Пусть дерево с n вершинами, помеченными числами 1, …,n. Свяжем с этим деревом последовательность натуральных чисел i1,…,in-2, построенную следующим образом:

1)положим j=0;

2)повторим следующий процесс n-2 раза:

увеличим значение j на единицу; найдем в дереве лист, помеченный натуральным числом с наименьшим значением. Пусть это значение kj, и пусть отцом листа kj является вершина, помеченная числом ij. Выберем значение ij в качестве j-ого элемента последовательности. Удалим в дереве ребро (ij,kj).

После исполнения этого алгоритма начальное дерево преобразуется в дерево, состоящее из одного ребра либо (in-2,n), либо, в случае in-2=n, – из ребра (n,n-1).




Дата добавления: 2015-09-11; просмотров: 20 | Поможем написать вашу работу | Нарушение авторских прав

Производящие функции для перестановок. | Решение линейных рекуррентных уравнений. | Числа Стирлинга первого и второго рода. | Представление перестановок в циклической форме. | Цикловые классы (типы). | Перестановки без единичных циклов | Композиции чисел. | Принцип включения и исключения. | Число способов, которыми можно пометить граф. | Связные графы. |


lektsii.net - Лекции.Нет - 2014-2024 год. (0.007 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав