Содержание к диссертации
Введение
Глава 1. Проблемы размещения информации и маршрутизации в научно-образовательных сетях 6
1.1. Российские научно-образовательные сети 6
1.2. Проблема оптимального размещения информационных ресурсов в научно-образовательных сетях 9
1.3. Принципы маршрутизации в телекоммуникационных сетях 12
1.4. Постановка задачи 26
Глава 2 Анализ методов описаний топологий телекоммуникационных сетей с точки зрения их использования для оптимального размещения информационных ресурсов 28
2.1 Основные топологические характеристики сетей 28
2.2 Характеристики типовых топологий сетей 31
2.3 Методы построения топологий 37
2.4 Методы размещения информационных ресурсов 45
2.5 Выводы 52
Глава 3 Методы размещения информационных ресурсов в телекоммуникационных образовательных сетях 54
3.1 Оптимальное размещение информационных ресурсов в сети 54
3.2 Выбор критерия оптимизации 55
3.3 Оптимальное размещение информационного ресурса в сети 57
3.4 Оптимальное размещение множества информационных ресурсов в сети 60
3.5 Оптимальное размещение информационных ресурсов с копированием 62
3.6 Обобщение задачи о назначениях 64
3.7 Минимизация суммарного потока на заданном множестве ребер сети за счет размещения информационных ресурсов 71
3.8 Определение пропускных способностей каналов связи сбалансированных сетей 82
3.9. Выводы 83
Глава 4. Методы корректировки маршрутов в телекоммуникационных сетях 84
4.1. Задача поиска кратчайших маршрутов 84
4.2. Алгоритм уменьшения размерности задачи поиска кратчайших путей 91
4.3. Алгоритм парных переходов 109
4.4. Выводы 131
Глава 5 Экспериментальная проверка предлагаемых решений 132
5.1. Алгоритмы размещения информационных ресурсов 132
5.2. Имитационная система для проверки алгоритмов поиска кратчайших путей в графе 140
Заключение 146
Список использованных источников 147
- Принципы маршрутизации в телекоммуникационных сетях
- Характеристики типовых топологий сетей
- Оптимальное размещение информационного ресурса в сети
- Алгоритм уменьшения размерности задачи поиска кратчайших путей
Введение к работе
Актуальность темы. Создание единой информационной сферы образования невозможно без формирования и поддержки ее телекоммуникационной инфраструктуры. Развитие научно образовательных сетей происходит во всех странах мира. В России в течение последних десяти лет уделяется существенное внимание созданию и развитию научно-образовательных телекоммуникационных сетей, основанных на Интернет-технологиях и имеющих выход в глобальный Интернет.
Основными российскими некоммерческими ІР-сетями,
специализирующихся на обслуживании организаций науки, образования, культуры и здравоохранения, являются сети RUNNET, RBnet, RELARN-IP, MSUnet и ряд других. Существующая межведомственная опорная сетевая структура обеспечивает техническую интеграцию всех научно-образовательных сетей, вне зависимости от их ведомственной принадлежности и предметной ориентации, в единую национальную компьютерную сеть науки и высшей школы Данная инфраструктура в настоящее время имеет точки присутствия в 55 субъектах Российской Федерации, использует ряд общих магистральных каналов, и интегрирована в глобальной Интернет-системе международных каналов, общая емкость которых в настоящий момент превышает 2 Гбит/с.
Ситуация в области применения научно-образовательных сетей выглядит сегодня следующим образом - чем более производительными и доступными становятся средства передачи данных, тем большее количество задач на них возлагается, что приводит к существенному увеличению нагрузок и, как следствие, относительному ухудшению их характеристик с точки зрения конечного пользователя. Подобная тенденция будет прослеживаться и в дальнейшем.
ния научно-
РОС: НАЦИОНАЛЬН«оі , БИБЛИОТЕК* СПет*я
Для повышения эффективност:
ІПОТЕКА >
образовательных сетей необходимо использовать также подходы при их построении, которые позволят сократить нагрузку на них и, следовательно, повысить эксплуатационные характеристики без использования дорогостоящей модернизаций линий связи и сетевого оборудования за счет минимизации информационных потоков, циркулирующих в сети.
В связи с этим в работе предлагается минимизировать суммарный поток во всех линиях связи сети за счет определения оптимальных мест размещения информационных ресурсов.
Кроме того, возможна организация ускоренной маршрутизации в сети, под которой понимается метод поиска оптимальных маршрутов для передачи информационных пакетов от узла - отправителя к узлу -получателю через составную телекоммуникационную сеть в условиях динамически меняющихся загрузок линий связи. Особую важность имеет эффективная маршрутизация сообщений в условиях отказов отдельных элементов сети, всплесков трафика и локальных перегрузок. Получение маршрутизатором новой маршрутной информации приводит к перерасчету кратчайших маршрутов между различными компонентами сети. При частом обновлении маршрутной информации важной также становится задача уменьшения трудоемкости расчета кратчайших путей.
Исходя из выше сказанного, можно сделать вывод об актуальности темы диссертационной работы.
В решение задачи анализа и синтеза сетей значительный вклад внесли отечественные и зарубежные ученые Альнах И.Н., Артамонов Г.Т., Брехов О.М., Васильев В.Н., Вишневский В.М., Гарсиа-Диас А., Зайченко Ю.П., Захаров Г.П., Ижванов Ю.Л., Клейнрок Л., Куракин Д.В., Мизин. И.А., Саксонов Е.А., Самойленко СИ., Тихонов А.Н., Филлипс Д., Ху Т., Янбых Г.Ф. и др.
Объект исследования. Объектом исследования являются научно-образовательные ЕР-сети.
' і 4
. і м» - Ч < .' ' *..!.
Предмет исследования. Исследуется влияние мест размещения информационных ресурсов в сетях на суммарный поток в сети. Рассмотрены методы ускоренной маршрутизации в сетях на основе использования разработанных в диссертации алгоритмов поиска кратчайших путей.
Цель исследования. Целью диссертационной работы является:
-
разработка алгоритмов, позволяющих уменьшить суммарный поток на всех линиях связи сети или на некотором подмножестве линий за счет оптимального распределения информационных ресурсов в узлах сети;
-
разработка способов повышения эффективности функционирования телекоммуникационных сетей, увеличения производительности маршрутизаторов путем разработки новых методов и алгоритмов поиска оптимальных маршрутов в телекоммуникационных сетях в условиях изменяющейся загрузки и реальной пропускной способности линий связи.
Задачи исследования Для достижения поставленных целей необходимо решить следующие задачи:
-
исследование существующих способов описания и построения топологий телекоммуникационных сетей, способов выбора мест размещения на них информационных ресурсов;
-
обоснование использования суммарного потока как критерия при оптимизации размещения информационных ресурсов;
-
размещение одного и множества информационных ресурсов в сети по критерию минимума суммарного потока без ограничений и при существовании количественных и структурных ограничений;
-
размещение информационных ресурсов при возможности их копирования;
-
размещение информационных ресурсов, минимизирующее суммарный поток на заданном подмножестве линий связи;
6) поиск оптимальных маршрутов при изменении значения метрики
линий связи, с учетом ее использования в дереве кратчайших путей.
Методы исследования. Для решения поставленных задач использован аппарат теории графов и сетей, теории вычислительных систем, теории дискретной оптимизации и математического программирования, теории матриц.
Научная новизна и положения, выносимые на защиту
Научная новизна состоит в следующем:
-
предложены модели и алгоритмы размещения информационных ресурсов в телекоммуникационных сетях по критерию минимума суммарного потока в линиях связи;
-
предложены модели и алгоритмы размещения информационных ресурсов в сетях по критерию минимума суммарного потока на произвольном подмножестве линий связи;
-
сформулирована и решена частная задача о назначениях, актуальная для распределенных баз данных и заключающаяся в распределении множества информационных ресурсов с учетом того, что каждый ресурс имеет строго фиксированное количество копий;
-
разработан алгоритм поиска оптимальных маршрутов в условиях изменяющейся метрики графа;
-
разработан алгоритм уменьшения разрядности задачи поиска кратчайших путей в графе в условиях изменения его метрики;
-
проведены доказательства правильности и получены оценки трудоемкости разработанных алгоритмов.
Достоверность Достоверность основных положений и полученных результатов диссертационной работы подтверждается математическими обоснованиями доказательствами, корректным использованием математического аппарата теории графов, теории вычислительных систем, теории дискретной оптимизации и математического программирования, теории матриц, результатами имитационного моделирования, апробацией
работы на ряде международных и всероссийских конференций.
Апробация результатов диссертации. Результаты данной работы докладывались на всероссийской научно - методической конференции «Телематика-2005» (Санкт-Петербург, 2005 г.), на всероссийских семинарах «Интернет-порталы: содержание и технологии» (Москва, 2003-2005 гг.), международных конференциях по дистанционному образованию (Москва, 1998-1999 г.г.).
Публикации. По теме диссертации опубликовано 5 печатных работ, в том числе 4 статьи и тезисы доклада.
Практическая значимость.
Результаты работы внедрены в ГНИИИТТ «Информика» (г.Москва) с целью повышения эффективности функционирования сети RUNNet.
Структура и объём диссертации. Диссертация состоит из введения, пяти глав и заключения и списка литературы. Диссертация содержит 155 страниц, список литературы состоит из 103 наименований.
Принципы маршрутизации в телекоммуникационных сетях
Важным фактором развития системы образования и науки является доступ образовательных учреждений к информационным ресурсам и современным видам сервиса глобальных телекоммуникационных компьютерных сетей. Создание единой информационной среды образования невозможно без формирования и поддержки ее телекоммуникационной инфраструктуры. В России в последнее время уделяется существенное внимание созданию и развитию научно - образовательных телекоммуникационных сетей, основанных на интернет-технологиях.
В России созданы и функционируют некоммерческие ІР-сети, специализирующиеся на обслуживании организаций науки и образования.
Сеть RUNNet. Крупнейшей научно-образовательной сетью России является сеть RUNNet (Russian University Network) - отраслевая телекоммуникационная сеть сферы образования. Сеть RUNNet была создана в 1991 г. в рамках государственной программы «Университеты России» как федеральная университетская компьютерная сеть России, т.е. ІР-сеть, объединяющая региональные сети, а также сети крупных научно-образовательных учреждений. Основные задачи RUNNet - формирование единого информационного пространства высшей школы России и его интеграция в мировое информационное сообщество.
Создание RUNNet началось со спутникового сегмента сети российских университетов, соединившего на первом этапе шесть регионов России через коммуникационные узлы на базе крупнейших университетов и представившего научно-образовательному сообществу условия доступа в Интернет и возможности работы с современными технологиями, которые в то время были недоступны в сетях коммерческих провайдеров Интернета. Реализуемые услуги - электронная почта, файловый обмен, доступ к распределенным базам данных, телеконференции. RUNNet первоначально планировалась в основном как университетская сеть. В настоящее время происходит смещение акцентов в деятельности сети на сферу общего среднего и начального профессионального образования. Во многих городах Российской Федерации, в которых имеются узлы сети RUNNet, существует собственная развитая опорная внутригородская телекоммуникационная инфраструктура, предназначенная для подключения к сети образовательных учреждений, а также организаций науки и культуры и здравоохранения. Точки опорной инфраструктуры находятся как в организациях, осуществляющих администрирование сети, так и в точках присутствия канальных телекоммуникационных операторов. Наиболее развита подобная инфраструктура в Москве и Санкт-Петербурге. Сетевая инфраструктура RUNNet в Москве и Санкт-Петербурге играет ключевую роль в работе всей сети образования. Она объединяет базовые узлы, в которых происходит подключения московских и петербургских организаций, региональных сетей (по междугородним наземным и спутниковым каналам), осуществляется обмен с другими интернет- провайдерами ( в точках Internet Exchange и путем прямых соединений), организован доступ к международному каналу. В Москве и Санкт-Петербурге созданы высокоскоростная опорная сеть на базе волоконно-оптических линий связи, в которой в качестве базовых используются технологии ATM (155 Мбит/с) и GigabitEthemet. RUNNet в настоящее время имеет прямой пиринг (связность на уровне прямых физических соединений) с научно-образовательными сетями RBnet, Relarn-IP, FREENet, MSUnet, Radio-MSU, UPnet и др. Уровень связности - 100 Мбит/с. RUNNet имеет прямую связность на физическом уровне более чем с 50 телекоммуникационными сетями общего пользования (сетями коммерческих интернет-провайдеров) и пиринг более чем со 100 телекоммуникационными сетями с использованием точек обмена трафиком MSK-IX, SPb-IX, NSK-IX на уровне 100 Мбит/с. Сеть RBnet. Сеть RBnet строилась в 1996-200 Іг.г. в рамках межведомственной программы «Создание национальной сети компьютерных телекоммуникаций для науки и высшей школы», проведенной Миннауки России, Минобразования России, РАН и РФФИ. Основная цель создания сети RBnet вытекает из ее названия - Russian Backbone Network, т.е. Российская Опорная сеть. Сеть обеспечивает внутри российскую связность некоммерческих IP- сетей различной ведомственной принадлежности и предметной ориентации путем создания единой транспортной инфраструктуры, охватывающей всю территорию страны и имеющей узлы, к которым подключаются региональные некоммерческие сети и отдельные организации. В настоящее время сеть RBnet совместно с партнерами охватывает свыше 50 российских регионов. Сеть FREEnet. Сеть FREEnet основана в 1991г. по инициативе Института органической химии им. Н.Д. Зелинского РАН. Сеть объединяет на добровольной основе академические компьютерные сети, организации РАН, университеты и вузы. Сеть FREEnet предоставляет пользователям сетевой и информационный сервис. Она имеет 14 региональных отделений в России и отделение в Республике Беларусь. Опорная сеть FREEnet использует высокопроизводительное маршрутизирующее оборудование и оптоволоконные каналы связи, обеспечивающие скорость передачи информации до 1 Гбит/с, сеть поддерживает протокол IPv6. Кроме этих трех некоммерческих сетей, имеющих точки присутствия в различных регионах России, можно отметить сети RELARN-IP, RUHER-Radio-MSU, RSSI, MSUnet, IlPnet, РОКСОН. Все перечисленные некоммерческие сети работают в настоящее время в тесном взаимодействии, которое заключается в обмене трафиком в узлах Internet Exchange, взаимном резервировании каналов связи, совместном использовании телекоммуникационных узлов для размещения оборудования, представлении услуг глобальной интернет-коннективности со стороны наиболее крупных сетей RUNNet и RBnet другим некоммерческим сетям.
Мониторинг состояния сетей показывает, что для эффективного функционирования любой сети необходимо решение комплекса взаимосвязанных задач начиная от организации каналов связи, выбора структуры . федеральных образовательных порталов, определения целесообразности развертывания зеркал федеральных образовательных порталов, выбор структуры узлов сети, выбора алгоритмов коммутации и маршрутизации, организации размещения информации в узлах сети и т.д.
В настоящей работе остановимся на разработке методов решения задач размещения информации в узлах сети и организации эффективной маршрутизации в телекоммуникационных сетях.
Характеристики типовых топологий сетей
Многослойные сети перестановочного типа. Многоярусные и в общем случае многослойные сети перестановочного типа получили распространение в системах коммутации [9]. В их основе лежит однослойная двухъярусная S-однородная сеть. Симметричный вариант этой сети, обозначаемый Q( 5,«), имеет п узлов в каждом ярусе. Формально сеть 0(S,n) можно определить следующим образом. Пусть имеется дп ребер с номерами h - 0(1) 7 -1. Тогда , где [х] - целая часть номера узлов, инцидентных ребру h суть h mod и и числа х. Сеть Q.(S,—) несвязанна и имеет п компонентов, изоморфных друг другу: Q{S,fa) = Qn(5,S). Пристраиванием третьего яруса эту сеть можно сделать связной, при этом увеличивается вдвое степень узлов (валентность) среднего яруса. Чтобы получившуюся сеть сделать однородной, нужно по той же схеме соединить дополнительными ребрами крайние ярусы. Однородная плоская триангуляция. Однородная плоская триангуляция -этор-арное дерево, на которое наложено его зеркальное отображение и которое дополнено ребрами уровней. В [45] показано, что число узлов на уровне п можно определить линейным возвратным уравнением второго порядка и+1 = Р я -Г.-1 и парой начальных условий Т0,Т1щ От обычного дерева триангуляция отличается резким увеличением живучести, причем достигается это введением сравнительно небольшого числа дополнительных ребер. Топология гипердерева. Гипердерево получается из бинарного дерева путем добавления на каждом уровне гиперкубических связей между узлами. При этом в первую очередь соединяют наиболее удаленные узлы, что приводит к существенному уменьшению диаметра графа. В гипердереве усиливаются лучшие свойства родительских топологий и в тоже время ослабляются недостатки, особенно свойственная гиперкубу неспособность к расширению [9]. Особое место в теории проектирования топологий архитектур мультикомпьютерных систем, распределенных вычислительных сетей и надежных сетей связи занимают неориентированные плотные регулярные графы с малыми диаметрами. Опыт разработки оптимальных структур вычислительных и телекоммуникационных систем и сетей показывает, что наилучшими структурами по различным критериям функционирования (транзитным задержкам, надежности, связности, самодиагностируемости, скорости коммуникаций) при одинаковом числе процессоров и линий связи у каждого из них являются графовые структуры с минимальными диаметром и средним расстоянием [29-32]. Графы с такими свойствами фигурируют в классе графов Кэли, в частности, в классе циркулянтных графов [55], и в классе графов Rs (N,V,g) [ЗІ], которые являются обобщениями циркулянтов, гиперкубов, торов, кубически связанных циклов [56], хордовых кольцевых сетей [57] и других подклассов однородных графов, описанных в литературе и реально применяемых при проектировании структур вычислительных и телекоммуникационных систем и сетей.
Класс Rs (N,V,g) параметрически описываемых регулярных графов, задаваемых полугруппами, включает в виде подклассов большинство известных однородных графов, используемых в качестве моделей при проектировании вычислительных систем. Оптимальные структуры имеют минимальный диаметр при заданных параметрах графа (порядке N, степени V, обхвате g, числе классов эквивалентности S). Актуальность обращения к графам Rs (N,V,g) и их исследования в качестве структур вычислительных систем продиктованы также появлением суперкомпьютерных систем с числом процессоров порядка 105 и более, для которых оптимальность диаметра сети связи уже реально сказывается на основных характеристиках функционирования вычислительной системы. Отметим, что в отличие от гиперкубов графы Rs (N,V,g) имеют логарифмическую (от числа вершин N) оценку диаметра при фиксированной степени вершины (диаметр оптимальных Rs (Ы,У )-графов приблизительно равен 0,21 log2 N в то время как диаметр гиперкубов равен logi N при одинаковой вершинной и реберной сложности исследуемых графов [32]).
Исследование характеристик топологий сетей необходимо для их конструктивного использования как при синтезе структур новых телекоммуникационных и вычислительных систем и сетей, так и для модернизации функционирующих систем и сетей с целью адресного улучшения их характеристик.
Оптимальное размещение информационного ресурса в сети
Создание сети для передачи контента, как правило, имеет некоторую очередность. То есть сеть создается не целиком, а отдельными фрагментами причем часто продолжительное время. В условиях быстрого развития средств передачи информации возникает ситуация, когда отдельные фрагменты сети существенно ограничивают ее производительность из-за низкой пропускной способности каналов связи, причем их замена оказывается невозможной по экономическим соображениям. В такой ситуации нежелательные последствия можно снизить за счет перераспределения информационных ресурсов в сети с целью минимизации потока на некотором ребре или множестве ребер.
Для построения алгоритма решения этой задачи будет полезным использование теории матроидов. В соответствии с [26] матроидом называется произвольная пара M= E,J , где Е-конечное множество, a JczP(E) - семейство его подмножеств, удовлетворяющих условиям: {о} є J и если А є J и В z Л, то В є J. Для произвольных А, В є J , таких что\В\ = \А\ + \,существуетэлементе є В\ А,такой что А {е} = J. (Условие {о} є J исключает вырожденный случай). Множество J называется независимым множеством. Матроиды тесно связаны с жадными алгоритмами оптимизации. Общая схема работы жадных алгоритмов выглядит следующим образом: 1. Упорядочить множество Е по убыванию весов. 3. Для каждого элемента е множества Е: если S J [є] є J, то S = S и \е), Связь матроидов и жадных алгоритмов дается известной теоремой Радо Эдмонса [26], которая формулируется следующим образом. Если М есть матроид, то множество S, найденное жадным алгоритмом, является независимым множеством с наибольшим весом. Утверждение 3.2. Существует жадный алгоритм для решения задачи распределения информационных ресурсов по критерию минимума потока на заданном ребре. Для доказательства этого утверждения, в соответствии с теоремой Радо-Эдмонса, достаточно показать, что конечное множество потоков на некотором выбранном ребре, образующихся при размещении информационных ресурсов по вершинам сети, вместе с семейством подмножеств, обладающих тем свойством, что каждый ресурс размещается на одном узле, образуют матроид. Очевидно, что обе аксиомы матроида в данном случае выполнены, поэтому жадный алгоритм распределения информационных ресурсов существует. Пусть топология сети описана в терминах теории графов (например, с помощью матрицы инцидентности). Заданы также интенсивности обменов между каждым узлом сети и каждым информационным ресурсом. Требуется разместить информационные ресурсы на сети таким образом, чтобы минимизировать суммарный поток на ребре t Матрицей путей для t-ребра назовем квадратную матрицу W размерности N, где N - число узлов сети, такую что \\,если путь из вершины і в вершину j проходит через ребро /; I 0,в противном случае. ПрИМеМ ПО Определению, ЧТО Wii=0. Последнее справедливо, поскольку обращение вершины к информационному ресурсу, который размещается в ней, не создает потока ни на каком ребре сети. Если сеть имеет топологию дерева, то есть существует единственный простой путь передачи информации между каждыми двумя вершинами сети, то матрица путей может быть получена непосредственно из топологического описания сети. В случае топологии общего вида матрица путей может быть построена из анализа таблиц статической маршрутизации (будем предполагать маршрутизацию статической).
Для построения матрицы путей для t-ребра по матрице инцидентности может быть использован алгоритм построения кратчайших путей на графе [10] с ребрами одинакового веса. Результатом работы этого алгоритма является список ребер, определяющих пути от любой вершины к любой. На основании анализа полученных списков можно получить матрицу путей.
Если V - матрица потоков между информационными ресурсами и вершинами сети, то F — WV содержит потоки в t - ребре сети возникающие при размещении і ресурса в j вершину. В случае отсутствия дополнительных ограничений решение задачи сводится к определению минимального элемента в каждой строке матрицы F и составлению вектора решения R из индексов минимальных элементов строк. Координата z этого вектора дает номер вершины, в которую необходимо поместить информационный ресурс z. В том случае, если минимальному значению соответствуют несколько индексов, координата вектора является множеством, включающим все такие индексы. Тогда получим множество решений, состоящее из всех возможных комбинаций элементов множеств координат (то есть получим все возможные решения).
Алгоритм уменьшения размерности задачи поиска кратчайших путей
Обозначим wij -вес ребра, соединяющего вершины v„ и vjt nwy - новое значение веса, полученное в результате изменения значения метрики линии связи. Вершина v,, располагается ниже по иерархии дерева кратчайших путей относительно v„. Обозначим Ет множество ребер, каждый элемент которого входит, по крайней мере, в один кратчайший путь из начальной вершины, ER -множество остальных ребер. ERUET=E, ЕЯГЕТ—0. Обозначим VT - множество вершин, до которых найден кратчайший путь из начальной вершины, VR -множество остальных вершин. V uVf=V, У п,Уг=0.
Будем называть Vk- путем Я& совокупность подмножества И сК вершин, через которые проходит кратчайший путь до вершины vk из исходной вершины v,, и подмножества с: Е ребер, составляющих этот путь.
Назовем Vk -деревом 7 совокупность подмножества VTok)c:V, состоящего из всех вершин, кратчайшие пути до которых из исходной вершины содержат вершину v и подмножества E/njc Е ребер, составляющих эти пути после v при движении от вершины vs.
Обозначим множество путей до вершины v„ из исходной вершины vs через Я„ где элемент множества л еЯ; будет множеством не повторяющихся ребер ецеЕ, образующих вместе путь, соединяющий vs, и v„. Для всех Я,іЄЯ, поставим в соответствие некоторое число, равное сумме весов, входящих в него ребер, т.е. длину пути d eD,,. На множестве П„ задан селектор Я, возвращающий кратчайший путь из множества Я,-. В том случае, если существует нескольких путей в Я, с минимальной длиной, то выбирается один из них. Кратчайший путь до вершины v, будем обозначать п,=Н(П,), оценку длины %-dt.
Для решения поставленной задачи сформулируем следующие теоремы: Теорема 4.1. Если «Wy Wy и ЄцеЕт, то изменению могут подвергнуться кратчайшие пути и оценки их длин для вершин V/1 .
Доказательство. Пусть увеличился вес ребра ЄцЄ.Ет, которое входит, по крайней мере, в один кратчайший путь я , например, в я іР. Вершины vb в кратчайшие пути до которых ребро вц не входит, будут составлять множество Vr вершин, кратчайшие пути до которых после изменения не изменятся (не изменится последовательность ребер и величины кратчайших путей). Действительно, пусть существует кратчайший путь %к nkp до вершины vk, и известно, что ребро Єц не входит в этот путь. Тогда увеличение веса этого ребра со значения w-ц до rw-ц не изменит маршрута этого пути и не повлияет на его величину dip , т.е. пКр и d p. Поскольку, еще до увеличения веса рассматриваемого ребра, включение этого ребра в кратчайший путь приводило к увеличению длины пути. Все вершины, не вошедшие во множество Vr, будут составлять множество VR. Кратчайшие пути до вершин множества v&VR станут «недействительными», т. е. невозможно будет без дополнительного расчета сказать, останутся они такими же или кратчайший путь до них не будет включать изменившееся ребро. Теорема доказана. Теорема 4.2. Если пюц м ц и еиеЕт, то без изменения останутся кратчайшие пути для вершин множества VG VJ(VJ JU , а для вершин множества V 1 неизменными останутся и оценки длин кратчайших путей.
Доказательство. Пусть уменьшился вес ребра вц&Ет , входящего в кратчайший путь щ - п р до вершины v eK- Ребро е-ц после изменения также будет входить в кратчайший путь щ до вершины vk. Поскольку вес ребра wtJ изменился, то измениться должны длины всех путей я,.г, в которые входит это ребро. Действительно, если ребро ец входит в какой-либо кратчайший путь и вес этого ребра уменьшается, то это изменение не потребует изменения кратчайшего пути щ_р (последовательности ребер) и длина пути d p изменится (уменьшится) на величину изменения веса ребра. Пути я у к/ иИ станут «недействительными», т. е. невозможно будет без дополнительного расчета сказать, останутся они такими же или кратчайший путь до них будет включать изменившееся ребро. Теорема доказана. Теорема 4.3. Если nWiJ wu и еиеЕг, то исходное дерево кратчайших путей и оценки длин путей всех вершин не изменятся.
Доказательство- Пусть ребро, не входящее ни в один кратчайший путь, увеличивает свой вес wJt/, ЄЦЄЕ , Никаких изменений дерева кратчайших путей при этом не происходит. Действительно, пусть ребро ец Е входит в путь Tl/ p до некоторой вершины vk, который не является кратчайшим для v„ -7с ,р я . Т.е. существует такой путь пк. к что d d . Тогда после увеличения веса wtJ увеличится оценка длины dk,p и неравенство d p djLt останется справедливым, Т.е. кратчайший путь и его оценка до вершины vk остается неизменной. Теорема доказана. Теорема 4,4. Если nWij Wjj и е Ет, то без изменения останутся кратчайшие пути и оценки их длин для вершин множества Vа 1 .
Доказательство. Пусть уменьшился вес ребра е Ец, которое не входит ни в один кратчайший путь. Допустим, что это ребро входит в путь 7С1г л„ и iij.p Kj- Если изменившееся ребро eSj не уменьшает оценок обеих инцидентных ему вершин v„ и v,, т.е. dik di и dJ-p d} , дерево кратчайших путей не изменится. Действительно, рассматриваемое ребро оказывает влияние, прежде всего на инцидентные ему вершины множества V. Если включение ребра e,j в дерево не уменьшает оценок пути d„dp то такое включение только увеличит оценки вершин. Т.к. существовавшие до изменения пути до этих вершин имели меньшую длину, то данное ребро не включается в дерево кратчайших путей. Если включение этого ребра приводит к уменьшению оценки какой-либо из инцидентных вершин, например v( то эта оценка dlk будет оценкой кратчайшего пути до вершины V;, и ребро вц войдет в искомое дерево кратчайших путей.
