Encyklopedia w Markpol

Reklama:

W teorii grafów drzewo to spójny graf acykliczny.

Równoważne definicje

Graf prosty G jest 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

    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ącą się od korzenia i zawierające 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.

    Zastosowanie

    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 informatyce. 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. Graf prosty, acykliczny i niespójny, który można traktować jako zbiór drzew, nazywa się lasem. Zobacz też: drzewo jako struktura danych w informatyce, teoria grafów

    Chcesz wypromować swoją stronę w internecie?? - nie zwlekaj pozycjonowanie w Luman.biz to rozsądny wybór
    2005 Encyklopedia
    These materials are based onWikipedia and licensed under the GNU FDL
    Advertising|New York Hotels|Loans|Mobile Phones|Vegas Hotel

    		•