Деревья графа.

Будем называть деревом связного графа любое покрывающее дерево, связывающее все его вершины и имеющее в качестве ветвей ребра этого графа.

Два дерева считаются различными, если они отличаются хотя бы одним ребром.

Существует простой способ определения количества различных деревьев графа без петель (мультиграфа) с р вершинами. Для этого необходимо записать квадратичную матрицу р-го порядка, по глав­ной диагонали которой расположена степень вершин, а ij-и ji-элементы равны взятому со знаком ''-'' числу ребер, связывающих вершины i и j.

Вычисляя любой из главных минора этой матрицы, получим исходное число деревьев.

Например, для графа имеем дерево (одно из 7в).

 

D₂₂ — один из главных миноров этой матрицы.

Это теорема Трента.