Важнейшие классы графов

Деревом называется связный граф, не имеющий циклов. Граф без циклов называют лесом.

Во всяком дереве, в котором больше одной вершины, имеется не менее двух вершин степени 1. Такие вершины называют листьями.

Теорема о свойствах деревьев. Если G – дерево, то

1) число ребер в нем на 1 меньше числа вершин;

2) в G любая пара вершин соединена единственным путем;

3) при добавлении к G любого нового ребра образуется цикл;

4) при удалении из G любого ребра он превращается в несвязный граф.

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

Центр дерева можно найти следующим образом. Если в дереве больше двух вершин, удалим все его листья. С полученным деревом поступаем так же, это продолжается, пока не останется дерево из одной или двух вершин. Эти вершины и образуют центр исходного дерева.

Наиболее компактным способом представления помеченных деревьев является код Прюфера. Пусть дерево имеет множество вершин . Код Прюфера этого дерева представляет собой последовательность , элементами которой являются вершины. Он строится с помощью следующей процедуры.