Drzewo (matematyka)

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

Równoważne definicje 
Graf prosty G jest drzewem jedynie, jeśli 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  gdzie  to zbiór wierzchołków grafu, a  to zbiór krawędzi. Następujące warunki są równoważne:
  jest drzewem
 dla każdych dwóch wierzchołków  w grafie  istnieje dokładnie jedna uv-ścieżka
  jest spójny i 
  jest acykliczny i 

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  wierzchołkach wynosi:
 

Formuła ta nosi nazwę wzoru Cayleya.

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

Zobacz też 

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

Przypisy

Linki zewnętrzne 
 

Grafy