Drzewo (matematyka)


Drzewo (matematyka) w encyklopedii

Z Wikipedii, wolnej encyklopedii Przejdź do nawigacji Przejdź do wyszukiwania

Drzewograf 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”)[1].

Spis treści

Równoważne definicje | edytuj kod

Graf prosty G jest drzewem jedynie, jeśli spełnia jeden z warunków[1]:

  • 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 | edytuj kod

Terminologia | edytuj kod

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 vpotomkami,
  • 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 | edytuj kod

Diagramy zależności | edytuj kod

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

Struktury danych | edytuj kod

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

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

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

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

Liczba oznaczonych drzew o n {\displaystyle n} wierzchołkach wynosi:

n n 2 . {\displaystyle n^{n-2}.}

Formuła ta nosi nazwę wzoru Cayleya.

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

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

Zobacz też | edytuj kod

Przypisy | edytuj kod

  1. a b Reinhard Diestel: Graph Theory. Nowy Jork: 2000, s. 12. ISBN 0-387-95014-1.
  2. Thomas Cormen: Wprowadzenie do algorytmów. Wyd. 8. Wydawnictwa Naukowo-Techniczne, 2007, s. 1114. ISBN 978-83-204-3328-9.
  3. 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 | edytuj kod

Na podstawie artykułu: "Drzewo (matematyka)" pochodzącego z Wikipedii
OryginałEdytujHistoria i autorzy