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

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

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

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

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

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

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

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

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

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