Otwórz menu główne

Równoważne definicjeEdytuj

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 drzewEdytuj

TerminologiaEdytuj

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 drzewEdytuj

Diagramy zależnościEdytuj

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

Struktury danychEdytuj

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

InneEdytuj

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 drzewEdytuj

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

  1.   jest drzewem
  2. dla każdych dwóch wierzchołków   w grafie   istnieje dokładnie jedna uv-ścieżka
  3.   jest spójny i  
  4.   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[2][3].

Liczba oznaczonych drzew o n wierzchołkach wynosi:

 

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ń d1, d2, ..., dn, a suma stopni to 2n – 2, wynosi:

 

Zobacz teżEdytuj

PrzypisyEdytuj

  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. Wydawnictwo 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ętrzneEdytuj