2
ОГЛАВЛЕНИЕ
Введение............................................. 4 стр.
Глава I. Нестандартная достижимость различных видов.
Кратчайшие пути на графах с нестандартной
достижимостью............................. 18 стр.
§1.1. Основные определения..................................... 18 стр.
§ 1.2. Смешанная достижимость на орграфах...................... 20 стр.
§ 1.3. Магнитная достижимость на орграфах...................... 24 стр.
§ 1.4. Барьерная достижимость на графах........................ 28 стр.
Заключение к главе I........................................... 32 стр.
Глава II. Случайные блуждания на графах с нестандартной
достижимостью........................................ 33 стр.
§2.1. Случайные блуждания на графах со смешанной
достижимостью.................................................. 34 стр.
§2.2. Случайные блуждания на графах с монотонной
достижимостью............................................ 38 стр.
§ 2.3. Случайные блуждания на графах с вентильной
достижимостью............................................ 45 стр.
Заключение к главе II ........................................ 51 стр.
Глава III. Потоки в сетях с нестандартной достижимостью 52 стр.
§3.1. Примеры потоков в сетях с нестандартной
достижимостью.................................................. 53 стр.
§ 3.2. Основные определения теории потоков в сетях с
нестандартной достижимостью 61 стр.
§ 3.3. Семейство сетей с барьерной достижимостью .... 65 стр.
Заключение к главе III ........................................ 67 стр.
Глава IV. Динамические потоки в сетях............... 68 стр.
§4.1. Основные определения..................................... 69 стр.
§4.2. Ограничения на величину динамического потока ... 71 стр.
3
§ 4.3. Временная развертка графа................. 77 стр.
§ 4.4. Всплеск динамического потока, ёмкость сети ... 85 стр.
Заключение к главе IV ........................... 96 стр.
Глава V Динамические графы и сети...................... 97 стр.
§5.1. Динамические графы. Определение и примеры ... 97 стр.
§ 5.2. Временная развертка динамического графа . . . . 101стр.
§ 5.3. Периодические динамические графы.......... 103 стр.
§ 5.4. Построение развёртки периодическог о динамического
графа............................................ 106 стр.
§ 5.5. О потоках в динамических сетях.................. 111 стр.
Заключение к главе V...................................... 113 стр.
Глава VI. Функции на графах 114 стр.
§6.1. Семейство функций Гранди ориентированного графа 115 стр.
§ 6.2. Семейство функций Гранди неориентированного графа 120 стр.
Заключение к главе VI.................................. 122 стр.
Библиографический список использованной литературы ... 123 стр.
Приложение 1. Некоторые сведения о конечных множествах в
ZuN........................................ 132 стр.
Настоящая работа посвящена ориентированным графам с нестандартной достижимостью и некоторым смежным вопросам дискретной математики. Ключевых слов в этом предложении несколько. Во-первых, «ориентированным» - автор не разделяет как-то высказанного суждения о том, что по-настоящему математическими объектами являются неориентированные графы. Действительно, если к графам подходить как к объектам, изучаемым методами алгебраической топологии, то этот так и есть. Но в приложениях чаще встречаются и более естественны для использования именно ориентированные графы. Автор настоящей работы считает, что класс ориентированных графов более широк и интересен. В большинстве случаев неориентированный граф можно считать симметрическим ориентированным графом. Вторым ключевым словом или фразой в первом предложении является «граф с нестандартной достижимостью». Именно эти объекты мы и будем рассматривать в нашей работе.
В прикладных задачах, как правило, изучается не сам граф, а процессы на нем. Большинство из них связано с перемещениями по графу по его путям. В классическом определении путь это последовательность дуг графа, в которой каждая следующая дуга начинается в вершине, в которой заканчивается предыдущая дуга пути. Соединимость одной вершины путем, ведущим из другой вершины, называется достижимостью одной вершины из другой. Три основных задачи прикладной теории графов и не только прикладной, а точнее сказать, алгоритмической теории графов связаны с достижимостью. Это сама задача о достижимости и нахождении кратчайшего пути, задача о случайных блужданиях но вершинам графа и задачи о потоках в сетях, поскольку поток можно считать перемещением (транспортировкой) вещества (материи, товаров, жидкости, энергии и т.п.) из источника в сток но путям, ведущим из источника в сток.
Когда мы говорим о графе с нестандартной достижимость, то это означает, что допустимыми к рассмотрению на нём являются не все пути, а пути, удовлетворяющие определенному условию (это условие называется типом
5
или видом нестандартной достижимости). Как правило, тип нестандартной достижимости возникает после того, как задано некоторое разбиение множества дуг графа, а ограничения на достижимость формулируются с помощью (в терминах) этого разбиения. Почему мы считаем, что 1рафы с нестандартной достижимостью являются по существу новыми, по сравнению с графами объектами? Во-первых, графы можно считать графами с нестандартной достижимостью (тривиальной), но главное не в этом. Как оказалось ([12]), для большинства известных видов нестандартной достижимости задача о максимальном целочисленном потоке в сети с нестандартной достижимостью является ЫР-полной, в отличие от этой задачи в обычных графовых сетях.
Актуальность. Родившаяся при решении головоломок и занимательных задач теория графов стала мощным средством решения проблем многих наук и техники. Её широкая применимость стала мощным стимулом развития. Посылая сообщение по электронной почте, мы пользуемся теорией графов, поскольку вся навигация в ИНТЕРНЕТе основана на решении задачи о кратчайшем маршруте, соединяющем заданные узлы сети. Новый этап развития теории графов можно назвать алгоритмическим, поскольку широкая применимость всегда связана с разработкой алгоритмов, позволяющих решать массовые задачи. Широкая применимость к прикладным задачам сделала сам термин «теория графов» неудачным, его стали заменять термином «Прикладная теория графов» или «Алгоритмическая теория графов» [32, 55, 70]. Всюду в дальнейшем в нашей работе под теорией графов мы понимаем термин «теория графов» именно в этом смысле.
Среди алгоритмов на графах следует особо выделить алгоритм Е.Дейкстры [57] нахождения кратчайших путей на графах, фактически первый динамический алгоритм, и алгоритм Д. Краскала [79] нахождения легчайшего покрывающего дерева.
Ещё одним выдающимся достижением алгоритмической теории графов стала теория потоков в сетях, созданная Л. Фордом и Д. Фалкерсоном (см. русск. пер.: Форд Л., Фалкерсон Д. Потоки в сетях. М.: Мир, 1966 и
[58,59]). В настоящий момент теория потоков в сетях находит все большее применение в связи с развитием телекоммуникаций (INTER.NET, мобильная связь, глобальные компьютерные сети и т.п.[43]), логистики, теории нейронных сетей, биоинформатики (см. напр.[30]). Вот что говорится во введении в книгу М. Ньюмана «Сети: введение» [83]: «Современная теория сетей стала прототипом междисциплинарных исследований: социология, компьютерные науки, химия, экономика, энергетика, транспорт, управление бизнесом и, сравнительно недавно, социальные сети и биоинформатика. Целям и задачам все этих наук служит эта теория». Современное состояние теории сетей изложено в книге Т. Левиса «Сетевая наука: теория и приложения» [80]. Следует отметить, что с точки зрения общих подходов к теории сетей, то они мало изменились по сравнению с подходом основоположников этой теории Л. Форда и Д. Фалкерсона ([62, 63]). В основном её развитие связано с разработкой и совершенствованием алгоритмов решения потоковых задач в сетях (см. [52, 53], [58-61], [64-69], [74-78]). Среди учёных, внесших основной вклад в развитие этого направления, необходимо назвать Г.Данцига, Е. Ди-ница, Дж. Эдмонтса, X. Габова, А. Гольдберга, Р. Карпа, В. Кинга, Р. Тарья-на. Если говорить о развитии общих подходов к теории сетей, то следует особо выделить работу А. Гольдберга и С. Рао [70].
Цель исследования. Настоящая работа посвящена, в основном, нестандартной достижимости на ориентированных графах. Нам представляется, что нестандартная достижимость на графах естественным образом возникает именно в прикладных задачах.
Поясним сказанное простым примером. Рассмотрим телекоммуникационную сеть. Будем интерпретировать се как граф, вершины которого соответствуют пунктам приема и передачи информации. Дуги соответствуют каналам связи, по которым передается информация между пунктами. Известно, что в процессе передачи сигнала несущего информацию по каналу связи с ним могут происходить изменения - сигнал может затухать и если его уровень понизится до уровня естественного шума, то возникает его потеря.
, . 1 >. , I
*
I
7
Имеется два типа основных средств борьбы с этим: пассивные и активные. Пассивные средства предполагают улучшение физических характеристик каналов, что обеспечивает более низкий уровень затухания сигнала и снижение уровня естественного шума в канале. Последним достижением в этой области являются оптоволоконные каналы связи, получившие в настоящее время широкое распространение. Активные средства предполагают повышение уровня сигнала с помощью разного рода усилителей, которые комбинируются со средствами фильтрации. Такая комбинация позволяет отфильтровать сигнал от шума и повысить его уровень. Таких активных улучшений сигнала во время его передачи по каналам связи может быть несколько, а может и не быть вовсе, все зависит от трассы, по которой передается сигнал (имеются ли на ней активные участки). Активные средства улучшения качества сигнала последнее время получили широкое распространение. Переломным моментом в развитии активных средств явился переход от аналоговых систем передачи информации к цифровым системам. Цифровые системы позволяют лучше и легче решать задачу фильтрации сигналов от шума, а также позволяют поднимать его уровень (усиливать), не внося искажений в отфильтрованный поток информации.
В нашей модели телекоммуникационной сети возникает естественное разбиение множества дуг на три типа: пассивные или нейтральные, прохождение сигнала по которым не влияет на его качество, активные («хорошие»), прохождение сигнала по которым улучшает его качество, регрессивные («плохие»), прохождение сигнала по которым существенно снижает его уровень.
Если бы мы находились на первоначальном этапе развития телекоммуникационных сетей, то все дуги следовало бы рассматривать как плохие. Ясно, что в этом случае минимальный ущерб качеству передачи будет получен в случае использования кратчайшей трассы из имеющихся трасс между пунктами передачи и приема информации.
8
Современный этап развития телекоммуникаций характерен тем, что большинство дуг являются либо нейтральными, либо активными, однако полное избавление от регрессивных дуг в ближайшее время не представляется возможным. Более того - наши требования к качеству передачи информации все время возрастают. Это приводит к тому, что часть дуг из первых двух категорий приходится «переводить» в третью (моральный износ), такой перевод может быть связан и с неизбежным физическим износом.
В случае наличия дуг трех типов далеко не всегда лучшей для передачи информации является кратчайшая трасса. Действительно, если она состоит только из регрессивных дуг, то затухание сигнала может оказаться таким, что он «утонет» в естественном шуме. Ясно, что задача выбора оптимальной трассы для передачи информации становится нетривиальной. Речь идет о выборе кратчайшего пути не из всего множества путей, имеющихся на нашем графе, а из некоторого подмножества путей. Эти пути нельзя рассматривать как пути на некотором частичном графе, т.е. когда, например, регрессивные дуги просто удалены.
Существенным при определении того, какой путь можно рассматривать, а какой путь нельзя, является не то - какие дуги участвуют в его формировании, и не то - какие дуги не участвуют. Определяющим, в нашем случае, является следующее: в какой комбинации дуги разных типов встречаются в последовательности дуг пути (улучшенный сигнал можно пропустить и через регрессивные дуги; регрессивные дуги не могут встречаться в последовательности дуг пути таким образом, что уровень сигнала понижается до недопустимого для дальнейшего прохождения уровня).
Характерной особенностью задач на графах с нестандартной достижимостью является неприменимость напрямую классических алгоритмов, поскольку все они предполагают, что все возможные пути на графе являются допустимыми. Это относится и к задаче о кратчайших путях, и к задаче о случайных блужданиях по 1рафу, и к задаче о максимальном потоке в сети. Графы с нестандартной достижимостью - первый известный пример, когда
9
мультиграфы (графы с кратными дугами) приходится рассматривать по существу, т.е. когда задача, исходно поставленная на мультиграфе, не может быть сведена к задаче на обычном графе заменой кратных дуг кратчайшей из них в задаче о кратчайших путях или дугой с суммарной пропускной способностью в потоковых задачах. Это связано с тем, что кратные дуги могут быть разных типов.
Степень разработанности проблемы. Изучение графов с нестандартной достижимостью началось сравнительно недавно, первые работы в этой области принадлежат Я.М.Ерусалимскому и Е.О.Басанговой ([4 - 7]). В работах [4, 6, 7] рассматривались частично-ориентированные графы, т.е. такие, которые содержат ориентированные дуги и неориентированные ребра. Принципиальным отличием нашего рассмотрения явилось следующее. В качестве допустимых путей на таких графах мы рассматривали смешанные пути двух типов. Первый тип - смешанная (9-достижимость. Допустимыми при (9-достижимости являются только такие пути, которые не проходят подряд по дугам, т.е. дуги такого пути должны «прореживаться ребрами. При УУ-достижимости допустимыми являются только такие пути, которые не проходят подряд по рёбрам частично-ориентированного графа, рёбра на пути должны «прореживаться» дугами.
Рассмотрение частично-ориентированных графов в этих работах было вызвано задачей, связанной с теорией базисов в пространствах Кёте. Существенным моментом в этих работах стали ограничения на множество допустимых путей, а не то, что рассматривались частично- ориентированные графы. В работах [5, 28] впервые было сформулировано понятие «ориентированный граф со смешанной достижимостью», состоящее в следующем -множество дуг такого графа представляет собой объединение попарно непе-ресекающихся множеств Цы и V7. Смешанным путем на таком 1рафе называется путь, на котором по дугам из множества Vг нельзя проходить более
одного раза подряд. Граф, на котором рассматриваются только смешанные пути, мы назвали графом со смешанной достижимостью. Основным мето-
дом для решения задач на таких графах оказалось построение вспомогательного графа, путям на котором соответствуют допустимые пути на графе со смешанной достижимостью. Это позволило свести задачу о кратчайших путях на графе со смешанной достижимостью к задаче о кратчайших путях на вспомогательном графе, который мы назвали развёрткой. Развертка в случае смешанной достижимости содержит в два раза больше вершин, чем исходный граф, а количество её дуг определяется формулой
И = 2|^| + |Уг| . (0.1)
Это в принципе означает, что трудоемкость решения задачи о кратчайших путях на графах со смешанной достижимостью такая же как и на обычных графах.
Для графов со смешанной достижимостью были рассмотрены классические задачи о кратчайших путях, случайных блужданиях, получен критерий эйлеровости таких графов. Наибольшая сложность возникла в задаче о максимальном потоке в таких сетях. Возникшие трудности связаны с появлением на вспомогательном графе новых дуг (одной дуге из множества Vы на вспомогательном графе соответствует две дуги). Если полагать, что новая дуга имеет такую же пропускную способность, как и дуга сё породившая, мы можем получить на вспомогательном графе поток, который нельзя будет интерпретировать, как допустимый поток на исходном графе.
В последующем мы изучили различные виды нестандартной достижимости, которые принципиально отличаются от смешанной достижимости. Однако, во всех рассмотренных случаях «идеология» оставалась прежней -построение вспомогательного графа и замена исходной задачи на графе с нестандартной достижимостью соответствующей задачей на вспомогательном графе. Это позволяет применять известные или соответствующим образом модифицированные алгоритмы для решения таких задач как задача о кратчайшем пути или задача о случайных блужданиях частицы по графу. Заметим, что последняя задача, в нашем случае, не является Марковской.
Наиболее сложными оказались потоковые задачи. Они потребовали существенного пересмотра даже исходной постановки. Пришлось пересмотреть базовое понятие потока, поскольку определение Форда-Фалкерсона [49] учитывает только локальную структуру графа, и никак не учитывает - по каким путям транспортируется поток. Важной для нашего понимания стала работа [32], в которой приведена теорема о декомпозиции потока в виде набора потоков по путям. Именно такой подход к потоку на графе мы сочли единственно возможным. Конструкция вспомогательного графа в случае барьерной достижимости очень похожа на конструкцию, которую применяют при исследовании динамических потоков в сетях (см., например, [53]), однако, смысл предложенной конструкции в нашем случае совсем другой. В работах по динамическим потокам мы имеем дело с разверткой графа во времени, в нашем случае можно говорить об энергетической развертке.
Главным для нас при определении графов с нестандартной достижимостью являются ограничения на множество рассматриваемых путей. Почему мы считаем это существенным. В большинстве прикладных задач на графах рассматриваются процессы и явления связанные с путями на графах. Это и задача о кратчайшем пути между вершинами графа, это и задача о случайных блужданиях (которые совершаются по путям на графе), это и эйлеровы или гамильтоновы обходы, это и задача о максимальном потоке в сети (поскольку поток - это транспортировка вещества по путям на графе из источника в сток). Как оказалось в дальнейшем нестандартная достижимость на графах не всегда связана с разбиением множества дуг графа. Этот подход позволил нам рассмотреть и другие объекты - динамические графы, структура которых и такие характеристики как веса дуг, меняются в дискретном времени (ґ є ТУ). В связи со сказанным выше мы считаем, что в данной работе представлены оригинальные подходы и результаты.
Цель к задача исследования. Разработать общую теорию графов с нестандартной достижимостью, которая позволяла бы решать классические задачи о кратчайших путях, случайных блужданиях и потоковые задачи в тех
ситуациях, когда классические алгоритмы неприменимы. Эта теория должна существенно расширить класс возможных приложений теории графов.
Объект исследования - ориентированные графы и сети с нестандартной достижимостью.
Предмет исследования - задачи о кратчайших путях и случайных блужданиях и потоковые задачи на таких графах и сетях.
Гипотеза исследования. Круг приложений теории 1рафов и класс рассматриваемых задач настолько расширились, что необходимо расширить наши представления об исходных объектах: графах и сетях. Такое расширение должно позволить рассматривать и решать задачи, к которым раньше аппарат теории графов был неприменим.
Методы исследований. В работе использованы методы дискретной математики, в том числе методы теории графов, комбинаторного анализа, дискретной оптимизации, а также методы алгебры и математического анализа.
Научная новизна. Все основные результаты диссертации являются новыми.
Теоретическая и практическая ценность. Работа носит теоретический и прикладной характер. Полученные результаты могут найти применение при анализе процессов и явлений, которые моделируются с помощью графов и сетей. Предложенный в работе подход позволяет учесть факторы, которые классическая теория не учитывает.
Основные положения, выносимые на защиту:
1. Новые объекты - графы и сети с нестандартной достижимостью.
2. Общая теория графов и сетей с нестандартной достижимостью, основанная на построении разверток графов и сетей с нестандартной достижимостью.
3. Методы решения задач о кратчайших путях и случайных блужданиях на графах с нестандартной достижимостью.
4. Теория потоков в сетях с нестандартной достижимостью.
5. Новые объекты - динамические графы и сети, структура которых
- Київ+380960830922