ДЕ́РЕВО

ДЕ́РЕВО в ма­те­ма­ти­ке, связ­ный граф без цик­лов (см. Гра­фов тео­рия). Сле­дую­щие свой­ст­ва гра­фа $G$ с $p$ вер­ши­на­ми и $q$ рёб­ра­ми эк­ви­ва­лент­ны то­му, что граф $G$ яв­ля­ет­ся Д.: лю­бые две вер­ши­ны в $G$ со­еди­не­ны един­ст­вен­ной про­стой це­пью (т. е. мар­шру­том с по­пар­но разл. вер­ши­на­ми), $G$ – связ­ный граф и $p=q+1$, $G$ – граф без цик­лов и $p=q+1$.

Граф, ка­ж­дая ком­по­нен­та ко­то­ро­го яв­ля­ет­ся Д., на­зы­ва­ет­ся ле­сом.