Деревья

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

Свойства деревьев:

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

2. Дерево – связный граф, в котором q = p – 1.

3. Любые две вершины соединены в дереве единственной простой цепью.

4. Любое ребро дерева есть мост.

Пример. Все различные (свободные) деревья с 6 вершинами.

Корневым ориентированным деревом (или ордеревом, или корневым деревом) называется орграф со следующими свойствами:

· существует единственный узел, полустепень захода которого равна 0; он называется корнем ордерева;

· полустепень захода всех остальных узлов равна 1;

· каждый узел достижим из корня.

Пример. Ориентированные деревья с 4 узлами.

Концевая вершина ордерева называется листом. Вершины, не являющиеся листьями, называются внутренними. Путь из корня в лист называется ветвью. Длина наибольшей ветви ордерева называется высотой. Уровень узла ордерева – это расстояние от корня до узла. Сам корень имеет уровень 0. Узлы одного уровня образуют ярус дерева.

Если наибольшая из полустепеней исхода для вершин дерева равна m, тогда дерево называется m-арным деревом. В частном случае, когда m = 2, дерево называется бинарным деревом. В каждом бинарном дереве каждый сын родителя обозначается либо как левый сын, либо как правый сын (но не то и другое одновременно).

В m-арном ориентированном дереве d^–(v) £ m для каждой его вершины v. Таким образом, родитель имеет не более m сыновей. Полным m-арным ориентированным деревом называется такое ориентированное дерево, в котором d^–(v) = m для каждой его вершины v, не являющейся листом, и все листы находятся на одном уровне. Таким образом, каждый родитель имеет в точности m сыновей.

Контрольные вопросы

1. Нарисуйте следующие графы:

а) К₅; б) К_1,4.

2. Изоморфны ли следующие графы?

а)

б)

3. Найдите дополнения приведенных ниже графов.

а) б)

4. Найдите точки сочленения, мосты, блоки.

5. Которые из приведенных ниже графов являются деревьями?

а) б) в)