На підставі наданого тексту, що оптимізує дерево мінімального розтягування?
Мінімальне дерево розтягування (MST) або дерево розтягування мінімальної ваги - це підсумок країв з'єднаного, обтяженого краєм непрямого графу, який з'єднує всі вершини разом, без будь-яких циклів і з мінімальною можливою загальною вагою краю. Тобто це обтяжливе дерево, сума боргових ваг якого якомога менша. Більш загалом, будь-який непрямий граф, зважений на межі (не обов'язково підключений), має мінімальний об'єм лісу, який є об'єднанням мінімальних об'ємних дерев для його підключених компонентів.

Є багато випадків використання для мінімального розтягування дерев. Одним з прикладів є телекомунікаційна компанія, яка намагається прокласти кабель в новому районі. Якщо він змушений закопувати кабель тільки уздовж певних шляхів (наприклад, Дороги), тоді буде граф, що містить точки (наприклад, будинків, пов'язаних з цими дорогами. Деякі шляхи можуть бути дорожчими, тому що вони довші, або вимагають, щоб кабель був похований глибше; ці шляхи були б представлені краями з більшими вагами. Валюта є прийнятною одиницею для ваги краю - немає вимоги для довжини краю, щоб підкорятися нормальним правилам геометрії, таким як нерівність трикутника. Дерево, що розтягує цей граф, буде підгрупою тих шляхів, які не мають циклів, але все одно з'єднують кожен будинок; може бути кілька дерев, що розтягують. Мінімальна протяжність дерева буде однією з найнижчих загальних витрат, що являє собою найменш дорогий шлях для прокладання кабелю.
Мінімальне дерево розтягування оптимізує графік таким чином, що мінімізує суму всіх ваг країв