Drzewo – graf nieskierowany, który jest spójny i acykliczny, czyli: z każdego wierzchołka drzewa można dotrzeć do każdego innego wierzchołka – spójność; można to zrobić tylko jednym sposobem – acykliczność, czyli brak możliwości chodzenia „w kółko”.
Równoważne definicje Graf prosty G jest drzewem jedynie wtedy, gdy 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
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.