Теорема. Деревья являются в некотором смысле простейшим классом графов

Деревья

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

Определение

Граф без циклов называется лесом.

Определение

Связный ациклический граф называется деревом.

Таким образом, компоненты связности леса – это деревья.

Определение

Граф , , в котором называется древовидным.

Пример

Следующая теорема устанавливает основные свойства деревьев.

Теорема

Пусть дан граф , с к компонентами связности и простыми циклами. Для графа следующие утверждения эквивалентны:

1) - дерево, то есть связный граф без циклов;

2) любые две вершины в соединены единственной простой цепью;

3) - связный граф и любое ребро есть мост;

4) - связный и древовидный, то есть к=1 и ;

5) - ацикличный и древовидный, то есть =0 и .