Деревья

Деревья – простейший класс графов.

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

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

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

Деревья – компоненты связности леса.

В связном графе G выполняется неравенство:

q(G) ³ p(G) — 1, где q – кол-во вершин, p – кол-во ребёр.

Граф G, в котором q(G)=p(G)-1, называется древовидным.

В ациклическом графе G z(G) = 0.

Пусть u, v — несмежные вершины графа G, х = (u, v) Ï Е. Если граф G + х имеет только один простой цикл z(G + х) = 1, то граф G называется субциклическим.

Теорема. Для неoрграфа G без петель содержащего n вершин следующие условия эквивалентны:

1) G — дерево;

2) G — связный граф, содержащий n - 1 ребро;

3) G — ациклический граф, содержащий n - 1 ребро;

4) Любые две несовпадающие вершины графа G соединяет единственная простая цепь;

5) G — ациклический граф, такой, что если какую-либо пару его несмежных вершин соединить ребром, то полученный граф будет содержать ровно один цикл.