Ряд задач из теории графов называется "Минимальное охватывающее дерево". В теории графов дерево - это способ соединить все вершины вместе, так что существует ровно один путь от любой одной вершины до любой другой вершины дерева. Если на графике представлено несколько городов, соединённых дорогами, то можно выбрать такое количество дорог, чтобы до каждого города можно было добраться из одного города в другой, но чтобы было не более одного пути из одного города в другой.
График может иметь более одного пролетного дерева, так же как и может быть более одного способа выбора дорог между городами.
Большую часть времени, графики взвешены; каждое соединение между двумя городами имеет вес: это может стоить чего-то, чтобы путешествовать по данной дороге, или одно соединение может быть длиннее, чем другое, это означает, что требуется больше времени, чтобы путешествовать по этому соединению. В языке теории графов соединения называются краями.
Минимальное охватывающее дерево - это дерево. Оно отличается от других деревьев тем, что минимизирует общий вес, прикрепленный к краям. В зависимости от того, как выглядит график, может быть более одного минимального пролетного дерева. В графе, где все ребра имеют одинаковый вес, каждое дерево является минимальным охватывающим деревом. Если все ребра имеют разный вес (т.е. нет двух ребер с одинаковым весом), то существует ровно одно минимальное дерево.
