Теория Морса минимальных сетей (1105006), страница 31
Текст из файла (страница 31)
3.20.Предложение 3.13 полностью доказано. 5.7Оценки количества локальных минимумов дляслучаев 3, 4 и 5 граничных точекСлучай трех граничных точекВ случае 3 граничных точек имеется только одно критическое множество(0 ), канонический представитель Γ0 которого имеет тип звезды. Минимальная параметрическая сеть Γ0 не расщепляется, поэтому множество (0 ) является комбинаторным локальным минимумом, а значит,в силу леммы 3.27, и локальным минимумом в традиционном смысле.
Та-Приложения171ким образом, в случае 3 граничных точек у функции ℓ на пространстве имеется ровно один локальный минимум.Случай четырех граничных точекВ случае 4 граничных точек имеется два набора 0 и 1 критическихподмножеств ( ) ранга ноль и один соответственно.Набор 0 состоит из одного критического множества (0 ), канонический представитель Γ0 которого имеет ранг 0, т.е. тип сети Γ0 — звезда.Отметим, что критическое множество (0 ) не является локальным минимумом, поскольку, согласно предложению 3.10, сеть Γ0 обладает геометрическими расщеплениями.Набор 1 состоит из нескольких критических подмножеств ( ),канонические представители которых имеют ранг 1. Сети ранга 1, т.е.бинарные деревья, не имеют расщеплений, поэтому все множества ( )из набора 1 являются локальными минимумами.Поскольку для случая 4 граничных точек функция ℓ на пространстве является комбинаторной функцией Морса, то мы можем воспользоваться основной формулой из теоремы 2.2, которая позволяет выразитьмощность набора 1 следующим образом|1 | = # 1 (Γ0 ).Согласно предложению 3.10, # 1 (Γ) равно либо 1, либо 2.Таким образом, получаем утверждениеУтверждение 3.13 Пусть — граничное множество общего положения, состоящее из 4 точек на манхэттенской плоскости.
Тогда всеканонические представители локальных минимумов функции ℓ на пространстве являются бинарными деревьями и количество этих локальных минимумов равно либо 1, либо 2.Случай пяти граничных точекВ случае 5 граничных точек имеется три набора 0 , 1 и 2 критическихмножеств ( ) ранга ноль, один и два соответственно.Набор 0 состоит из одного критического множества (0 ), канонический представитель Γ0 которого имеет ранг 0, т.е. тип сети Γ0 — звезда.Приложения172Отметим, что критическое множество (0 ) не является локальным минимумом, поскольку, согласно предложению 3.11, сеть Γ0 обладает геометрическими расщеплениями.Лемма 3.39 Все мощные расщепления сети Γ0 элементарно порождены.Доказательство.
У сети Γ0 есть расщепления только двух рангов: 1 и2. Мощные расщепления ранга один 1 (Γ0 ) всегда являются элементарными.Покажем теперь, что мощные расщепления ранга 2 элементарно порождены. Пусть Γ′ — мощное расщепление ранга 2, а Γ1 и Γ2 — сети ранга1, образующие полный набор производных расщеплений для расщепления Γ′ . Из леммы 3.30 вытекает, что субградиенты 1 ,. . . , 5 граничныхребер 1 ,. . . , 5 сети Γ0 определяются однозначно. Следовательно, определяются однозначно и субградиенты граничных ребер сетей Γ1 , Γ2 и Γ′ .Они также равны 1 ,. . . , 5 . По субградиентам граничных ребер однозначно определяются субградиенты внутренних ребер сетей Γ1 , Γ2 и Γ′ .Поэтому, если элементарные расщепления Γ1 и Γ2 не могут уменьшитьдлину сети Γ (т.е.
они являются минимальными параметрическими сетями), то расщепление Γ′ также не может уменьшить длину сети Γ, чтопротиворечит исходному предположению. Следовательно, одно из расщеплений Γ1 или Γ2 является геометрическим. Набор 1 состоит из нескольких критических подмножеств ( )ранга 1. Отметим, что критические множества ( ) не являются локальными минимумами, поскольку, согласно предложению 3.12, их канонические представители Γ обладают геометрическими расщеплениями.Набор 2 состоит из нескольких критических подмножеств ( )ранга 2.
Сети ранга 2, т.е. бинарные деревья, не имеют расщеплений,поэтому все множества ( ) из набора 2 являются локальными минимумами.Поскольку для случая 5 граничных точек функция ℓ на пространстве является комбинаторной функцией Морса и все мощные геометрические расщепления минимальных параметрических сетей элементарнопорождены, то мы можем воспользоваться основной формулой из теоремы 2.2, которая позволяет выразить мощности наборов 1 и 2 следую-Приложения173щим образом:|1 | = #∑︀1 (Γ0 ),|2 | =# 2 (Γ ) − # 2 (Γ0 ).( )∈1Воспользовавшись этими двумя равенствами и предложением 3.12, согласно которому # 2 (Γ ) ≤ 2, получим неравенство:|2 | ≤ 2|1 | − # 2 (Γ0 ) = 2# 1 (Γ0 ) − # 2 (Γ0 ).Осталось применить предложение 3.11, которое нам дает оценку |2 | ≤ 6.Резюмируя теперь результаты случаев 4 и 5 граничных точек, получаем следующую теоремуТеорема 3.3 Пусть ℋ — плоскость R2 с манхэттенской нормой,∙ и ⊂ ℋ — граница общего положения, состоящая из четырех точек.
Тогда все канонические представители локальных минимумовфункции ℓ на пространстве являются бинарными деревьями иколичество этих локальных минимумов равно либо 1, либо 2.∙ и ⊂ ℋ — граница общего положения, состоящая из пяти точек. Тогда все канонические представители локальных минимумовфункции ℓ на пространстве являются бинарными деревьями иколичество этих локальных минимумов не превосходит 6.5.8Некоторые примеры для случая 6 граничных точекНа рис. 3.30 приведен пример минимальной параметрической сети Γ[],затягивающей границу общего положения из 6 точек. В соответствующем множестве minℓ [] существует минимальная параметрическая сетьΓ1 с вырожденным ребром 1 , и существует минимальная параметрическая сеть Γ2 с вырожденным ребром 2 , но не существует минимальнойпараметрической сети Γ0 с обоими вырожденными ребрами.Этот пример показывает, что для 6 граничных точек общего положения предложение 3.13 не верно, и функция ℓ на пространстве неявляется комбинаторной функцией Морса.Приложения174Рис.
3.30:Рис. 3.31:На рис. 3.31 приведен пример еще одной минимальной параметрической сети Γ′ [′ ], затягивающей границу общего положения из 6 точек.В соответствующем множестве minℓ [′ ] сеть Γ′ является каноническимпредставителем и не обладает геометрическими расщеплениями. Следовательно, критическое множество minℓ [′ ] является локальным минимумом.Таким образом, для 6 граничных точек имеются локальные минимумы, канонический представитель которых не является бинарным деревом.Литература[1] Александров П. С., Комбинаторная топология. — М.-Л.: Гостехиздат,1947.[2] Горески М., Макферсон Р., Стратифицированная теория Морса.
—М.: Мир, 1991.[3] Громол Д., Мейер В., Клингенберг В., Риманова геометрия в целом.— М.: Мир, 1975[4] Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И.,Лекции по теории графов. — М.: Наука, 1990.[5] Иванов А. О. Геометрические свойства локально минимальных сетей. — Дис.. . . доктора физ.-мат. наук. М.: МГУ, 1998.[6] Иванов А. О., Тужилин А. А., Разветвленные геодезические. Геометрическая теория локально минимальных сетей. — Lewiston: TheEdwin Mellen Press, 1999.[7] Иванов А.О., Тужилин А.А. Геометрия минимальных сетей и одномерная проблема Плато.
— УМН, 1992, т. 47, N2, сс. 53–115.[8] Иванов А. О., Тужилин А. А., Геометрия множества минимальныхсетей данной топологии с фиксированной границей. — Изв. РАН.,Сер. Матем., 1997, т. 61, N6, сс. 119–152.[9] Комбинаторный анализ. Задачи и упражнения. Под ред. К. А. Рыбникова — М.: Наука, 1982.[10] Милнор Дж., Теория Морса. — М.: Мир, 1965.175Приложения176[11] Михайлевич В. С., Трубин В. А., Шор Н. З., Оптимизационные задачи в индустриальном планировании: модели, методы, алгоритмы.— М.: Наука, 1986.[12] Мусин О. Р., О некоторых задачах вычислительной геометрии и топологии. — Сборник ВоронежГУ “Алгебраические вопросы анализаи топологии.”, 1990, сс.
30–51.[13] Понтрягин Л. С., Основы комбинаторной топологии. — М.: Наука,1986.[14] Препарата Ф., Шеймос М., Вычислительная геометрия: Введение.— М.: Мир, 1989.[15] Пронин M. В., Локально минимальные сети на римановых многообразиях отрицательной секционной кривизны. — Вестник МГУ, Серия 1, Математика и механика, 1998, N5, сс. 12–16.[16] Скляренко Е. Г., Гомологии и когомологии общих пространств. —Итоги науки и техники. Современные проблемы математики. Фундаментальные направления, Т. 50, сс.
129-266, М.: ВИНИТИ, 1989.[17] Тужилин А. А. Классификация локально минимальных плоских сетей с выпуклыми границами. — Дис.. . . доктора физ.-мат. наук. М.:МГУ, 1997.[18] Феллер В., Введение в теорию вероятностей и ее приложения, т. 1.— М.: Мир, 1967.[19] Фоменко А.
Т., Фукс Д. Б., Курс гомотопической топологии. — М.:Наука, 1989.[20] Харари Ф., Палмер Э., Перечисление графов. — М.: Мир, 1977.[21] Cieslik D., The Steiner Ratio of Metric Spaces. — Greifswald, preprintof Inst. of Math. and C.S., Ernst–Moritz–Arndt Univ., Greifswald,Germany, 1998.[22] Du D. Z., Hwang F. K. and Chao S. C., Steiner minimal trees for pointson a circle. — Proc. Amer.
Math. Soc., 1985, vol. 95, N4, pp. 613–618.Приложения177[23] Du D. Z., Hwang F. K. and Weng J. F., Steiner minimal trees forpoints on a zig-zag lines. — Trans. Amer. Math. Soc., 1983, vol. 278,N1, pp. 149–156.[24] Du D. Z., Hwang F. K. and Weng J. F., Steiner minimal trees forRegular Polygons. — Disc. and Comp. Geometry, 1987, vol. 2, pp. 65–84.[25] Eggleston H. G., Convexity.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
