Деревья

Существует один простой и важный тип графов, которому разные авторы дали одинаковое название, это- деревья. Деревья важны не только потому, что они находят приложения в различных областях знания, но и в силу особого положения их в самой теории графов. Последнее вызвано предельной простотой строения деревьев. Часто при решении какой-либо задачи о графах ее сначала исследуют на деревьях. Примером служит гипотеза Улама, приведенная в гл. 2.

Ниже дано несколько определений дерева. Сначала в геометрических терминах изучается понятие центральности дерева. Затем рассматриваются деревья, естественным образом связанные с произвольным связным графом, именно деревья блоков и точек сочленения. Наконец, будет показано, как каждый остов графа G приводит к набору его независимых циклов, и обратно, для каждого ко-остова можно построить набор независимых коциклов.