Сегодня мы поговорим об одной из первых задач теории больших сетей, которая может быть решена полностью на самом простом базовом уровне, но которая от этого не становится менее интересной. Это задача о кратчайшей системе дорог или задача Штейнера.
Впервые она появилась, когда еще никаких практических надобностей для больших сетей не было: в тридцатые годы XX века. На самом деле Штейнер начал ее изучать еще раньше, в XIX веке. Это была чисто геометрическая задача, практические приложения которой стали известны только несколько десятилетий спустя.
Разговор пойдет о той области математики, которая впоследствии выросла в теорию больших сетей и разбилась на несколько областей. Это прикладная отрасль, которая задействует очень много методов из других математических дисциплин: дискретной математики, теории графов, функционального анализа, теории чисел и т.д. Бурное развитие теории больших сетей пришлось на конец девяностых и начало двухтысячных годов. Связано это конечно, с прикладными задачами: развитием интернета, мобильной связи, транспортных задач для больших городов. Кроме того теория сетей используется в биологии (нейронные сети), при построении больших электронных плат и т.п.
Сама задача формулируется очень просто. Есть несколько точек на плоскости, которые нужно связать системой дорог наименьшей суммарной длины таким образом, чтобы по этим дорогам можно было из каждой точки добраться в любую другую. Число точек конечно.
Начать рассказ стоит с истории о том, как на Малом мехмате двум группам учеников – восьмиклассникам и одиннадцатиклассникам дали решать одну и ту же задачу. Четыре деревни расположены в вершинах квадрата со стороной четыре километра. Существует ли система дорог, которая связывала бы все эти деревни между собой и имела бы суммарную длину не превосходящую 11 километров.
Если соединять деревни последовательно, то ничего короче, чем три стороны квадрата мы не придумаем. При таком соединении у нас будет ровно 12 километров. Можно соединять по диагонали, но это будет только хуже, т.к. диагональ длиннее стороны.
Если поставить дополнительную вершину, тогда из нее можно будет проехать в любые четыре деревни. Если мы возьмем дороги, связывающие диаметрально противоположные вершины, то по неравенству треугольника, сумма их длин будет больше, чем длина диагонали. У и двух других сумма длин тоже больше, чем длина диагонали. Соответственно, сумма всех дорог у нас будет ≥2∙4√2=8√2≈11.31. Примерно так рассуждали одиннадцатиклассники, которые пытались доказать невозможность существования такой системы дорог.
В это же самое время в соседней аудитории восьмиклассники при помощи обычной линейки с делениями строили эту самую систему дорог. И в итоге им это удалось. Система представляет собой нечто похожее на букву Н, все углы в которой равны 120°. Ее длина составляет ≈10.98 километра. Это и есть сеть Штейнера, соединяющая четыре точки. Таких сетей может быть много, может быть несколько кратчайших, но такую задачу о кратчайшей системе дорог можно решить полностью методами элементарной геометрии.
Чтобы окончательно покончить с этой задачей, найдем ошибку в первом решении, где мы вроде как доказали, что ничего короче 8√2 быть не может. Просто в этом решении не была учтена возможность многократно использовать один и тот же участок.
Сеть Штейнера для треугольника была известна еще за 200 лет до самого Якоба Штейнера, в XVII веке. Это так называемая точка Ферма-Торичелли-Штейнера.
Начнем мы с того, что докажем одно вспомогательное утверждение, называемое иногда теоремой Помпею. Если мы возьмем на плоскости равносторонний треугольник и любую другую точку плоскости, тогда сумма расстояний до двух вершин A и B всегда больше или равно расстоянию до третьей вершины C: MA + MB ≥ MC. Более того, MA + MB = MC только в том случае, когда точка M лежит на дуге описанной окружности, не содержащей точку С. Т.е. угол AMB должен быть равен 120°. В противном случае MA + MB > MC.
Конечно, если речь идет о равностороннем треугольнике, нам часто в таких задачах помогает поворот на 60° относительно какой-нибудь вершины. Это мы и сделаем: повернем заштрихованный треугольник AMB относительно вершины A по часовой стрелке. Точка B у нас перейдет в точку C, а Точка M – в точку M’. В итоге у нас получается, что AM = AM’ = MM’, а M’C = MB.Теперь мы можем применить обычное неравенство треугольника на треугольнике MM’C. В нем сумма двух сторон M’M и M’C больше, чем MC. Соответственно, MA + MB ≥ MC. А когда же достигается равенство? Равенство достигается, когда точка M’ точно попадает на прямую MC, т.е. когда угол AMC равен 120°.
Теперь перейдем непосредственно к задаче Штейнера для трех точек. Формулируется она следующим образом. Задан треугольник. Нужно найти точку на плоскости, сумма расстояний от которой до вершин этого треугольника наименьшее. TA + TB + TC → min.
Что же это за точка? Мы знаем несколько замечательных точек треугольника: центры вписанной и описанной окружностей, точка пересечения медиан, точка пересечения высот. К сожалению, ни одна из них на роль точки с наименьшей суммой расстояний не подходит. Эта точка совершенно особая, и называется по-разному: точкой Торичелли, точкой Ферма, точкой Штейнера. Представляет она собой точку, из которой все три вершины треугольника видны под одинаковыми углами – 120°. Разберемся, почему это именно так. Впервые решение задачи о точке с наименьшей суммой расстояний до всех вершин треугольника документально впервые появилось в книге итальянского физика и математика Винченцо Вивиани в середине XVII века. Однако известно, что решение этой задачи было получено еще раньше другом Вивиани, Эванджелиста Торичелли – оба они были учениками Галилея. Приведенное в книге решение не было геометрическим, оно было основано на физических принципах. Эту задачу до Торичелли знал, а возможно, и решил Пьер Ферма: они состояли в переписке, и про эту задачу Торичелли узнал именно от Ферма, но было ли у нег свое решение – неизвестно.
Первое геометрическое решение этой задачи появилось лишь спустя 200 лет, и автором его стал Якоб Штейнер. Он был одним из первых синтетических геометров, решавшим геометрические задачи исключительно геометрическими методами. Основывалось решение Штейнера на рассмотренной нами выше теореме Помпею.
Существует ли вообще такая точка, из которой все углы треугольника видны под углом 120°? Существует она не всегда, а только в том случае, если все углы треугольника строго меньше 120°.
Если все углы треугольника > 120°, то существует единственная точка Торичелли. Построим равносторонний треугольник во внешнюю сторону относительно стороны BC. Построим окружность, которая проходила бы через точки B, A’ и C. Если тока Торичелли в данном случае существует, то она должна лежать на этой окружности, на дуге между точками B и C. Во вписанном четырехугольнике сумма противоположных углов составляет 180°. Треугольник BA’C равносторонний, соответственно, все углы в нем равны 60°. А значит, если мы поставим точку на дуге между точками B и C, а затем достроим четырехугольник, угол напротив вершины A’ будет равен 120°.
Но где именно расположить точку, чтобы все вершины были видны под углом 120°. Нужно построить еще один равносторонний треугольник, на этот раз – относительно стороны AC. И точно так же впишем его в окружность. Точка пересечения двух окружностей и будет точкой Торичелли. Мы уже определили, что угол BTC равен 120°, угол ATC получен тем же способом и также равен 120°. В сумме все три угла должны дать 360°, а значит, угол BTA также равен 120°. Таким образом, мы доказали не только существование точки Торичелли, но и то, что она может быть только одна, так как построенные нами дуги могут иметь не более одной точки пересечения. Теоретически окружности могли бы пересечься вне треугольника ABC, но случиться это могло бы только в том случае, если хотя бы один из его углов был больше 120°.
Итак, мы научились находить местоположение точки Торичелли, но так и не объяснили, почему с ее помощью можно решить задачу Штейнера о минимальной сумме расстояний до вершин треугольника. Снова возьмем треугольник ABC, где все углы будут меньше 120° и построим внешний равносторонний треугольник относительно стороны AC. Назовем его AB’C. Далее возьмем произвольную точку M на плоскости и соединим ее со всеми тремя вершинами треугольника ABC. В силу теоремы Помпею MA + MC ≥ MB’. Значит, MA + MB + MC ≥ MB’ + MB, а MB + MB’ ≥ BB’. Так как MB + MB’ не может быть меньше BB’, точка M будет иметь наименьшую сумму расстояний до вершин треугольника ABC только в том случае, когда MB + MB’ = BB’. При каких же условиях такое равенство будет верно? По теореме Помпею для этого нужно, во-первых, чтобы MA + MC было равно MB’, т.е. угол AMC должен быть равен 120°, а во-вторых, сумма отрезков BM и MB’ должна быть равна BB’, т.е. точка M должна лежать на отрезке BB’. Соответственно, углы AMB и BMC также будут равны 120°. Из всего этого следует, что MB + MB’ = BB’ только в том случае, когда точка M совпадает с точкой Торичелли. В этом и заключается решение задачи Штейнера для трех точек.
Каково же решение этой задачи для того случая, когда один из углов треугольника больше или равен 120°? Не будем подробно рассматривать доказательство для этого варианта, скажем лишь, что минимальная сумма расстояний достигается в вершине наибольшего угла треугольника. Доказать это самостоятельно несложно, нужно лишь учесть все то, что мы уже проделали выше.
Оказывается, что точка Ферма-Торичелли-Штейнера – это все, что нужно для построения систем дорог наименьшей длины. Основная задача формулируется следующим образом. На плоскости задано конечное множество (k ≥ 2) точек. Нужно соединить их кратчайшей системой дорог. Сам Штейнер решил эту задачу для k = 3 и привел некоторые примеры для k = 4. Для k ≥ 2 Штейнер даже не ставил задачи. Впервые эта задача была поставлена через 70 лет после смерти Якоба Штейнера двумя чешскими математиками Кесслером и Ярником. В 1934 году задача была опубликована в чешском математическом журнале, но первые несколько лет ей никто не интересовался. Однако в 1941 году два уже известных на тот момент американских математика Гурвиц и Курант поместили ее со ссылкой на Кесслера и Ярника в своей книге, после чего задача стала очень известной.
Досмотрев лекцию до конца, вы узнаете, как решается задача Штейнера в общем виде на плоскости и в пространстве.
Впервые она появилась, когда еще никаких практических надобностей для больших сетей не было: в тридцатые годы XX века. На самом деле Штейнер начал ее изучать еще раньше, в XIX веке. Это была чисто геометрическая задача, практические приложения которой стали известны только несколько десятилетий спустя.
Разговор пойдет о той области математики, которая впоследствии выросла в теорию больших сетей и разбилась на несколько областей. Это прикладная отрасль, которая задействует очень много методов из других математических дисциплин: дискретной математики, теории графов, функционального анализа, теории чисел и т.д. Бурное развитие теории больших сетей пришлось на конец девяностых и начало двухтысячных годов. Связано это конечно, с прикладными задачами: развитием интернета, мобильной связи, транспортных задач для больших городов. Кроме того теория сетей используется в биологии (нейронные сети), при построении больших электронных плат и т.п.
Сама задача формулируется очень просто. Есть несколько точек на плоскости, которые нужно связать системой дорог наименьшей суммарной длины таким образом, чтобы по этим дорогам можно было из каждой точки добраться в любую другую. Число точек конечно.
Начать рассказ стоит с истории о том, как на Малом мехмате двум группам учеников – восьмиклассникам и одиннадцатиклассникам дали решать одну и ту же задачу. Четыре деревни расположены в вершинах квадрата со стороной четыре километра. Существует ли система дорог, которая связывала бы все эти деревни между собой и имела бы суммарную длину не превосходящую 11 километров.
Если соединять деревни последовательно, то ничего короче, чем три стороны квадрата мы не придумаем. При таком соединении у нас будет ровно 12 километров. Можно соединять по диагонали, но это будет только хуже, т.к. диагональ длиннее стороны.
Если поставить дополнительную вершину, тогда из нее можно будет проехать в любые четыре деревни. Если мы возьмем дороги, связывающие диаметрально противоположные вершины, то по неравенству треугольника, сумма их длин будет больше, чем длина диагонали. У и двух других сумма длин тоже больше, чем длина диагонали. Соответственно, сумма всех дорог у нас будет ≥2∙4√2=8√2≈11.31. Примерно так рассуждали одиннадцатиклассники, которые пытались доказать невозможность существования такой системы дорог.
В это же самое время в соседней аудитории восьмиклассники при помощи обычной линейки с делениями строили эту самую систему дорог. И в итоге им это удалось. Система представляет собой нечто похожее на букву Н, все углы в которой равны 120°. Ее длина составляет ≈10.98 километра. Это и есть сеть Штейнера, соединяющая четыре точки. Таких сетей может быть много, может быть несколько кратчайших, но такую задачу о кратчайшей системе дорог можно решить полностью методами элементарной геометрии.
Чтобы окончательно покончить с этой задачей, найдем ошибку в первом решении, где мы вроде как доказали, что ничего короче 8√2 быть не может. Просто в этом решении не была учтена возможность многократно использовать один и тот же участок.
Три точки
Сеть Штейнера для треугольника была известна еще за 200 лет до самого Якоба Штейнера, в XVII веке. Это так называемая точка Ферма-Торичелли-Штейнера.
Начнем мы с того, что докажем одно вспомогательное утверждение, называемое иногда теоремой Помпею. Если мы возьмем на плоскости равносторонний треугольник и любую другую точку плоскости, тогда сумма расстояний до двух вершин A и B всегда больше или равно расстоянию до третьей вершины C: MA + MB ≥ MC. Более того, MA + MB = MC только в том случае, когда точка M лежит на дуге описанной окружности, не содержащей точку С. Т.е. угол AMB должен быть равен 120°. В противном случае MA + MB > MC.
Конечно, если речь идет о равностороннем треугольнике, нам часто в таких задачах помогает поворот на 60° относительно какой-нибудь вершины. Это мы и сделаем: повернем заштрихованный треугольник AMB относительно вершины A по часовой стрелке. Точка B у нас перейдет в точку C, а Точка M – в точку M’. В итоге у нас получается, что AM = AM’ = MM’, а M’C = MB.Теперь мы можем применить обычное неравенство треугольника на треугольнике MM’C. В нем сумма двух сторон M’M и M’C больше, чем MC. Соответственно, MA + MB ≥ MC. А когда же достигается равенство? Равенство достигается, когда точка M’ точно попадает на прямую MC, т.е. когда угол AMC равен 120°.
Теперь перейдем непосредственно к задаче Штейнера для трех точек. Формулируется она следующим образом. Задан треугольник. Нужно найти точку на плоскости, сумма расстояний от которой до вершин этого треугольника наименьшее. TA + TB + TC → min.
Что же это за точка? Мы знаем несколько замечательных точек треугольника: центры вписанной и описанной окружностей, точка пересечения медиан, точка пересечения высот. К сожалению, ни одна из них на роль точки с наименьшей суммой расстояний не подходит. Эта точка совершенно особая, и называется по-разному: точкой Торичелли, точкой Ферма, точкой Штейнера. Представляет она собой точку, из которой все три вершины треугольника видны под одинаковыми углами – 120°. Разберемся, почему это именно так. Впервые решение задачи о точке с наименьшей суммой расстояний до всех вершин треугольника документально впервые появилось в книге итальянского физика и математика Винченцо Вивиани в середине XVII века. Однако известно, что решение этой задачи было получено еще раньше другом Вивиани, Эванджелиста Торичелли – оба они были учениками Галилея. Приведенное в книге решение не было геометрическим, оно было основано на физических принципах. Эту задачу до Торичелли знал, а возможно, и решил Пьер Ферма: они состояли в переписке, и про эту задачу Торичелли узнал именно от Ферма, но было ли у нег свое решение – неизвестно.
Первое геометрическое решение этой задачи появилось лишь спустя 200 лет, и автором его стал Якоб Штейнер. Он был одним из первых синтетических геометров, решавшим геометрические задачи исключительно геометрическими методами. Основывалось решение Штейнера на рассмотренной нами выше теореме Помпею.
Существует ли вообще такая точка, из которой все углы треугольника видны под углом 120°? Существует она не всегда, а только в том случае, если все углы треугольника строго меньше 120°.
Если все углы треугольника > 120°, то существует единственная точка Торичелли. Построим равносторонний треугольник во внешнюю сторону относительно стороны BC. Построим окружность, которая проходила бы через точки B, A’ и C. Если тока Торичелли в данном случае существует, то она должна лежать на этой окружности, на дуге между точками B и C. Во вписанном четырехугольнике сумма противоположных углов составляет 180°. Треугольник BA’C равносторонний, соответственно, все углы в нем равны 60°. А значит, если мы поставим точку на дуге между точками B и C, а затем достроим четырехугольник, угол напротив вершины A’ будет равен 120°.
Но где именно расположить точку, чтобы все вершины были видны под углом 120°. Нужно построить еще один равносторонний треугольник, на этот раз – относительно стороны AC. И точно так же впишем его в окружность. Точка пересечения двух окружностей и будет точкой Торичелли. Мы уже определили, что угол BTC равен 120°, угол ATC получен тем же способом и также равен 120°. В сумме все три угла должны дать 360°, а значит, угол BTA также равен 120°. Таким образом, мы доказали не только существование точки Торичелли, но и то, что она может быть только одна, так как построенные нами дуги могут иметь не более одной точки пересечения. Теоретически окружности могли бы пересечься вне треугольника ABC, но случиться это могло бы только в том случае, если хотя бы один из его углов был больше 120°.
Итак, мы научились находить местоположение точки Торичелли, но так и не объяснили, почему с ее помощью можно решить задачу Штейнера о минимальной сумме расстояний до вершин треугольника. Снова возьмем треугольник ABC, где все углы будут меньше 120° и построим внешний равносторонний треугольник относительно стороны AC. Назовем его AB’C. Далее возьмем произвольную точку M на плоскости и соединим ее со всеми тремя вершинами треугольника ABC. В силу теоремы Помпею MA + MC ≥ MB’. Значит, MA + MB + MC ≥ MB’ + MB, а MB + MB’ ≥ BB’. Так как MB + MB’ не может быть меньше BB’, точка M будет иметь наименьшую сумму расстояний до вершин треугольника ABC только в том случае, когда MB + MB’ = BB’. При каких же условиях такое равенство будет верно? По теореме Помпею для этого нужно, во-первых, чтобы MA + MC было равно MB’, т.е. угол AMC должен быть равен 120°, а во-вторых, сумма отрезков BM и MB’ должна быть равна BB’, т.е. точка M должна лежать на отрезке BB’. Соответственно, углы AMB и BMC также будут равны 120°. Из всего этого следует, что MB + MB’ = BB’ только в том случае, когда точка M совпадает с точкой Торичелли. В этом и заключается решение задачи Штейнера для трех точек.
Каково же решение этой задачи для того случая, когда один из углов треугольника больше или равен 120°? Не будем подробно рассматривать доказательство для этого варианта, скажем лишь, что минимальная сумма расстояний достигается в вершине наибольшего угла треугольника. Доказать это самостоятельно несложно, нужно лишь учесть все то, что мы уже проделали выше.
Оказывается, что точка Ферма-Торичелли-Штейнера – это все, что нужно для построения систем дорог наименьшей длины. Основная задача формулируется следующим образом. На плоскости задано конечное множество (k ≥ 2) точек. Нужно соединить их кратчайшей системой дорог. Сам Штейнер решил эту задачу для k = 3 и привел некоторые примеры для k = 4. Для k ≥ 2 Штейнер даже не ставил задачи. Впервые эта задача была поставлена через 70 лет после смерти Якоба Штейнера двумя чешскими математиками Кесслером и Ярником. В 1934 году задача была опубликована в чешском математическом журнале, но первые несколько лет ей никто не интересовался. Однако в 1941 году два уже известных на тот момент американских математика Гурвиц и Курант поместили ее со ссылкой на Кесслера и Ярника в своей книге, после чего задача стала очень известной.
Досмотрев лекцию до конца, вы узнаете, как решается задача Штейнера в общем виде на плоскости и в пространстве.
