LINEBURG


<< Пред. стр.

страница 2
(всего 5)

ОГЛАВЛЕНИЕ

След. стр. >>

а) в)
б)
a2 b
M
Читатель без труда выведет уравнения этих кривых, при этом
F
фокусы эллипса и гиперболы нужно расположить на оси Ox сим- F2 F1
F2 F1
метрично относительно начала координат, а фокус параболы —
M
на оси Oy. Если a=b, то эллипс превращается в окружность радиу- d
са a, а гипербола в этом случае становится так называемой прямой
гиперболой, которая после поворота на 45? относительно начала ко- Рис. 10
ординат принимает вполне знакомый вид y=k/x, где k=a2 /2.
Из уравнения эллипса видно, что он получается из окружности Таким образом, луч света, вышедший из фокуса эллипса, отра-
после сжатия вдоль оси Oy в a/b раз, чем оправдывает слова зится от его поверхности и попадёт во второй фокус. Если в фокусе
о том, что он является <сжатой окружностью>. Это можно было эллипса находится источник света, то пучок световых лучей после
бы установить и без уравнения. Дело в том, что эллипс получается отражения от поверхности эллипса сойдётся во втором фокусе.
в сечении не только конуса, но и цилиндра (рис. 9), при этом дока- Если источник света поместить в одном из фокусов гиперболы,
12 13
то отражённый пучок световых лучей будет расходящимся, а во-
ображаемые продолжения лучей соберутся во втором фокусе.
Наконец, пучок света, выходящий из фокуса параболы, отра-
зившись от её поверхности, становится пучком параллельных лучей.
B A
Фокальное свойство параболы, открытое ещё Аполлонием, ны-
не используется повсеместно. Параболическое зеркало в карманном
лучевой
фонарике создаёт узкий направленный световой луч. Принцип шнур
работы параболической антенны или параболического зеркала в те-
лескопе также основан на свойстве параболы превращать пучок
параллельных лучей (а значит, и лучей, идущих от далёкого ис- Рис. 11
точника) в пучок, сходящийся в одной точке.
теперь всему миру гиперболоиде инженера Гарина на самом де-
В фантастическом романе Алексея Толстого <Гиперболоид инже-
ле нет ни одного гиперболоида. Внешнее зеркало A должно иметь
нера Гарина> устройство страшного разрушительного оружия — ги-
форму эллипсоида, а внутреннее B — параболоида.
перболоида, которым Гарин хотел покорить мир, — описывалось так:
Нам осталось доказать фокальные свойства коник.
Д о к а з а т е л ь с т в о т е о р е м ы. Проведём касательную
<Гарин, раскрывая чемодан, посматривал на неё обведёнными синевой блестя-
к эллипсу в точке M. Точка M лежит на эллипсе, поэтому MF1 +
щими глазами.
— Вот мой аппарат, — сказал он, ставя на стол два металлических ящика: +MF2 =c, все остальные точки касательной лежат вне эллипса,
один — узкий, в виде отрезка трубы, другой — плоский, двенадцатигранный —
поэтому для остальных точек сумма расстояний до фокусов боль-
втрое большего диаметра. . .
Он наклонился над Зоиным креслом (вдохнул запах её волос), развернул ше c. Таким образом, в точке M достигается минимум суммы
чертёжик, размером с половину листа писчей бумаги.
расстояний до точек F1 и F2 . Значит, точка, симметричная F2 от-
— Вы хотели, Зоя, чтобы я также рискнул всем в нашей игре. . . Смотрите
носительно касательной, лежит на прямой F1 M, откуда следует
сюда. . . Это основная схема. . . Это просто, как дважды два. Чистая случайность,
что это до сих пор не было построено. Весь секрет в гиперболическом зеркале A, фокальное свойство. Точно так же доказывается фокальное свой-
напоминающем формой зеркало обыкновенного прожектора, и в кусочке шамо-
ство гиперболы (при этом применяется результат задачи 7).
нита B, сделанном также в виде гиперболической сферы. Закон гиперболических
Докажем фокальное свойство параболы. Опустим из произ-
зеркал таков: лучи света, падая на внутреннюю поверхность гиперболического зер-
кала, сходятся все в одной точке, в фокусе гиперболы. Это известно. Теперь, вот вольной точки M параболы перпендикуляр MH на директрису
что неизвестно: я помещаю в фокусе гиперболического зеркала вторую гипербо-
и проведём прямую, которая делит угол HMF пополам (рис. 12).
лу (очерченную, так сказать, навыворот) — гиперболоид вращения B, выточенный
из тугоплавкого, идеально полирующегося минерала — шамонита, — залежи его Любая точка этой прямой равноудалена от точек F и H, а значит,
на севере России неисчерпаемы. Что же получается с лучами? Лучи, собираясь
расстояние от неё до точки F больше, чем до директрисы (если
в фокусе зеркала A, падают на поверхность гиперболоида B, и отражаются от не-
только эта точка не совпадает с M). Поэтому все точки этой пря-
го математически параллельно, — иными словами, гиперболоид B концентрирует
все лучи в один луч, или в <лучевой шнур> любой толщины. . . Путём установки мой, кроме M, лежат вне параболы. Значит это — касательная.
гиперболоида B, я доводил <лучевой шнур> до толщины вязальной спицы и легко
Таким образом, касательная образует равные углы с прямой FM
разрезывал им дюймовую доску. . . Здания, крепости, дредноуты, воздушные кора-
и осью параболы.
бли, горы, кора земли — всё пронижет, разрежет мой луч. . . >
18. Дано семейство эллипсов с фокусами в двух данных точ-
ках F1 и F2 , а также семейство гипербол с фокусами в тех же
Вы наверняка заметили несколько неточностей в конструкции
точках F1 , F2 . Тогда любой эллипс пер-
гиперболоида. Гиперболическое зеркало переводит пучок свето-
вого семейства перпендикулярен любой
вых лучей, выходящих из фокуса, не в сходящийся, а, напротив, N
гиперболе второго семейства (две линии
в расходящийся пучок света. Как мы теперь знаем, лучи вовсе
называются перпендикулярными, если
не сойдутся в фокусе гиперболы. Это их воображаемые продолже-
касательные к ним, проведённые в их
ния сойдутся в фокусе. Для того чтобы отражённые лучи сошлись M
F
точке пересечения, перпендикулярны).
в фокусе, внешнее зеркало A должно иметь форму не гипербо-
19. Рассмотрим множество углов на
лы, а эллипса. А чтобы внутреннее зеркало B переводило пу-
d
плоскости, у каждого из которых од-
чок отражённых лучей в параллельный пучок (<лучевой шнур>),
H
на сторона лежит на данной прямой,
оно должно иметь форму, опять же, не гиперболы, а параболы
а другая проходит через данную точку. Рис. 12
(рис. 11). В этом писатель ошибся. Парадоксально, но в известном
14 15
Тогда биссектрисы всех этих углов касаются одной параболы. времени, снабдил длинным названием: <Пятая книга сочинений
(В таком случае говорят, что эта парабола является огибающей Аполлония Пергского о конических сечениях, заключает в се-
данного семейства прямых.) бе первые исследования о наибольших и наименьших величинах
20. Из любой точки директрисы парабола видна под прямым и признаётся самым замечательным памятником этого великого
углом. геометра> (<De maximis et minimis geometrica divinatio in quintum
21. На плоскости дан угол. Найти огибающую всевозможных conicorum Apollonii Pergoei nunc desideratum>). Среди множества
прямых, отсекающих от него треугольник данной площади. задач на максимум и минимум, помещённых в этой книге, есть такая:
22. На плоскости дана окружность и точка A. На окружности 27. На плоскости даны три точки A, B, C, не лежащие на одной
берётся произвольная точка N и через неё проводится перпенди- прямой. Для какой точки T плоскости сумма расстояний AT+
куляр к прямой AN. Тогда +BT+CT наименьшая?
а) если A лежит внутри окружности, то все такие перпендику- Ещё до книги Вивиани этой задачей интересовался итальян-
ляры касаются эллипса; ский математик Бенавентура Кавальери (1598—1647), автор зна-
б) если A лежит вне окружности, то все перпендикуляры каса- менитого <принципа Кавальери> для вычисления площадей и объ-
ются гиперболы. ёмов, предвосхитившего интегральное исчисление, а также мате-
в) Соответствует ли <пограничный> случай (точка A лежит матик и физик Эванджелиста Торричелли (1608—1647). Говорят,
на окружности) параболе? Сформулируйте и докажите утвержде- что именно Торричелли получил первое решение этой задачи (ско-
ние, аналогичное а) и б), которое бы соответствовало параболе. рее всего, основанное на физических соображениях). Торричелли,
23. Все точки, из которых эллипс виден под прямым углом, как и Вивиани, был учеником Галилея. Именно им в конце
образуют окружность. своей жизни уже ослепший Галилей диктовал главы из своей
24 (теорема Шюллера). К параболе проведены три касатель- книги <Беседы о механике>. Подобно многим учёным позднего
ные. Описанная окружность треугольника, образованного этими Возрождения, Торричелли был разносторонним человеком. Бу-
касательными, проходит через фокус, а точка пересечения высот дучи профессором математики Флорентийского университета, он
этого треугольника лежит на директрисе. много занимался задачами физики (его закон распределения да-
25. На плоскости дана прямая, точка C, лежащая на ней, вления жидкости известен теперь каждому школьнику), а также
и точки A и B, не лежащие на ней. На прямой берётся точка M. механики, баллистики и оптики, и даже написал несколько ра-
Найти огибающую прямых, симметричных прямой BM относи- бот по конструированию оптических приборов и шлифовке линз.
тельно биссектрисы угла AMC. Согласно другим источникам, независимо от Торричелли, эту за-
26. Луч света, идущий внутри эллипса и не проходящий че- дачу решил и величайший французский математик Пьер Ферма
рез его фокусы, последовательно отражается от его поверхности, (1601—1665). А первое чисто геометрическое решение принад-
двигаясь по ломаной линии. Докажите, что все стороны этой лежит, по-видимому, швейцарскому геометру Якобу Штейнеру
ломаной касаются некоторого эллипса. Где расположены его фо- (1796—1863), о котором речь ещё впереди.
кусы? Во что превращается этот эллипс, если луч проходит через Р е ш е н и е. Вновь воспользуемся тем же приёмом: выстроим
фокус исходного эллипса? отрезки AT, BT и CT в ломаную линию. Теперь, однако, вместо
симметрии применим поворот. Повер-
нём плоскость на 60? вокруг точки A, D
§ 3. ЗАДАЧА ФЕРМА—ТОРРИЧЕЛЛИ—ШТЕЙНЕРА
при этом точка C перейдёт в некоторую C
История этой задачи насчитывает более трёх с половиной точку D, а точка T — в точку N. Тре-
столетий. Она была помещена в книге итальянского физика и ме- угольник AND равен треугольнику ATC,
ханика Вивиани <О максимальных и минимальных значениях> поскольку переходит в него при повороте
N
на 60? , значит TC=ND. Треугольник
в 1659 году. Винченто Вивиани (1622—1703) был учеником ве-
ликого Галилео Галилея. Нам он более известен как изобретатель ANT — равносторонний, так как AT=
=AN и ?TAN=60? , поэтому TA=TN.
ртутного барометра (прибора для измерения атмосферного давле- T
ния), а своим современникам — как один из лучших специалистов Итак, сумма AT+BT+CT равна длине
A B
по задачам на максимум и минимум, а также по теории кони- ломаной BTND, а значит, она не меньше
ческих сечений. Своё сочинение Вивиани, следуя традициям того длины отрезка BD (рис. 13). Рис. 13

16 17
Равенство достигается, когда точки B, T, N, тупой (пусть это угол MAC), а зна-
C C
и D лежат на одной прямой (в указанной по- чит, MC>AC, с другой стороны,
M
M
M
M
следовательности). Это означает, что ?BTA+ по неравенству треугольника, MA+
+?ATN=180? и, следовательно, ?BTA= +MB>AB, поэтому N
B
=120? ; а также ?AND+?ANT=180? , значит,
120? A
A
A
A
MA+MB+MC>AB+AC.
?AND=120? , поэтому ?ATC=120? . Таким D
T
образом, лучи TA, TB и TC образуют два
B Если же M лежит внутри угла A, Рис. 15
угла в 120? , поэтому и третий угол между
A ?
то вновь повернём плоскость на 60
ними также равен 120? (рис. 14). (рис. 15), и получим, что треугольник BAD лежит внутри че-
Рис. 14
Точка T, из которой все стороны тре- тырёхугольника BMND, поэтому периметр треугольника меньше
угольника видны под углами 120? , имеет несколько названий. периметра четырёхугольника. Следовательно,
Иногда её называют точкой Ферма, иногда — точкой Торричелли,
AB+AC=AB+AD<BM+MN+ND=BM+AM+CM.
иногда — точкой Штейнера. Доказательство, которое мы привели,
с поворотом плоскости на 60? , принадлежит Якобу Штейнеру. С его Теорема Торричелли—Ферма—Штейнера. Если все углы тре-
замечательными результатами мы ещё не раз встретимся в этой угольника меньше 120? , то точкой минимума суммы расстояний
книге. А первым по времени из этих трёх математиков был Торри- до его вершин является точка Торричелли. Если же один из углов
челли. Поэтому мы будем называть эту точку, по праву первенства, больше или равен 120? , то такой точкой является вершина этого
точкой Торричелли (мы и обозначили её буквой T). Это ещё од- угла.
на замечательная точка треугольника, наряду с центром тяжести 28. Все углы треугольника ABC меньше 120? . На его сторо-
(точкой пересечения медиан), ортоцентром (точкой пересечения нах во внешнюю сторону построены равносторонние треуголь-
высот), центрами вписанной и описанной окружностей. Правда, ники ABC? , BCA? и CAB? . Тогда описанные окружности этих
в отличие от четырёх замечательных точек, точка Торричелли су- треугольников и отрезки AA? , BB? и CC? пересекаются в одной
ществует не у любого треугольника. Однако мы уже доказали, что точке — точке Торричелли. Кроме того, AA? =BB? =CC? .
Если у треугольника есть точка Торричелли, то она является 29 (теорема Наполеона). Центры описанных окружностей тре-
единственной точкой минимума суммы расстояний до вершин угольников ABC? , BCA? и CAB? являются вершинами равносторон-
треугольника. него треугольника (треугольника Наполеона). Чему равна сторона
Когда же точка Торричелли существует? Пусть из трёх углов треугольника Наполеона, если AA? =c?
треугольника угол при вершине A является наибольшим. Построим
Это утверждение приписывают Наполеону, хотя неизвестно, имеет ли он
на сторонах AC и AB вовнутрь треугольника ABC дуги окруж-
к нему какое-либо отношение. Наполеон немного увлекался геометрией и вполне
ностей, содержащие по 120? . Эти дуги пересекаются в точке A. уважительно относился к математике и математикам. Его окружало много вы-
Если же угол A меньше 120? , то эти дуги имеют ещё и вторую точ- дающихся математиков того времени — Лаплас, Монж, Фурье. Однако многие
историки полагают, что его авторство утверждения о равностороннем треугольни-
ку пересечения (докажите это!), которую мы обозначим через T. ке — не более чем миф, созданный придворными льстецами.
Это и есть точка Торричелли. В самом деле, так как углы ATC
и ATB по построению равны 120? , то и третий угол BTC так- 30. Если на сторонах данного треугольника построить во вну-
же получается равен 360? ?120? ·2=120? . И наоборот, если точка треннюю сторону равносторонние треугольники, то их центры
Торричелли существует, то она строится именно таким образом, также являются вершинами равностороннего треугольника (вну-
поскольку должна лежать на пересечении дуг окружностей вели- треннего треугольника Наполеона). Разность площадей внешнего
чиной в 120? , построенных на сторонах треугольника. Итак, и внутреннего треугольников Наполеона равна площади исходно-
Треугольник имеет точку Торричелли тогда и только тогда, го треугольника.
когда все его углы меньше 120? . 31 (теорема Помпею). Вокруг равностороннего треугольни-
А если один из углов треугольника больше или равен 120? ка ABC описана окружность. Если точка M лежит на меньшей
(например, угол A), то в какой точке сумма расстояний до вершин дуге AB этой окружности, то MC=MA+MB. Для всех осталь-
будет минимальна? Ответ: в вершине этого угла. Доказать это ных точек M плоскости выполнено неравенство MC<MA+MB.
просто. Пусть ?A?120? , а M — произвольная точка плоскости. 32. Докажите, что сумма расстояний от произвольной точки
Если M не лежит внутри угла A, то один из углов MAC или MAB — внутри равностороннего треугольника до его сторон — величина
18 19
постоянная. С помощью этого утверждения получите другое до- Примерно так рассуждали десятиклассники, доказывая, что
казательство теоремы Ферма—Торричелли—Штейнера. ответ в задаче отрицательный. В то время как ничего не подо-
П о д с к а з к а. Через каждую вершину треугольника проведите прямую, зревавшие восьмиклассники, не знавшие даже теоремы косинусов,
перпендикулярную отрезку, соединяющему эту вершину с точкой Торричелли.
экспериментально, с помощью линейки, приняв 1 сантиметр в те-
Эти прямые образуют равносторонний треугольник.
тради за 1 км, без труда строили необходимую систему дорог.
33. На плоскости даны две точки и прямая. Найдите точку,
37. Найдите ошибку в приведённом <доказательстве>.
сумма расстояний от которой до данных точек и до прямой
Оказывается, кратчайшая система дорог в задаче имеет длину
минимальна.
v
34. Дан выпуклый четырёхугольник ABCD. Для какой точ-
4( 3+1)=10,928. . . км.
ки плоскости сумма расстояний до его вершин будет наимень-
шей? Ответ ясен: для точки пересечения диагоналей. Пусть тре- Получается, что отрезки, соединяющие некоторую точку плоско-
угольник ABC — остроугольный. Представим, что вершина D при- сти с вершинами многоугольника, вовсе не обязательно составляют
ближается к вершине C. Тогда четырёхугольник ABCD стремит- кратчайшую систему дорог, соединяющих все вершины. Уже для
ся к треугольнику ABC, а точка минимума суммы расстояний — квадрата кратчайшая система дорог имеет более сложный вид. Ка-
точка пересечения диагоналей — стремится к вершине C. В пре- кой? Ответ мы узнаем чуть позже, пока же от квадрата спустимся
деле получим, что вершина C — точка минимума суммы расстоя- к треугольнику. А для трёх точек будет ли решение задачи Фер-
ний для треугольника ABC. Но ведь на самом деле, как мы знаем, ма—Торричелли—Штейнера давать кратчайшую систему дорог?
минимум суммы расстояний до вершин треугольника ABC дости- То, что минуту назад казалось очевидным, теперь уже вызыва-
гается в его точке Торричелли, а не в вершине C. Противоречие? ет сомнения. Но, оказывается, что для трёх точек всё нормально:
35. Для трёх точек A, B и C на плоскости найдите такую если углы треугольника меньше 120? , то кратчайшая система до-
точку M, для которой значение выражения а) AM+BM+2CM; рог, соединяющая его вершины, будет состоять из трёх отрезков
б) AM+BM?CM достигает наименьшего значения. от точки Торричелли до вершин, а если найдётся угол, больший
или равный 120? , то из двух отрезков — сторон треугольника, вы-
§ 4. СЕТИ ШТЕЙНЕРА ходящих из этой вершины. Однако, попытка напрямую обобщить
Много лет назад автор этих строк давал школьникам на заня- это утверждение с плоскости на пространство почему-то даёт сбой:
тиях на Малом мехмате следующую задачу: 38. Паук связал паутину, соединяющую все вершины правиль-
36. Четыре деревни расположены в вершинах квадрата со сто- ного тетраэдра. Чему равна наименьшая длина паутины, если
роной 4 км. Жители хотят соединить их системой дорог так, ребро тетраэдра равно 1?
чтобы из каждой деревни можно было проехать в любую другую. Дадут ли ответ четыре отрезка, соединяющие вершины с цен-
Они собрали деньги на 11 км дороги. Хватит ли этого? тром тетраэдра? Или паук сможет обойтись меньшей длиной?
Вообще говоря, ясно, что ответ — нет. Если соединить дорога- В отличие от аналогичной <плоской> задачи — сможет! Суммар-
ми три стороны квадрата (буквой <П>), то длина составит 12 км. ная длина четырёх отрезков от центра тетраэдра до вершин равна
v
Если vпровести две диагонали с перекрёстком в центре, то длина бу- 6=2,449. . . В то время как наименьшая возможная длина пау-
v v
дет 8 2=11,31. . . км. Меньше ничего уже быть не может. В самом тины равна 3+1/ 2=2,439. . . Отличие всего в одну сотую!
деле: если есть только одна дорога, соединяющая последователь- Задача Штейнера. В пространстве дано k точек. Соединить их
но все вершины (иначе говоря, если перекрёстков не будет), то её системой кривых наименьшей суммарной длины.
длина будет не меньше трёх сторон квадрата (поскольку дорога, Эта задача была впервые поставлена великим геометром Яко-
соединяющая две вершины квадрата, не меньше его стороны), т. е. бом Штейнером (1796—1863). Родившийся в Швейцарии в кре-
не меньше 12 км. Если же есть хотя бы один перекрёсток, то он стьянской семье Штейнер был в математике самоучкой. В возрасте
соединён дорогами со всеми вершинами квадрата. Значит, длина двадцати лет он переехал в Германию, где и работал до конца
v
дорог не меньше, чем 8 2, потому что сумма расстояний от пере- жизни, сначала в университете Гейдельберга, а затем — Берлина.
крёстка до вершин квадрата не меньше, чем от центра квадрата Вклад Штейнера в геометрию огромен. Ему принадлежит мно-
до вершин (как мы знаем, минимум суммы расстояний от точки жество новых идей и красивых, иногда весьма трудных теорем.
до вершин четырёхугольника достигается в точке v пересечения диа- Он впервые доказал, что треугольник с двумя равными биссек-
гоналей). В этом случае длина дорог не меньше 8 2=11,31. . . трисами — равнобедренный, что все геометрические построения,
20 21
выполнимые с помощью циркуля и линейки, могут быть осуще- В самом деле, если из вершины A выходят рёбра AB и AC,
и угол между ними меньше 120? , то мы можем заменить эту пару
ствлены с помощью одной линейки, если только нам дана хотя бы
одна окружность и её центр. Так называемый поризм Штейнера, рёбер другими, также связывающими точки A, B и C, но имеющи-
или <ожерелье Штейнера>, теорема о цепочке касающихся окруж- ми меньшую суммарную длину. Если в треугольнике ABC все углы
меньше 120? , то поставим одну дополнительную вершину T — точ-
ностей, по праву считается одним из красивейших утверждений
геометрии. Как представитель <чистой геометрии>, он был убе- ку Торричелли этого треугольника, соединим её с вершинами A, B
ждён, что геометрию надо изучать умозрительно, без привлечения и C, а рёбра AB и AC уберём. Получим связный граф меньшей
вычислений. Он говорил, что <расчёт заменяет мышление, а гео- длины. А если в треугольнике ABC, скажем, угол при вершине B
больше или равен 120? , то убираем ребро AC, а вместо него ста-
метрия, напротив, это мышление укрепляет>. По его убеждению,
каждая геометрическая задача должна иметь чисто геометриче- вим BC. Вновь получим связный граф меньшей длины (рис. 16).
ское решение. Если Штейнеру не удавалось найти геометрическое
A A
решение, он считал задачу не решённой вовсе и не публиковал ре-
шения. По этой причине многие теоремы Штейнера дошли до нас а) б)
без доказательств.
C C
Р е ш е н и е. Мы решим задачу Штейнера для k точек на плос- T
кости. С незначительными изменениями это же доказательство C C A B A B
B B
годится и для k точек в пространстве, и даже в пространстве n
Рис. 16
произвольной размерности. В этом смысле решение задачи Штей-
нера универсально! Из этого свойства непосредственно следует, что
Решение разобьём на несколько этапов. Итак, пусть на плос- в) и з н а с т о я щ е й в е р ш и н ы м о ж е т в ы х о д и т ь о д н о,
кости даны k точек A1 , A2 , . . ., Ak . Посмотрим, какими свойствами д в а и л и т р и р е б р а; е с л и в ы х о д и т д в а р е б р а, т о у г о л
м е ж д у н и м и б о л ь ш е и л и р а в е н 120? ; е с л и т р и, т о о н и
должна обладать кратчайшая система дорог, соединяющая эти точки.
о б р а з у ю т м е ж д у с о б о й у г л ы в 120? .
Первое свойство достаточно очевидно, и вытекает из того, что крат-
чайшим путём из одной точки в другую является отрезок прямой: Больше трёх рёбер выходить не может, иначе один из углов
будет меньше 120? .
а) к р а т ч а й ш а я с и с т е м а д о р о г с о с т о и т и з о т р е з к о в.
Таким образом, кратчайшая система дорог является плоским Таким образом, настоящие вершины бывают трёх типов. С допол-
графом — объединением конечного числа отрезков. Концы этих нительными вершинами дело обстоит проще — все они одного типа:
отрезков — вершины графа, а сами отрезки — его рёбра. Дан- г) и з к а ж д о й д о п о л н и т е л ь н о й в е р ш и н ы в ы х о д я т
т р и р е б р а п о д у г л а м и 120? .
ные точки A1 , . . ., Ak мы будем называть настоящими вершинами
этого графа, все прочие его вершины (перекрёстки дорог) — допол- Действительно, первый тип для дополнительной вершины не-
нительными. По условию этот граф связный, т. е. из любой его возможен (если из дополнительной вершины выходит только одно
вершины можно добраться по рёбрам в любую другую. Более того, ребро, то эта вершина не нужна, потому что её можно убрать вме-
этот граф односвязный, т. е. для любой пары вершин существует сте с ребром), второй — также невозможен (если дополнительная
единственный путь по рёбрам, их связывающий (при этом всегда вершина M соединена рёбрами только с двумя вершинами B и C,
считаем, что никакой путь не проходит дважды по одному ребру). то уберём эти рёбра вместе с самой вершиной M, а точки B и C
Связный граф является односвязным тогда и только тогда, когда соединим ребром; получим связный граф меньшей длины).
он не содержит замкнутых путей (доказательство этого факта — Определение. Сетью Штейнера данных точек A1 , . . ., Ak , на-
простое упражнение). Если бы кратчайшая система дорог не была зывается односвязный граф, имеющий среди своих вершин все
односвязной, то существовал бы замкнутый путь. Убрав любое ре- данные точки (эти вершины называются настоящими, прочие —
бро из этого пути, мы получили бы связный граф меньшей длины. дополнительными), причём все его настоящие вершины принад-
Итак, кратчайшую систему дорог надо искать среди односвяз- лежат одному из трёх типов (пункт в), а все дополнительные
ных графов, которые содержат данные точки в качестве вершин вершины принадлежат только третьему типу (пункт г)).
(но могут иметь и дополнительные вершины). На рис. 17 показана сеть Штейнера, связывающая девять точек.
б) л ю б ы е д в а р е б р а, в ы х о д я щ и е и з о д н о й в е р ш и- Теорема. Кратчайшая система дорог, связывающая k точек,
н ы, о б р а з у ю т у г о л н е м е н е е 120? . является сетью Штейнера.
22 23
Как строить такие сети? И вообще, И н д у к т и в н ы й п е р е х о д. Пусть
A9 A8 C C
сколько их может быть у данного набо- k?3. Предположим, что для любых k?1 B B
120?
точек на плоскости существует лишь ко- A
ра точек? Ведь мы вольны ставить сколько
A7
угодно дополнительных вершин! Оказывает- нечное число сетей Штейнера, и мы умеем Рис. 18
ся, что для данного набора точек существует их все строить. Пусть нам дано k точек.
A2
лишь конечное число сетей Штейнера. Согласно лемме, любая сеть Штейнера, со-
K K
Можно построить их все, а затем выбрать единяющая эти точки, содержит либо ту-
A6
A1
из них ту, которая имеет кратчайшую пиковую вершину, либо тупиковую пару B
длину. Она и будет кратчайшей системой вершин.
D
A5 дорог, связывающей данные точки. В первом случае (рис. 18) мы можем
A
A3
Как построение, так и доказательство убрать тупиковую вершину вместе с един-
осуществляется по индукции. Для этого ственным исходящим из неё ребром. Полу-
нам понадобится лишь одно вспомогатель- чаем граф, который будет сетью Штейнера
ное утверждение. Настоящую вершину сети для оставшихся k?1 точек.
M M
A4
Штейнера назовём тупиковой, если из неё Во втором случае (рис. 19) обозначим
Рис. 19
выходит только одно ребро, и это ребро со- через A и D тупиковую пару вершин, со-
Рис. 17
единяет её с другой настоящей вершиной. единённых с дополнительной вершиной B,
Две настоящие вершины назовём тупиковой парой вершин, если а через BK — третье ребро, выходящее из вершины B. Построим
из каждой из них выходит по одному ребру, и эти рёбра соединя- на стороне AD равносторонний треугольник AMD так, что точки M
ют их с одной и той же дополнительной вершиной. Сеть Штейнера и B лежат по разные стороны от прямой AD. Так как B — допол-
нительная вершина, ?ABD=?ABK=?DBK=120? . Следовательно,
на рис. 17 имеет две тупиковые вершины — A1 и A8 , и одну тупи-
ковую пару вершин — {A4 , A5 }. точки A, B, D и M лежат на одной окружности, поэтому ?MBA=
=?MDA=60? . Таким образом, точка B лежит на отрезке MK.
Лемма. В каждой сети Штейнера есть либо тупиковая верши-
на, либо тупиковая пара вершин. Уберём вершины A и D вместе с дополнительной вершиной B
Д о к а з а т е л ь с т в о л е м м ы. Среди всех путей по рёбрам гра- и со всеми рёбрами, выходящими из B. Вместо них поставим одну
фа выберем путь, состоящий из наибольшего числа рёбер. Пусть он настоящую вершину M и соединим её ребром с вершиной K. По-
начинается в вершине A, а следующая вершина — B. Тогда AB — лучим сеть Штейнера, связывающую k?1 точек.
единственное ребро, выходящее из A, и A — настоящая вершина. Таким образом, построение любой сети Штейнера для k точек
Если и B — настоящая, то всё доказано: вершина A — тупико- сводится к аналогичной задаче для k?1 точек. Получаем и н д у к-
вая. Если B — дополнительная вершина, то из неё выходят ещё т и в н ы й а л г о р и т м. Пусть дано k точек A1 , . . ., Ak . Тогда:
два ребра: BC и BD. По крайней мере одно из этих рёбер (пусть 1-й способ. Временно убираем любую из точек Aj , j=1, . . ., k,
это будет BD) не лежит на выбранном пути. Докажем, что BD — строим сеть Штейнера для оставшихся k?1 точек, затем соединя-
единственное ребро, выходящее из вершины D. Если из D выходит ем Aj ребром с любой из этих k?1 точек.
ещё какое-нибудь ребро BE, то путь E>D>B>. . . будет содер- 2-й способ. Выбираем две точки Ai , Aj из
жать больше рёбер, чем путь A>B>. . ., что невозможно. Таким k данных, строим равносторонний треугольник
K
образом, A и D составляют тупиковую пару вершин. MAi Aj и временно заменяем две точки Ai , Aj на од-
Построение сети Штейнера. Б а з а и н д у к ц и и. Если k=2, ну точку M. Для получившихся k?1 точек стро-
B
то отрезок, соединяющий две вершины, будет единственной сетью им сеть Штейнера. Обозначаем через B точку пе-
Aj
Штейнера. Действительно, как мы доказали, самый длинный путь ресечения описанной окружности треугольника
Ai
в графе (т. е. содержащий наибольшее число рёбер) оканчивается MAi Aj с ребром MK, выходящим из вершины M.
либо тупиковой вершиной, либо тупиковой парой вершин. В обоих Теперь убираем вершину M, ставим обратно вер-
случаях это две настоящие вершины. У пути два конца, а настоя- шины Ai и Aj , ставим дополнительную вершину B
щих вершин у нас всего две. Поэтому единственная возможность — и соединяем её рёбрами с вершинами Ai , Aj и K.
M
самый длинный путь состоит из одного ребра и соединяет две на- После каждого шага нужно проверить, бу-
стоящие вершины. Значит, вся сеть состоит из одного ребра. дет ли построенный граф сетью Штейнера для Рис. 20

<< Пред. стр.

страница 2
(всего 5)

ОГЛАВЛЕНИЕ

След. стр. >>

Copyright © Design by: Sunlight webdesign