WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 | 2 || 4 | 5 |   ...   | 7 |

него треугольника (треугольника Наполеона). Чему равна сторона Когда же точка Торричелли существует Пусть из трёх углов треугольника Наполеона, если 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

просто. Пусть A120, а M — произвольная точка плоскости. 32. Докажите, что сумма расстояний от произвольной точки Если M не лежит внутри угла A, то один из углов MAC или MAB — внутри равностороннего треугольника до его сторон — величина 18 постоянная. С помощью этого утверждения получите другое до- Примерно так рассуждали десятиклассники, доказывая, что казательство теоремы Ферма—Торричелли—Штейнера. ответ в задаче отрицательный. В то время как ничего не подоП о д с к а з к а. Через каждую вершину треугольника проведите прямую, зревавшие восьмиклассники, не знавшие даже теоремы косинусов, перпендикулярную отрезку, соединяющему эту вершину с точкой Торричелли.

экспериментально, с помощью линейки, приняв 1 сантиметр в теЭти прямые образуют равносторонний треугольник.

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

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

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

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 км.



ная длина четырёх отрезков от центра тетраэдра до вершин равна Если провести две диагонали с перекрёстком в центре, то длина бу6=2,449... В то время как наименьшая возможная длина пау дет 8 2=11,31... км. Меньше ничего уже быть не может. В самом тины равна 3+1/ 2=2,439... Отличие всего в одну сотую! деле: если есть только одна дорога, соединяющая последовательЗадача Штейнера. В пространстве дано k точек. Соединить их но все вершины (иначе говоря, если перекрёстков не будет), то её системой кривых наименьшей суммарной длины.

длина будет не меньше трёх сторон квадрата (поскольку дорога, Эта задача была впервые поставлена великим геометром Якосоединяющая две вершины квадрата, не меньше его стороны), т. е.

бом Штейнером (1796—1863). Родившийся в Швейцарии в крене меньше 12 км. Если же есть хотя бы один перекрёсток, то он стьянской семье Штейнер был в математике самоучкой. В возрасте соединён дорогами со всеми вершинами квадрата. Значит, длина двадцати лет он переехал в Германию, где и работал до конца дорог не меньше, чем 8 2, потому что сумма расстояний от пережизни, сначала в университете Гейдельберга, а затем — Берлина.

крёстка до вершин квадрата не меньше, чем от центра квадрата Вклад Штейнера в геометрию огромен. Ему принадлежит мнодо вершин (как мы знаем, минимум суммы расстояний от точки жество новых идей и красивых, иногда весьма трудных теорем.

до вершин четырёхугольника достигается в точке пересечения диаОн впервые доказал, что треугольник с двумя равными биссек гоналей). В этом случае длина дорог не меньше 8 2=11,31... трисами — равнобедренный, что все геометрические построения, 20 выполнимые с помощью циркуля и линейки, могут быть осуще- В самом деле, если из вершины 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 B B A B A B годится и для k точек в пространстве, и даже в пространстве n Рис. произвольной размерности. В этом смысле решение задачи Штейнера универсально! Из этого свойства непосредственно следует, что Решение разобьём на несколько этапов. Итак, пусть на плос- в) и з н а с т о я щ е й в е р ш и н ы м о ж е т в ы х о д и т ь о д н о, кости даны k точек A1, A2,..., Ak. Посмотрим, какими свойствами д в а и л и т р и р е б р а; е с л и в ы х о д и т д в а р е б р а, т о у г о л должна обладать кратчайшая система дорог, соединяющая эти точки. м е ж д у н и м и б о л ь ш е и л и р а в е н 120; е с л и т р и, т о о н и Первое свойство достаточно очевидно, и вытекает из того, что крат- о б р а з у ю т м е ж д у с о б о й у г л ы в 120.

чайшим путём из одной точки в другую является отрезок прямой: Больше трёх рёбер выходить не может, иначе один из углов а) к р а т ч а й ш а я с и с т е м а д о р о г с о с т о и т и з о т р е з к о в. будет меньше 120.

Таким образом, кратчайшая система дорог является плоским Таким образом, настоящие вершины бывают трёх типов. С дополграфом — объединением конечного числа отрезков. Концы этих нительными вершинами дело обстоит проще — все они одного типа:

отрезков — вершины графа, а сами отрезки — его рёбра. Дан- г) и з к а ж д о й д о п о л н и т е л ь н о й в е р ш и н ы в ы х о д я т ные точки A1,..., Ak мы будем называть настоящими вершинами т р и р е б р а п о д у г л а м и 120.

этого графа, все прочие его вершины (перекрёстки дорог) — допол- Действительно, первый тип для дополнительной вершины ненительными. По условию этот граф связный, т. е. из любой его возможен (если из дополнительной вершины выходит только одно вершины можно добраться по рёбрам в любую другую. Более того, ребро, то эта вершина не нужна, потому что её можно убрать вмеэтот граф односвязный, т. е. для любой пары вершин существует сте с ребром), второй — также невозможен (если дополнительная единственный путь по рёбрам, их связывающий (при этом всегда вершина M соединена рёбрами только с двумя вершинами B и C, считаем, что никакой путь не проходит дважды по одному ребру). то уберём эти рёбра вместе с самой вершиной M, а точки B и C Связный граф является односвязным тогда и только тогда, когда соединим ребром; получим связный граф меньшей длины).

он не содержит замкнутых путей (доказательство этого факта — Определение. Сетью Штейнера данных точек A1,..., Ak, напростое упражнение). Если бы кратчайшая система дорог не была зывается односвязный граф, имеющий среди своих вершин все односвязной, то существовал бы замкнутый путь. Убрав любое ре- данные точки (эти вершины называются настоящими, прочие — бро из этого пути, мы получили бы связный граф меньшей длины. дополнительными), причём все его настоящие вершины принадИтак, кратчайшую систему дорог надо искать среди односвяз- лежат одному из трёх типов (пункт в), а все дополнительные ных графов, которые содержат данные точки в качестве вершин вершины принадлежат только третьему типу (пункт г)).





(но могут иметь и дополнительные вершины). На рис. 17 показана сеть Штейнера, связывающая девять точек.

б) л ю б ы е д в а р е б р а, в ы х о д я щ и е и з о д н о й в е р ш и- Теорема. Кратчайшая система дорог, связывающая k точек, н ы, о б р а з у ю т у г о л н е м е н е е 120. является сетью Штейнера.

22 Как строить такие сети И вообще, И н д у к т и в н ы й п е р е х о д. Пусть A9 AC C сколько их может быть у данного набо- k3. Предположим, что для любых k-1 B B A A7 ра точек Ведь мы вольны ставить сколько точек на плоскости существует лишь коРис. угодно дополнительных вершин! Оказывает- нечное число сетей Штейнера, и мы умеем ся, что для данного набора точек существует их все строить. Пусть нам дано k точек.

Aлишь конечное число сетей Штейнера. Согласно лемме, любая сеть Штейнера, соK K AМожно построить их все, а затем выбрать единяющая эти точки, содержит либо туAиз них ту, которая имеет кратчайшую пиковую вершину, либо тупиковую пару B длину. Она и будет кратчайшей системой вершин.

A5 D дорог, связывающей данные точки. В первом случае (рис. 18) мы можем A3 A Как построение, так и доказательство убрать тупиковую вершину вместе с единосуществляется по индукции. Для этого ственным исходящим из неё ребром. Полунам понадобится лишь одно вспомогатель- чаем граф, который будет сетью Штейнера ное утверждение. Настоящую вершину сети для оставшихся k-1 точек.

M M AШтейнера назовём тупиковой, если из неё Во втором случае (рис. 19) обозначим Рис. выходит только одно ребро, и это ребро со- через A и D тупиковую пару вершин, соРис. единяет её с другой настоящей вершиной. единённых с дополнительной вершиной B, Две настоящие вершины назовём тупиковой парой вершин, если а через BK — третье ребро, выходящее из вершины B. Построим из каждой из них выходит по одному ребру, и эти рёбра соединя- на стороне AD равносторонний треугольник AMD так, что точки M ют их с одной и той же дополнительной вершиной. Сеть Штейнера и B лежат по разные стороны от прямой AD. Так как B — дополна рис. 17 имеет две тупиковые вершины — A1 и A8, и одну тупи- нительная вершина, ABD=ABK=DBK=120. Следовательно, ковую пару вершин — {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, то путь EDB... будет содер- 2-й способ. Выбираем две точки Ai, Aj из жать больше рёбер, чем путь AB..., что невозможно. Таким k данных, строим равносторонний треугольник K образом, A и D составляют тупиковую пару вершин. MAiAj и временно заменяем две точки Ai, Aj на одПостроение сети Штейнера. Б а з а и н д у к ц и и. Если k=2, ну точку M. Для получившихся k-1 точек строB то отрезок, соединяющий две вершины, будет единственной сетью им сеть Штейнера. Обозначаем через B точку пеAj Штейнера. Действительно, как мы доказали, самый длинный путь ресечения описанной окружности треугольника Ai в графе (т. е. содержащий наибольшее число рёбер) оканчивается MAiAj с ребром MK, выходящим из вершины M.

либо тупиковой вершиной, либо тупиковой парой вершин. В обоих Теперь убираем вершину M, ставим обратно верслучаях это две настоящие вершины. У пути два конца, а настоя- шины Ai и Aj, ставим дополнительную вершину B щих вершин у нас всего две. Поэтому единственная возможность — и соединяем её рёбрами с вершинами Ai, Aj и K.

M самый длинный путь состоит из одного ребра и соединяет две на- После каждого шага нужно проверить, буРис. стоящие вершины. Значит, вся сеть состоит из одного ребра. дет ли построенный граф сетью Штейнера для 24 точек A1,..., Ak. При этом как бы мы ни действовали, хоть по пер- в ы й с п о с о б н е д а ё т с е т и Ш т е й н е р а.

A4 Aвому, хоть по второму способу, нет гарантии, что всякий раз будет В т о р о й с п о с о б. Убираем пару вершин.

Pages:     | 1 | 2 || 4 | 5 |   ...   | 7 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.