§ 4. СЕТИ ШТЕЙНЕРА

Back

Много лет назад автор этих строк давал школьникам на заня-

тиях на Малом мехмате следующую задачу:

36. Четыре деревни расположены в вершинах квадрата со сто-

роной 4 км. Жители хотят соединить их системой дорог так,

чтобы из каждой деревни можно было проехать в любую другую.

Они собрали деньги на 11 км дороги. Хватит ли этого?

Вообще говоря, ясно, что ответ — нет. Если соединить дорога-

ми три стороны квадрата (буквой <П>), то длина составит 12 км.

Если провести две диагонали с перекрёстком в центре, то длина бу-

дет 8√2=11,31. . . км. Меньше ничего уже быть не может. В самом

деле: если есть только одна дорога, соединяющая последователь-

но все вершины (иначе говоря, если перекрёстков не будет), то её

длина будет не меньше трёх сторон квадрата (поскольку дорога,

соединяющая две вершины квадрата, не меньше его стороны), т. е.

не меньше 12 км. Если же есть хотя бы один перекрёсток, то он

соединён дорогами со всеми вершинами квадрата. Значит, длина

дорог не меньше, чем 8√2, потому что сумма расстояний от пере-

крёстка до вершин квадрата не меньше, чем от центра квадрата

до вершин (как мы знаем, минимум суммы расстояний от точки

до вершин четырёхугольника достигается в точке пересечения диа-

гоналей). В этом случае длина дорог не меньше 8√2=11,31. . .

20

Примерно так рассуждали десятиклассники, доказывая, что

ответ в задаче отрицательный. В то время как ничего не подо-

зревавшие восьмиклассники, не знавшие даже теоремы косинусов,

экспериментально, с помощью линейки, приняв 1 сантиметр в те-

тради за 1 км, без труда строили необходимую систему дорог.

37. Найдите ошибку в приведённом <доказательстве>.

Оказывается, кратчайшая система дорог в задаче имеет длину

4(√3+1)=10,928. . . км.

Получается, что отрезки, соединяющие некоторую точку плоско-

сти с вершинами многоугольника, вовсе не обязательно составляют

кратчайшую систему дорог, соединяющих все вершины. Уже для

квадрата кратчайшая система дорог имеет более сложный вид. Ка-

кой? Ответ мы узнаем чуть позже, пока же от квадрата спустимся

к треугольнику. А для трёх точек будет ли решение задачи Фер-

ма—Торричелли—Штейнера давать кратчайшую систему дорог?

То, что минуту назад казалось очевидным, теперь уже вызыва-

ет сомнения. Но, оказывается, что для трёх точек всё нормально:

если углы треугольника меньше 120◦, то кратчайшая система до-

рог, соединяющая его вершины, будет состоять из трёх отрезков

от точки Торричелли до вершин, а если найдётся угол, больший

или равный 120◦, то из двух отрезков — сторон треугольника, вы-

ходящих из этой вершины. Однако, попытка напрямую обобщить

это утверждение с плоскости на пространство почему-то даёт сбой:

38. Паук связал паутину, соединяющую все вершины правиль-

ного тетраэдра. Чему равна наименьшая длина паутины, если

ребро тетраэдра равно 1?

Дадут ли ответ четыре отрезка, соединяющие вершины с цен-

тром тетраэдра? Или паук сможет обойтись меньшей длиной?

В отличие от аналогичной <плоской> задачи — сможет! Суммар-

ная длина четырёх отрезков от центра тетраэдра до вершин равна

√6=2,449. . . В то время как наименьшая возможная длина пау-

тины равна √3+1/√2=2,439. . . Отличие всего в одну сотую!

Задача Штейнера. В пространстве дано k точек. Соединить их

системой кривых наименьшей суммарной длины.

Эта задача была впервые поставлена великим геометром Яко-

бом Штейнером (1796—1863). Родившийся в Швейцарии в кре-

стьянской семье Штейнер был в математике самоучкой. В возрасте

двадцати лет он переехал в Германию, где и работал до конца

жизни, сначала в университете Гейдельберга, а затем — Берлина.

Вклад Штейнера в геометрию огромен. Ему принадлежит мно-

жество новых идей и красивых, иногда весьма трудных теорем.

Он впервые доказал, что треугольник с двумя равными биссек-

трисами — равнобедренный, что все геометрические построения,

21

выполнимые с помощью циркуля и линейки, могут быть осуще-

ствлены с помощью одной линейки, если только нам дана хотя бы

одна окружность и её центр. Так называемый поризм Штейнера,

или <ожерелье Штейнера>, теорема о цепочке касающихся окруж-

ностей, по праву считается одним из красивейших утверждений

геометрии. Как представитель <чистой геометрии>, он был убе-

ждён, что геометрию надо изучать умозрительно, без привлечения

вычислений. Он говорил, что <расчёт заменяет мышление, а гео-

метрия, напротив, это мышление укрепляет>. По его убеждению,

каждая геометрическая задача должна иметь чисто геометриче-

ское решение. Если Штейнеру не удавалось найти геометрическое

решение, он считал задачу не решённой вовсе и не публиковал ре-

шения. По этой причине многие теоремы Штейнера дошли до нас

без доказательств.

Р еше н и е. Мы решим задачу Штейнера для k точек на плос-

кости. С незначительными изменениями это же доказательство

годится и для k точек в пространстве, и даже в пространстве 3n

произвольной размерности. В этом смысле решение задачи Штей-

нера универсально!

Решение разобьём на несколько этапов. Итак, пусть на плос-

кости даны k точек A1, A2, . . ., Ak. Посмотрим, какими свойствами

должна обладать кратчайшая система дорог, соединяющая эти точки.

Первое свойство достаточно очевидно, и вытекает из того, что крат-

чайшим путём из одной точки в другую является отрезок прямой:

а) к р а т ч а йша я с и с т е м а д о р о г с о с т о и т и з о т р е з к о в.

Таким образом, кратчайшая система дорог является плоским

графом — объединением конечного числа отрезков. Концы этих

отрезков — вершины графа, а сами отрезки — его рёбра. Дан-

ные точки A1, . . ., Ak мы будем называть настоящими вершинами

этого графа, все прочие его вершины (перекрёстки дорог) — допол-

нительными. По условию этот граф связный, т. е. из любой его

вершины можно добраться по рёбрам в любую другую. Более того,

этот граф односвязный, т. е. для любой пары вершин существует

единственный путь по рёбрам, их связывающий (при этом всегда

считаем, что никакой путь не проходит дважды по одному ребру).

Связный граф является односвязным тогда и только тогда, когда

он не содержит замкнутых путей (доказательство этого факта —

простое упражнение). Если бы кратчайшая система дорог не была

односвязной, то существовал бы замкнутый путь. Убрав любое ре-

бро из этого пути, мы получили бы связный граф меньшей длины.

Итак, кратчайшую систему дорог надо искать среди односвяз-

ных графов, которые содержат данные точки в качестве вершин

(но могут иметь и дополнительные вершины).

б) л ю б ы е д в а р е б р а, в ы х о д ящи е и з о д н о й в е рши-

ны, о б р а з ую т у г о л н е м е н е е 120◦.

22

В самом деле, если из вершины A выходят рёбра AB и AC,

и угол между ними меньше 120◦, то мы можем заменить эту пару

рёбер другими, также связывающими точки A, B и C, но имеющи-

ми меньшую суммарную длину. Если в треугольнике ABC все углы

меньше 120◦, то поставим одну дополнительную вершину T — точ-

ку Торричелли этого треугольника, соединим её с вершинами A, B

и C, а рёбра AB и AC уберём. Получим связный граф меньшей

длины. А если в треугольнике ABC, скажем, угол при вершине B

больше или равен 120◦, то убираем ребро AC, а вместо него ста-

вим BC. Вновь получим связный граф меньшей длины (рис. 16).

A

B C

T

A

B C

а)

A B

C

A B

C

б)

Рис. 16

Из этого свойства непосредственно следует, что

в) и з н а с т о яще й в е рши н ы м оже т в ы х о д и т ь о д н о,

д в а и л и т р и р е б р а; е с л и в ы х о д и т д в а р е б р а, т о у г о л

м ежд у н и м и б о л ьше и л и р а в е н 120◦; е с л и т р и, т о о н и

о б р а з ую т м ежд у с о б о й у г л ы в 120◦.

Больше трёх рёбер выходить не может, иначе один из углов

будет меньше 120◦.

Таким образом, настоящие вершины бывают трёх типов. С допол-

нительными вершинами дело обстоит проще — все они одного типа:

г) и з к ажд о й д о п о л н и т е л ь н о й в е рши н ы в ы х о д я т

т р и р е б р а п о д у г л а м и 120◦.

Действительно, первый тип для дополнительной вершины не-

возможен (если из дополнительной вершины выходит только одно

ребро, то эта вершина не нужна, потому что её можно убрать вме-

сте с ребром), второй — также невозможен (если дополнительная

вершина M соединена рёбрами только с двумя вершинами B и C,

то уберём эти рёбра вместе с самой вершиной M, а точки B и C

соединим ребром; получим связный граф меньшей длины).

Определение. Сетью Штейнера данных точек A1, . . ., Ak, на-

зывается односвязный граф, имеющий среди своих вершин все

данные точки (эти вершины называются настоящими, прочие —

дополнительными), причём все его настоящие вершины принад-

лежат одному из трёх типов (пункт в), а все дополнительные

вершины принадлежат только третьему типу (пункт г)).

На рис. 17 показана сетьШтейнера, связывающая девять точек.

Теорема. Кратчайшая система дорог, связывающая k точек,

является сетью Штейнера.

23

Как строить такие сети? И вообще,

A1

A9 A8

A6

A4

A3

A5

A2

A7

120◦

Рис. 17

сколько их может быть у данного набо-

ра точек? Ведь мы вольны ставить сколько

угодно дополнительных вершин! Оказывает-

ся, что для данного набора точек существует

лишь конечное число сетей Штейнера.

Можно построить их все, а затем выбрать

из них ту, которая имеет кратчайшую

длину. Она и будет кратчайшей системой

дорог, связывающей данные точки.

Как построение, так и доказательство

осуществляется по индукции. Для этого

нам понадобится лишь одно вспомогатель-

ное утверждение. Настоящую вершину сети

Штейнера назовём тупиковой, если из неё

выходит только одно ребро, и это ребро со-

единяет её с другой настоящей вершиной.

Две настоящие вершины назовём тупиковой парой вершин, если

из каждой из них выходит по одному ребру, и эти рёбра соединя-

ют их с одной и той же дополнительной вершиной. Сеть Штейнера

на рис. 17 имеет две тупиковые вершины — A1 и A8, и одну тупи-

ковую пару вершин — {A4, A5}.

Лемма. В каждой сети Штейнера есть либо тупиковая верши-

на, либо тупиковая пара вершин.

Д о к а з а т е л ь с т в о л е м м ы. Среди всех путей по рёбрам гра-

фа выберем путь, состоящий из наибольшего числа рёбер. Пусть он

начинается в вершине A, а следующая вершина — B. Тогда AB —

единственное ребро, выходящее из A, и A — настоящая вершина.

Если и B — настоящая, то всё доказано: вершина A — тупико-

вая. Если B — дополнительная вершина, то из неё выходят ещё

два ребра: BC и BD. По крайней мере одно из этих рёбер (пусть

это будет BD) не лежит на выбранном пути. Докажем, что BD —

единственное ребро, выходящее из вершины D. Если из D выходит

ещё какое-нибудь ребро BE, то путь E→D→B→. . . будет содер-

жать больше рёбер, чем путь A→B→. . ., что невозможно. Таким

образом, A и D составляют тупиковую пару вершин.

Построение сети Штейнера. Б а з а и н д у к ц и и. Если k=2,

то отрезок, соединяющий две вершины, будет единственной сетью

Штейнера. Действительно, как мы доказали, самый длинный путь

в графе (т. е. содержащий наибольшее число рёбер) оканчивается

либо тупиковой вершиной, либо тупиковой парой вершин. В обоих

случаях это две настоящие вершины. У пути два конца, а настоя-

щих вершин у нас всего две. Поэтому единственная возможность —

самый длинный путь состоит из одного ребра и соединяет две на-

стоящие вершины. Значит, вся сеть состоит из одного ребра.

24

И н д у к т и в н ы й п е р е х о д. Пусть

A

B B

C C

Рис. 18

k≥3. Предположим, что для любых k−1

точек на плоскости существует лишь ко-

нечное число сетей Штейнера, и мы умеем

их все строить. Пусть нам дано k точек.

A

M

D

B

K

M

K

Рис. 19

Согласно лемме, любая сеть Штейнера, со-

единяющая эти точки, содержит либо ту-

пиковую вершину, либо тупиковую пару

вершин.

В первом случае (рис. 18) мы можем

убрать тупиковую вершину вместе с един-

ственным исходящим из неё ребром. Полу-

чаем граф, который будет сетью Штейнера

для оставшихся k−1 точек.

Во втором случае (рис. 19) обозначим

через A и D тупиковую пару вершин, со-

единённых с дополнительной вершиной B,

а через BK — третье ребро, выходящее из вершины B. Построим

на стороне AD равносторонний треугольник AMD так, что точки M

и B лежат по разные стороны от прямой AD. Так как B — допол-

нительная вершина, \ABD=\ABK=\DBK=120◦. Следовательно,

точки A, B, D и M лежат на одной окружности, поэтому \MBA=

=\MDA=60◦. Таким образом, точка B лежит на отрезке MK.

Уберём вершины A и D вместе с дополнительной вершиной B

и со всеми рёбрами, выходящими из B. Вместо них поставим одну

настоящую вершину M и соединим её ребром с вершиной K. По-

лучим сеть Штейнера, связывающую k−1 точек.

Таким образом, построение любой сети Штейнера для k точек

сводится к аналогичной задаче для k−1 точек. Получаем и н д у к-

т и в н ый а л г о р и т м. Пусть дано k точек A1, . . ., Ak. Тогда:

1-й способ. Временно убираем любую из точек Aj, j=1, . . ., k,

строим сеть Штейнера для оставшихся k−1 точек, затем соединя-

Ai

M

Aj

B

K

Рис. 20

ем Aj ребром с любой из этих k−1 точек.

2-й способ. Выбираем две точки Ai, Aj из

k данных, строим равносторонний треугольник

MAiAj и временно заменяем две точки Ai, Aj на од-

ну точку M. Для получившихся k−1 точек стро-

им сеть Штейнера. Обозначаем через B точку пе-

ресечения описанной окружности треугольника

MAiAj с ребром MK, выходящим из вершины M.

Теперь убираем вершину M, ставим обратно вер-

шины Ai и Aj, ставим дополнительную вершину B

и соединяем её рёбрами с вершинами Ai, Aj и K.

После каждого шага нужно проверить, бу-

дет ли построенный граф сетью Штейнера для

25

точек A1, . . ., Ak. При этом как бы мы ни действовали, хоть по пер-

вому, хоть по второму способу, нет гарантии, что всякий раз будет

получаться сеть Штейнера. Например, если действовать по пер-

вому способу, то новое ребро, соединяющее точку Aj с некоторой

точкой Am, может составлять угол, меньший 120◦ с каким-либо

из <старых> рёбер, выходящих из Am. Если действовать по второму

способу, то ребро MK может вовсе не пересечь окружность MAiAj,

а может пересечь её не в том месте (нужно, напомним, чтобы точка

пересечения лежала на дуге AiAj, не содержащей точку M). В обо-

их случаях мы не сможем поставить дополнительную вершину B.

Важно другое: л ю б а я сеть Штейнера точек A1, . . ., Ak полу-

чается таким способом! Все сетиШтейнера будут содержаться среди

построенных графов. Мы уже доказали это, опираясь на лемму.

Посмотрим, как строятся сети Штейнера для малого числа

точек. Со случаем k=2 всё ясно, займёмся случаем k=3.

Пр и м е р 1. k=3, точки A1, A2, A3 — произвольные.

П е р в ы й с п о с о б. Уберём любую из трёх точек, напри-

мер, A1. Сетью Штейнера оставшихся двух точек будет отрезок

A2A3. Теперь соединяем точку A1 с любой из вершин A1 или A2.

В любом случае получаем две стороны треугольника A1A2A3. Если

угол между ними не меньше 120◦, то это будет сетью Штейнера.

В т о р о й с п о с о б. Убираем две вершины, например, A1

и A2. Строим равносторонний треугольник A1MA2, затем находим

точку пересечения дуги A1A2 его описанной окружности с отрез-

ком MA3. Если они пересекаются, то обозначаем точку пересечения

через B. Получаем сеть Штейнера, состоящую из трёх отрез-

ков BA1, BA2, BA3. Легко видеть, что B — точка Торричелли

треугольника A1A2A3. Итак,

Для трёх точек всегда существует единственная сеть Штейне-

ра. Если один из углов треугольника с вершинами в этих точках

больше или равен 120◦, то сеть состоит из двух рёбер — сторон

этого угла. Если все углы меньше 120◦, то она состоит из трёх

рёбер, соединяющих точку Торричелли (дополнительную верши-

ну) с тремя вершинами.

Уже для четырёх точек может быть несколько сетей Штейнера.

Всё зависит от их взаимного расположения. Построим кратчайшую

систему дорог для четырёх вершин квадрата, решив, таким обра-

зом, задачу 36.

Пр и м е р 2. k=4, точки A1, A2, A3, A4 — вершины квадрата.

П е р в ы й с п о с о б. Убираем вершину A1. В оставшемся тре-

угольнике A2A3A4 углы меньше 120◦, поэтому его сеть Штейнера

состоит из отрезков TA2, TA3, TA4, где T — точка Торричелли

треугольника A2A3A4. Теперь нужно соединить A1 с любой из вер-

шин A2, A3 или A4. Однако, как легко видеть, при этом каждый

раз будут получаться два ребра с углом меньше 120◦. Итак, п е р-

26

вы й с п о с о б н е д а ё т с е т и Шт е й н е р а.

В т о р о й с п о с о б. Убираем пару вершин.

A1 A2

A3 A4

B

T

M

Рис. 21

В силу симметрии, достаточно рассмотреть два

случая: вершины A1, A3 (концы диагонали)

и вершины A1, A2 (концы стороны). В первом

случае (убрали A1 и A3) строим равносторон-

ний треугольник A1MA3. Три точки M, A2 и A4

лежат на одной прямой, поэтому их сеть Штей-

нера состоит из двух отрезков MA2 и A4A2.

Ребро MA2 не пересекает дуги A1A3 описан-

ной окружности треугольника A1MA3. Таким

образом, этот случай не даёт сети Штейне-

A1 A2

A3 A4

Рис. 22

ра. Во втором случае (убрали A1 и A2) строим

равносторонний треугольник A1MA2. Если он

построен во внутреннюю сторону квадрата, то

вновь не получается сети Штейнера (оставим

разобрать этот случай читателю). Если во внеш-

нюю сторону, то A3MA4 — остроугольный; его

сеть Штейнера — три отрезка, соединяющие

его вершины с точкой Торричелли T. Ребро TM

пересекает описанную окружность треугольни-

ка A1MA2 в точке B (рис. 21).

В итоге мы получили сеть Штейнера, показанную на рис. 22.

Она состоит из пяти рёбер и имеет две дополнительные вершины.

Если сторона квадрата равна 4 (как в задаче о деревнях), то сум-

марная длина дорог равна

4(√3+1)=10,928. . .

Оказывается, что кратчайшая система дорог имеет два перекрёст-

ка, а не один!

Как видим, уже для четырёх точек требуется перебрать много

вариантов, чтобы построить сеть Штейнера. Для пяти точек таких

вариантов будет ещё больше, кроме того, самих сетей Штейнера

может быть много. Вообще говоря, только одна (или несколько)

из них является кратчайшей системой дорог, все остальные —

локально кратчайшие, т. е. любая система, достаточно близкая

к данной, будет иметь бо’ льшую длину. Математики в таких случа-

ях говорят, что каждая сеть Штейнера даёт локальный минимум

в задаче, а одна или несколько из них дают глобальный мини-

мум, т. е. являются самыми короткими среди всех систем дорог,

а не только среди близких. Так, уже для квадрата существует

не одна, а две сети Штейнера (первая — та, которую мы построили,

вторая — получающаяся из первой поворотом на 90◦ вокруг цен-

тра квадрата). Они равны, поэтому обе дают глобальный минимум.

27

Современная вычислительная техника даёт возможность осу-

ществлять перебор огромного числа вариантов и легко строить

сети Штейнера, например, для двадцати точек. Системы дорог

в местностях с однородным рельефом (например, в степи) строятся

по сетям Штейнера. Нефтяные и газовые трубопроводы в россий-

ской и канадской тундре также строятся по сетям Штейнера. Сети

Штейнера можно встретить и в природе, например, в структу-

ре полимерных молекул. А увидеть их наглядно можно, проделав

следующий опыт: вбить в доску несколько гвоздей, опустить её

в мыльный раствор, а затем вытащить. Мыльная плёнка натянется

между гвоздями по сети Штейнера. Вернее, по одной из возмож-

ных сетей (ведь если гвоздей больше трёх, то сетей может быть

несколько), причём не обязательно по самой короткой. Мы вернём-

ся к этой модели в § 8 (задача 72).

39. Постройте сети Штейнера для четырёх вершин прямо-

угольника размером 3×4. Какая из них является кратчайшей

системой дорог, и чему равна её длина?

40. Сколько сетей Штейнера может быть у равнобедренной

трапеции? Приведите соответствующие примеры.

41. Постройте кратчайшую систему дорог, соединяющих вер-

шины правильного пятиугольника.

42. Придумайте способ построения сетей Штейнера для k точек

в пространстве и проведите все доказательства.

43. Постройте сети Штейнера для четырёх вершин правильно-

го тетраэдра (решив, таким образом, задачу 38 о пауке).

44. Постройте хотя бы одну сеть Штейнера для вершин куба.

Навигация