В теории графов дерево — это неориентированный граф , в котором любые две вершины соединены ровно одним путем , или, что то же самое, связный ациклический неориентированный граф. [1] Лес — это неориентированный граф, в котором любые две вершины соединены не более чем одним путем, или, что то же самое, ациклический неориентированный граф или, что то же самое, непересекающееся объединение деревьев. [2]
Полидерево [ 3] (или ориентированное дерево [4] или ориентированное дерево [5] [6] или односвязная сеть [7] ) — это ориентированный ациклический граф (DAG), базовым неориентированным графом которого является дерево. Полилес ( или направленный лес , или ориентированный лес ) — это ориентированный ациклический граф, базовым неориентированным графом которого является лес.
Различные типы структур данных, называемые деревьями в компьютерных науках , имеют в основе графы , которые в теории графов являются деревьями, хотя такие структуры данных обычно являются корневыми деревьями . Корневое дерево может быть направленным, называемым направленным корневым деревом , [8] [9] , либо все его ребра направлены в сторону от корня — в этом случае оно называется древовидным [4] [10] или внешним деревом [11] . ] [12] — или сделать так, чтобы все его ребра указывали на корень — в этом случае он называется анти-древовидным [13] или в дереве. [11] [14] Само корневое дерево определяется некоторыми авторами как ориентированный граф. [15] [16] [17] Корневой лес — это непересекающееся объединение корневых деревьев. Корневой лес может быть направленным, называемым направленным корневым лесом , либо заставляя все его края указывать в сторону от корня в каждом корневом дереве — в этом случае он называется разветвленным или внешним лесом, — либо заставляя все его края указывать на корень. в каждом корневом дереве — в этом случае оно называется антиветвящимся или внутрилесным .
Если G имеет конечное число вершин, скажем, n из них, то приведенные выше утверждения также эквивалентны любому из следующих условий:
Как и везде в теории графов, граф нулевого порядка (граф без вершин) обычно не считается деревом: хотя он бессвязен как граф (любые две вершины могут быть соединены путем), он не равен 0 . -связен (или даже (−1)-связен) в алгебраической топологии, в отличие от непустых деревьев, и нарушает отношение «на одну вершину больше, чем ребер». Однако его можно рассматривать как лес, состоящий из нулевых деревьев.
Внутренняя вершина (или внутренняя вершина или вершина ответвления ) является вершиной степени не ниже 2. Точно так же внешняя вершина (или внешняя вершина , терминальная вершина или лист ) является вершиной степени 1.