Деревья, их свойства

Характеристические числа графов. Сети

Дерево – это связный ациклический граф.

Теорема 1

Граф G является деревом тогда и только тогда, когда любые 2 его вершины связаны единственной простой цепью.

Теорема 2

Граф G является деревом с n вершинами тогда и только тогда, когда у него ровно n-1 ребро.

Лес из k деревьев – это несвязный ациклический граф, содержащий ровно k компонент связности.

Теорема 3

Лес с n вершинами, состоящий из k деревьев, содержит ровно n-k ребер.

Остов графа G – это подграф графа G, который является деревом.

Концевая вершина дерева – вершина, локальная степень которой равна 1. Концевое ребро – ребро инцидентное концевой вершине.

Пусть дано дерево Т.

Назовем концевые вершины дерева Т вершинами типа 1.

Удалим из дерева Т все концевые ребра. Получим дерево Т1. Его концевые вершины назовем вершинами типа 2 (для исходного дерева Т). Продолжаем процесс, пока не останутся вершины максимального типа. Их может быть 1 или 2.