Материал: деревья

Остовное дерево

Следствие. Число ребер произвольного графа G с n вершинами, m ребрами и k компонентами связности, которые необходимо удалить для получения остовного дерева, не зависит от последовательности их удаления и равно v(G) = m− n + k .

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

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

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

Остовное дерево

В каждом связном графе имеется остовное дерево. В общем случае остовное дерево определено неоднозначно.

Возникает вопрос: сколько остовных деревьев имеется в данном графе?

Для ответа на этот вопрос необходимо ввести еще одну матрицу, ассоциированную с графами.

Матрицей Кирхгофа неориентированного графа G с числом вершин n называется квадратная матрица C порядка n с элементами

Остовное дерево

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

Теорема. Центрами дерева являются вершины максимального типа k . Дерево имеет либо один, либо два центра, причем в первом случае радиус дерева равен k −1, а во втором случае радиус равен k .

Ориентированные деревья

Ориентированные деревья