Остов графа (также называется остовным деревом) — это подграф связного графа, содержащий все его вершины и не содержащий циклов. 14

Алгоритм построения остовного дерева: 4

1. Выбрать произвольное ребро и включить его в остовное дерево вместе с концевыми вершинами. 4 Полагать n = 1. 4
2. Если n < p−1, выбрать очередное ребро e = (u, v), где u принадлежит остовному дереву, а v — не принадлежит. 4 Включить вершину v и ребро u в дерево. 4
3. Положить n = n + 1 и перейти к шагу 2. 4
4. Остовное дерево построено. 4

Значимость остова графа для анализа связности заключается в том, что остовное число графа (количество остовных деревьев, которые можно построить на связях графа) является характеристикой всего графа. 5

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