Содержание к диссертации
Введение
1 V-компонентные поля в евклидовом и р-адическом пространствах 17
1.1 Общие определения и обозначения 17
1.2 (а — 3 /2d) -разложение 21
1.3 (4 — d) -разложение 29
1.4 Случай р-адического пространства 38
1.5 Сравнение (а — 3/2d)- и -разложений 40
1.6 Доказательство теорем о контрчленах 41
1.7 Вычисление вершинных частей фейнмановских графов . 57
2 V-компонентная фермионная иерархическая модель 70
2.1 Описание модели 70
2.2 Свойства преобразования ренормгруппы 76
2.3 Неподвижные точки преобразования РГ 82
3 V-компонентная бозонная иерархическая модель 88
3.1 Описание модели ., 88
3.2 е-разложения 92
3.3 Связь между фермионной и бозонной моделями 95
4 Задачи комбинаторной оптимизации в ультраметрических пространствах 98
4.1 Алгоритмы решения ЗКО 98
4.2 Средние значения оптимальных решений ЗКО 103
Заключение 114
Список литературы 117
- Вычисление вершинных частей фейнмановских графов
- Свойства преобразования ренормгруппы
- Связь между фермионной и бозонной моделями
- Средние значения оптимальных решений ЗКО
Введение к работе
Актуальность темы. Состояние систем с большим числом степеней свободы в статистической физике обычно описывается с помощью гиббсов-ских случайных полей. Преобразование ренормализационной группы (РГ) соответствует переходу от одного гиббсовского случайного поля к другому с помощью операций суммирования и нормировки. При этом речь идет о суммах сильно зависимых случайных величин. Теорию ренормализационной группы можно рассматривать как развитие классической теории предельных теорем для гиббсовских случайных полей. Распределения вероятностей, инвариантные относительно действия РГ, называются автомодельными распределениями вероятностей или неподвижными точками РГ.
Гауссовские автомодельные процессы, известные сейчас под названием дробного броуновского движения, впервые были рассмотрены А.Н. Колмогоровым. Связь автомодельных распределений с предельными теоремами теории вероятностей обсуждалась Ламперти и Р.Л Добрушиным. Проблемой автомодельных распределений занимались также Галлавоти, Йона-Лазинио, М. Розенблатт, Такку, Дайсон, Я.Г. Синай, П.М. Блехер, М.Д. Миссаров и другие.
Интерес к преобразованиям ренормгруппы и к автомодельным распределениям вероятностей объясняется тем, что данные объекты возникают в фундаментальных вопросах статистической физики и квантовой теории поля. Как известно, макроскопические характеристики разнообразных физических систем с бесконечным числом степеней свободы при изменении температуры или некоторых констант связи могут иметь особенности (фазовые переходы) Оказывается, состояние таких систем в критической точке определяется автомодельными распределениями вероятностей. Метод ренормализационной группы в теории критических явлений был создан Вильсоном, Кадановым, Фишером и другими. Данный метод позволяет вычислять критические показатели, характеризующие поведение систем в критической точке
ЗІ РОС. НАЦИОНАЛЬНАЯ I
БИБЛИОТЕКА |
Диссертация посвящена исследованию преобразования ренормализаци-оной группы в различных ЛГ-компонентных моделях статистической физики. Рассматриваемые случайные поля определены в евклидовом или р-адическом пространстве или на иерархической решетке, являющейся дискретной версией р-адического пространства.
Иерархические модели были предложены Ф Дайсоном. Большой вклад в теорию РГ в иерархических моделях внесли ГТ М. Блехер и Я Г Синай. Первые р-адические модели математической физики появились в работах В С. Владимирова и И.В. Воловича Связь между иерархическими и р-адическими моделями была установлена в работах М.Д. Миссарова и Э Ю. Лернера. Важным достоинством р-адических моделей является то, что сложные проблемы современной математической физики получают точное решение. Например, многие проблемы теории РГ в четырехком-понентной фермионной иерархической модели получили явное решение
Еще один класс задач, рассмотренных в диссертационной работе, представлен стохастическими версиями известных задач комбинаторной оптимизации (задача коммивояжера, задача о минимальном паросочетании и задача о минимальном остовном дереве) в р-адических пространствах. Идеи, близкие к идеям релормгруплы, позволили явно вычислить математические ожидания оптимальных решений и исследовать их асимптотическое поведение.
Цель работы - исследовать преобразование ренормализационной группы в различных ./V-компонентных моделях статистической физики; исследовать стохастические задачи комбинаторной оптимизации (ЗКО) в ультраметрических пространствах.
Направления исследования.
1. Распространить формализм проеционных гамильтонианов на случай 0(]\Г)-симметричных ./V-компонентных бозонных случайных полей, заданных как в евклидовом, так и в р-адическом пространствах. Вычислить критические показатели до второго порядка теории возмущений
2 Исследовать 2Лг-компонентную фермионную иерархическую модель.
-
Исследовать ЛГ-компонентную бозонную иерархическую модель.
-
Для стохастических задач комбинаторной оптимизации в d-мерном р адическом пространстве вычислить математические ожидания сумм длин ребер в оптимальных решениях, а также исследовать их асимптотику при п — оо, где п - число точек
Методы исследования. Для исследования преобразования РГ Вильсона в случае JV-компонентных 0(]У)-симметричных случайных полей в евклидовом и р-адическом пространствах используется техника фейнма-новских диаграмм и перенормировок, а для описания неподвижных точек РГ и критических показателей строятся формальные ряды теории возмущений 2.Л/-компонентная фермионная иерархическая модель исследуется с привлечением понятий из суперанализа и теории динамических систем. Стохастические задачи комбинаторной оптимизации исследуются с помощью комбинаторных рассуждений с привлечением сведений из теории вероятностей и математического анализа.
Научная новизна. Формализм перенормированных гамильтонианов распространен автором на случай TV-компонентных 0(]У)-симметричных полей, заданных как в евклидовом, так и в р-адическом пространствах. Получены формулы для симметрийных коэффициентов фейнмановских графов, доказаны теоремы о контрчленах, построены ряды теории возмущений для неподвижных гамильтонианов РГ и критических показателей.
Критические показатели в евклидовой и р-адической теориях вычислены в рамках (а — Ъ/2й)- и (4—й)-разложений. Проведен их сравнительный анализ.
Автором исследовано преобразование РГ для 2ІУ-компонентньіх фер-мионных случайных полей, заданных на иерархической решетке. Ряд наблюдений, полученных для данной модели, не имеет аналогов в других известных N компонентных моделях статистической физики Например, преобразование РГ удалось представить в виде конечномерного преобра-
зования в пространстве констант связи, а для определения неподвижных точек предложена система алгебраических уравнений.
Автором установлена интересная связь между преобразованиями РГ в бозонной и фермиониой 2ЛГ-компонентных моделях. Оказалось, что одно преобразование переходит в другое при формальной замене N на — N.
Удалось явно вычислить математические ожидания оптимальных решений стохастических задач комбинаторной оптимизации в р-адическом пространстве, а также исследовать их асимптототическое поведение
Практическая ценность результатов. Результаты, полученные в работе, носят в основном теоретический характер.
Развитый в диссертации формализм проекционных гамильтонианов позволяет вычислять критические показатели для iV-компонентных 0(N)-симметричных случайных полей, пользуясь (а - 3/2с)-разложением, либо (4 - с2)-разложением.
Строгие результаты, полученные для фермиониой и бозонной иерархических моделей позволяют глубже понять динамику преобразования РГ. Наблюдения, полученные для этих моделей могут быть источником гипотез для евклидовых моделей математической физики.
Публикации. Основные результаты диссертации опубликованы в 11 работах. Две работы приняты к печати.
Апробация и внедрение результатов. Результаты работы докладывались и обсуждались на всероссийских и международных конференциях: III Всероссийский симпозиум по прикладной и промышленной математике, секция «Вероятность и статистика» (Сочи, октябрь 2002), Международная конференция по р-адической математической физике (Москва, 1-5 октября 2003), XI Всероссийская школа-коллоквиум по стохастическим методам (Сочи, сентябрь 2004), VI Всероссийский симпозиум по прикладной и промышленной математике, секция «Вероятность и статистика» (Санкт-Петербург, май 2005), Вторая международная конференция по р-адической математической физике (Белград, Сербия и Черногория, сентябрь 2005).
Структура и объем диссертации: Диссертационная работа состоит из введения, четырех глав, заключения и библиографического списка, содержащего 48 наименований. Работа изложена на 123 листах и содержит 1 рисунок.
Вычисление вершинных частей фейнмановских графов
Докажем, что приведенный алгоритм находит оптимальное решение задачи МП в ультраметрическом пространстве.
Для этого достаточно доказать, что существует оптимальное решение G, содержащее пару (жі,ж2) обладающую свойством (4,3). Зафиксируем произвольное оптимальное решение G\% и предположим, что G\ не содержит данную пару.
Возможны два случая: либо в разбиении G\ вершинам х\ и х2 соответствуют парные вершины у\ и г/2, либо одна из этих точек (предположим, что это точка жі), вовсе не имеет пары, что возможно в случае нечетного числа точек. В случае, если вершина х\ в решении G\ не имеет пары, а точке Х2 соответствует парная вершина г/, то из G\ переходим к G заменой пары (х2, у) на пару (rci, х2). Очевидно, полученное решение G также является МП и содержит пару (агі,Ж2). Если же вершины х\ и х2 в разбиении G\ спарены, соответственно, с вершинами у\ и j/2, то переходим к графу G заменой ребер (жь уі), (жг, у%) В силу леммы 4.1 данная замена не ухудшает сумму длин ребер. Алгоритм решения задачи МОД Пусть имеется множество X, состоящее из п точек. Выберем из него произвольную точку х\ и найдем для нее точку Х2 X, для которой р(х\,Х2) = тіш р{х\,у). Зафиксируем ребро (аг жг) в решении и ис уХ, уфхх ключим из дальнейшего рассмотрения точку х\. Затем применим данную процедуру к п — 1 точкам в Х\{х\}, и так далее. Когда останется только одна точка, зафиксированные ребра будут образовывать граф, являющийся, как легко видеть, остовным деревом. Докажем, что данное остовное дерево является оптимальным решением. Будем доказывать по индукции: предположим, что для \Х\ = п — 1 утверждение выполнено (что в случае двух точек очевидно), докажем для X1 = п. Решение G, построенное по алгоритму, является объединением ребра ( 1,3) и полученного по тому же алгоритму минимального остовного дерева G для п — 1 точек множества Х\{х\}. Следовательно для доказательства утверждения достаточно проверить, что существует минимальное остовное дерево С?ь являющееся объединением ребра (Х\,Х2) и некоторого минимального остовного дерева G" для п — 1 точек множества Х\{жі}. Действительно, если бы такое МОД G\ существовало, то G также было бы МОД. Сначала докажем, что существует оптимальное решение G i, содержащее ребро ( 1,3), Для которого p{xi,X2) = min p(xi,y). Пусть Сз - произвольное минимальное остовное дерево, и пусть В С?з точки х\,Х2 не соединены ребром. Так как G$ - дерево, то существует единственный путь, соединяющий точки х\,х2- соединим точки Жі,Ж2 в Gz ребром, тем самым получив единственный цикл, который содержит ребро (жі, X2J- Удалим из данного цикла ребро (х±, у), отличное от ребра (х\, х2). Легко видеть, что полученный граф G2 является также остовным деревом, сумма длин ребер которого не превышает сумму длин ребер G3, следовательно, является минимальным остовным деревом. Итак, существует оптимальное решение С?2, содержащее ребро (жь г)-Теперь необходимо показать, что существует оптимальное решение G\, в котором содержится ребро (хі,Ж2), и не содержится других ребер вида Для этого покажем, что если в решении G2, содержащем ребро (xi, гг), содержится ребро (хі,у),у ф Х2, то ребро (жі, у) может быть заменено на ребро (х2, у), и полученный граф С?4 также будет являться минимальным остовным деревом. Легко видеть, что граф G$ является допустимым остовным деревом, и что сумма длин ребер дерева G не превышает суммы длин ребер Gi- Последнее следует из того, что в ультраметрическом пространстве из неравенства p(xi,X2) p{xi,y) следует равенство p(xi,y) = р(х2,у). Заменив в (?2 все ребра вида (жі, у), у ф Жг на ребра (а?2, у), мы получаем оптимальное решение G\, содержащее ребро (xj, х%), и не содержащее других ребер вида (жь у). Очевидно, что данное дерево Gi является объединением ребра (х\} ж2) и некоторого минимального остовного дерева G" для п — 1 точек множества Х\{жі}. Следовательно для \Х\ = п утверждение доказано. Алгоритм решения ЗК Замечание: данный алгоритм известен, как "метод ближайшего города". Пусть имеется множество X, состоящее из п точек. Выберем начальной точкой маршрута любую точку ж і Є X. Найдем для х\ точку х% для которой р(жі,ж2) = min р(х\,у). уЄХ, уфхі Зафиксируем ребро (х\, ж г) и исключим из дальнейшего рассмотрения точку х\. Затем повторим процедуру для п —1 оставшихся точек Х\{жі}, а именно найдем точку ж3, такую что р(ж2, ж3) = min р(ха, у), зафик-сируем ребро (жг,жз)і исключим точку Ж2, и так далее. В итоге получим путь х\ — хп. Добавлением ребра (ж„,жі), получим маршрут Докажем, что указанный алгоритм позволяет найти оптимальное решение задачи ЗК в ультраметрическом пространстве.
Свойства преобразования ренормгруппы
В главе 1 формализм перенормированных проекционных гамильтонианов распространен на случай iV-компонентных 0(.т/)-симметричных случай ных полей, заданных в евклидовом или р-адическом пространстве. Рас смотрены два метода разложений - метод (а — S/2d)-разложений и ме тод (4 — -разложений. Для обоих типов разложений доказаны теоремы о контрчленах. Преобразование РГ на многообразии перенормированных проекционных гамильтонианов записано в виде дифференциального опе ратора. Получены формулы для вычисления неподвижной точки РГ и критических показателей v и г} в виде формальных степенных рядов по параметру разложения.
Полученные ответы для критических показателей в евклидовом случае в рамках (4 — гі)-разложения совпали с аналогичными ответами, полученными на основе формализма уравнений Каллана-Симанзика [48]. Сравнение (4 — d) и (а — 3/2rf)-разложений до второго порядка теории возмущений показывает, что при а — 2 + d—77, где rj - аномальная размерность, ответы для критического показателя v в обоих типах разложения совпадают. Сравнение ответов для евклидового и р-адического пространств показывает, что во втором порядке теории возмущений существует следующая связь между ответами: ответы совпадают вплоть до замены функции Т(х) в евклидовом случае на ее р-адический аналог fp(x) а константы Эйлера 7 - на — In р.
В главе 2 исследовано преобразование РГ в 2ІУ-компонентной фер-мионной иерархической модели. Данное преобразование явно вычислено в iV-мерном проективном пространстве коэффициентов связи. Доказана его симметрия относительно преобразования Фурье. Вычислено его обратное преобразование. Для случая а — 1 для фермионных случайных полей доказан аналог центральной предельной теоремы.
Показано, что неподвижные точки РГ могут быть определены, исходя из системы N алгебраических уравнений с N неизвестными. Оказалось, что при N 1 данная система имеет несколько нетривиальных решений. При N = S количество нетривиальных решений зависит от а. В главе 3 мы исследовали преобразование РГ в ЛГ-компонентной бо-зонной иерархической модели. Многие свойства преобразования РГ в этой модели аналогичны свойствам преобразования РГ в фермионной иерархической модели. Нетривиальные неподвижные точки преобразования РГ можно искать по теории бифуркаций от гауссовской неподвижной точки. При этом можно пользоваться (а — 3/2)-разложением и (4 — d)-разложением. Ответы для неподвижных точек в случае d — 3, полученные до второго порядка теории возмущений обоими типами разложений, имеют одинаковую асимптотику по параметру р, где р - диаметр элементарного блока иерархической решетки. Данный факт говорит в пользу того, что оба разложения описывают одну и ту же неподвижную точку в размерности d = 3.
Показано, что если формально определить преобразование РГ в пространстве констант связи, то преобразование РГ в 2ІУ-компонентной бо-зонной иерархической модели при замене N на — N переходит в преобразование РГ в 2і\Г-компонентной фермионной иерархической модели.
В главе 4 мы исследовали некоторые задачи комбинаторной оптимизации, в которых необходимо соединить ребрами случайно выбранные точки в ультраметрическом пространстве так, чтобы сумма длин ребер была наименьшей. Рассмотрены три известные задачи: задача коммивояжера, задача о минимальном паросочетании и задача о минимальном остовном дереве. Для этих задач показано, что в ультраметрическом пространстве "жадные" алгоритмы дают оптимальное решение. Для случая р-адического пространства вычислены средние значения сумм длин ребер в оптимальных решениях, а также изучена их асимптотика при большом количестве точек п.
Связь между фермионной и бозонной моделями
Заметим, что гамильтониан 2 o,a,R является гауссовской неподвижной точкой оператора Rx,a, то есть задает гауссовское случайное поле, инвариантное относительно преобразования РГ.
Для подсчета возникающих функциональных интегралов будем пользоваться техникой фейнмановских диаграмм.
Пусть G - некоторый связный фейнмановский граф, построенный на п вершинах, п - натуральное число, и пусть все эти вершины пронумерованы числами от 1 до п. Степенью вершины называется количество линий, выходящих из данной вершины. Обозначим степень вершины с номером v через 2kv (считаем, что это всегда четное число). Пусть все линии, выходящие из вершины v} пронумерованы числами от 1 до 2kv.
Предположим, что граф G имеет 2к внешних линий. Каждая внешняя линия определяется набором (t),m), где v - номер вершины, из которой выходит линия, т - ее порядковый номер среди линий данной вершины. Отождествим каждую внутреннюю линию с четверкой {v\,m\yV2ifTfH)-При этом считаем, что внутренняя линия (vi,mi,V2,m2) соединяет вершины v\, vi и имеет для вершины v\ номер mi, а для вершины v% номер
ГП2- где суммирование ведется по всем связным невакуумным фейнмановским графам (7, построенным на п вершинах, причем количество линий, выходящих из вершины с номером v равно 2kv, v = 1,... ,п. Интегрирование ведется по подпространству импульсов gfJJ, M.d (по одной переменной-импульсу на каждую внешнюю линию графа), для которых выполняется закон сохранения импульсов:
Как и в случае однокомпонентной модели, анализ дифференциала РГ на гауссовской ветви неподвижных точек показывает, что значение а — 3/2d является бифуркационным значением. Дальнейшие разложения будут строиться по параметру є = а — 3/2d. Поскольку фейнмановские амплитуды, задающие коэффициентные функции проекционных гамильтонианов вида (1.7), расходятся при є — 0, то для их определения в точке є = 0 нам понадобится процедура перенормировки. Наиболее естественной процедурой перенормировки является процедура аналитической перенорм ировки.
Пусть A.R cio) - операция аналитической перенормировки [44] по параметру є фейнмановской амплитуды Tcio), соответствующей графу различным разбиениям графа G на подграфы Gj,..., Gr, такие что множество вершин каждого подграфа Gj совпадает с Vj, G\G\,..., Gr граф, получаемый из G путем "стягивания" подграфов G\y..., Gr, 0(Gj) - вершинные части графов Gj. Известно [44], что при d, не кратном 4, вершинная часть 0(G) является полиномом от є-1, отличным от 0 только в следующих случаях: Граф G состоит из одной вершины и не имеет внутренних линий. В этом случае 0(G) = 1. Граф G одночастично неприводим, степени всех вершин равны 4 и число внешних линий равно 4. В этом случае 0(G) - полином от є 1 без свободного члена. Граф G одночастично неприводим, степень одной вершины равна 2, степени остальных вершин равны 4, а число внешних линий равно 2. В этом случае, как и в предыдущем, 0(G) - полином от є-1 без свободного члена. Вершинные части 0(G) подбираются таким образом, чтобы величина A.R.J:G(Q) не имела полюса в точке є = 0. Это условие и формула (1.8) фактически задают рекурсивный алгоритм вычисления вершинных частей.
Средние значения оптимальных решений ЗКО
Пусть имеется множество X, состоящее из п точек. Выберем из этого множества такие точки х\, х% что и соединим эти точки в пару. Из оставшихся п — 2 точек снова найдем две ближайшие точки и соединим их в пару, и так далее. Когда в множестве X число неспаренных точек станет равно 0 или 1, получаем решение исходной задачи.
Докажем, что приведенный алгоритм находит оптимальное решение задачи МП в ультраметрическом пространстве. Для этого достаточно доказать, что существует оптимальное решение G, содержащее пару (жі,ж2) обладающую свойством (4,3). Зафиксируем произвольное оптимальное решение G\% и предположим, что G\ не содержит данную пару. Возможны два случая: либо в разбиении G\ вершинам х\ и х2 соответствуют парные вершины у\ и г/2, либо одна из этих точек (предположим, что это точка жі), вовсе не имеет пары, что возможно в случае нечетного числа точек. В случае, если вершина х\ в решении G\ не имеет пары, а точке Х2 соответствует парная вершина г/, то из G\ переходим к G заменой пары (х2, у) на пару (rci, х2). Очевидно, полученное решение G также является МП и содержит пару (агі,Ж2). Если же вершины х\ и х2 в разбиении G\ спарены, соответственно, с вершинами у\ и j/2, то переходим к графу G заменой ребер (жь уі), (жг, у%) на ребра (жьж2),(уъЫ Пусть имеется множество X, состоящее из п точек. Выберем из него произвольную точку х\ и найдем для нее точку Х2 X, для которой р(х\,Х2) = тіш р{х\,у). Зафиксируем ребро (аг жг) в решении и исключим из дальнейшего рассмотрения точку х\. Затем применим данную процедуру к п — 1 точкам в Х\{х\}, и так далее. Когда останется только одна точка, зафиксированные ребра будут образовывать граф, являю-щийся, как легко видеть, остовным деревом. Докажем, что данное остовное дерево является оптимальным решением. Будем доказывать по индукции: предположим, что для \Х\ = п — 1 утверждение выполнено (что в случае двух точек очевидно), докажем для X1 = п. Решение G, построенное по алгоритму, является объединением ребра ( 1,3) и полученного по тому же алгоритму минимального остовного дерева G для п — 1 точек множества Х\{х\}. Следовательно для доказательства утверждения достаточно проверить, что существует минимальное остовное дерево С?ь являющееся объединением ребра (Х\,Х2) и некоторого минимального остовного дерева G" для п — 1 точек множества Х\{жі}. Действительно, если бы такое МОД G\ существовало, то G также было бы МОД. Сначала докажем, что существует оптимальное решение G i, содержащее ребро ( 1,3), Для которого p{xi,X2) = min p(xi,y). Пусть Сз - произвольное минимальное остовное дерево, и пусть В С?з точки х\,Х2 не соединены ребром. Так как G$ - дерево, то существует Gz ребром, тем самым получив единственный цикл, который содержит ребро (жі, X2J- Удалим из данного цикла ребро (х±, у), отличное от ребра (х\, х2). Легко видеть, что полученный граф G2 является также остовным деревом, сумма длин ребер которого не превышает сумму длин ребер G3, следовательно, является минимальным остовным деревом. Итак, существует оптимальное решение С?2, содержащее ребро (жь г)-Теперь необходимо показать, что существует оптимальное решение G\, в котором содержится ребро (хі,Ж2), и не содержится других ребер вида Для этого покажем, что если в решении G2, содержащем ребро (xi, гг), содержится ребро (хі,у),у ф Х2, то ребро (жі, у) может быть заменено на ребро (х2, у), и полученный граф С?4 также будет являться минимальным остовным деревом. Легко видеть, что граф G$ является допустимым остовным деревом, и что сумма длин ребер дерева G не превышает суммы длин ребер Gi- Последнее следует из того, что в ультраметрическом пространстве из неравенства p(xi,X2) p{xi,y) следует равенство p(xi,y) = р(х2,у). Заменив в (?2 все ребра вида (жі, у), у ф Жг на ребра (а?2, у), мы получаем оптимальное решение G\, содержащее ребро (xj, х%), и не содержащее других ребер вида (жь у). Очевидно, что данное дерево Gi является объединением ребра (х\} ж2) и некоторого минимального остовного дерева G" для п — 1 точек множества Х\{жі}. Следовательно для \Х\ = п утверждение доказано. Замечание: данный алгоритм известен, как "метод ближайшего города". Пусть имеется множество X, состоящее из п точек. Выберем начальной точкой маршрута любую точку ж і Є Зафиксируем ребро (х\, ж г) и исключим из дальнейшего рассмотрения точку х\. Затем повторим процедуру для п —1 оставшихся точек Х\{жі}, а именно найдем точку ж3, такую что р(ж2, ж3) = min р(ха, у), зафик-сируем ребро (жг,жз)і исключим точку Ж2, и так далее. В итоге получим путь х\ — Ж2— хп. Добавлением ребра (ж„,жі), получим маршрут Докажем, что указанный алгоритм позволяет найти оптимальное решение задачи ЗК в ультраметрическом пространстве.
