Drzewo (matematyka)

Drzewo – graf nieskierowany, który jest acykliczny i spójny, czyli taki graf, w którym z każdego wierzchołka drzewa można dotrzeć do każdego innego wierzchołka (spójność) tylko jednym sposobem (acykliczność, brak możliwości chodzenia „w kółko”).

Równoważne definicje

Graf prosty G jest drzewem jedynie wtedy, gdy spełnia jeden z warunków:

• dowolne dwa wierzchołki łączy dokładnie jedna ścieżka prosta
• G jest acykliczny i dodanie krawędzi łączącej dowolne dwa wierzchołki utworzy cykl
• G jest spójny i usunięcie dowolnej krawędzi spowoduje, że G przestanie być spójny

Przykłady drzew

• 
• 

• 
• 

Terminologia

Drzewo, w którym jest wyróżniony jeden z wierzchołków, nazywamy drzewem ukorzenionym, a wyróżniony wierzchołek – korzeniem.

Na takim drzewie możemy również określić relacje „rodzinne” pomiędzy wierzchołkami.

Dla dowolnej ścieżki prostej rozpoczynającej się od korzenia i zawierającej wierzchołek v:

• wierzchołki występujące w ścieżce przed v nazywamy jego przodkami v, a wierzchołki występujące po v – potomkami,
• wierzchołek bezpośrednio przed v nazywamy rodzicem lub ojcem, a bezpośrednio po – dzieckiem lub synem,
• wierzchołki mające wspólnego ojca nazywamy braćmi.

Wierzchołki, które nie mają synów, nazywamy liśćmi drzewa.

Najdłuższą ścieżkę w drzewie nazywamy średnicą drzewa. Jej długość liczymy, stosując programowanie dynamiczne.

W informatyce bardzo często wymaga się, żeby synowie tworzyli nie zbiór, lecz listę uporządkowaną. Taki twór co prawda nie jest matematycznie grafem, jednak ma ogromne znaczenie w tej dziedzinie matematyki.

Graf prosty, acykliczny i niespójny, który można traktować jako zbiór drzew, nazywa się lasem.

Podstawowe operacje na drzewach to:

• wyliczenie wszystkich elementów drzewa,
• wyszukanie konkretnego elementu,
• dodanie nowego elementu w określonym miejscu drzewa,
• usunięcie elementu.

Zastosowanie drzew

Diagramy zależności

W naturalny sposób reprezentują hierarchię danych (obiektów fizycznych i abstrakcyjnych, pojęć itp.) lub zależności typu klient-serwer.

Struktury danych

W informatyce wiele struktur danych jest konkretną realizacją drzewa matematycznego. Wierzchołki drzewa reprezentują konkretne dane (liczby, napisy albo bardziej złożone struktury danych). Odpowiednie ułożenie danych w drzewie może ułatwić i przyspieszyć ich wyszukiwanie. Znaczenie tych struktur jest bardzo duże i ze względu na swoje własności drzewa są stosowane praktycznie w każdej dziedzinie informatyki (np. algorytmika, kryptografia, bazy danych, grafika komputerowa, przetwarzanie tekstu, telekomunikacja).

Specjalne znaczenie w informatyce mają drzewa binarne (liczba dzieci ograniczona do dwóch) i ich różne odmiany, np. drzewa AVL, drzewa czerwono-czarne, BST; drzewa, które posiadają więcej niż dwoje dzieci, są nazywane drzewami wyższych rzędów.

Zobacz też: Kopiec, Kodowanie Huffmana

Inne

Jako drzewa przedstawia się składnie języków formalnych, w tym rachunku lambda. W teorii gier występują drzewa decyzyjne. Bazy danych i systemy plików stosują wiele algorytmów opartych na drzewach i specjalnych postaciach drzew takich jak drzewa binarne, B drzewa, B+ drzewa, drzewa AVL i inne.

Własności drzew

W grafie $G=(V,E),$ gdzie $V$ to zbiór wierzchołków grafu, a $E$ to zbiór krawędzi. Następujące warunki są równoważne:

1. $G$ jest drzewem
2. dla każdych dwóch wierzchołków $u,v\in V$ w grafie $G$ istnieje dokładnie jedna uv-ścieżka
3. $G$ jest spójny i $|V|=|E|+1$
4. $G$ jest acykliczny i $|V|=|E|+1$

W drzewie ukorzenionym istnieje dokładnie jedna ścieżka pomiędzy węzłem a korzeniem. Liczba krawędzi w ścieżce jest nazywana długością (lub głębokością) – liczba o jeden większa określa poziom węzła. Z kolei wysokość drzewa jest równa wysokości jego korzenia, czyli długości najdłuższej ścieżki prostej od korzenia do liścia.

Liczba oznaczonych drzew o $n$ wierzchołkach wynosi:

$n^{n-2}.$

Formuła ta nosi nazwę wzoru Cayleya.

Liczba drzew na zbiorze $n$-wierzchołków (gdzie $n$ jest większe bądź równe 2), z których każdy ma stopień $d_1,d_2,\dots ,d_n,$ a suma stopni to $2n-2,$ wynosi:

$(\genfrac{}{}{0ex}{}{n-2}{d_1-1,d_2-1,\dots ,d_n-1})=\frac{(n-2)!}{(d_1-1)!(d_2-1)!\dots (d_n-1)!}.$

Zobacz też

• drzewo jako struktura danych w informatyce
• drzewo rozpinające
• teoria grafów

Linki zewnętrzne

• Szablon:MathWorld