Виконано формалізацію алгоритму Крускала побудови мінімального покривного дерева неорієнтованого графа з використанням математичного апарату модифікованих систем алгоритмічних алгебр В.М. Глушкова. Запропоновано концепцію його розпаралелювання для архітектур комп"ютерних систем зі спільною пам"яттю. Проведено низку досліджень алгоритму та сформовано його часові характеристики. Наведено рекомендації щодо використання алгоритму при розв"язанні прикладних задач