Определение. Граф — это совокупность непустого множества вершин и множества пар его вершин

Граф — это совокупность непустого множества вершин и множества пар его вершин.

Обычно связи между вершинами представляют как дуги, соединяющие эти вершины.

Граф называют ориентированным, если отмечено направление всех дуг (от одной вершины к другой).

Граф называют планарным, если можно изобразить его на плоскости.

Пример.

Квадрат с диагоналями является планарным графом (проверьте!). А пятиугольник с диагоналями не является планарным графом.

Деревья *

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

Такое название дано потому, что любой древовидный граф можно нарисовать так, что он будет похож на дерево-растение. На таком изображении видны «корень» и «ветви». Листьями в дереве называются вершины, соединённые с графом только одной дугой.

В деревьях число вершин всегда на единицу меньше числа дуг. В самом деле, если мы будем отстригать от дерева листья вместе с дугами, на которых они висят, то разность между числом вершин и числом дуг меняться не будет. В конце стрижки останется одинокая вершина. Следовательно, эта разность равна единице.

В ориентированном дереве, в котором дуги идут от корня к ветвям, выходящие дуги связывают родительскую вершину с дочерними, а входящие – с родительскими.

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

Применение древовидных графов.

1. Древовидная файловая система, или дерево директорий.

2. Дерево поиска, при котором все потомки с левой стороны всегда меньше родителя, а в правом не меньше.

3. Дерево для вычисления математических формул – например, префиксной и постфиксной формы записи.

Задачи по теме «Деревья»

1. Какое максимальное количество листьев может быть у дерева из n вершин? А минимальное?

2. Могут ли в дереве две вершины соединяться двумя различными путями?

3. Существует ли дерево, у которого одна вершина является и листом, и корнем?

4. Докажите, что в ориентированном дереве у каждой вершины не более одного родителя.