Задача Штейнера

Задача Штейнера о минимальном дереве состоит в поиске кратчайшей сети, соединяющей заданный конечный набор точек плоскости.Задача получила своё название в честь Якоба Штейнера (1796—1863). Альтерантивное условие задачи заключается в поиске минимального подграфа, соединяющего конечное число заданных вершин (терминалов) и образующего таким образом сеть кратчайших путей между этими вершниами. Задача является таким образом обобщением задачи поиска минимального остовного дерева.