Drzewo (matematyka).html

Niniejszy artykuł jest częścią cyklu teoria grafów.

Najważniejsze pojęcia
graf
drzewo
podgraf
cykl
klika
stopień wierzchołka
dopełnienie grafu
obwód grafu
pokrycie wierzchołkowe
liczba chromatyczna
indeks chromatyczny
izomorfizm grafów
homeomorfizm grafów

więcej...

Wybrane klasy grafów
graf pełny
graf spójny
drzewo
graf dwudzielny
graf regularny
graf eulerowski
graf hamiltonowski
graf planarny

więcej...

Algorytmy grafowe
A*
Bellmana-Forda
Breadth-first search
Depth-first search
Dijkstry
Fleury'ego
Floyda-Warshalla
Johnsona
Kruskala
Prima
przeszukiwanie grafu
najbliższego sąsiada

Zagadnienia przedstawiane jako problemy grafowe
problem komiwojażera
problem chińskiego listonosza
problem kojarzenia małżeństw

Inne zagadnienia
kod Graya
diagram Hassego

edytuj ten szablon

Drzewo – oznacza w teorii grafów graf, który jest acykliczny i spójny. Mówiąc językiem obrazowym, z każdego wierzchołka drzewa można dotrzeć do każdego innego wierzchołka (spójność) i tylko jednym sposobem (acykliczność, czyli brak możliwości chodzenia w "kółko").

edytuj 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

edytuj Przykłady drzew

edytuj 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.

edytuj Zastosowanie drzew

edytuj Diagramy zależności

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

edytuj 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

edytuj 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.

edytuj Własności drzew

W drzewie ukorzenionym istnieje dokładnie jedna ścieżka pomiędzy węzłem a korzeniem, na rys. przykładowa droga do węzła J jest zaznaczona na czerwono. 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 to największy poziom istniejący w drzewie (przykładowe drzewo ma wysokość 4).

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₁, d₂, ..., d_n, a suma stopni to 2n - 2, wynosi:

${n-2 \choose d_1-1, d_2-1, \ldots, d_n-1} = {(n-2)! \over {(d_1-1)! (d_2-1)! \cdots (d_n-1)!}}$ .