Алгоритмы построения минимальных деревьев соединений

Задача трассировки проводного монтажа – для множества выводов, соответствующих эквипотенциальным точкам некоторой схемы, требуется разработать монтажную схему соединения этих выводов в единую цепь с минимальной суммарной длиной проводников.

Математической моделью монтажной схемы является граф, вершины которого соответствуют выводам рассматриваемой цепи, ребра – монтажным проводникам. С точки зрения теории графов монтажное соединение должно представлять собой дерево, то есть граф без циклов.

Фрагмент графа – группа соединенных ребрами вершин.

Изолированная вершина – вершина, не соединенная ни с одной другой вершиной.

Степень вершины графа – число соединенных с ней ребер.

Таким образом, задача трассировки проводного монтажа сводится к задаче теории графов. А именно: для заданного множества вершин требуется построить дерево, включающее в себя все эти вершины и имеющее минимальную суммарную длину ребер.