Големина на текста:
Темата: ДЪРВЕТА
ДЪРВЕТА
Основни нови понятия
Основните нови понятия са дърво, корен, кореново дърво, поддърво, връх на дърво,
предшественик, наследник на връх, листо, дължина на път.
Изложение на учебното съдържание по темата
I. Логическо описание
Идея за дърво може да бъде дадена като се разгледа схема на родословно дърво. На
нея са посочени родителите и прародителите на дадено лице.
Нина Петър
Нина
Ангел
Ангел
Тодор
Петър Елена Петър Бояна Васил Иван Диана
Анна Лилия
Фиг. 85
Неориентиран свързан граф без цикли се нарича дърво.
На фиг. 86, 87, 88 са дадени примери за графи, от които само графите от фиг.86 и
фиг.87 са дървета, а от фиг.88 не е, тъй като съдържа цикли.
A
B
G E
F
CD
H
A
B
D
E
C
G F H
A
BD
E
F
C
G
H
Фиг. 86Фиг. 87 Фиг. 88
За да се усвои смисъла на понятието дърво, в час може да се коментира следната
задача:
Задача 1: Графът от фиг.88 не е дърво. Да се отстранят необходимия брой ребра, за
да се получи дърво.
1
Темата: ДЪРВЕТА
За всяко дърво са в сила следните свойства:
1)Ако Т е дърво, то между всеки два върха на Т съществува единствен прост път.
(В графа от фиг.88 има върхове, между които съществува повече от един прост път.)
Вярно е и обратното свойство:
2)Ако в един граф между всеки два върха съществува единствен прост път, то
графът е дърво.
В редица случаи един от върховете на дървото се избира като специален и се
нарича корен на дървото. След избора на корен на дървото, може да се определи посоката
на всяко от ребрата и те да станат ориентирани. Например, дървото от фиг.86 е без корен,
а дървото от фиг.87 – с корен върха А.
Върховете, които са свързани с корена се наричат негови наследници (деца), а
коренът – техен предшественик (родител). Наследниците на корена са върхове от първо
ниво за дървото. Наследниците на върховете от първо ниво са наследници от второ ниво и
т.н. Върхове, които нямат наследници се наричат листа.
Максималното ниво се нарича височина на дървото (фиг.89).
A
B
D E F
C
G H
L K
ниво 1
ниво 2
ниво 3
ниво 4
в
и
с
о
ч
и
н
а
Фиг. 89
Коренът на всяко дърво няма предшественик, а всеки връх, с изключение на
корена, има точно един предшественик.
Всеки връх на дървото може да се разглежда като корен на отделно дърво,
наречено поддърво.
Броят на поддърветата с корен върха t се нарича степен на върха t. Степента на
листата е 0.
При графичното представяне на дърветата е прието коренът да се изобразява най-
отгоре.
С цел усвояване на въведените основни понятия в час може да се разгледа следната
задача:
Задача 2: За дърветата от фиг.87 и фиг.89 да се посочат:
а) наследниците на върховете А, В, С, F;
б) предшествениците на върховете А, В, F, Н;
в) листата на дървото;
г) поддървото с корен върха В;
д) височината на дървото;
2
Темата: ДЪРВЕТА
е) степените на върховете А, В, F, Н.
II. Представяне на дървета
Съществуват четири основни начина за представяне на дървета:
чрез вложени множества
A
B
C
D
E
F
Фиг. 90 Представяне чрез вложени множества
чрез вложени скоби
( A (B(D)(E)(F)) (C) )
Фиг. 91 Представяне чрез вложени скоби
графично
A
B
D
E
F
C
Фиг. 92 Графично представяне чрез ацикличен свързан граф
чрез стъпаловидно отместване
A
B
D
E
F
C
Фиг. 93 Представяне чрез стъпаловидно отместване
На фиг.90, фиг.91, фиг.92 и фиг.93 са показани различни начини за нагледно
представяне на дърво. Дървото T={A, B, C, D, E, F} на тези фигури е следното: върхът A е
корен на дървото, а T
1
={C} и T
2
={B, D, E, F} са негови поддървета (върхът C е листо). В
дървото T
2
={B, D, E, F} корен е върхът B, а поддървета са {D},{E},{F} (D, E и F са листа).
Следващата задача не изисква програмна реализация и цели усвояване на начините
за представяне на дърво.
Задача 3: Нека е дадено дървото от фиг.87. Да се представи по четирите основни
начина.
Път в дърво T е такава последователност от върхове t
1
, t
2
, t
3
..., t
k
, че върхът t
i
е
3

Това е само предварителен преглед

За да разгледате всички страници от този документ натиснете тук.
Последно свалили материала:
ДАТА ИНФОРМАЦИЯ ЗА ПОТРЕБИТЕЛЯ
19 окт 2020 в 01:04 в момента не учи на 62 години
11 юни 2016 в 12:30 студент на 27 години от Шумен - Шуменски университет "Епископ Константин Преславски", факулетет - Факултет по математика и информатика, специалност - Информатика, випуск 2016
18 мар 2016 в 18:40 студент на 26 години от София - Технически университет, факулетет - Факултет Компютърни системи и управление, специалност - Компютърни системи и технологии, випуск 2014
02 дек 2014 в 13:34 в момента не учи на 47 години от София
10 апр 2014 в 23:41 учител на 44 години
13 фев 2014 в 08:24 учител на 44 години от Хасково - ОУ "Шандор Петьофи", випуск 2016
18 яну 2014 в 16:30 ученик на 26 години от Видин - ПМГ "Екзарх Антим I", випуск 2013
12 дек 2013 в 14:16 студент на 27 години от София - Университет по библиотекарство и информационни технологии, факулетет - KN, випуск 2016
 
Подобни материали
 

Упражнения по Приложна математика

01 юли 2008
·
997
·
5
·
392
·
1,046
·
2
·
1

Упражнения по Приложна математика 2 семестър - Матрици, Детерминанти и др.
 

Лекции по дискретна математика

09 яну 2008
·
1,137
·
127
·
24,966
·
1,230
·
2

Множества, релации, функции, комбинаторика, графи, дървета, най-къс път в граф, алгоритъм на Дийкстра, формални взици и граматики, автоматни езици, крайни автомати, булеви функции, затворени мн-ва от булеви функции...
 

Задачи по математика

15 мар 2007
·
2,051
·
4
·
120
·
1,431
·
14

Кое е най-голямото цяло число, което е решение на двете неравенства.....?
 

Задачи, давани на конкурсен изпит за прием в математическите гимназии

04 юни 2007
·
555
·
28
·
1,150
·
781
·
1

Задачи от конкурсни изпити по математика, заеднос решенията.
 

Пищови по висша математика

15 окт 2007
·
3,635
·
5
·
2,036
·
2,254
·
1
·
2

Матрици, детерминанти, интеграли и т.н..................
1 2 3 4 5 » 11
 
Онлайн тестове по Математика
Тест по математика за 9-ти клас - входно ниво
входен тест по Математика за Ученици от 9 клас
Тестът съдържа 10 задачи със затворен отговор. Само един от посочените отговори е верен. Служи за изходно ниво от 8-ми и входно ниво за 9-ти клас.
(Лесен)
10
263
1
07.10.2016
Национално външно оценяване по математика за IV-ти клас
изпитен тест по Математика за Ученици от 4 клас
Тест от НВО за 2018 г. от Министерство на образованието и науката, даден на 14 май 2018 г. Всички въпроси имат само по един верен отговор.
(Лесен)
19
10
1
7 мин
08.07.2019
» виж всички онлайн тестове по математика

Дървета (приложна математика)

Материал № 111254, от 13 мар 2008
Свален: 116 пъти
Прегледан: 291 пъти
Качен от:
Предмет: Математика
Тип: Общ материал
Брой страници: 4
Брой думи: 408
Брой символи: 3,395

Потърси помощ за своята домашна:

Имаш домашна за "Дървета (приложна математика)"?
Намери бързо решение, с помощтта на потребители на Pomagalo.com:

Намери частен учител

инж. Анна Йолчева
преподава по Математика
в град Варна
с опит от  12 години
200 37

Иванка Димитрова
преподава по Математика
в град Варна
с опит от  36 години
49 37

виж още преподаватели...
Последно видяха материала
Сродни търсения