TreeEdit

drzewo jest nieukierunkowanym grafem G, który spełnia jeden z następujących równoważnych warunków:

• G jest połączony i acykliczny (nie zawiera cykli).
• G jest acykliczny i powstaje prosty cykl, jeśli do G zostanie dodana jakaś krawędź.
• G jest połączone, ale stanie się odłączone, jeśli pojedyncza krawędź zostanie usunięta z G.
• G jest połączone, a 3-wierzchołkowy pełny wykres K3 nie jest minorem G.
• dowolne dwa wierzchołki w G mogą być połączone unikalną prostą ścieżką.

Jeśli G ma skończenie wiele wierzchołków, powiedzmy n z nich, to powyższe stwierdzenia są również równoważne z którymkolwiek z poniższych warunków:

• G jest połączone i ma N − 1 krawędzi.
• G jest połączone, a każdy podgraf g zawiera co najmniej jeden wierzchołek z zerową lub jedną krawędzią incydentu. (Czyli G jest połączone i 1-zdegenerowane.)
• G nie ma prostych cykli i ma N-1 krawędzie.

jak gdzie indziej w teorii grafów, Graf rzędu zera (Graf bez wierzchołków) na ogół nie jest uważany za drzewo: chociaż jest on połączony próżniowo jako Graf (dowolne dwa wierzchołki mogą być połączone ścieżką), w topologii algebraicznej nie jest połączony z 0 (lub nawet (-1)-połączony), w przeciwieństwie do niepustych drzew i narusza relację „o jeden więcej wierzchołków niż krawędzi”. Można go jednak uznać za Las składający się z zero drzew.

wierzchołek wewnętrzny (lub wierzchołek wewnętrzny lub wierzchołek gałęziowy) jest wierzchołkiem stopnia co najmniej 2. Podobnie zewnętrzny wierzchołek (lub zewnętrzny wierzchołek, końcowy wierzchołek lub liść) jest wierzchołkiem stopnia 1.

drzewo nieredukowalne (lub drzewo zredukowane szeregowo) to drzewo, w którym nie ma wierzchołka stopnia 2 (wyliczonego w sekwencji a000014 w OEIS).

ForestEdit

las jest wykresem nieskierowanym, w którym dowolne dwa wierzchołki są połączone co najwyżej jedną ścieżką. Równoważnie, las jest nieukierunkowanym grafem acyklicznym, którego wszystkie połączone elementy są drzewami; innymi słowy, Graf składa się z rozdzielonego związku drzew. W szczególnych przypadkach przykładem lasów jest Graf rzędu zera (Las składający się z zerowych drzew), pojedyncze drzewo i Graf bez krawędzi.Ponieważ dla każdego drzewa V-E = 1, Możemy łatwo policzyć liczbę drzew znajdujących się w lesie, odejmując różnicę między całkowitymi wierzchołkami i całkowitymi krawędziami. TV-TE = Liczba drzew w lesie.

PolytreeEdit

polytree (lub skierowane drzewo lub zorientowane drzewo lub pojedynczo podłączona sieć) jest skierowanym grafem acyklicznym (dag), którego podstawowym wykresem jest drzewo. Innymi słowy, jeśli zamienimy jego skierowane krawędzie na niezorientowane krawędzie, otrzymamy niezorientowany wykres, który jest zarówno połączony, jak i acykliczny.

niektórzy autorzy ograniczają frazę „directed tree” do przypadku, w którym krawędzie są skierowane w kierunku określonego wierzchołka lub wszystkie skierowane w kierunku określonego wierzchołka (patrz arborescence).

PolyforestEdit

polyforest (lub ukierunkowany Las lub las zorientowany) jest ukierunkowanym grafem acyklicznym, którego podstawowym wykresem jest las. Innymi słowy, jeśli zamienimy jego skierowane krawędzie na nieukierunkowane krawędzie, otrzymamy nieukierunkowany wykres, który jest acykliczny.

niektórzy autorzy ograniczają frazę „directed forest” do przypadku, w którym krawędzie każdego połączonego elementu są skierowane w kierunku określonego wierzchołka lub wszystkie skierowane w kierunku określonego wierzchołka (patrz rozgałęzienia).

drzewo Ukorzenioneedit

drzewo ukorzenione to drzewo, w którym jeden wierzchołek został wyznaczony jako korzeń. Krawędzie ukorzenionego drzewa można przypisać naturalnej orientacji, z dala od korzenia lub w kierunku korzenia, w którym to przypadku struktura staje się skierowanym ukorzenionym drzewem. Gdy skierowane ukorzenione drzewo ma orientację z dala od korzenia, nazywa się arborescence lub out-tree; gdy ma orientację w kierunku korzenia, nazywa się anty-arborescence lub in-tree. Porządek drzewa jest częściowym porządkiem na wierzchołkach drzewa z u < v wtedy i tylko wtedy, gdy unikalna ścieżka od korzenia do v przechodzi przez u. ukorzenione drzewo T, które jest podgrafem jakiegoś grafu G, jest normalnym drzewem, jeśli końce każdej ścieżki T w G są porównywalne w tym porządku drzewa (Diestel 2005, str. 15). Ukorzenione drzewa, często o dodatkowej strukturze, takiej jak uporządkowanie sąsiadów na każdym wierzchołku, są kluczową strukturą danych w informatyce; patrz struktura danych drzewa.

w kontekście, w którym drzewa mają mieć korzeń, drzewo bez żadnego wyznaczonego korzenia nazywa się wolnym drzewem.

drzewo oznaczone jest drzewem, w którym każdy wierzchołek otrzymuje unikalną Etykietę. Wierzchołki drzewa znakowanego na N wierzchołkach są zwykle oznaczone etykietami 1, 2, …, N. drzewo rekurencyjne to drzewo zakorzenione, w którym etykiety wierzchołków respektują porządek drzewa (np., jeśli u < v dla dwóch wierzchołków u I v, wtedy Etykieta u jest mniejsza niż etykieta v).

w ukorzenionym drzewie, rodzic wierzchołka v jest wierzchołkiem połączonym z v na ścieżce do korzenia; każdy wierzchołek ma unikalnego rodzica, z wyjątkiem korzenia, który nie ma rodzica. Potomek wierzchołka v jest wierzchołkiem, którego V jest rodzicem. Ascendent wierzchołka v jest dowolnym wierzchołkiem, który jest albo rodzicem v, albo jest (rekurencyjnie) ascendentem rodzica V. Potomek wierzchołka v jest dowolnym wierzchołkiem, który jest dzieckiem v lub jest (rekurencyjnie) potomkiem któregokolwiek z dzieci v. rodzeństwo do wierzchołka v jest dowolnym innym wierzchołkiem na drzewie, który ma tego samego rodzica co V. liść jest wierzchołkiem bez dzieci. Wierzchołek wewnętrzny to wierzchołek, który nie jest liściem.

wysokość wierzchołka u ukorzenionego drzewa jest długością najdłuższej ścieżki w dół do liścia od tego wierzchołka. Wysokość drzewa to wysokość korzenia. Głębokość wierzchołka jest długością ścieżki do jego korzenia (root path). Jest to powszechnie potrzebne w manipulacji różnych drzew samobalansujących, w szczególności drzew AVL. Korzeń ma głębokość zero, liście mają wysokość zero, a drzewo z tylko jednym wierzchołkiem (stąd zarówno korzeń, jak i liść) ma głębokość i wysokość zero. Konwencjonalnie, puste drzewo (drzewo bez wierzchołków, jeśli takie są dozwolone) ma głębokość i wysokość -1.

drzewo k-ary to ukorzenione drzewo, w którym każdy wierzchołek ma co najwyżej K dzieci. Drzewa 2-ary są często nazywane drzewami binarnymi, podczas gdy drzewa 3-Ary są czasami nazywane drzewami trójwarstwowymi.

uporządkowane drzewkoedytuj

uporządkowane drzewo (lub Platan) jest zakorzenionym drzewem, w którym kolejność jest określona dla dzieci każdego wierzchołka. Jest to nazywane „Platanem”, ponieważ uporządkowanie dzieci jest równoznaczne z osadzeniem drzewa w płaszczyźnie, z korzeniem na górze i dziećmi każdego wierzchołka niższego od tego wierzchołka. Biorąc pod uwagę osadzenie ukorzenionego drzewa w płaszczyźnie, jeśli ktoś ustala kierunek dzieci, powiedzmy od lewej do prawej, to osadzenie daje kolejność dzieci. Odwrotnie, biorąc pod uwagę uporządkowane drzewo i konwencjonalnie rysując korzeń u góry, wierzchołki potomne w uporządkowanym drzewie mogą być rysowane od lewej do prawej, dając zasadniczo unikalne osadzenie planarne.