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

Тази статия е за математическото понятие дърво. За растителната форма вижте Дърво.

---

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

Пример за (неориентирано) дърво с корен върха 4: има 4 листа. Височината му е 2, а разклонеността е 3

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

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

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

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

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

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

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

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

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

Твърдения

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

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

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

Източници

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

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

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

Тази статия, свързана с математика, все още е мъниче. Помогнете на Уикипедия, като я редактирате и разширите.