Drzewo (matematyka)

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
Niniejszy artykuł jest częścią cyklu teoria grafów.




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


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


Algorytmy grafowe
A*
Bellmana-Forda
Dijkstry
Fleury'ego
Floyda-Warshalla
Johnsona
Kruskala
Prima
przeszukiwanie grafu
wszerz
w głąb
najbliższego sąsiada


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


Inne zagadnienia
kod Graya
diagram Hassego
kod Prüfera


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").

Równoważne definicje[edytuj | edytuj kod]

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

Przykłady drzew[edytuj | edytuj kod]

Terminologia[edytuj | 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 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[edytuj | edytuj kod]

Diagramy zależności[edytuj | 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 | 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 | 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 | edytuj kod]

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 jest równa wysokości jego korzenia, czyli długości najdłuższej ścieżki prostej od korzenia do liścia[1][2].

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ń d1, d2, ..., dn, 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)!}}.

Zobacz też[edytuj | edytuj kod]

Przypisy

  1. Thomas Cormen: Wprowadzenie do algorytmów. Wyd. 8. Wydawnictwo Naukowo-Techniczne, 2007, s. 1114. ISBN 9788320433289.
  2. Lech Banachowski, Krzysztof Diks, Wojciech Rytter: Algorytmy i struktury danych. Warszawa: Wydawnictwa Naukowo-Techniczne, 2006, s. 34. ISBN 83-204-3224-3.