Реферат: Структуры данных

вставить вершину;

удалить вершину;

заменить вершину;

добавить дугу;

удалить дугу;

найти в графе заданный подграф.

В терминах графов строка - линейный неориентированный граф.

Раздел математики изучающий свойства графов называется теорией графов.

3.3.Деревья

Определение.

Дерево - связный ациклический (без циклов) граф.

Подчеркнем что здесь в цикле ориентация дуг не учитывается.

Определение.

Одна вершина в дереве имеет степень захода 0. Эта вершина назывется корнем дерева.

Одна или несколько вершин в дереве имееют степень исхода 0. Эти вершины называются листьями.

Следствием условия ацикличности является то, что все вершины в графе, кроме корня, имеют сепень захода 1.

Деревья могут быть как ориентированные так и нет.

Определение.

Высотой дерева называется самый длинный путь в дереве из корня к листу.

Примеры.

1. Группа родственников с отношением быть ребенком;

2. Дерево игры;

3. Слова в алфавите: разбиваются на классы эквивалентности по первому символу, каждый класс в свою очередь разбивается на классы эквивалентности по второму символу и т.д.

Определение.

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

Рекурсивное определение дерева.

1.Множество из одной вершины - дерево;

2.Если Т1, Т2, ...ТN - деревья, то вершина

T1 T2 T3 ... TN - дерево

Основные операции над деревьями: