Особенности применения теории графов при решении задач и в практической деятельности

курсовая работа

6. Графы - деревья. Корень

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

Любая цепь в графе без циклов является элементарной; любая часть такого графа также будет графом без циклов. Здесь элементарная цепь, как уже определялось ранее, - это цепь, при обходе которой, каждая вершина встречается только один раз.

Корень. Исходная вершина дерева называется его корнем. Заметим, что корнем может служить любая вершина дерева.

Число вершин и рёбер дерева. Для подсчёта числа элементов дерева служит теорема: "Дерево с n вершинами имеет n - 1 рёбер".

Как выглядит дерево рассмотрим следующий рис. 11:

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

Рис.11

Рассмотрим произвольное дерево с n заданными и пронумерованными в произвольном порядке вершинами. Пусть например, т = 11(левый, рис.12).

Рис.12

Но ведь те же 11 вершин можно соединить попарно 10 рёбрами и по- другому, чтобы получилось какое-то новое дерево (правый рисунок). У этого нового дерева совпадает с предыдущим только 3 ребра.

Спрашивается: сколько существует таких разных деревьев?

Английскому математику А.Кэлли (1875 г.) опыт, приобретённый в процессе непосредственного подсчёта числа деревьев, помог найти правильный ответ на этот вопрос. Деревьев с n пронумерованными вершинами существует nn-2..

Делись добром ;)