Niniejszy artykuł jest częścią cyklu teoria grafów.
 |
|
Najważniejsze pojęcia Wybrane klasy grafów Algorytmy grafowe Zagadnienia przedstawiane jako problemy grafowe Inne zagadnienia |
| 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").
Spis treści |
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:
- nn − 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ń d1, d2, ..., dn, a suma stopni to 2n - 2, wynosi:
.