double arrow

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

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

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

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

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

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

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

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


Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:  



Сейчас читают про: