Характеристики конечных метрических пространств, порожденных графами Рублёва Ольга Владимировна

Содержание к диссертации

Введение

1 Аддитивные конечные метрические пространства и минимальные заполнения 14

1.1 Основные определения 14

1.2 Аддитивные пространства. Определения, примеры, свойства

1.2.1 Свойства аддитивных пространств 16

1.2.2 Примеры аддитивных и неаддитивных пространств 17

1.3 Одномерная задача Громова о минимальном заполнении 18

1.3.1 Примеры минимальных заполнений 19

1.3.2 Свойства минимальных заполнений 20

1.4 Периметры метрических пространств. Определения, примеры, свойства 21

1.4.1 Определения 21

1.4.2 Примеры 22

1.4.3 Свойства 23

1.5 Критерий аддитивности конечного метрического пространства 24

2 Кривизна Риччи взвешенного дерева 26

2.1 Определения 26

2.1.1 Транспортная задача, как задача линейного программирования 26

2.1.2 Обобщение транспортной задачи 27

2.1.3 Двойственная транспортная задача линейного программирования 27

2.1.4 Обобщенная двойственная транспортная задача и функция Вассерштейна 1 порядка 28

2.1.5 Кривизны Риччи для метрических пространств со случайным блужданием

2.2 Предварительные результаты 30

2.3 Формула кривизны Риччи для взвешенного дерева 30

2.4 Следствия из формулы кривизны Риччи для взвешенного дерева

2.4.1 Случай бинарного дерева с постоянной весовой функцией. 35

2.4.2 Связь структуры бинарного дерева с кривизнами Риччи на его вершинах 35

2.4.3 Оценка суммы кривизн Риччи на парах смежных вершин дерева 36

2.5 Доказательства следствий 36

2.5.1 Доказательство следствия 1 36

2.5.2 Доказательство следствия 2 37

2.5.3 Доказательство следствия 3 40

2.6 Оценка кривизны Риччи 42

Заключение 45

Список публикаций по теме диссертации 47

Литература

• Свойства аддитивных пространств
• Двойственная транспортная задача линейного программирования
• Кривизны Риччи для метрических пространств со случайным блужданием
• Оценка суммы кривизн Риччи на парах смежных вершин дерева

Введение к работе

Актуальность темы

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

Понятие одномерного минимального заполнения конечного метрического пространства впервые возникло в работе Иванова и Тужилина¹ при изучении двух задач — проблемы Штейнера о кратчайших сетях и задачи Громова о минимальном заполнении.

Проблема Штейнера о кратчайших сетях — это задача о нахождении оптимального соединения конечного подмножества метрического пространства. Впервые этот вопрос, по-видимому, возник в XVII веке в работах Пьера Ферма, и первоначально задача формулировалась так: для трех заданных точек на плоскости нужно найти такую четвертую, чтобы сумма расстояний от нее до трех заданных точек была минимальной².

Поставленная П. Ферма задача решалась в течение нескольких столетий. Первые решения и расположения точек предложили Э. Торричелли и Б. Кавальєри (в XVII в.), затем их конструкцию усовершенствовал спустя столетие Т. Симпсон. Наконец в конце XIX века Ф. Хайнен и Ж. Бертрам получили полное решение задачи Ферма³. Одним из обобщений задачи Ферма является транспортная задача о соединении четырех городов кратчайшей системой дорог, которую решил К.Ф. Гаусс, предложив ввести две точки-развилки. Также обобщение задачи Ферма для множеств, состоящих из 4 и 5 точек, рассматривали французские математики — Ж.Д. Жергонн, Б.П.Э. Клайперон и Г. Ламе.

Обобщение задачи Ферма для п точек начал исследовать еще Штейнер. Он предложил рассмотреть единственную дополнительную точку с минимальной суммой расстояний от этой точки до заданных. Но в 1934 г. В.Ярник и О.Кеслер⁴ предложили увеличить количество вспомогательных точек, как это делали в частных случаях Гаусс и Жергонн, для минимизации суммы расстояний между всеми точками. Сегодня именно эту задачу принято называть проблемой Штейнера.

Напомним теперь классическую задачу Громова. Пусть М — гладкое замкнутое многообразие, на котором задана функция расстояния р. Рассмотрим всевозможные «пленки» W, затягивающие М, т.е. замкнутые компактные многообразия с краем, равным М. Рассмотрим на многообразии W функцию рас-

¹ А. О. Иванов, А. А. Тужилин, Одномерная проблема Громова о минимальном заполнении, Математ. сборник (2011).

²Ferma Р. 1643 ED Н Tannery, ed "Oeuveres", vol.1, Paris 1891

³G. Loria, G. Vassura (1919), Opere de Evangelista Torriceli, vol. 1, cc. 79-97

⁴V. Jarnik, O. Kossler (1934), О minimalnich grafech obsahujicich n danych bodu, Cas, Pestovani Mat. (Essen) T. 63: 223-235.

стояния — d, не уменьшающую расстояния между точками из М. Такое пространство W = (И-⁷, d) будем называть заполнением метрического пространства Л4 = (М, р). Задача Громова состоит в описании точной нижней грани объемов заполнений, а также в поиске тех пространств W, называемых минимальными заполнениями, на которых эта точная нижняя грань достигается. Минимальные заполнения нашли применения в теории динамических систем, асимптотической геометрии и математической физике.

А.О. Иванов и А.А. Тужилин рассмотрели в качестве М конечное метрическое пространство, а заполнениями этого пространства стали метрическое пространства, имеющие структуру одномерных стратифицированных многообразий, которые можно рассматривать как графы с неотрицательной весовой функцией на ребрах. Таким образом, А.О. Иванов и А.А. Тужилин⁵ получили обобщение проблемы Громова на случай стратифицированных многообразий, которое формулируется так.

Пусть М — произвольное конечное множество, G = (V, Е) — некоторый связный граф. Говорят, что граф G соединяет М, если V D М. Пусть АЛ = (М, р) — конечное псевдометрическое пространство, a G = (V, Е) — связный граф, соединяющий М. На ребрах графа зададим функцию ш: Е —> М₊, где Ш₊ — неотрицательные числа. Как правило, эту функцию ш называют весовой функцией, а пару (G,uj) — взвешенным графом. Функция ш порождает на множестве вершин V графа G индуцированную псевдометрику d_w, которая по определению равна наименьшему весу пути между двумя заданными вершинами связного графа. Если для любых точек р и q из множества М псевдометрика d_w не уменьшает расстояние между этими точками относительно псевдометрики р, т.е. du(p,q) > p(p,q), то взвешенный граф Q = (G,uj) называется заполнением метрического пространства Л4, а граф G — типом этого заполнения. Число mf(jM) = inf cu(Q) по всем заполнениям метрического пространства Л4 называется весом минимального заполнения. Одномерная задача Громова состоит в нахождении заполнения Q с весом, равным mf(jVf). Такое заполнение метрического пространства называется минимальным заполнением пространства Л4.

Оказалось, что в теории минимальных заполнений псевдометрических пространств важную роль играют так называемые аддитивные и псевдоаддитивные пространства⁶, которые также часто встречаются в приложениях, таких как биоинформатика и теория эволюции . Конечное метрическое пространство Л4 = (М, р) называется аддитивным, если существует взвешенное дерево Q = (G,uj), G = (V_}E), такое что М С V, и метрика р совпадает с ограничением на М метрики d_w. Дерево Q в этом случае называется порождающим для

⁵А. О. Иванов, А. А. Тужилин, Одномерная проблема Громова о минимальном заполнении, Математ. сборник (2011).

^еА. О. Иванов, А. А. Тужилин, Одномерная проблема Громова о минимальном заполнении, Математ. сборник (2011).

⁷М. М. Deza, Е. Deza, Encyclopedia of Distances// Berlin, Heidelberg, Springer-Verlag, (2009).

м.

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

Вторая характеристика конечных метрических пространств, исследуемая в диссертации, — кривизна Риччи.

Понятие кривизны Риччи для метрических пространств общего вида впервые возникло в работах Бакри и Эмери⁸. Ими была также определена так называемая «нижняя граница» кривизны Риччи на классе измеримых метрических пространств. Были найдены свойства измеримых метрических пространств, необходимые для существования «нижней границы» кривизны Риччи этих пространств. Существование «нижней границы» кривизны Риччи позволяет установить верхнюю границу для диаметра метрического пространства (теорема Бонне-Майера). В случае, когда метрическое пространство порождено графом, можно установить верхнюю границу для диаметра графа (аналог теоремы Бонне-Майера для графа), а также оценить количество вершин в графе. Оказывается, «нижняя граница» кривизны Риччи является также нижней границей для первого ненулевого собственного значения лапласиана для G. В 2009 году Оливье⁹ дал определение грубой кривизны Риччи на цепях Маркова, которое можно использовать для метрических пространств, порожденных графами.

Чанг и Яу¹⁰ впервые ввели определение кривизны Риччи для графов в 1996 году. А в 2011 году Лин, Лу и Яу¹¹ модифицировали определение Оливье для кривизны Риччи цепей Маркова на метрических пространствах¹².

Лин, Лу и Яу рассматривали взвешенный граф G = (V,E), функцию ш: Е —> Ш, которая ставит в соответствие каждому ребру вес, равный 1. Функция uj называется единичной весовой функцией и порождает функцию d = d_w: V х V —> К, называемую расстоянием, порожденным единичной весовой функцией. Эта функция, очевидно, удовлетворяет стандартным аксиомам метрики, поэтому пару 2J = (V, d) можно рассматривать как метрическое пространство. Пусть на этом метрическом пространстве задано распределение вероятности т": V —> [0,1] специального вида:

( а, если х = у,

_{КХу) = I вд >} ^{если х} _{~ у>}

[ 0, если х оо у и х т^ 2/, где х ~ у обозначает, что вершины х и у — смежны¹³. Функция Вассерштейна

⁸Bakry D., Emery М., Diffusions hypercontractives // Lect. Notes Math., 1985, 1123, 177-206.

⁹011ivier Y., Ricci curvature of Markov chains on metric, spaces // J.Funct.Anal. 2009, 256(3), 810-864. ¹⁰Fan Chung, S.-T. Yau Logarithmic Harnack inequalities Math. Res. Lett., 1996, 793-812. ¹¹Lin Y., Lu L.Y., Yau S.T. Ricci curvature of graphs // Tohoku Mathematical Journal, 2011, 63, 605-627. ¹²011ivier Y., Ricci curvature of Markov chains on metric, spaces // J.Funct.Anal. 2009, 256(3), 810-864. ¹³J.Jost, S. Lui, Ollivier's Ricci curvature, local clustering and curvature dimension inequalities on graphs, Discrete and computational geometry, 51 (2014),2, 300-322.

1 порядка \(т^7Пу), которая измеряет расстояние между двумя функциями т_х и rriy на 2J = (V, d), определяется так:

W{m^a_x,m^a_y)= max ^ f(v)(m_x(v) - m_y(v)) (1)

і — 1-липшицева функция ' *

В работах Лин, Л у, Яу^{14 15} а-кривизна Риччи определяется формулой к_а(х_}у) = 1 — W(т_х,rriy)Jd(:r,у). При а = 0 величина ко(х_}у) — кривизна Риччи-Оливье. Кривизной Риччи называется функция:

к(х,у):= lim*^-.

a->i 1-а

В отличие от работ Лин, Лу, Чанг и Яу в диссертации рассмотрен случай произвольных взвешенных деревьев и изучены свойства кривизны Риччи на паре вершин произвольного взвешенного дерева.

Цель работы

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

Основные методы исследования

В диссертации применяются методы метрической, дискретной геометрии, методы теории графов, методы теории минимальных заполнений конечных метрических пространств.

Научная новизна

Результаты диссертации являются новыми, получены автором самостоятельно и заключаются в следующем:

1. Доказан критерий аддитивности конечного метрического пространства в терминах его минимальных заполнений и периметра (Теорема 1).

2. Получена явная формула для вычисления кривизны Риччи для взвешенных деревьев (Теорема 2).

3. Установлена связь между структурой бинарного дерева с единичной весовой функцией на ребрах и кривизнами Риччи на парах вершин этого дерева (Следствие 2).

¹⁴Lin Y., Lu L.Y., Yau S.T. Ricci curvature of graphs // Tohoku Mathematical Journal, 2011, 63, 605-627 ¹⁵Fan Chung, S.-T. Yau Logarithmic Harnack inequalities Math. Res. Lett., 1996, 793-812.

4. Получены точные верхняя и нижняя оценки кривизны Риччи взвешенного дерева с произвольной весовой функцией (Теорема 12).

Теоретическая и практическая ценность работы

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

Апробация диссертации

Результаты диссертации докладывались на следующих семинарах и конференциях:

4. Научная конференция «Ломоносовские чтения» (МГУ, апрель 2011 года);

5. Международная конференция «Воронежская зимняя математическая школа С.Г. Крейна» (28 января 2012 года);

6. Международная конференция Александровские чтения (МГУ, май 2012 года);

4. Семинар «Дифференциальная геометрия и приложения» под руковод
ством академика А.Т. Фоменко (МГУ, 18 ноября 2013 года);

5. Международная конференция «Воронежская зимняя математическая школа С.Г. Крейна» (29 января 2014 года);

6. Семинар «Минимальные сети» под руководством профессоров А. О. Иванова и А. А. Тужилина, неоднократно (МГУ, 2010 — 2016 гг.);

7. Международная конференция Александровские чтения (МГУ, май 2016 года).

Структура и объем диссертации

Свойства аддитивных пространств

Пусть G = (V, Е) — произвольное дерево с некоторой границей М. Напомним, что в силу сделанного соглашения, М содержит все вершины дерева G степени 1 и 2. Выбросим из G некоторое ребро е, и пусть G\ и G — связные компоненты полученного леса. Положим МІ = М C\Gi. Легко проверить, что множества МІ не пусты. Полученное разбиение {M\ M z) множества М обозначим через Vc(e).

Определение. Пусть S — множество, содержащее к элементов. Назовем циклическим, порядком, на множестве S произвольную циклическую перестановку 7Г: S — S. Два элемента из S назовем соседними в смысле циклического порядка 7Г, если один из них является 7г-образом другого. Нумерацию (si,..., Sk) элементов из S назовем согласованной с циклическим порядком 7Г, если 7T(SJ) = Sj+i для каждого і, і к. Ясно, что нумерация (si,..., s ), к = \S\, согласована с циклическим порядком 7Г, если и только если Si+\ = 7r (si) для всех і, і к. Для каждого циклического порядка на множестве S существует к согласованных с ним нумераций.

Определение. Циклический порядок 7Г на границе М дерева G назовем планар-ным по отношению к G или обходом G, если для каждого є Є Е и МІ Є Va(e) существует единственная вершина р Є Mj, для которой тг(р) МІ. Последнее означает, что имеется такая нумерация множества М, согласованная с 7Г, что в ней элементы множества М\ предшествуют элементам множества М .

Приведем эквивалентное, см. [1], определение планарного порядка наМ в терминах укладок. Пусть G — некоторая укладка (вложение) дерева G на плоскость. Рассмотрим обход вокруг дерева G . Изобразим последовательно встречающиеся при таком обходе точки, соответствующие вершинам из М, последовательными точками на ориентированной окружности S1. Отметим, что каждая вершинар из М встречается degp раз, где degp - степень вершины р. Для каждой вершины р Є М степени больше 1, из всех соответствующих ей точек окружности оставим одну произвольную. Тем самым, мы построили инъекцию v. М — S1. Определим циклическую перестановку 7Г, положив тг(р) = q7 где u(q) следует за ь {р) на окружности S1. Будем говорить, что построенный циклический порядок 7Г порожден укладкой G . Ясно, что укладка G порождает 2\\ eMdegp циклических порядков.

Определение. Пусть Л4 = (М, р) — конечное псевдометрическое пространство, и 7Г — произвольный циклический порядок на М. Периметром пространства Л4 по отношению к порядку 7Г назовем величину Р ЕМ а шііітг P(jM,7r), где минимум берется по всевозможным циклическим порядкам 7Г на М, назовем периметром псевдометрического пространства М и обозначим через Р(Л4). Полупериметром псевдометрического пространства М по отношению к порядку 7Г назовем величину р(Л4,тг) = 12Р(Л4,тт).

Кроме того, в дальнейшем нам понадобится следующее обозначение. Если Q = (G, ио) — некоторое взвешенное дерево, соединяющий точки конечного псевдометрического пространства Л"! = (М, р), то множество всех циклических порядков на М, планарных по отношению к дереву G, т.е. всех обходов G, будем обозначать через 0{G) или через 0{Q). Будем также говорить, что каждый такой планарный порядок определен на Л4. 1.4.2 Примеры Рассмотрим в качестве метрического пространства.М — вершины квадрата х1, Х2: Ж3 и Ж4 со стороной 1 на евклидовой плоскости (расстояние между диагональными точками равно л/2)- Нумерация вершин по часовой стрелке, начиная с левой верхней вершины. Зададим первый обход по порядку, согласно заданной нумерации вершин. В этом случае периметр считается так: Р(Л ,7Гі) = р(хі,х2) + р(х2,хз) + р(ж3,ж4) + р(ж4,жі) = = 1 + 1 + 1 + 1 = 4. Можно задать другой обход на множестве М следующим образом: 7Г2: Х\ — %э, - %2 - %4- В этом случае периметр пространства считается следующим образом: Р(М,тт2) = р(жі,жз) +р( з,ж2) + р(х2,хА) + р(ж4,жі) = = \/2 + 1 + \/2 + 1 = 2 + 2\/2 Отсюда найдем периметр данного метрического пространства Р(М) = minP(7W,7r) = 4. По утверждению 1 вес минимального заполнения пространства Л4 равен u(G) = -lmm(p(xi,x2) + р(х3, ж4), р(жі,жз) + р( 2,ж4), р(жі, ж4) + р(жз, жг)) + тах(р(жі, ж2) + ) (жз, ж4), р(жі, ж3) + р( 2, ж4), р(жі, ж4) + /о(ж3, ж2)) J = 1 + \/2. Так как вес минимального заполнения метрического пространства не равен его полупериметру, то это пространство не является аддитивным (Теорема 7).

Теорема 7 ([1], утверждение 7.2). Пусть Q = (G,UJ) — взвешенное дерево с границей М, и 7Г — произвольный циклический порядок на М. Тогда J2Mp (p) ) 2uj(G). Р ЕМ Более того, равенство достигается, если и только если ТГ — некоторый пленарный порядок по отношению к G. Теорема 8 ([1], следствие 7.1). Пусть Q = (G,UJ) — произвольное заполнение псевдом,етрического пространства Л4, и тг — некоторый планарный порядок из 0(G). Тогда UJ(G) р(М,тг). 1.5 Критерий аддитивности конечного метрического пространства Основным результатом первой главы является следующий критерий аддитивности. Теорема 1. (Рублёва О.В., [1.1],) Вес минимального заполнения псевдометрического пространства равен полупериметру этого пространства тогда и только тогда, когда пространство аддитивно. Для доказательства критерия понадобится несколько вспомогательных лемм. Лемма 1. Пусть Q = (G,UJ) — минимальное заполнение псевдометрического пространства Л4. Предполооїсим, что вес минимального заполнения равен полупериметру данного метрического пространства, т.е. р(Л4) = UJ(G). Тогда р(тг}Л4) = р(Л4) для любого планарного порядка тг Є 0(G). Доказательство. По теореме 6 для произвольного планарного порядка 7Г Є 0{G) выполняется неравенство p(ir, Л4) uo{G). Следовательно, так как р{ЛЛ) — наименьший полупериметр, имеем р(Л4) р(тг,А4) uo{G). Но по условию леммы р(Л4) = UJ(G), откуда р(тг,Л4) = р(Л4), что и требовалось доказать. Лемма 2. Пусть Q = (G,UJ) — минимальное заполнение метрического пространства Л4 = (М,р). Предположим, что р(Л4) = UJ(G). Пусть 7г Є O(G) — произвольным планарный порядок. Тогда все граничные пути, соединяющие соседние относительно порядка 7Г вершины, точны.

Двойственная транспортная задача линейного программирования

Доказательство. Пусть дана матрица К = (kij) кривизн Риччи дерева G. Обозначим вершины дерева натуральными числами 1,..., п. Рассмотрим сначала случай, когда в дереве две вершины степени 1, то есть дерево состоит из одного ребра. В этом случае матрица кривизн Риччи будет содержать только неотрицательные величины и иметь вид: Рассмотрим второй случай, когда в дереве три вершины степени 1, тогда в этом дереве ровно одна вершина степени 3. В этом случае, в силу следствия 1, матрица будет содержать только неотрицательные величины. Кривизны на паре вершин степени 1 равны 1, а на паре вершин, одна из которых степени 3, а вторая степени 1, равны 2/3. Тогда, с точностью до нумерации вершин, матрица К будет иметь следующий вид: Очевидно, что вершина степени 3 — та, у которой в столбце и строке стоят 2/3. Если вершин степени 1 больше трех, то вершин степени 3 больше одной, и в матрице К появляются отрицательные элементы. Предъявим алгоритм, позволяющий определить для каждой вершины степени 1 единственную смежную с ней вершину степени 3, а для каждой вершины степени три — смежные с ней вершины, таким образом восстанавливая матрицу смежности.

Сначала находим в матрице элемент kij = 1. Этот элемент существует, так как в бинарном дереве есть усы. Согласно следствию 1, имеем ливок(х,у) = d, ч = 1, либо к(х,у) = 3d? ч = 1, либо к(х,у) = — 3d? ч = 1. Второй и третий случай невозможны, иначе d(x,y) = ±2/3. В первом случае d(x,y) = 2, это означает, что х и у, вершины степени 1, соединены двумя ребрами. Итак, номера і и j — номера вершин степени 1, образующих усы. Теперь надо найти вершину степени 3, смежную вершинам усов і и j. Кривизна на парс вершин — і и смежной с ней вершине степени 3, по формуле из Следствия 1, равна 2/3. Чтобы найти эту вершину найдем в і-строке элементы, равные 2/3. Кривизне, равной 2/3, соответствует вершина степени 3, расстояние до которой от вершины і равно 1 ребру, либо вершины степени 1, расстояние до которых от вершины і равно 3. Для усов і и j такая вершина степени 1 единственна, поэтому надо отличить вершину степени 1 от вершины степени 3. По предположению, дерево G имеет не менее двух вершин степени 3, поэтому существует еще хотя бы одна вершина степени 3, смежная с данной. Следовательно, в столбце, соответствующем вершине степени три, есть отрицательные числа (как минимум одно, равное —2/3). Таким образом, определили номер (пусть т) вершины степени 3, соседней с вершинами і и j. Для удобства отметим в матрице столбцы и строки, содержащие элементы к , kji7 кіті кті, kjmj kmjj то есть соответствующие вершинам і, j, т.

Далее, рассмотрим вершину степени 3, соседнюю ст. Обозначим ее — /. Найдем соседние вершины с вершиной /. Всего таких вершин три. Одна из них — это вершина т, возможны три варианта: обе оставшиеся смежные вершины степени 1; обе оставшиеся вершины степени 3; одна из оставшихся вершин степени 1, другая — степени 3. В первом случае — это дерево с четырьмя вершинами степени 1 и двумя вершинами степени 3. Этому случаю соответствует два элемента 2/3 в строке с номером / и матрица 5x5.

Если в строке с номером / содержатся ровно два элемента —2/3, то реализовался третий случай. В этом случае, ищем в строке с номером / кривизну, равную 2/3 — это кривизна на паре вершин — данной вершине / и соседней с ней вершине степени 1, и кривизну, равную —2/3 и стоящую в непомеченном столбце, — это кривизна на паре вершин — вершине / и соседней вершине степени 3. Такие элементы в строке / единственны. Действительно, посмотрим чему может равняться количество ребер п между вершинами (одна из которых /), для которых кривизна равна 2/3. Поскольку deg/ = 3, то применимы 2 и 3 формулы из следствия 1, то есть 2/3 = ±(2/3)п, следовательно, п = ±1. Случай п = — 1 невозможен, следовательно, кривизна, равная 2/3, достигается на вершине степени 1, смежной с /. Мы рассматривали случай, когда у вершины / смежная вершина степени 1 единственная, поэтому соответствие смежной с / вершины степени 1 и элемента 2/3 в матрице, стоящего в /-ой строке, определено однозначно. Аналогично, посмотрим чему может равняться количество ребер между вершинами (одна из которых /), для которых кривизна равна —2/3. Поскольку deg/ = 3, то —2/3 = ±(2/3)п. Снова получаем п = 1, то есть это вершины, смежные с / и имеющие степень 3. В нашем случае таких вершин две, которым соответствуют два равных элемента —2/3 в /-ой строке матрицы. Один из этих элементов стоит в помеченном столбце, поскольку одной из смежных с / вершин степени 3 является т. Следовательно, третья смежная с / вершина / устанавливается однозначно.

Если в строке с номером / найдутся три элемента —2/3, то реализовался второй случай. В этом случае в строке / один из элементов —2/3 стоит в помеченном столбце, а оставшиеся два соответствуют кривизнам между вершиной / и двумя другими смежными с ней вершинами 1\ и І2 степени 3. Поэтому дерево восстанавливается с точностью до перестановки поддеревьев, начинающихся в вершинах 1\ и І2- Помечаем строки и столбцы, в которых стоят элементы матрицы с номерами, содержащими один индекс — смежную вершину с /, второй — один из ранее установленных. Далее, для поддеревьев, начинающихся с вершины степени 3, смежной с / (во втором случае это вершины 1\ и /2, в третьем — / ), повторяем рассуждения — находим смежные вершины и вычеркиваем элементы, соответствующие кривизнам между каждой смежной вершиной и всеми предыдущими вершинами. Делаем это до тех пор, пока все столбцы и строки не будут помечены.Q

Кривизны Риччи для метрических пространств со случайным блужданием

Теперь перегруппируем слагаемые и перейдем от суммирования по ребрам к суммированию по вершинам, при этом слагаемые из выражения для кривизны пары (ж, у) распределим по двум суммам: V к(х,у)=у[ ( 1 + \ Vdegrr degy x y:x,y&V хуЄЕ \ degx-1 , , degy-1 , , у d{x,Xi) ул d{y,yj) f J НРСГ or ЛІТ in ( J Y degx d(x,y) -f degyd{x,y) Рассмотрим все возможные кривизны, в которых есть слагаемые, зависящие от вершины х. Всего их deg(ir). Продолжаем преобразования: і і/:і,уУ xGV Y v- (d(x,Xi) d(x,Xj) degrr I d(x, Xj) d(x,Xi Для каждого слагаемого вида ,.-х,Хг + г,ж аЛ применим оценку а+- 2. Каждой вершине v соответствуют С различных комбинаций пар ребер, смежных с этой вершиной. Следовательно, количество слагаемых вида а + - равно С\ . Таким образом, имеем:

Для графов выполняется равенство: ydegx = l2\E\J где i? — количество ребер. Для деревьев имеем: degrr = 2\Е\ = 2(vol(G) - 1) жЄУ Из этого равенства имеем: Y к(х,у) 2vol(G) -2(vol(G) - 1) 2 Ж г/:ж,г/ЄУ Следствие 3 доказано. 2.6 Оценка кривизны Риччи Для формулировки основной теоремы данного раздела введем новое обозначение: U(x) := tek?) z xK d(zix), г&еК = +1! если d(z,x) = miiv d( ,i;), и k z = -1 для остальных v х. В частности, если deg(:r) = 1, [/(ж) = і(ж, х ), где ж ж . Теорема 12. (Рублева О.В., [1.3]) Пусть G = (V}E) — произвольное дерево, ио — весовая функция, d — функция, измеряющая вес пути между вершинами дерева. Тогда кривизну Риччи на любой паре вершин дерева G, не являющегося, отрезком, можно оценить сверху и снизу так: причем эти оценки являются точными. Для дерева G, являющегося отрезком ху, кривизна к(х,у) = 2. Доказательство. Рассмотрим сначала частный случай дерева — отрезок ху. В этом случае применим формулу для грубой кривизны Риччи (коэффициенты kz из определения выше): к[х у) = шш (шх) k d[z х) + ш Е fe а(г-у) ) z y В данном примере deg(:r) = deg(y) = 1, кх = ку = +1, получаем: ( ,у) = т r( d(x,y) + d(y,x) ) =2 d(:r,?/)v Оценка сверху. Докажем, что к(х,у) 1 для любых двух вершин х,у Є V. Рассмотрим общую формулу: к(х у) = dih) (шх) - d ) + щи Е » «к , у) ) , z-y Рассмотрим слагаемое de л Х ж -г d(z, ж). Заметим, что в этой сумме все слагаемые, кроме одного, отрицательные, поэтому все слагаемое принимает наибольшее значение, когда знаменатель deg(:r) наименьший из всех возможных, т.е. deg(:r) = 1, и, соответственно, в числителе стоит единственное положительное слагаемое, т.е. к(х,у) — r( d(zi,x) + d(z2,y) d{x,y)\ Точки Z\ и %2 лежат на пути ху и являются смежными с точками, соответственно, х и у, поэтому справедливо неравенство: d(x,y) d(x,zi) + d(z2,y), причем равенство достигается, когда Z\ = z и ж, z\,y — последовательные точки пути ху. Поэтому имеем: Нх,„) рУ\ 1. d{x,y) Оценка снизу. Докажем, что в сделанных выше обозначениях к(х,у) diiS(G)(2mi v( W)). Рассмотрим снова общую формулу для кривизны Риччи: Из определения функции U(x) справедлива следующая оценка: U(x) del(x) Х ж kz d(x,y). Поставим ее в цепочку неравенств: (2 »») с1йыст(2 иС») 1 /„ . ,„, ,Л 1 d(x,y)\ VGV J diam(G) Точность оценок. Пусть G — дерево с постоянной весовой функцией. Оценка снизу d(x,y) diam(G) ( minvev(U(v))) достигается и совпадает с формулой из теоремы 1 для вершин дерева G степени 1, расстояние между которыми равно diam(G). Оценка сверху к(х,у) 1 достигается и совпадает с оценкой из теоремы 1 для вершин из усов взвешенных деревьев с постоянной весовой функцией, равной 1 на каждом ребре.

Оценка суммы кривизн Риччи на парах смежных вершин дерева

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

Определение. Взвешенным графом называется пара Q = (G,u;), где G = (V}E) — связный граф, а ш: Е — Ш+ — функция, которая каждому ребру графа G ставит в соответствие неотрицательное вещественное число. Эту функцию называют весовой функцией.

Для каждого пути 7 и каждого подграфа Н во взвешенном графе Q определены их веса о;(7) и ио{Н) соответственно, равные сумме весов всех входящих в них ребер. Это позволяет превратить множество вершин связного взвешенного графа Q в псвдометрическое пространство, положив расстояние между вершинами графа Q равным наименьшему возможному весу соединяющего их в Q пути. Так определенную функцию расстояния обозначим через dw и назовем расстоянием, порожденным весовой функцией UJ. Доказательство аксиом псевдометрического пространства следует непосредственно из определения функции dw.

Определение. Конечное метрическое пространство Л4 = (М, р) называется аддитивным, если существует взвешенное дерево Q = (G,UJ), G = (V, Е)} такое что dG С М С У, и метрика р совпадает с ограничением на М метрики dw. Дерево Q в этом случае называется порождающим для Л4.

Критерием аддитивности пространства является следующее известное правило, называемое правилом четырех точек. Теорема 3. ([5]) Псевдометрическое пространство Л4 = (М,р) аддитивно, если и только если для любых четырех точек р{, pj, р\ , Pi из М величины p(Pi,Pj)+p(j k,Pi), p(Pi,Pk)+p(Pj,Pi), p(Pi,Pi)+p(Pj,Pk) являются длинами сторон некоторого равнобедренного треугольника с основанием, не превосходящим боковой стороны. В работах [15, 17] доказана единственность порождающего дерева с ребер ненулевого веса, называемого невырожденным. Теорема 4. ([15} 17\) Если ограничиться рассмотрением невырожденных деревьев, то порождающее дерево аддитивного метрического пространства единственно. Следующий результат, сформулированный и доказанный в работе [1], полностью решает задачу о минимальных заполнениях аддитивных пространств. Теорема 5. ( [1]) Минимальными заполнениями аддитивного псевдометрического пространства являются его порождающие деревья и только они.

Неаддитивным пространством является, например, четырехточечное пространство (М, р) такое, что три его точки в данной метрике образуют на плоскости треугольник со сторонами 2, 3, 4, а четвертая точка лежит в центре описанной окружности. Обозначим центр описанной окружности — р\7 а остальные точки этого пространства — Р2,Рз,Р4 так, что p(pi,pi) = г для і = 2,3,4, ар(р2,Рз) = 2, Р{Р2,,РА) = 4, Р(Р2,РА) = 3. Имеем p(PhP2)+ Р(РЗ,РА) = Г + 4, p(PhPs) + p{P2iPi) = г + 3, РІРІІРА) + РІР2,Р:І) = г + 2. Для аддитивности пространства (М, р) необходимо равенство двух из трех величин. Но в данном примере это условие не выполняется, следовательно, пространство неаддитивно. Пример 2. Аддитивным пространством является, например, четырехточечное пространство (М, р), три точки которого образуют равносторонний треугольник со стороной 1, а расстояние от четвертой точки до вершин этого треугольника равно Порождающим деревом этого пространства будет звезда с вершиной в этой чет 1