«ДЕРЕВО» в теории графов
— связный граф без циклов (см. Графов теория). Наиболее важные характеристические свойства
выражены следующими шестью равносильными друг другу высказываниями:
(определение «Д.»);
; для любой пары вершин
у в L существует одна и только одна цепь, соединяющая
но если из L удалить любое ребро, то для полученного графа
будет к
но если к L добавить любое ребро (не добавляя вершин), то у полученного графа L будет
Здесь L — произвольный граф, (L) - к-во его вершин,
ребер, к
компонент,
— цикломатическое число.
Произвольный граф без циклов часто наз. лесом (поскольку каждая его компонента — 
), Ордерево, растущее из 
это 
в котором выделена одна вершина 
а ребра ориентированы т. о., что все цепи, начинающиеся в 
являются путями (т. е. их дуги ориентированы в направлении обхода). А. Зыков.
