Лес – ациклический граф.
Дерево – связный ациклический граф.
Замечание: Лес является обыкновенным графом.
Теорема: Для (m,n) – графа G следующие условия эквивалентности:
1) граф G – дерево;
2) граф G – связный и m=n-1;
3) G – ациклический граф и число m=n-1;
4) G – граф, в которой любые две вершины соединены единственной простой цепью;
5) G – ациклический граф и добавление нового ребра приводит к появлению ровно одного простого цикла.
Неодноэлементное дерево имеет по крайней мере две висячие вершины.
Лемма: Произвольный (m,n,k)-граф G является лесом тогда и только тогда, когда m=n-k.
Пусть G – связный (m,n) граф, если он содержит хотя бы один цикл, то удаление одного ребра приводит к уменьшению числа циклов по крайней мере на единицу. Таким образом, последовательно разрушая циклы графа, можно прийти к остовному подграфу, являющемуся деревья.
Так как дерево с n-вершинами содержит (n-1)- ребро, то для получения остовного дерева из графа G нужно удалить (m-n+1) ребро. В этом случае мы придем к остовному лесу или остову графа G.
Пр.
Т – остов графа G
Число r*(G)= m - n + k– цикломатическое число графа G (n,m,k).
r(G)=n-k – ранг графа G.
Лемма: Пусть G – произвольный граф. Тогда
1. G ацикличен тогда и только тогда, когда его цикломатическое число r*(G)=0;
2. G содержит единственны цикл тогда и только тогда, когда r*( G)=1.
Лемма: Любой ациклический подграф графа G содержится в некотором его остове.
