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

В теории графов деревом называется граф, в котором все вершины соединены рёбрами (возможно, посредством других вершин) и отсутствуют циклы (последовательности рёбер, соединяющие какую-либо вершину саму с собой). В данном случае деревья являются корневыми, то есть имеют определённую вершину - корень. Это понятное, но неформальное определение дерева. Теорема Краскала утверждает последовательность деревьев TREE(n), описанную следующими законами: TREE(1) даёт единственное дерево с одной вершиной: если попытаться добавить ещё одно с двумя вершинами, при удалении любой из них получится первая...