Остовное дерево графа. Теорема Прима о минимальном остовном дереве (МОД)

Остовное дерево – суграф связного графа со свойствами дерева.

Минимальное остовное дерево – остовное дерево взвешенного графа с минимальным суммарным весом.

Теорема Прима. Если для уже известно некоторое поддерево – поддерево МОД то присоединив к нему новое ребро где – поддерево МОД