Геометрические свойства локально минимальных сетей

Цель настоящей диссертации — изучение геометрических свойств локально минимальных сетей на римановых многообразиях. С точки зрения римановой геометрии, локально минимальные сети являются естественным обобщением обычных геодезических. Напомним, что соединяющая пару фиксированных точек риманова многообразия геодезическая обладает следующим определяющим свойством: каждый ее фрагмент между достаточно близкими точками, А и В является кратчайшей кривой среди всех кривых, соединяющих, А ж В. Предположим теперь, что фиксировано не две точки риманова многообразия IV, а некоторое конечное его подмножество М, состоящее из большего числа точек. Чтобы обобщить на этот случай понятие геодезических, естественно перейти от кривых к рассмотрению связных одномерных континуумов — сетей. Затягивающая множество М С И/Г сеть называется абсолют, но минимальной, если она имеет наименьшую возможную длину, и локально минимальной, если каждый достаточно малый ее фрагмент имеет наименьшую возможную длину, т. е. является абсолютно минимальной сетью. В этом смысле естественно говорить о локально минимальных сетях как о «разветвленных геодезических» .

Локально минимальные сети также естественно возникают при рассмотрении обобщений следующей классической задачи: среди всех сетей (связных одномерных континуумов), затягивающих данное конечное множество точек плоскости, найти сеть наименьшей длины, т. е. абсолютно минимальную сеть. Эта задача, известная в современной литературе как проблема Штейнера, на протяжении многих десятков лет привлекает внимание специалистов (см. исторический обзор ниже). Неослабевающий интерес к проблеме Штейнера объясняется не только большим количеством приложений, таких как транспортная задача, но также и тем, что, несмотря на простоту постановки, эта задача оказывается чрезвычайно нетривиальной. Хотя имеется несложный алгоритм Мелзака-Хванга построения кратчайшей сети, затягивающей данное множество точек плоскости (см. ниже), этот алгоритм 1 связан с прямым перебором очень большого числа возможных топологий (комбинаторных структур) кратчайшей сети. На самом деле, как показано в [29], задача Штейнера является Á-Í-V-трудной, т. е., неформально говоря, скорее всего не существует алгоритма, строящего решение за полиномиальное время. Поэтому большое значение имеет изучение геометрических ограничений, накладываемых на возможную структуру сетей условием минимальности. При таком геометрическом подходе естественно, как и в случае кратчайших кривых, расширить класс рассматриваемых сетей, перейдя от сетей кратчайших «в целом» к изучению сетей кратчайших «в малом», т. е. перейти к изучению локально минимальных сетей.

Отметим, что нетривиальность задачи описания локально минимальных сетей проявляется, в отличие от задачи описания обычных геодезических, уже в случае когда объемлющее многообразие — это евклидово пространство Rn, п > 2. Оказывается, уже здесь возникает ряд новых эффектов, не имеющих аналогов в теории обычных геодезических. К таким эффектам можно отнести возможное изменение топологии сети при зшеныпении ее длины, необходимость перебора всевозможных топологий сети, наличие геометрических ограничений на возможные топологии минимальной сети, существование непрерывных семейств локально минимальных сетей, обусловленное ее топологическими свойствами. Изучению этих новых эффектов и посвящена настоящая диссертация.

1 Исторический обзор

Понятие локально минимальной сети впервые неявным образом появилось при изучении следующей классической задачи, известной в литературе как проблема Штейнера: среди всех сетей (связных одномерных континуумов), затягивающих данное конечное множество М т, очек плоскости, найти сеть наименьшей длины. Эта задача была названа «проблемой Штейнера» в замечательной книге Ричарда Куранта и Герберта Е. Роббинса ilTimo такое матемагпика’Р' в честь Якоба Штейнера (Jacol) Steiner, 1796−1863), швейцарского математика, профессора Берлинского университета. Именно после появления этой очень популярной книги интерес к абсолютно минимальным сетям разгорелся с новой силой, и терминология, предложенная Курантом и Роб-бинсом стала общепринятой.

Следует отметить, однако, что сама задача о поиске абсолютно минимальных сетей имеет более длинную историю. Мы проследим ее здесь, воспользовавшись историческими обзорами в [88], [62], [37] и [34].

Рис. 1: Точка Торричелли.

По-видимому, впервые задача такого типа была поставлена Ферма (1601−1665) до 1640 года. А именно, Ферма интересовал ответ на следующий вопрос: как расположить на плоскости точку F так, чт. обы сумма расстояний от нее до трех фиксированных точек А, Ач и была наименьшей?

Торричелли предложил геометрическое решение этой задачи. Построим на сторонах заданного треугольника AiA2A^ вне его три правильных треугольника и опишем вокруг них окружности. Тогда, как показал Торричелли, построенные три окружности пересекутся в одной точке Т, которая известна теперь в планиметрии как точка Торричелли, см. рис. 1. Торричелли утверждал, что F = Т, т. е. эта точка Т и является решением задачи, поставленной Ферма. Однако, заметим, Торричелли ошибся: его рассуждения справедливы только в предположении, что все углы треугольника AA-iA3 не превосходят 120°. Если же один из этих углов, скажем угол Ai, больше 120°, то, как легко видеть, точка Торричелли лежит вне треугольника, А А2 A3 и не минимизирует суммарное расстояние до вершин треугольника. В этом случае, как независимо заметили Хейнен (в 1834 году) и, позднее, Бертран (в 1853 году), искомой точкой является вершина А.

Вернемся в XVII век. В 1647 году выходит книга Кавальери иЕх-cercitationes Geom, etricaey', в которой отмечается важное свойство точки Торричелли Т, в предположении, что эта точка лежит внутри треугольника А1А2А3: все углы между отрезками А{Т равны между собой и равны 120°. Этот факт оказывается весьма фундаментальным, и его аналоги, как мы увидим, имеют место в существенно более общих ситуациях.

В середине следующего столетия, в 1750 году, в своей книге '" Doctrine and Application of Fluctions" Симпсон предложил другой способ построения точки Торричелли. Конструкция Симпсона состоит в еле.

Рис. 2: Линии Симпсона пересекаются в точке Торричелли. дующем. Снова построим на сторонах треугольника АА^Аг и вне его правильные треугольники. Объединение каждого из построенных нами треугольников с исходным треугольником А1А2А3 представляет собой четырехугольник, одна из диагоналей которого совпадает с соответствующей стороной треугольника АА2А^. Проведем недостающие диагонали. Три построенных отрезка называются теперь линиями Симпсона. Симпсон показал, что эти отрезки или их продолжения пересекаются в одной точке, совпадающей с точкой Торричелли, рис. 2.

Уже в XIX веке, в 1834 году, Хейнен показал, что если точка Торричелли лежит внутри треугольника А1А2А3, то длины всех трех линий Симпсона равны между собой и равны сумме расстояний от точки Торричелли до вершин треугольника. Таким образом, собирая воедино все сказанное выше, мы получаем следующий полный ответ на поставленную Ферма задачу.

Решение задачи Ферма. Точка Р. являющаяся решением задачи Ферма. единственна.

Если один из углов треугольника АА2Аз, скажем Ау больше или равен 120°, то F =.

Если же все углы треугольника А2Аз меньше 120°. то Р1 совпадает с точкой Торричелли. В этом случае все углы между отрезками 5А{ равны между собой и равны 120°. При этом линии Симпсона имеют одинаковые длины, равные ?5A.il + |5Аг| + |5Аз|.

Симпсон предложил следующее обобщение задачи Ферма: найти на плоскости (в ¿—мерном пространстве) точку 5, сумма расстояний от которой до п данных точек наименьшая из возможных. Отметим, что эта задача отличается от сформулированной выше проблемы Штей-нера, так как в задаче Симпсона рассматриваются не все возможные сети, затягивающие данное множество М, а лишь сети, имеющие ровно одну дополнительную вершину — вершину 5*. Одним из вариантов задачи Симпсона занимался Якоб Штейнер.

Другое обобщение задачи Ферма получается, если в качестве объекта, 3' которого минимизируется длина, рассматривать произвольные сети, затягивающие данные множества точек. Впервые случай 4 и 5 точек рассматривался в работах французских математиков Жергонна, Клайперона и Ламе, а также в письмах Гаусса. Наконец, в 1934 году Ярник и Кесслер поставили задачу в следующем современном виде: найти кратчайшую сеть, свлзываюгцую п данных точек плоскости.

Ярник и Кесслер решили поставленную проблему для граничных множеств, образующих вершины правильных п-угольников при п = 3, 4, 5 и п > 13. Для п = 3, 4, 5 Ярник и Кесслер нашли очевидные абсолютно минимальные сети, а для п > 13 показали, что абсолютно минимальная сеть состоит из (п — 1)-ой стороны рассматриваемого правильного п-угольника. В работе этих авторов не было ссылок на Ферма, так как им, по-видимому, казалось, что они занимаются совсем другой задачей. Переписка Гаусса и работы французских математиков им также не были известны. Заметим, кстати, что случаи оставшихся п были разобраны лишь в работе [21] Ду, Хванга и Венга 1987 года, где было показано, что и в этих случаях ответ такой же, как и для п > 13.

Как мы уже отметили выше, проблема Штейнера получила свое называние благодаря книге Куранта и Роббинса «Что такое математиканаписанной ими в 1941 году. Авторы этой книги сформулировали описанную выше задачу Ферма, назвав ее проблемой Штейнера, а затем поставили проблему Ярника и Кесслера как естественное обобщение проблемы Штейнера. Ни на Ферма, ни на Ярника и Кесслера ссылок сделано не было. Как уже отмечалось, благодаря огромной популярности книги, терминология, связанная с именем Штейнера, стала в этом контексте общепринятой. Отметим, что книга Куранта и Роббинса породила не только недоразумение в вопросах приоритета, но, что гораздо более важно, привлекла к проблеме поиска минимальных сетей интерес большого числа ученых.

В дальнейшем проблемой Штейнера занимались многие известные математики, такие как Винтер, Гйлберт, Грехем, Гэри, Джонсон, Ду, Кокейн, Мелзак, Поллак, Рубинштейн, Томас, Хванг и другие. Ниже мы вкратце опишем основные результаты, полученные в этой науке за последние 40 лет. Одна из причин этого неослабевающего интереса специалистов к минимальным сетям состоит в том, что у проблемы Штейнера имеется много различных интерпретаций и приложений. Например, очевидно, заданное конечное множество М можно интерпретировать как набор конечных (терминальных) пунктов. Тогда минимальная сеть — это самая дешевая транспортная система, обеспечивающая коммуникации между данными конечными пунктами. Здесь естественно предполагается, что стоимость коммуникаций пропорциональна их длине. Отметим здесь же, что в реальных задачах часто встречаются ситуации, когда коэффициент пропорциональности между стоимостью отдельного участка транспортной сети и длиной этого участка зависит от конкретного участка сети. В этом случае естественно определить взвешенную длину сет, и как линейную комбинацию длин ребер сети с некоторыми положительными коэффициентами (для каждого ребра фиксирован свой коэффициент, называемый весом этого ребра). Отметим что в этом случае топология сети предполагается фиксированной. Сети, для ребер которых фиксированы веса, будем называть взвешенными. На случай взвешенных сетей естественным образом переносятся понятия абсолютно минимальных и локально минимальных сетей (в смысле взвешенной длины), см. [46]. Взвешенные минимальные сети так же изучаются в данной работе. Оказывается, что многие результаты, справедливые для обычных локально минимальных сетей обобщаются на случай взвешенных локально минимальных сетей.

Локально минимальные сети можно наблюдать в несложных физических экспериментах, описанных ниже, а так же в живой природе. Скажем, если пренебречь высотой пчелиных сот, то получится локально минимальная сеть, построенная из шестиугольников с углами по 120°. Таким образом, пчелы, повинуясь инстинкту, уменьшают количество воска, идущего на постройку сот.

Перейдем теперь к физическим опытам. Отметим, что в них, как и в случае пчелиных сот, возникают именно локально минимальные сети, а вовсе не обязательно абсолютно минимальные сети. Это обстоятельство лишний раз подчеркивает естественность рассматриваемых нами объектов.

В первом эксперименте мы получим локально минимальные сети наблюдая за мыльными пленками — физическими моделями минимальных поверхностей.

Возьмем две прозрачные пластины, расположим их в параллельных плоскостях на некотором расстоянии друг от друга, и соединим их произвольным числом штырьков, перпендикулярных пластинам. Опустим полученную конструкцию в мыльный раствор и осторожно извлечем ее наружу. На конфигурации осядет мыльная пленка, перпендикулярная пластинам (рис. 3).

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

Рис. 3: Мыльные пленки, моделирующие локально минимальные сети. наковых «следов», по которым пленка касается пластин. Если К — расстояние между пластинами, а I — длина одного из «следов», то площадь мыльной пленки равна Ы.

Хорошо известно, что мыльная пленка всегда стремится занять такое положение, в котором ее площадь больше нельзя уменьшить без предварительного увеличения. Поэтому каждый из «следов» является сетью, длину которой нельзя уменьшить малыми шевелениями, оставляющими на месте точки крепления штырьков — границу этой сети, т. е. является локально минимальной сетью.

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

Возьмем п кусков нерастяжимой нити, например лески. На одном конце каждого из кусков, кроме одного, сделаем незатягивающуюся петельку. Из полученных п — 1-ого отрезка с петелькой выберем к штук,'И через петельки проденем единственный отрезок без петли. Тем самым мы получим конфигурацию, состоящую из к + 1-ого отрезка и имеющую к + 2 концов.

Далее, из оставшихся незадействованными отрезков лески выберем к2 штук и проденем через их петельки концы построенной конфигурации. Тем самым мы получим новую конфигурацию уже с к + /-'2 + 2 концами. Опять из оставшихся отрезков выберем и вновь перестроим конфигурацию. Будем продолжать это процесс до тех пор, пока все отрезки не буд}гт заняты. В результате мы построим конфигурацию С, число концов которой равно п + 1.

Возьмем пластину, скажем лист оргстекла или фанеры, и просверлим в ней п + 1 маленькое сквозное отверстие (отверстия будут соответствовать граничным точкам минимальной сети). Расположим пластину горизонтально и пропустим сверху концы конфигурации С через отверстия так, чтобы на каждое из них приходилось по одному.

Рис. 4: Механическая реализация локально минимальных сетей. концу из (?. Прикрепим теперь к концам грузики одинаковой массы. Когда полученная механическая система прийдет в состояние равновесия, конфигурация из лески образует локально минимальную сеть, граница которой — набор просверленных отверстий, рис. 4.

Все основные результаты диссертации являются новыми и получены автором самостоятельно. Часть результатов получена автором совместно с А. А. Тужилиным и включена в диссертацию для полноты изложения.

Апробация работы.

Результаты диссертации рассказаны и обсуждены на многочисленных научных конференциях, в том числе, на международных конференциях и математическом конгрессе, а также на ведущих научно-исследовательских семинарах как в России, так и за рубежом. В частности, на Ломоносовских чтениях (МГУ, Москва) — на Зимних математических школах в Воронежена Ташкентской конференции по геометрии инвариантов многообразий (Ташкент, 1992) — на конференции, посвященной Лобачевскому (Санкт-Петербург, 1992) — на семинаре по геометрической визуализации под руководством проф. Т. Kunii (Айзу, Япония, 1993, 1997) — на Александровских чтениях в МГУ, в том числе на международной конференции посвященной 100-летию П. С. Алексндрована международном математическом конгрессе (Цюрих, Швейцария, 1994) — на конференции по уравнениям в частных производных и их приложениям (Санкт-Петербург, СПОМИ РАН, 1995) — на конференции, посвященной Чебышеву, (МГУ, Москва, 1996) — на международной конференции по дифференциальной геометрии (Рио де Жанейро, Бразилия, 1996) — на международной конференции по геометрии (Санкт Петербург, Международный Математический Институт Эйлера, 1997) — на международной конференции по интеллектуальным системам (Москва, МГУ, 1997) — на молодежной научной школе по дискретной математике (Москва, МГУ, 1997) — на научных семинарах в Московском государственном университетена семинаре профессора J. Jost в Рурском университете (Бохум, Германия, 1993) — на семинаре профессора А. Rigas в Институте математики, статистики и компьютерных методов (IMECC) университета г. Кампи-наса (Кампинас., Бразилия, 1993) — на семинаре профессора F. Мег сигу в Институте математики, статистики и компьютерных методов (IMECC) университета г. Кам-пинас.а (Кампинас, Бразилия, 1994) — на семинаре профессора R. Asperty в университете г. Сан-Пауло (Сан-Пауло, Бразилия, 1994) — на семинаре профессора S. Hildebrandt в Боннском университете (Бонн, Германия, 1996) — на семинаре профессора F. Tomi в Хайдельбергском университете (Хайдельберг, Германия, 1996) — на семинаре профессора Ю. Манина в институте Макса Планка (Бонн, Германия, 1996) — на семинаре профессора Н. в Рурском университете (Бохум, Германия, 1994, 1996) — на семинарах по геометрии и топологии в ПОМИ РАН (Санкт Петербург, 1997).

Публикации.

Основное содержание диссертации опубликовано в 14 работах, список которых приводится в конце автореферата.

Автор глубоко признателен своему учителю академику Анатолию Тимофеевичу Фоменко, который научил автора работать, сформировал его научные интересы, и постоянно проявляет внимание к автору и интерес к его работе. Автор также глубоко благодарен своему другу и коллеге Алексею Августиновичу Тужилину за многолетнее плодотворное сотрудничество в решении научных, а так же многих других проблем.

Глава 1.

Обобщенные сети на многообразиях.

В данной главе строятся основы теории сетей на многообразиях. Мы рассмотрим два подхода: можно рассматривать сеть как отображение в многообразие некоторого фиксированного топологического графа (так называемые параметрические сети), а можно определять сеть просто как подмножество многообразия, допускающее представление в виде образа некоторой, неважно какой именно, параметрической сети (так называемые сети-следы). Если объемлющее многообразие — ри-маново, то естественно определяется функция — длина сети (или, более общо, взвешенная длина). В следующей главе вся эта общая теория будет использована для постановки и решения задач минимизации длины и взвешенной длины сети, см. формальные определения ниже. В данной же главе приводится ряд общих определений и предварительных технических результатов, таких как формулы первой и второй вариации длины, необходимых для дальнейшего изложения.

1.1 Графы: топологический подход.

Мы будем рассматривать графы с топологической точки зрения. Такой подход будет удобен для нас в дальнейшем при определении сетей и работе с ними. Кроме того, одним из преимуществ топологического подхода является то обстоятельство, что он естественнее, чем классический комбинаторный подход, позволяет работать с графами, имеющими кратные ребра и петли, что тоже важно для нас.

1.1.1 Топологические графы, их эквивалентность.

Суть топологического подхода к теории графов состоит в том, что графы рассматривается сразу вместе с введенной на них естественной топологией. Цель данного пункта — дать определение графа как топологического пространства. Говоря неформально, топологическим графом называется совокупность отрезков, склеенных по своим концам. Формальное определение удобно дать на языке клеточных комплексов.

Напомним, см., например, [28], что хаусдорфово топологическое пространство К называется клеточным комплексом, если задано его представление в виде объединения U^L0 U? e/n ef попарно непересекающихся множеств (клеток), причем для каждой клетки е&tradeсуществует непрерывное отображение ср стандартного замкнутого n-мерного диска Dn С Еп в К, называемое характеристическим отображением клетки ef, такое что сужение р> на внутренность int Dn диска Dn есть гомеоморфизм Lp: int Dn -> e? Кроме того, предполагаются выполненными следующие две независимые аксиомы.

С) Граница def = (ele") е? клетки е" содержится в объединении конечного числа клеток е&tradeразмерности т < п.

W) Множество F С К замкнуто в К тогда и только тогда, когда для любой клетки е&tradeпересечение F П ele" замкнуто в К.

Представление пространства К в виде объединения клеток называется клеточным разбиением. Ограничение ipSn-i характеристического отображения р клетки е" на границу S™" 1 диска Dn называется приклеивающим отображением. Число п называется размерностью клетки е", а верхняя грань размерностей всех клеток комплекса К — размерностью К. Говорят, что комплекс конечен, если он состоит из конечного числа клеток.

Замкнутое подмножество клеточного комплекса К, являющееся объединением его клеток, называется подкомплексом. Ясно, что каждый подкомплекс — это клеточный комплекс. Если К = U^0U?e/ne?'' — клеточный комплекс, то легко видеть, что множество Кт = U™0 Uе" является замкнутым подмножеством в К, т. е. является подкомплексом. Подкомплекс Кт называется т-ым остовом комплекса К.

Далее, непрерывное отображение <р клеточного комплекса Л' в клеточный комплекс У называется клеточным, если (р (Хт) С Ут для любого т. Как известно, см. например [28], каждое непрерывное отображение одного клеточного комплекса в другой гомотопно клеточному.

Иногда бывает удобным фиксировать характеристические отображения клеток клеточного комплекса. Клеточные комплексы с заданными характеристическими отображениями иногда называют оснащенными.

Дадим теперь определение топологического графа.

Определение. Топологическим графом G назовем произвольный оснащенный одномерный клеточный комплекс. Клетки размерности 0 называются вершинами графа G, а клетки размерности 1 — ребрами. Замыкания ребер графа G будем называть замкнутыми ребрами.

Замечание. Каждый клеточный комплекс К может быть построен из стандартных замкнутых шаров с помощью приклеивающих отображений. В самом деле, пусть уже построен (п — 1)-ый остов Кп~1. и (ра: D" - —> К — характеристическое отображение, соответствующее n-мерной клетке е", комплекса К. Поскольку (p{dD™) С Кп~1. определено отображение Ф несвязного объединения S = U^tSaгде S" -" «1 = в Кп~ а именно, $L,-i = Пусть V = Uav. ci С* ' о a .->a.

Тогда очевидно, что Кп — V Ц1ф, т. е. n-ый остов Кп получается из Кп~1 приклеиванием всех n-мерных клеток по их приклеивающим отображениям.

В частности, каждый топологический граф — это топологическое пространство, склеенное из набора отрезков по некоторой эквивалентности, отождествляющей концевые точки этих отрезков.

Пусть G и Сх2 — топологические графы. Клеточное отображение (fi: G —)• G.

Определение. Отображение графов называется эквивалентностью, если оно — гомеоморфизм. Графы G и G2 называются эквивалентными, если существует эквивалентность ip: G —> G2..

С точки зрения теории графов эквивалентные графы устроены одинаково, и их, как правило, не различают..

Ребро е и вершина v топологического графа G называются инцидентными, если v лежит в замыкании ребра е. Две различных вершины vi и i>2 графа называются смежными, если они инцидентны одному и тому же ребру е, про которое говорят, что оно соединяет, вершины и V2- Два различных ребра графа называются соседним/а, если они инцидентны одной и той же вершине. Ребро графа, инцидентное ровно одной вершине, называется петлей. Ребра, не являющиеся петлями, называются простыми..

Граф G называется простым, если он, во-первых, не имеет петель, и, во-вторых, каждые две вершины из С соединяются не более чем одним ребром. Ясно, что, с точностью до эквивалентности, простой граф можно задать как систему двухэлементных подмножеств множества всех его вершин. При этом каждое двухэлементное подмножество задает ребро графа С. соединяющее соответствующие вершины. Такой подход принят в комбинаторной теории графов, см. например [25]. Однако, для наших дальнейших целей топологический подход гораздо более удобен..

Пусть V — произвольная вершина топологического графа Рассмотрим ее полный прообраз при характеристических отображениях всех инцидентных ей ребер. Этот полный прообраз представляет собой объединение тех концов отрезков, параметризующих ребра, которые отображаются в вершину V. Количество элементов в этом множестве называется степенью вершины V и обозначается через с^(г.>). Таким образом, если представить топологический граф склеенным из отрезков, то степень вершины равна числу концов отрезков, склеивающихся в эту вершину. Ясно, что степень вершины V равна сумме числа простых ребер, инцидентных V, и удвоенного числа инцидентных V петель..

Замечание. Из аксиом клеточного комплекса вытекает, что степень каждой вершины топологического графа конечна. Следовательно, если граф имеет конечное число вершин, то он компактен..

Поскольку каждый топологический граф по определению является топологическим пространством, в дальнейшем терминология, относящаяся к топологическим пространствам (связность, компактность и т. д.), будет, как правило, без оговорок применяться к графам. Так же без оговорок будет использоваться терминология, относящаяся к клеточным комплексам..

1.1.2 Маршруты, пути, циклы.

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

Определение. Пусть </?: С1 —У (?2 — отображение графов. Отображение (р называется погружением, если никакое ребро графа С не отображается в точку..

Погружение (р назовем невырожденным, если никакая пара ребер графа не отображается в одно и то же ребро графа С^- Погружение <р назовем вложением, если оно гомеоморфно отображает граф С на его образ в &*2. Другими словами, вложение не склеивает ни ребер, ни вершин графа, а невырожденное погружение может склеивать вершины, но не может склеивать ребра..

Определение. Граф Ь, гомеоморфный отрезку, назовем топологической (незамкнутой) ломаной, а граф 5, гомеоморфный окрзокности, — топологической замкнутой ломаной..

Маршрутом в графе С называется погружение (р топологической ломаной в граф 6?. Маршрут называется замкнутым, если ломаная замкнута, и незамкнутым в противном случае. Если отображение <р — невырожденное погружение, то соответствующий маршрут называется погруженным путем. Если отображение <р — вложение, то соответствующий маршрут называется простым путем или, для краткости, пут, ем, а замкнутый простой путь — циклом..

1.1.3 Подграфы, остовы.

Произвольный подкомплекс графа <7 называется подграфом в О. Ясно, что каждый подграф сам является графом..

Пусть (р: Ь —)¦ (7 — простой путь в графе <7. Тогда р (Ь) С С является, очевидно, подграфом в С, который мы также будем называть простым пут, ем. Далее, пусть (р: 5 —" (? — цикл в графе С. Тогда (5) С О является, очевидно, подграфом в б, который мы также будем называть циклом..

Определение. Простой связный граф, несодержащий циклов, называется деревом..

Простой граф С называется полным, если любые две его вершины смежны. Степень каждой вершины полного графа с п вершинами равна, очевидно, п — 1. При п = 2 полный граф является деревом, а при п > 2 — не является..

Простой граф С с п + 1 вершиной называется звездой с п лучами, если п его вершин имеют степень 1, а одна — степень п. Вершина степени п звезды с п лучами называется центром звезды. Очевидно, что звезда является деревом, каждое из ребер которого соединяет центр звезды с соответствующей вершиной степени.

Легко проверить, что имеет место следующий результат, см. например [25]..

Предложение 1.1 Простой связный граф Gen вершинами является деревом, если и только если G имеет ровно (п — 1) ребро..

Подграф H графа G называется остовным, если множества вершин графов H и G совпадают. Остовный подграф связного графа G называется остовом, если он является деревом..

Каждый связный граф имеет остов. Количество остовов конечного связного графа может быть вычислено с помощью классической матричной теоремы Кирхгофа, см. например [25]. Нам, однако, понадобится лишь следствие из нее..

Предложение 1.2 Число остовов полного графа сп вершинами равно пп~2..

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

1.1.4 Операции над графами.

Пусть G — некоторый топологический граф, и е — произвольное его ребро. Рассмотрим подпространство G' в G. полученное выкидыванием из G внутренности ребра е. Подпространство G' наделим структурой одномерного клеточного комплекса, т. е. топологического графа, объявив клетками размерности 0 (т.е. вершинами) комплекса G' все вершины графа G, а клетками размерности 1 (т.е. ребрами) комплекса G' — все ребра графа G, за исключением ребра е. Описанная только что перестройка графа G называется выкидыванием из G ребра е и обозначается G е..

Пусть G — топологический граф, и v — произвольная его вершина. Пару (G, v) назовем отмеченным топологическим графом..

Пусть (G, v) и (G', vf) — два отмеченных топологических графа. Пусть I = [а, Ъ] — отрезок. Склеим G, I и G' (как топологические пространства) следующим образом. Точку, а? I отождествим с v, а точку bel — с г/. Полученное топологическое пространство G наделим структурой графа, выбрав в качестве вершин все вершины из G и G', а в качестве ребер — все ребра из G и G', а также отрезок I (точнее, его образ при склейке). Эта операция называется склейкой отмеченных графов (G, v) и (G', v'), а ребро, полученное из отрезка I, — ребром склейки..

Пусть G — топологический граф, иг- — произвольная его вершина степени больше 1. Построим новый граф G', перестав отождествлять те концы отрезков, параметризующих инцидентные v ребра, которые склеиваются в вершину v графа G. Говорят, что граф G' получен из G разрезанием по вершине ь. Ясно, что граф С имеет столько же ребер, что и граф, а количество вершин у графа О' больше, чем у графа.

0 на степень й вершины ь в графе О без единицы. Отметим, что у графа С имеется ровно й вершин, которые возникли при разрезании вершины V (в графе О они все склеиваются в вершину у)..

Пусть (? — топологический граф, е — произвольное его ребро, и.

1 = [а, Ъ] — отрезок, параметризующий ребро е. Пусть V и г/ — вершины графа С, инцидентные ребру е (эти вершины могут совпадать, если е — циклическое ребро). Для определенности, предположим, что точка, а е I отождествляется с г>, а точка Ь? I — си'. Выберем на е (фактически, на [а, 6]) некоторую внутреннюю точку А, и рассмотрим два отрезка: Д = [а, ^4] и 12 = [А, Ь], Выбросим из графа С? ребро е и к полученному графу С е приклеим отрезки 1 и 12, отождествив вершину V с точкой, а? Д, а вершину ь' — с точкой Ь? 12. Полученное топологическое пространство наделим структурой графа, объявив вершинами все вершины из Се. а также две разные точки, А — А? и А2 = А € 12 в качестве ребер возьмем все ребра из С е, плюс отрезки 1 и 12. Описанная операция называется разрезанием графа С по точке, А и обозначается С А. Естественные вложения отрезков 1 и 12 в отрезок I порождают очевидным образом погружение графа (?Ав граф Спри этом точки, А и А2 переходят в одну точку, А 6 е. Ребро е будем называть ребром разреза, а точку, А — точкой разреза. Также скажем, что ребро е при разрезании по точке, А распадается на два ребра е.1 и е2, параметризованных соответственно отрезками Д и 12, а точка, А распадается на две вершины, А и А2 графа 0А..

Определим теперь операцию на графе С, обратную к разрезанию. Для этого выберем в С две вершины V и г/ степени 1, и пусть еже1 — ребра, инцидентные соответственно V и V1. Отождествим вершины V и у'. Полученное топологическое пространство обозначим через С. Параметризуем очевидным образом объединение е и е' некоторым отрезком, и после этого введем на С структуру графа, выбрав в качестве вершин все вершины из С, за исключением и и и', а в качестве множества ребер графа С — множество всех ребер из С, из которого выброшены еие’и добавлено е и е'. Так полученный граф обозначим через С?/г> ~ г/, а описанную операцию назовем склейкой графа С по вершинам и и у'. Вершины V и г/ называются вершинами склейки..

Более общо, пусть Н — произвольный подграф в топологическом графе О. Фактор-пространство О/Н, очевидно, является графом, т. е. одномерным клеточным комплексом. Граф О/Н называется фактор-графом графа С по подграфу Н..

В частности, пусть граф С получен из графа О разрезанием по вершине ь степени с1, и. ., ь'(1 — вершины графа С, возникшие при этом разрезании. В качестве подграфа Н' в С выберем граф с вершинами ь[,., г^ и не содержащий ребер, т. е. пустой граф с вершинами Очевидно, граф С/Н' эквивалентен исходному графу С. Соответствующую проекцию С С — С/Н' мы обозначим через V и назовем восстанавливающим отображением. Если граф С получен из Ст разрезанием по нескольким вершинам, то восстанавливающее отображение определяется точно так же. Формально, в последнем случае граф С получается последовательным применением операции разрезания по одной вершине, и восстанавливающее отображение можно определить как композицию соответствующих восстанавливающих отображений..

1.1.5 Граница графа, локальный граф.

Предположим, что в графе б выделено некоторое подмножество В множества его вершин. Такой граф С мы будем называть графом, с границей дС = В. Вершины из 8С будем называть граничными или неподвижными, а все остальные вершины — внутренними или подвижными. Ребра графа, инцидентные граничным вершинам, также назовем граничными, а ребро, не инцидентное никакой граничной вершине, назовем внутренним..

Пусть б? — некоторый граф с границей В. Обозначим через С в подграф в С, порожденный всеми подвижными вершинами графа 6?. Подграф называется подвижным подграфом графа С (по отношению к границе В). Отметим, что подвижный подграф состоит в точности из всех внутренних ребер графа С?..

Пусть (9 — произвольный граф с границей дС (возможно, пустой), и Р? С — некоторая его точка. Допустимой окрестностью [/ С С точки Р графа С называется замыкание связной окрестности этой точки, не содержащее вершин графа С, отличных от Р, если Р — вершина, и не содержащее петель из Ст. Наделим окрестность 17 структурой графа, объявив вершинами все точки из 817 и {Р}, а ребрами — отрезки в 17, соединяющие эти точки. Полученную звезду обозначим через С с/ и будем называть локальным графом с центром в точке Р. Определим каноническую границу дСц локального графа Си, включив в нее все вершины из 817, а также вершину Р, если Р — граничная вершина графа С. Другими словами, дСи = (<9С? П 17) и [С П 817)..

Отметим, что количество ребер произвольного локального графа графа (? с центром в вершине V графа С равно степени этой вершины в графе С..

Пусть С — некоторый граф с границей <9С. Разрежем граф С по всем граничным вершинам степени больше 1, и обозначим через Сг полученные связные компоненты. Пусть, как и выше, ь> — это восстанавливающее отображение графа UGi на G. Для каждой компоненты Gi определим границу dGi как множество всех тех вершин из G% степени 1, которые лежат в прообразе v~l{dG) границы dG при восстанавливающем отображении v. Каждая компонента Gi с границей dGi называется невырожденной компонентой графа G..

1.1.6 Взвешенные графы, остовы минимального веса.

В заключение раздела 1.1, рассмотрим классическую оптимизационную задачу теории графов — задачу о поиске остова наименьшего веса..

Понятие взвешенного графа естественно возникает в приложениях, где различные ребра графа не всегда равноправны. Это находит отражение в следующем определении..

Граф G, на множестве Е ребер которого задана функция со: Е —> Е называется взвешенным графом, а сама функция со — весовой функцией взвешенного графа G. Если е — произвольное ребро графа G, то значение со (е) весовой функции на этом ребре называется весом ребра е. Рассмотрим произвольный подграф Н С G. Тогда вес со (Н) подграфа Н естественным образом определяется как сумма весов всех ребер из Н..