Дърво (математика)

Вижте пояснителната страница за други значения на Дърво.

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

В някои източници присъства и условието дървото да съдържа поне два върха (възела).

Дърветата могат да бъдат ориентирани или неориентирани. Ориентираното дърво е ориентиран свързан граф без цикли. Някои автори налагат допълнителното ограничение ребрата (дъгите) да са ориентирани винаги към или от даден конкретен връх.

Понятието ориентирано дърво може да се въведе и по следния начин: Дървото е граф без цикли, при който:

съществува връх, към който не сочи нито едно ребро (нарича се корен),
към всеки друг връх на дървото сочи точно едно ребро,
съществува единствен път от корена до всеки връх на дървото.

Върховете, от които не излизат ребра към други върхове (т.е. нямат наследници), се наричат още листа на дървото.

Несвързан граф без цикли се нарича гора. Гората може да съдържа както дървета (с поне два върха), така и изолирани върхове.

Две са основните характеристики на дървото:

Височина или още дълбочина – Височина на даден връх е дължината на пътя (т.е. броя свързващи ребра) от корена до върха. Максималната височина на връх в едно дърво се нарича височина на това дърво.
Разклоненост – Максималният брой върхове наследници, които връх в дървото може да има, се нарича разклоненост на дървото.

Терминология

Корен – най-важният връх в дървото; няма предшественици
Родител – предшественик на наследник
Братя – върхове с общ родител
Непряк наследник – връх, който не е пряк наследник
Дете – пряк наследник
Прародител – връх, който е непряк родител
Вътрешен връх – връх, който има и родител, и дете
Външен връх (или листо) – връх, който няма наследници
Ребро – пряка връзка между два върха
Път – поредица от ребра между върховете
Дължина на път – брой на ребрата, свързващи върховете
Дълбочина на връх – дължината на пътя от корена до върха
Височина на дърво – максималната дълбочина
Гора – съвкупност от несвързани дървета

Приложение в програмирането

Основна статия: Дърво (структура от данни)

Дърво или дървовидна структура в програмирането е рекурсивна структура от данни, която се състои от върхове, които са свързани помежду си с ребра.

За дърветата са в сила твърденията:

Всеки връх може да има 0 или повече преки наследници (деца).
Всеки връх има най-много един баща. Съществува точно един специален връх, който няма предшественици – коренът (ако дървото не е празно).
Всички върхове са достижими от корена, т.е. съществува път от корена до всички тях.

В практиката често се налага да работа със съвкупност от обекти (данни). Данните, организирани в т. нар. структура от данни, позволяват обработване, така че това да доведе до подобрение качеството на работа с тях. Понякога се добавят елементи, понякога се премахват, друг могат да бъдат подредени по специфичен начин. В програмирането дървото е често използвана структура от данни, която изобразява по естествен начин всякакви йерархии от обекти и тяхната взаимосвързаност.^[1]

Дърво с разклоненост 2 се нарича двоично дърво и намира особено широко приложение като структура от данни в програмирането.

Твърдения

Между всеки два върха в едно дърво съществува единствен път. Доказателството се извършва с допускане на противоречие.
Всяко дърво с n върха съдържа точно n-1 ребра. Доказателството се извършва с пълна индукция.
За всяко дърво с височина h и разклоненост m може да се каже, че има не повече от m^h листа. Доказателството се извършва с индукция по височината на дървото.

Обхождане на дърво

Обхождане в дълбочина
Обхождане в ширина

Източници

↑ Наков, Светлин. Въведение в програмирането с Java. София, 2017. ISBN 978-954-400-055-4. с. 561-594.

„Математически енциклопедичен речник“, В. Гелерт, Х. Кестнер, З. Нойбер, ДИ Наука и изкуство, София, 1983
„Oxford Dictionary of Computing“, Fourth edition, 1996, Oxford University Press, ISBN 0-19-280046-9
„Лексикон Математика“, Георги Симитчиев, Георги Чобанов, Иван Чобанов, ИК Абагар, София, 1995, ISBN 954-584-146-Х

Външни препратки

Статия за математическата структура дърво // Wolfram MathWorld. (на английски)

[INTRO-1] Наков, Светлин. Въведение в програмирането с Java. София, 2017. ISBN 978-954-400-055-4. с. 561-594.

[1]