Теория графов. Деревья. Сети. Сетевые модели представления информации. Применение графов и сетей

Неориентированное дерево (или просто дерево) – это конечный связный граф с выделенной вершиной (корнем) без циклов. Дерево не имеет  петель и кратных рёбер.
Дерево и названо дерево, поскольку, будучи нарисованным, выглядит как дерево, только перевёрнутое «вверх ногами»

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

Для каждой пары вершин дерева – узлов – существует единственный маршрут, поэтому вершины удобно классифицировать по степени удалённости от корневой вершины. Расстояние до корневой вершины

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

Рекомендуем посмотреть:

Практическое занятие по теме «Теория графов»

Теория графов. Основные понятия теории графов. Операции над графами. Способы задания графов. Плоские графы, маршруты, цепи, циклы графа.

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

Нет комментариев. Ваш будет первым!