Геометрические свойства локально минимальных сетей (1097521), страница 16
Текст из файла (страница 16)
Тзк полученный граф обозначим через С1н и', а описанную операцию назовем склейкой графа С по вершинам и и н'. Вершины н и о' называются вершинами склейки. Более общо, пусть Н произвольный подграф в топологическом графе С. Фактор-пространство С(Н, очевидно, является графом, т.с. одномерным клеточным комплексом. Граф С1Н называется фактор- графом графа С по подграфу Н. В частности, пусть граф С' получен из графа С разрезанием по вершине н степени и, и н(,..., н„' вершины графа С', возникшие при Глава 1.
Обобщенные сети на многообразиях. этом разрезании. В качестве подграфа Н' в С' выберем граф с вершинами и',,...,и„' и не содержащий ребер, т.е. пустой граф с вершинами о'„...,о„'. Очевидно., граф С'(Н' эквивалентен исходному графу С, Соответствуя>щук> проекцию С' — > С = С'~Н' мы обозначим через и и назовем восстанавливаю>цим отображением. Если граф С' получен из С разрезанием по нескольким вершинам, то восстанавливающее отображение определяется точно так же.
Формально, в последнем случае граф С' получается последовательным применением операции разрезания по одной вершине, и восстанавливающее отображение можно определить как композицию соответствующих восстанавливающих отображений. 1.1.5 Граница графа, локальный граф Предположим, что в графе С выделено некоторое подмножество В множества его вершин.
Такой граф С мы будем называть графом с границей дС = В. Вершины из дС будем называть граничными или неподвижными, а все остальные, вершины - внутренними или подвижными. Ребра графа, инцидентные граничным вершинам, также назовем граничными, а ребро, не инцидентное никакой граничной вершине, назовем внутренним. Пусть С --. некоторый граф с границей В. Обозначим через Св подграф в С, порожденный всеми подвижными вершинами графа С. Подграф Св называется подвижным подграфом графа С (по отношению к границе В). Отметим, что подвижный подграф состоит в точности из всех внутренних ребер графа С.
Пусть С произвольный граф с границей дС (возможно, пустой), и Р Е С некоторая его точка. Допустимой окрестпностью Н С С точки Р графа С называется замыкание связной окрестности этой точки, не содержащео вершин графа С, отличных от Р, если Р вершина, и не содержащее петель из С. Наделим окрестность Н структурой графа, объявив вершинами все точки из дН 0 1Р), а ребрами— отрезки в Н, соединяющие эти точки. Полученную звезду обозначим через Сп и будем называть локальным графом с центром в точке Р, Определим каноническую границу дСп локального графа Сп, включив в нее все вершины из дН, а также вершину Р, если Р граничная вершина графа С.
Друти>ли словами, дСц = (дС О Н) 0 (С О дН). Отметим, что количество ребер произвольного локального графа графа С с центром в вершине и графа С равно степени этой вершины в графе С. Пусть С некоторый граф с границей дС. Разрежем граф С по всем граничным вершинам степени больше 1, и обозначим через С, 1.1. Графы: топологический подход. полученные связные компоненты. Пусть, как и выше, и --. это восстанавливающее отображение графа ЫС; на С. Для каждой компоненты С; определим границу дС, как множество всех тех вершин из С, степени 1, которые лежат в прообразе о в(дС) границы дС при восстанавливающем отображении о. Каждая компонента С; с границей дС; называется невырожденной компонентой грифа С. 1.1л6 Взвешенные графы, остовы минимального веса В заключение раздела 1.1., рассмотрим классическую оптимизационную задачу теории графов -- задачу о поиске остова наименьшего веса.
Понятие взвешенного графа естественно возникает в приложениях, где различные ребра графа не всегда равноправны. Это находит отражение в следующем определении. Граф С, на множестве Е ребер которого задана функция иы Š— ~ К называется взвшиенным графом, а сама функция ш весовой функцией взвешенного графа С. Если е произвольное ребро графа С, то значение ьз(е) весовой функции на этом ребре называется весом ребра е. Рассмотрим произвольный подграф Н с С.
Тогда вес ьз(Н) подграфа Н естественным образом определяется как сумма весов всех ребер из Н. В приложениях, таких как транспортная задача, часто возникает необходимость найти во взвешенном графе С подграф специального вида (например, остов) и экстремального веса. Задача о поиске остова минимального веса относится как раз к задачам такого типа. Задача 1.1 (Об остове минимального веса) Пусть С связный простой взвешенный граф с весовой функцией ш. Нийпьи осгаов То графа С наимень1иего возможного веса ш(Тв), т.е. ы(Тв) = ш1п(и (Т))Т вЂ” осгаов графа С). Отметим, что решение этой задачи, очевидно существует (напомним, что мы предполагаем конечность графа С), и называется остовом минимального веса или минимальным остовным деревом в графе С.
Однако, а ртог1 вовсе нс очевидно, что существует полиномиальный алгоритм, строящий остов минимального веса. Действительно, например полный граф К„с и вершинами имеет п" " различных остовов, см. предложение 1.'2, поэтому простой перебор вариантов не полиномиален.
Глава 1. Обобшенные сети на многообразиях. Полиномиальные алгоритмы построения минимальных остовных деревьев были построены практически одновременно и независимо Дейкстрои [14], Краскалом [61] и Примам [70]. Проиллюстрируем идею работы алгоритмов такого типа на примере алгоритма Краскала. Этот алгоритм состоит в следующем. Пусть С простой связный взвешенный граф, количество вершин которого обозначим через и.
Начнем с так называемого пустого подграфа Оо с С, т.е, графа, состоящего из а вершин и не имеющего ребер. На первом шаге алгоритма построим подграф Ть С С, который получается из Оь добавлением к нему ребра е1 графа С., где еь одно из ребер наименьшего веса: ш[е1) < ш[е) для произвольного ребра е графа С. Пусть на 1-ом шаге работы алгоритма построен некоторый подграф Т; с С. Тогда на [1-~- 1)-ом шаге построим подграф Тьы с С так. Рассмотрим множество Е; ребер графа С, не входящих в подграф Т,, и таких, что добавление любого ребра из Е, к подграфу Т, не приводит к образованию циклов. Выберем из множества Е, ребро еьь1 наименьшего веса. Тогда подграф Тьы получается из подграфа Т; присоединением ребра еььь Алгоритм заканчивает работу, построив подграф Ть Имеет место следующий несложный результат [сьь, например, [25]).
Предложение 1.3 Пусть С взвешенный граф, весовая функция ш которого неотрицагаельна. В сделанных выше обозначениях, для произвольного 1, 2 < 1 < и — 1, подграф Т; может бьппь построен. Более того, подграф Т„1 является остовом минимального веса взвешенного графа С. Можно показать, что алгоритм Краскала находит минимальное остовное дерево взвешенного графа С, имеющего и вершин и т ребер, за О[пт) шагов [26].
Минимальные остовные деревья встречаются в приложениях, в частности, как приближенные решения проблемы Штейнера [см, Введение и [69]). 1.2 Общее определение сети 1'ак уже отмечалось выше, в зависимости от специфики конкретной вариационной задачи, понятие сети на многообразии определяется по разному. В настоящем параграфе обсуждаются два основных подхода и даются общие определения сетей на многообразии, Пусть Их произвольное гладкое многообразие. 1.2. Общее определение сети. Определение. Связное подмножество Г многообразия И' назовем сетью, если оно представимо в виде образа 1(С) некоторого топологического графа С при непрерывном отображении у; С вЂ” з И", т.е.
если существует некоторый топологический граф С и его непрерывное отображение 1 в многообразие И', такое что Г = 1'(С). Непрерывное отображение у: С -+ И' в этом случае называется параметризаиией сети Г, а граф С -- параметризуют м графом сети Г, Пусть Г произвольная сеть на многообразии 1И. Тогда, очевидно, существует бесконечно много различных параметризации сети Г. Пример.
На рис. 1.1 показаны различные параметризации одной и той же сети на плоскости Кз. Отображение 1",: С, — > Кз переводит вершину графа С, с номером й в точку Аь сети Г, а все вершины без номера в точку Ап Ребро графа Сб инцидентное вершине с номером й, отображается в отрезок кривой АьАю а все ребра, соединяющие нсзанумерованные вершины из С,, отображаются в точку Аю Отметим, что параметризующие графы С1 и Сз параметризаций ~~. С1 -+ Из и 1з; Сз — з И' эквивалентны, а параметризующий граф Сз параметризапии )з.' Сз — > И' нс эквивалентен графам С1 и Сз.
Рис. 1.1; Несколько разных параметризаций сети на плоскости Замечание. Отметим, что из связности сети как подмножества мно- гообразия не вытекает связность ее параметризуюшего графа. Иногда бывает удобно зафиксировать некоторую конкретную параметризацию сети. Определение. Сеть Г вместе с некоторой фиксированной параметризацисй 1о.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
