Геометрические свойства локально минимальных сетей (1097521), страница 15

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 15)

Ребро е и вершина и топологнческого графа С называются иниидентными, если о лежит в замыкании ребра е. Две различных вершины о~ и из графа называются смежными, если они инцидентны одному и тому жс ребру с, про которое говорят, что оно соединяет вершины ш и оя. Два различных ребра графа назывшотся соседними, если они инцидентны одной и той же вершине. Ребро графа, инцидентное ровно одной вершине, называется петлей. Ребра, не являющиеся петлями, называются простыми.

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

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

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

1.1.2 Маршруты, пути, циклы Определим теперь стандартные понятия маршрута, пути, цикла и т.д. воспользовавшись топалогическим подходом. Начнем с определения погру жения графов. Определение. Пусть ~р: С~ — ~ Сз - отображение графов. Отображение д называется позружепием, если никакое ребро графа Сл не отображается в точку. 1.1. Графы: топологический подход. Погружение у назовем невырожденны.м, если никакая пара ребер графа С» не отображается в одно и то же ребро графа С . Погружение р назовем вложением, если оно гомооморфно отображает граф С» на его образ в Сз. Другими словами, вложение не склеивает ни ребер. ни вершин графа, а невырожденное погружение может склеивать вершины, но не может склеивать ребра. Определение. Граф 1,, гомсоморфный отрезку, назовем тополозической»незамкнутой) ломаной, а граф л', гомеоморфный окружности, тополозической замкну»пой ломаной.

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

1.1.3 Подграфы, остовы Произвольный падком»»лекс графа С нязь»вается подграфом в С. Ясно., что каждый подграф сам является графом. Пусть уп А — ~ С простой путь в графе С. Тогда»»»(»,) С С является. очевидно, подграфом в С, который мы также будем называть простым путем. Далее. пусть»о: о' — » С цикл в графе С. Тогда »о»о) с С является, очевидно, подграфом в С, который мы также будем называть циклом. Определение. Простой связный граф, несодержащий циклов, назы- вается деревом. Простой граф С называется полным, если любые две ого вершины смежны. Степень каждой вершины полного графа с п, вершинами равна, очевидно, п — 1.

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

Глава 1. Обобщенные сети на многообразиях. Предложение 1.1 Простой связный граф' С с и вершинами является деревом, если и только если С имеет ровно (и — 1) ребро. Подграф Н графа С называется остовным, если множества вершин графов Н и С совпадают. Остовныи подграф связного графа С называется остовом, если он является деревом.

Каждый связный граф имеет остов. Количество остовов конечного связного графа может быть вычислено с помощью классической матричной теоремы Кирхгофа, см, например (25], Пам, однако, понадобится лишь следствие из нес. Предложение 1.2 Число остовов полного графа с п вершинами равно пь — 2 Замечание. В дальнейшем, там где не оговорено противное, мы бу- дем предполагать все графы конечными.

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

ребрами) комплекса С' .- все ребра графа С, за исключением ребра е, Описанная только что перестройка графа С назгявается вьтидыванием из С ребра е и обозначается С У е. Пусть С топологический граф, и о произвольная его вершина. Пару (С, и) назовем отмеченным тополоеическим графом. Пусть (С,и) и (С',о') - - два отмеченных топологических графа. Пусть 1 = (а,Ь] --. отрезок. Склеим С, 1 и С' (как топологические пространства) следующим образом. Точку а Е 1 отождествим с о, а точку Ь Е 1 с о'.

Полученное топологическое пространство С наделим структурой графа, выбрав в качестве вершин все вершины из С и С', а в качестве ребер — - все ребра из С и С', а также отрезок 1 (точнее, его образ при склейке). Эта операция называется склейкой отмеченных графов (С, о) и (С', о'). а ребро, полученное из отрезка П ребром склейки. Пусть С вЂ” топологический граф, и о произвольная его вершина степени больше 1.

Построим новый граф С', перестав отождествлять те концы отрезков, параметризующих инцидснтныс о ребра, которые склеиваются в вершину о графа С. Говорят, что граф С' получен из С 1.1, Графы: топологический подход. разрезанием по вершине е, Ясно, что граф С' имеет столько же ребер, что и граф С, а количество вершин у графа С' больше. чем у графа С на степень и* вершины н в графе С без единицы. Отметим., что у графа С' имеется ровно й вершин, которые возникли при разрезании вершины н (в графе С они все склеивзлотся в вершину н). Пусть С .-- топологический граф, е --- произвольное его ребро, и 1 = (а,Ь) отрезок, параметризующий ребро е, Пусть е и н' вершины графа С, инцидентные ребру е (эти вершины могут совпадать. если е циклическое ребро).

Для определенности, предположим, что точка а е 1 отождествляется с н, а точка Ь е 1 с н'. Выберем на е (фактически, на (а, Ь)) некоторую внутреннюю точку А, и рассмотрим два отрезка: 1~ = [а,.4) и 1з = (А,Ь). Выбросим из графа С ребро е и к полученному графу С 1 е приклеим отрезки 1~ и 1м отождествив вершину и с точкой а е 1м а вершину и' с точкой Ь е 1 . Полученное топологическое пространство наделим структурой графа, объявив вершинами все вершины из С'1с, а также две разные точки.4~ — — А й 1~ и Аз = А й 1; в качестве робер возьмем все ребра из С '1 е, плюс отрезки 1~ и 1з.

Описанная операция называется разрезанием графа С по точке А и обозначается С 1.4. Естественные вложения отрезков 1~ и 1з в отрезок 1 порождают очевидным образом погружение графа С 1, А в граф С, при этом точки А~ и Аз переходят в одну точку А й е. Ребро е будем называть ребром разреза, а точку .4 точкой разреза. Также скажем, что ребро е при разрезании по точке А распадается на два рейра е~ и ез, параметризованных соответственно отрезками 1~ и 1з, а точка А Риспадаетсл на две веРшины А, и Аз гРафа С 1 А. Определим теперь операцию на графе С, обратную к разрезанию.

Для этого выберем в С две вершины н и н' степени 1, и пусть е и е' ребра, инцидентные соответственно н и н'. Отождествим вершины н и н'. Полученное топологическое пространство обозначим через С'. Параметризуем очевидным образом объединение е 0 е' некоторым отрезком, и после этого введем на С' структуру графа, выбрав в качестве вершин все вершины из С, за исключением н и н', а в качестве множества ребер графа С' множество всех ребер из С, из которого выброшены е и е' и добавлено е 0 е'.

Характеристики

Список файлов диссертации