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

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

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

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

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