Drzewo (matematyka)

Drzewo – graf nieskierowany, który jest acykliczny^[1] i spójny^[2]^[1], 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”)^[3].

Równoważne definicje

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

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:

$G$ jest drzewem
dla każdych dwóch wierzchołków $u,v\in V$ w grafie $G$ istnieje dokładnie jedna uv-ścieżka
$G$ jest spójny i $|V|=|E|+1$
$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^[4]^[5].

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:

{n-2 \choose d_{1}-1,d_{2}-1,\dots ,d_{n}-1}={\frac {(n-2)!}{(d_{1}-1)!(d_{2}-1)!\ldots (d_{n}-1)!}}.

Zobacz też

Przypisy

↑ ^a ^b Słownik terminologiczny informacji naukowej, MariaM. Dembowska, Wrocław–Warszawa–Kraków–Gdańsk: Zakład Narodowy imienia Ossolińskich, 1979, s. 40 .
↑ graf, [w:] Encyklopedia PWN [online], Wydawnictwo Naukowe PWN [dostęp 2022-03-10] .
↑ ^a ^b Reinhard Diestel: Graph Theory. Nowy Jork: 2000, s. 12. ISBN 0-387-95014-1.
↑ Thomas Cormen: Wprowadzenie do algorytmów. Wyd. 8. Wydawnictwa Naukowo-Techniczne, 2007, s. 1114. ISBN 978-83-204-3328-9.
↑ Lech Banachowski, Krzysztof Diks, Wojciech Rytter: Algorytmy i struktury danych. Warszawa: Wydawnictwa Naukowo-Techniczne, 2006, s. 34. ISBN 83-204-3224-3.

Linki zewnętrzne

Eric W.E.W. Weisstein Eric W.E.W., Tree, [w:] MathWorld, Wolfram Research [dostęp 2020-12-12] (ang.).

[:02-1] Słownik terminologiczny informacji naukowej, MariaM. Dembowska, Wrocław–Warszawa–Kraków–Gdańsk: Zakład Narodowy imienia Ossolińskich, 1979, s. 40 .

[epwn-2] graf, [w:] Encyklopedia PWN [online], Wydawnictwo Naukowe PWN [dostęp 2022-03-10] .

[tree-3] Reinhard Diestel: Graph Theory. Nowy Jork: 2000, s. 12. ISBN 0-387-95014-1.

[4] Thomas Cormen: Wprowadzenie do algorytmów. Wyd. 8. Wydawnictwa Naukowo-Techniczne, 2007, s. 1114. ISBN 978-83-204-3328-9.

[5] Lech Banachowski, Krzysztof Diks, Wojciech Rytter: Algorytmy i struktury danych. Warszawa: Wydawnictwa Naukowo-Techniczne, 2006, s. 34. ISBN 83-204-3224-3.

[1]

[2]

[3]

[4]

[5]