Големина на текста:
Темата: ДЪРВЕТА
ДЪРВЕТА
Основни нови понятия
Основните нови понятия са дърво, корен, кореново дърво, поддърво, връх на дърво,
предшественик, наследник на връх, листо, дължина на път.
Изложение на учебното съдържание по темата
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

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

За да разгледате всички страници от този документ натиснете тук.

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

Основните нови понятия са дърво, корен, кореново дърво, поддърво, връх на дърво, предшественик, наследник на връх, листо, дължина на път.
Изпратен от:

на 2008-03-13
Добавен в:
Общи материали
по Математика
Статистика:
116 сваляния
виж още
 
Подобни материали
 

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

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
·
557
·
28
·
1,150
·
781
·
2
·
1

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

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

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

Матрици, детерминанти, интеграли и т.н..................
1 2 3 4 5 » 11
 
Онлайн тестове по Математика
Тест по Математика за 7-ми клас на тема "Неравенства в триъгълник"
тематичен тест по Математика за Ученици от 7 клас
Тестът съдържа 10 въпроса със 4 предполагаеми отговора като всеки въпрос има един верен отговор. Предназначен е за ученици от 7-ми клас.
(Труден)
10
31
1
2 мин
22.08.2018
Тест по математика за IV-ти клас
междинен тест по Математика за Ученици от 4 клас
Тестът е предназначен за междинна диагностика на ученици от ІV клас при проверка на знанията след първи учебен срок. Въпросите са само с един верен отговор.
(Много лесен)
11
12
1
3 мин
05.04.2019
» виж всички онлайн тестове по математика

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

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

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

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

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

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

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

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