Кратчайшие сети. Доступное введение в задачах и решениях

Сергей Гашков
Кратчайшие сети. 
Доступное введение 
в задачах и решениях
Москва, 2024

УДК	 514
ББК 22.151
Г24
Гашков С. Б.
Г24 	 Кратчайшие сети. Доступное введение в задачах и решениях. – 
М.: ДМК Пресс, 2024. – 114 с.: ил. 
ISBN 978-5-93700-298-3
Книга посвящена старой, но незаслуженно забытой задаче о том, 
как соединить данное множество пунктов на плоскости кратчайшей 
сетью прямолинейных отрезков. Этот важный вопрос интересен еще 
и тем, что даже в простейших случаях он приводит к любопытным 
и непростым геометрическим решениям. В общем случае эта задача 
трудна и является предметом серьезных современных исследований. 
В данном пособии будет подробно рассмотрен только случай трех или 
четырех точек на плоскости либо в пространстве.
Изложение доступно даже школьникам и будет интересно всем 
любителям математики.
УДК  514
ББК  22.151
Все права защищены. Любая часть этой книги не может быть воспроизведена в какой бы то ни было форме и какими бы то ни было средствами 
без письменного разрешения владельцев авторских прав.
	
©  Гашков С. Б., 2024
ISBN 978-5-93700-298-3	
©  Оформление, издание,  
ДМК Пресс, 2024

Содержание
От издательства.................................................................................... 5
Введение.................................................................................................. 6
Глава 1. Кратчайшие сети и задача  
Ферма–Торричелли............................................................................ 9
1.1. Случай трех точек................................................................................ 9
1.2. Точки Ферма–Торричелли для треугольника................................11
1.3. Кратчайшие сети из двух отрезков и из трех отрезков................15
1.3.1. Окончание решения задачи 4: почти чистая геометрия......16
1.3.2. Завершение решения задачи 3: алгебра и немного 
тригонометрии......................................................................................16
1.3.3. Еще одно неравенство для длины сети  
Ферма–Торричелли..............................................................................19
1.3.4. Второе доказательство неравенства t £ P/ 3.........................20
1.3.5. Еще о треуголках Наполеона.....................................................20
1.4. Точка Ферма–Торричелли и механика...........................................22
1.5. Еще доказательства свойств точки Ферма–Торричелли 
и неравенства t £ P/ 3..............................................................................24
Глава 2. Задача Ферма–Торричелли для многих  
точек.........................................................................................................27
2.1. Свойство выпуклости........................................................................27
2.2. Необходимое условие для точки Ферма–Торричелли..................29
2.2.1. Задача Ферма–Торричелли для четырехугольников.............30
2.3. А если точек много?...........................................................................32
2.3.1. Случай многоугольников...........................................................34
2.4. Невозможность построения точки Ферма–Торричелли 
циркулем и линейкой  в общем случае...................................................36

4    Содержание
Глава 3. Точки Ферма–Торричелли в пространстве..........41
3.1. Точки Ферма–Торричелли в тетраэдрах.........................................41
3.1.1. Для какой четверки единичных векторов сумма равна 
нулю?......................................................................................................43
3.1.2. Четверки векторов и равногранные тетраэдры.....................44
3.1.3. Когда точка Ферма–Торричелли лежит внутри  
тетраэдра?..............................................................................................47
3.2. Точки Ферма–Торричелли в правильных многогранниках........51
Глава 4. Плоские сети Штейнера................................................53
4.1. Что такое сети, или деревья, Штейнера?........................................53
4.1.1. Свойства деревьев Штейнера....................................................56
4.2. Сети Штейнера для трех и четырех точек......................................61
4.2.1. Деревья Штейнера для параллелограммов.............................69
4.2.2. Деревья Штейнера для трапеций.............................................71
Глава 5. Деревья Штейнера в пространстве.........................77
5.1. Сети Штейнера для правильного и полуправильного  
тетраэдров..................................................................................................79
5.2. Дерево Штейнера и минимальная стягивающая сеть  
без точек Штейнера..................................................................................85
Глава 6. Минимальные стягивающие деревья  
в графах..................................................................................................89
6.1. Алгоритм Ярника–Прима.................................................................93
6.2. Алгоритм Краскала..........................................................................101
6.3. Минимальные стягивающие деревья на плоскости...................108
Литература...........................................................................................111
Предметный указатель..................................................................112

От издательства
Отзывы и пожелания
Мы всегда рады отзывам наших читателей. Расскажите нам, что 
вы ду-маете об этой книге – что понравилось или, может быть, не 
понравилось. Отзывы важны для нас, чтобы выпускать книги, которые будут для вас максимально полезны.
Вы можете написать отзыв на сайте www.dmkpress.com, зайдя 
на страницу книги и  оставив комментарий в  разделе «Отзывы 
и рецензии». Также можно послать письмо главному редактору по 
адресу dmkpress@gmail.com, указав название книги в теме письма. 
Если вы являетесь экспертом в какой-либо области и заинтересованы в написании новой книги, заполните форму на нашем сайте 
по адресу http://dmkpress.com/authors/publish_book/ или напишите 
в издательство по адресу dmkpress@gmail.com.
Список опечаток
Хотя мы приняли все возможные меры для того, чтобы обеспечить 
высокое качество наших текстов, ошибки все равно случаются. Если 
вы найдете ошибку в одной из наших книг, мы будем очень благодарны, если вы сообщите о ней главному редактору по адресу dmkpress@
gmail.com. Сделав это, вы избавите других читателей от недопонимания и поможете нам улучшить последующие издания этой книги. 
Нарушение авторских прав
Пиратство в  интернете по-прежнему остается насущной проблемой. Издательство «ДМК Пресс» очень серьезно относится к вопросам защиты авторских прав и лицензирования. Если вы столкнетесь 
в интернете с незаконной публикацией какой-либо из наших книг, 
пожалуйста, пришлите нам ссылку на интернет-ресурс, чтобы мы 
могли применить санкции.
Ссылку на подозрительные материалы можно прислать по адресу элект-ронной почты dmkpress@gmail.com.
Мы высоко ценим любую помощь по защите наших авторов, 
благодаря которой мы можем предоставлять вам качественные 
материалы.

Введение
Книга посвящена задаче о том, как соединить данное множество 
пунктов на плоскости кратчайшей сетью прямолинейных отрезков. Этот трудный и важный вопрос интересен еще и тем, что даже 
в простейших случаях он приводит к любопытным и непростым 
геометрическим задачам.
Пример такой задачи: где построить школу для учащихся из трех 
деревень, так чтобы сумма расстояний от нее до этих деревень 
была минимальна. Автор в школьные годы не раз встречал ее в научно-популярной математической литературе. Впоследствии он 
узнал, что этой задаче чуть менее 400 лет и она вызывала интерес 
у нескольких ученых XVII века, наиболее известными из которых 
были Пьер Ферма и Эванджелиста Торричелли (разумеется, речь 
шла не о деревнях, а о точках плоскости). Трудно сказать, как они 
пришли к этой задаче. Вряд ли у них был прикладной интерес, 
скорее всего, она их привлекла простотой и естественностью своей 
формулировки. Наверное, сыграло роль и то обстоятельство, что 
в  XVII веке ученые начали широко исследовать экстремальные 
задачи (задачи, в которых нужно было найти максимум или минимум некоторой величины) и искать методы их решения. Одним 
из первопроходцев в этой области и был Ферма (до этого времени 
экстремальные задачи исследовались лишь эпизодически, например древнегреческий геометр Зенодор изучал задачу о построении 
многоугольника данного периметра и максимальной площади).
Но если обратиться к прикладному значению этой задачи, то 
стоит заметить, что оно существенно только в случае, когда руководство района решит соединить школу с деревнями шоссейными 
дорогами и начнет возить школьников на учебу на автобусах. Тогда 
оптимальный выбор места для школы минимизирует и расходы на 
строительство шоссе, и расходы на горючее для автобусов. В случае когда школьникам приходится ходить пешком, наверное, школу лучше построить на равном расстоянии от деревень (в центре 
описанного вокруг данного треугольника круга), чтобы никому не 
было обидно. 

Введение    7
Разумеется, рассматриваемую задачу можно интерпретировать 
и по-другому, например как выбор оптимального места установки 
электростанции (с целью минимизации расходов на постройку линий электропередач). Эта интерпретация сразу подсказывает обобщение рассматриваемой задачи: где для данных n точек выбрать 
одну точку так, чтобы минимизировать сумму расстояний от нее до 
данных точек. Но и с точки зрения чистой математики этот вопрос 
также возникает естественно, поэтому неудивительно, что им занимались и в XIX веке. И он оказался более сложным, чем случай трех 
точек. Было установлено, что оптимальная точка всегда существует 
и определена однозначно. Любопытно, что для 4 точек плоскости 
эта задача решается проще, чем в  случае n  =  3. Действительно, 
если четырехугольник выпуклый, то оптимальная точка совпадает 
с пересечением его диагоналей, а для треугольника ответ зависит 
от величины его углов. Если один из углов не меньше 120°, то оптимальная точка совпадает с его вершиной, а в противном случае эта 
точка лежит внутри треугольника и его стороны из нее видны под 
равными углами (очевидно, по 120° каждый).
Однако если четыре точки не лежат в одной плоскости (т. е. являются вершинами некоторого тетраэдра), то задача поиска оптимальной точки становится гораздо более сложной, чем в плоском 
случае. А если пять точек лежат на плоскости, то в некоторых случаях оптимальную точку нельзя построить циркулем и линейкой. 
Впрочем, в некоторых случаях оптимальную точку можно легко 
построить. Например, если n точек лежат в вершинах правильного 
n-угольника, то оптимальная точка совпадает с его центром. 
Но интерпретация рассматриваемой задачи как проблемы построения минимальной сети из линий электропередач приводит 
естественным образом к следующему ее обобщению: допустим, 
что для построения этой сети можно использовать не одну вспомогательную точку (из которой идут отрезки во все данные точки), 
а несколько точек, которые можно соединять отрезками как между 
собой, так и с данными точками, и данные точки тоже можно соединять отрезками напрямую друг с другом. В частности, можно 
соединить данные точки отрезками прямых, вообще не используя 
вспомогательных точек, можно соединить, используя только одну 
вспомогательную точку, можно соединить, используя две вспомогательные точки, и т. д. Как из всего этого множества вариантов 
(при большом n огромного множества) выбрать оптимальный? Эту 
задачу сейчас связывают с именем знаменитого швейцарского геометра Якоба Штейнера.

8    Введение
В общем случае эта задача очень трудна и является предметом 
серьезных современных исследований. Разумеется, ее обобщили 
во многих разных направлениях. В нашей книжке будет подробно рассмотрен только случай данных трех или четырех точек на 
плоскости либо в пространстве, но зато на уровне, доступном пониманию даже школьников.
В последней главе рассматривается задача о нахождении минимального стягивающего дерева для данного n-вершинного графа, 
в котором ребрам приписаны произвольные веса (числа). Она является естественным обобщением задачи Штейнера для данных 
n точек плоскости или пространства, в которой запрещено использовать вспомогательные точки. В случае малых n эта задача легко 
решается полным перебором всех стягивающих деревьев. Однако 
с ростом n размер перебора растет настолько быстро, что его становится невозможно выполнить даже на суперкомпьютере. Тем не 
менее в 20-е г. XX века чешские математики Борувка и Ярник изобрели быстрые алгоритмы для решения этой задачи, не использующие прямой перебор. В случае применения этих алгоритмов для 
построения кратчайшей сети для точек плоскости еще большего 
их ускорения можно достичь, дополняя эти алгоритмы найденным 
в  30-е г. известным советским математиком Б. Н. Делоне алгоритмом построения триангуляции для данного множества точек 
(триангуляции Делоне). После переоткрытия этих алгоритмов американскими программистами в 50-е годы XX века они стали едва 
ли не самыми популярными алгоритмами информатики. Читатель 
найдет их описание в конце нашей книжки.

Глава 1
Кратчайшие сети и задача 
Ферма–Торричелли
Всё к лучшему в этом лучшем из миров, 
и все законы природы должны выражаться экстремальными принципами.
Г. В. Лейбниц
1.1. Случай трех точек
Пусть даны три точки. Расстояния между ними обозначим a, b, c. 
Обозначения выберем так, чтобы a £ b £ c. Периметр a + b + c 
этого треугольника (он может вырождаться в отрезок) обозначим 
P (буквой p обычно обозначают полупериметр P/2). Кажется очевидным, что кратчайшая сеть (система линий), соединяющая эти 
точки, имеет длину f = a + b и состоит из двух «меньших» сторон 
треугольника.
Действительно, кратчайшие линии, попарно соединяющие эти 
точки, имеют длины, не меньшие a, b, c соответственно, а для связности сети достаточно двух линий из трех.
Первая задача простая.
Задача 1. Докажите, что P/2 £ f £ 2P/3, и приведите примеры, показывающие, что эти неравенства точные (другими словами, они 
могут обращаться в равенства).
Довольно неожиданно, что если использовать вспомогательную 
точку, то сумма расстояний от нее до вершин треугольника (случай 

10    Кратчайшие сети и задача Ферма–Торричелли
вырождения треугольника в отрезок очевиден и поэтому далее не 
упоминается) иногда может быть меньше f.
Точка, в которой достигается минимум этой суммы расстояний, 
называется точкой Ферма–Торричелли, а сам этот минимум далее 
обозначается t.
Задача 2. Если треугольник имеет угол, не меньший 120°, то f = t, 
значит, P/2 < f = t £ 2P/(2 + 
), причем левое неравенство хотя 
и неточное, но заменить его на неравенство cP £ t, где c > 1/2, 
нельзя. Правое неравенство лучше, чем следующее из задачи 1 неравенство t = f £ 2P/3, и оно точное, так как достигается в случае 
равнобедренного треугольника с углом 120° при вершине.
Задача 3. Если в треугольнике все углы не больше 120°, то P/2 < t £ 
P/
, причем левое неравенство, как и в задаче 2, улучшить нельзя, 
а правое неравенство точное и достигается только для правильных 
треугольников. Точка Торричелли однозначно определяется тем, 
что из нее все стороны треугольника видны под равными углами 
(очевидно, по 120°).
Задача 4. Если в треугольнике все углы не больше 120°, то 
f/2 £ t 
< f, причем правое неравенство улучшить нельзя, а левое неравенство точное и достигается только для правильных треугольников. 
Убедиться в точности данных неравенств несложно. В задаче 2 
достаточно вычислить отношения сторон указанного в ней равнобедренного треугольника, а в задаче 3 нужно воспользоваться 
указанным свойством точки Ферма–Торричелли и заметить, что 
в случае правильного треугольника она совпадает с его центром, 
а потом вычислить радиус описанного вокруг него круга.
Неравенство f > P/2 следует из неравенства треугольника f = a + 
b > c, неравенство t > P/2 на самом деле справедливо для суммы 
расстояний до вершин от любой точки на плоскости треугольника.
Задача 5. Докажите, что для любой точки O справедливо неравенство AO + BO + CO ³ (AB + AC + BC)/2.
Указание. В силу неравенства треугольника AO + BO ³ AB. Напишите еще два аналогичных неравенства и почленно их сложите. 
Остается поделить пополам обе части.
Задача 6. Докажите, что неравенство t > P/2 улучшить, вообще 
говоря, нельзя.