Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Тема 7.7 Деревья. Код Пруфера

 

Деревом называется всякий несвязный граф без циклов.

 
 


Граф, состоящий из изолированной вершины, тоже считается деревом.

Вершина дерева, степень которой равна 1, называется висячей.

Лесом называется граф представленный в виде объединения деревьев.

Теорема: Если у дерева n вершин, то ребер n-1.

Рассмотрим произвольное дерево с 11 вершинами, пронумерованными в произвольном порядке.

       
   
 

 


В результате возникает вопрос: сколько существует таких деревьев с 11 вершинами?

Английский математик Кэли нашел ответ на этот вопрос: деревьев с n вершинами можно создать столько, сколько существует последовательностей вида: , где и таких последовательностей будет nn-2.

Немецкий математик Пруффер продолжил решать эту проблему и указал алгоритм, согласно которому любому дереву можно поставить во взаимно-однозначное соответствие – код.

Алгоритм:

1. выбираем висячую вершину с наименьшим номером.

2. удаляем ее вместе с принадлежащим ей ребром.

3. записываем номер вершины полученного дерева ближайшей к удаленной.

4. повторяем данные действия до тех пор пока не останется две висячие вершины, связанные между собой ребром.

 

1. вершина № 2

2. записываем вершину № 1

3. выбираем вершину № 3

4. записываем вершину № 1

и т.д., в результате получаем код: (1, 1, 5, 5, 6, 6, 6, 6, 5)

И наоборот, зная код можно изобразить дерево.

Алгоритм составления дерева по коду:

1. находим наименьшее натуральное число, которое не встречается в последовательности.

2. это число – номер вершины, которую необходимо соединить с вершиной, которая встречается первой в коде.

3. находим следующее число

Дан код (1, 5, 5, 3, 6, 4).

Количество вершин = 8,

1. наименьшее число, не встречающееся в последовательности – 2

2. строим эту вершину и соединяем ребром с вершиной №1

3. аналогично перебираем все цифры не встречающиеся в последовательности до 8.

 
 


<== предыдущая лекция | следующая лекция ==>
Тема 7.6 Плоские графы | Тема 7.8 Понятие ориентированный граф (орграф)
Поделиться с друзьями:


Дата добавления: 2014-01-04; Просмотров: 2461; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.01 сек.