Деревом называется связный неорграф, не содержащий циклов. Любой неорграф без циклов называется ациклическим графом или лесом. Таким образом, компонентами связности любого леса являются деревья.
ТеоремаДля неорграфа G без петель, содержащего n вершин, следующие условия эквиваленты:
1) G-дерево;
2) G-связный граф, содержащий n-1 ребро;
3) G-ациклический граф, содержащий n-1 ребро;
4) любые две несовпадающие вершины графа G соединяет единственная простая цепь;
5) G- ациклический граф, такой, что если какую-нибудь пару его несмежных вершин соединить ребром, то полученный граф будет содержать ровно один цикл.
Пусть G=‹M;R›- неорграф. Часть G΄=‹M̕;R΄› графа G называется остовом или каркасом графа G, если M=M̕ и G΄-лес, который на любой связной компоненте графа G образует дерево. Таким образом, если G-связный граф, то остов G̕ является деревом, которое будем называть остовным деревом графа G.
Понятие остова для ортграфа G определяется как часть G̕ графа G, для которой F(G̕) является остовом графа F(G). Аналогично вводится понятие остовного дерева для связного орграфа G.
Очевидно, что в каждом графе существует остов: разрушая в каждой связной компоненте циклы, т.е. удаляя лишние ребра, получаем остов.
П р и м е р. В качестве остова графа, G изображенного ниже, можно взять лес с ребрами 2,3,4,6,7 (вообще говоря, остов определяется неоднозначно).
1
2 3 4
6 7
5 8