Остов графа (также называется остовным деревом) — это подграф связного графа, содержащий все его вершины и не содержащий циклов. 14
Алгоритм построения остовного дерева: 4
Значимость остова графа для анализа связности заключается в том, что остовное число графа (количество остовных деревьев, которые можно построить на связях графа) является характеристикой всего графа. 5
Если с какой-либо вершиной графа нет связи (это означает наличие в графе нескольких компонент), то остовное число графа (его общая связность) равно нулю. 5 Также связность подмножества вершин графа равна остовному числу подграфа, построенного на данном подмножестве вершин. 5