Деревья. 
Теория графов

Деревом называется связный граф, не содержащий циклов, Любой граф без циклов называется ациклическим (или лесом). Таким образом, компонентами леса являются деревья. На рис. 1.6 изображены все деревья шестого порядка.

Рис. 1.7.

Существует несколько вариантов определения дерева; некоторые из них отображены в следующей теореме.

Теорема 1.1 Для (n, m)-графа G следующие утверждения эквивалентны:

• 1) G-дерево;
• 2) G-связный граф и m=n-1;
• 3) G-ациклический граф и m=n-1;
• 4) любые две несовпадающие вершины графа G соединяет единственная простая цепь;
• 5) G-циклический граф, обладающий тем свойством, что если какую-либо пару его несмежных вершин соединить ребром, то полученный граф будет содержать ровно один цикл.

Следствие 1.1 В любом дереве порядка n2 имеется не менее двух концевых вершин.

Следствие 1.2 Граф G является лесом тогда и только тогда, когда (G)=0.

Следствие 1.3 Граф G имеет единственный цикл тогда и только тогда, когда (G)=1.

Следствие 1.4 Граф, в котором число ребер не меньше, чем число вершин, содержит цикл.

Теорема 1.2 Центр любого дерева состоит из одной или из двух смежных вершин.

В связном графе остовом служит любое остовное дерево, т. е. остовный подграф, являющийся деревом. Число остовов в связном графе определяется в неявной форме следующей теоремой.

Теорема Кирхгофа (1847). Число остовных деревьев в связном графе G порядка равно алгебраическому дополнению любого элемента матрицы Кирхгофа B (G).