Сегодня мы поговорим об одной из первых задач теории больших сетей, которая может быть решена полностью на самом простом базовом уровне, но которая от этого не становится менее интересной. Это задача о кратчайшей системе дорог или задача Штейнера.
Впервые она появилась, когда еще никаких практических надобностей для больших сетей не было: в тридцатые годы XX века. На самом деле Штейнер начал ее изучать еще раньше, в XIX веке. Это была чисто геометрическая задача, практические приложения которой стали известны только несколько десятилетий спустя.
Разговор пойдет о той области математики, которая впоследствии выросла в теорию больших сетей и разбилась на несколько областей. Это прикладная отрасль, которая задействует очень много методов из других математических дисциплин: дискретной математики, теории графов, функционального анализа, теории чисел и т.д. Бурное развитие теории больших сетей пришлось на конец девяностых и начало двухтысячных годов. Связано это конечно, с прикладными задачами: развитием интернета, мобильной связи, транспортных задач для больших городов. Кроме того теория сетей используется в биологии (нейронные сети), при построении больших электронных плат и т.п.
Сама задача формулируется очень просто. Есть несколько точек на плоскости, которые нужно связать системой дорог наименьшей суммарной длины таким образом, чтобы по этим дорогам можно было из каждой точки добраться в любую другую. Число точек конечно.
Начать рассказ стоит с истории о том, как на Малом мехмате двум группам учеников – восьмиклассникам и одиннадцатиклассникам дали решать одну и ту же задачу. Четыре деревни расположены в вершинах квадрата со стороной четыре километра. Существует ли система дорог, которая связывала бы все эти деревни между собой и имела бы суммарную длину не превосходящую 11 километров.
Читать полностью »
