Własności drzew
Graf acykliczny, spójny i nieskierowny nazywany jest drzewem. Lasem natomiast jest graf acykliczny, nieskierowany który niekoniecznie jest spójny. Zatem możemy niejawnie powiedzieć, że drzewem jest las spójny, albo że drzewem jest las mający $1$ składową.
Niech $T$ będzie grafem, który ma $n$ wierzchołków, wtedy następujące twierdzenia są równoważne:
- $T$ jest drzewem.
- $T$ jest acykliczny i każda krawędź $T$ jest mostem.
- Każde dwa wierzchołki $T$ są połączone dokładnie jedną drogą.
- $T$ jest grafem spójnym i zawiera $n - 1$ krawędzi.
- $T$ jest acykliczny i zawiera $n - 1$ krawędzi.
- $T$ jest acykliczny, lecz jeśli dodamy do $T$ jakąkolwiek krawędź, to powstały graf zawiera dokładnie jeden cykl.
Drzewa spinające
Drzewo zawierające każdy wierzchołek grafu spójnego $G$ oraz krawędzie, z których każda należy do $E(G)$ nazywamy drzewem spinającym grafu $G$ (lub drzewem rozpinającym graf $G$).
Tę definicję możemy rozszerzyć do grafów niekoniecznie spójnych. Jeśli wybierzemy dowolny cykl pewnej składowej grafu $G$ i będziemy usuwać tyle krawędzi, aż ta składowa nie będzie miała cykli, lecz nadal będzie grafem spójnym oraz powtórzymy tę czynność dla pozostałych składowych grafu $G$, to otrzymany graf będziemy nazywać lasem spinającym grafu $G$, natomiast liczbę usuniętych krawędzi rzędem cykliczności (lub liczba cyklomatyczną) grafu $G$, którego oznaczamy symbolem $\gamma(G)$. Liczbę krawędzi w lesie spinającym grafu $G$ nazywamy rzędem rozcięcia (lub rzędem spójności) grafu $G$ i oznaczamy symbolem $\xi(G)$. Warto również dodać, że graf $G$ który ma $n$ wierzchołków, $m$ krawędzi i $k$ składowych, rząd cykliczności tego grafu jest równy $m - n + k$, a rząd rozcięcia równy $n - k$.
Jeśli $T$ jest lasem spinającym grafu $G$, to dopełnieniem lasu spinającego $T$ nazywamy graf otrzymany przez usunięcie z grafu $G$ krawędzi należących do $E(T)$.
Fundamentalne zbiory
Znane już nam jest twierdzenie mówiące o tym, że jeśli dodamy do drzewa jedną krawędź to powstały graf będzie zawierać dokładnie jeden cykl. Powiedzmy, że $T$ jest lasem spinającym grafu $G$, jeśli będziemy dołączać do $T$ oddzielnie każdą krawędź należącą do $G$, to otrzymamy zbiór cykli nazywany fundamentelnym zbiorem cykli związanym z $T$. Możemy również powtórzyć tę procedurę dla każdego lasu spinającego grafu $G$, wtedy otrzymany zbiór cykli będziemy wtedy nazywać fundamentalnym zbiorem cykli grafu $G$.
Drzewa ukorzenione
Jeśli drzewo zawiera jeden wyróżniony wierzchołek - korzeń drzewa - to wtedy nazywamy je drzewem ukorzenionym, a wszystkie wierzchołki tego drzewa węzłami. Drzewa z wyróżnionym korzeniem zazwyczaj rysowane są tak, że ich korzeń znajduje się na górze.
Słownictwo stosowane do opisu części drzew jest swego rodzaju mieszaniną, zarówno terminologii genealogicznej jak i nazewnictwa drzew w biologii. Weźmy pod uwagę, węzeł $v$ drzewa ukorzenionego $T$, w którym korzeniem jest $r$. Każdy węzeł $s$ na ścieżce prostej z $r$ do $v$ (gdzie $s \ne v$) nazywany jest przodkiem węzła $v$. Odwrotnie, jeśli $s$ jest przodkiem $v$, to $v$ jesty potomkiem węzła $s$.
Jeśli $T$ jest drzewem to poddrzewem o korzeniu $v$ będzie drzewo $T_v$ składające się z węzła $v$, wszystkich potomków $v$ i wszystkich krawędzi łączących $v$ z potomkami $v$.
Jesli ostatnią krawędzią drzewa $T$ na ścieżce prostej od korzenia $r$ do węzła $v$ jest $sv$, to $s$ jest ojcem $v$, a $v$ synem $s$. Jeśli dwa węzły mają tego samego ojca to nazywamy je braćmi. Węzel który nie ma synów nazywany jest liściem drzewa (lub węzłem zewnętrznym). Węzeł, który nie jest liściem, jest wówczas nazywany węzłem wewnętrznym.
