Для графа G, заданного матрицей весов, построить минимальный по весу остов G' и найти его вес (G). Используя матричную теорему Кирхгофа, найти число остовных деревьев. Нарисовать 5 остовов.

Нарисуем граф.

Для построения минимального остова применим алгоритм Прима.

Разобьём множество вершин V графа на два подмножества V' и V'' таких, что , , , . Назовём число пошаговым расстоянием между множествами ' и '' .