Введение к работе
Настоящая работа посвящена ориентированным графам с нестандартной достижимостью и некоторым смежным вопросам дискретной математики. Ключевых слов в этом предложении несколько. Во-первых, «ориентированным» - автор не разделяет суждения о том, что по-настоящему математическими объектами являются неориентированные графы. Действительно, если к графам подходить как к объектам, изучаемым методами алгебраической топологии, то этот так и есть, но в приложениях чаще встречаются и более естественны для использования именно ориентированные графы. Класс ориентированных графов более широк и интересен, в большинстве случаев неориентированный граф можно считать симметрическим ориентированным графом. Вторым ключевым словом или фразой в первом предложении является «граф с нестандартной достижимостью». Именно эти объекты мы в основном и будем рассматривать в нашей работе.
В прикладных задачах, как правило, изучается не сам граф, а процессы на нем. Большинство из них связано с перемещениями по путям на графе. В классическом определении путь – это последовательность дуг графа, в которой каждая следующая дуга начинается в вершине, в которой заканчивается предыдущая дуга пути. Соединимость одной вершины путм, ведущим из другой вершины, называется достижимостью одной вершины из другой. Три основных задачи прикладной теории графов и не только прикладной, а точнее сказать, алгоритмической теории графов связаны с достижимостью на графах. Это сама задача о достижимости и нахождении кратчайшего пути, задача о случайных блужданиях по вершинам графа и задачи о потоках в сетях. Поток можно считать перемещением (транспортировкой) вещества (материи, товаров, жидкости, энергии и т.п.) из источника в сток по путям, ведущим из источника в сток.
Когда мы говорим о графе с нестандартной достижимость, то это означает, что допустимыми на нм являются не все пути, а пути, удовлетворяющие определенному условию (это условие называется типом или видом нестандартной достижимости). Как правило, тип нестандартной достижимости возникает после того, как задано некоторое разбиение множества дуг графа, а ограничения на достижимость формулируются с помощью (в терминах) этого разбиения. Почему мы считаем, что графы с нестандартной достижимостью являются по существу новыми объектами, по сравнению с обычными графами? Во-первых, графы можно считать графами с нестандартной достижимостью (тривиальной), но главное не в этом. Как оказалось
([12]), для большинства известных видов нестандартной достижимости задача о максимальном целочисленном потоке в сети с нестандартной достижимостью в отличие от этой задачи в обычных графовых сетях является NP-полной.
Актуальность. Родившаяся при решении головоломок и занимательных задач теория графов стала мощным средством исследования во многих отраслях науки и техники1. Е широкая применимость стала и мощным стимулом развития. Посылая сообщение по электронной почте, мы пользуемся теорией графов, поскольку вся навигация в ИНТЕРНЕТе основана на решении задачи о кратчайшем маршруте, соединяющем заданные узлы сети, пользуясь JPS-навигаторами, мы невольно используем теорию графов.
Новый этап развития теории графов можно назвать алгоритмическим,
поскольку широкая применимость всегда связана с алгоритмами, позволяю
щими решать массовые задачи. Прикладная направленность сделала сам
термин «теория графов» неудачным. Его стали заменять термином «При
кладная теория графов» или «Алгоритмическая теория графов»2. Всюду в
дальнейшем в нашей работе под «теорией графов» мы понимаем этот тер
мин именно в этом смысле.
Среди алгоритмов на графах следует особо выделить алгоритм Е.Дейкстры3 нахождения кратчайших путей на графах, фактически первый динамический алгоритм, и алгоритм Д. Краскала4 нахождения легчайшего покрывающего дерева.
Ещ одним выдающимся достижением алгоритмической теории графов стала теория потоков в сетях, созданная Л. Фордом и Д. Фалкерсоном5. В настоящий момент теория потоков в сетях находит все большее применение в связи с развитием телекоммуникаций (INTERNET, мобильная связь, глобальные компьютерные сети6 и т.п.), логистики, теории нейронных сетей, биоинформатики7). Вот что говорится во введении в книгу М.Ньюмана8:
1 Химические приложения топологии и теории графов/под. ред. Р.Кинга//М.: Мир, 1978
Применение теории графов в химии/под ред. Н.С. Зефирова и С.И. Кучанова//Новосибирск: Наука, 1988
2 Кристофидес Н. Теория графов. Алгоритмический подход. // –М.:Мир, 1978. – 432с.
3 Dijkstra E.W. A Note in two problems in connection with graphs, Numtrische Mathematic ,1959, #1, p.269
4 Kruskal J.B. On the shortes spannig subtree of a graph and the traveling salesman problem, Proc. American Ma
thematical Soc., 1956, #7, p. 48
5 Форд Л., Фалкерсон Д. Потоки в сетях. М.: Мир, 1966
6 Самуйлов К.Е., Чукарин A.B. К расчету плана маршрутизации сети системы сигнализации №7 //
Системы телекоммуникаций и моделирование сложных систем. -М.: ПАИМС, 2001
7 Ерусалимский Я.М. Дискретная математика для биоинформатиков//Ростов н/Д: Изд-во ЮФУ.
2011, 122с.
8 Newman M. Networks: an Introduction//Oxford University Press, Inc., New York, NY,2010.
p.720
«Современная теория сетей стала прототипом междисциплинарных исследований: социология, компьютерные науки, химия, экономика, энергетика, транспорт, управление бизнесом и, сравнительно недавно, социальные сети и биоинформатика. Целям и задачам все этих наук служит эта теория». Современное состояние теории сетей изложено в книге Т. Левиса 9. Следует отметить, что с точки зрения общих подходов к теории сетей, то они мало изменились по сравнению с подходом основоположников этой теории Л. Форда и Д. Фалкерсона. В основном е развитие связано с разработкой и совершенствованием алгоритмов решения потоковых задач в сетях10. Среди учных, внесших основной вклад в развитие этого направления, необходимо назвать Г. Данцига, Е. Диница, Дж. Эдмонтса, Х. Габова, А. Гольдберга, Р. Карпа, В. Кинга, Р. Тарьяна, С. Рао. Если говорить о развитии общих подходов к теории сетей, то следует особо выделить работу А. Гольдберга и С. Рао11.
Следует отметить то различие, которое имеется в понимании и подходах к теории сетей, которое существует. С точки зрения дискретной математики теория сетей занимается изучением транспортной способности сетей (классическая теория Форда-Фалкерсона, основанная на понятии допустимый поток). Второй подход к теории сетей – изучение побудительных причин наличия потока в сети, изучение закономерностей динамики таких потоков, связан в основном с приложениями сетей в других науках: теория электрических цепей, берущая свое начало от работ Г. Кирхгофа, теория гидравлических сетей, сетевая логистика, сетевые методы в экономике и финансах12 и т.п. Среди последних работ по применению теории гидравлических сетей в
9 Lewis T. Network Science: Theory and Applications// Wiley Publ., Hoboken, NJ, 2009. p. 524
10 Helmberg C. Network Models with Convex Cost Structure like Bundle Methods. / C. Helmberg // Models and
Algorithms for Optimization in Logistics, Dagstuhl Seminar Proceedings.
Karp R.M. Reducibility among Combinatorial Problems. / Karp R.M. // Complexity of Computer Computations; R.
E. Miller and J. W. Thatcher (editors). –New York: Plenum, 1972. – pp.85–103. Karzanov, A.V. Determining the maximal flow in a network by the method of preflows. / A.V. Karzanov // Sov.
Math. Dokl. –1974. –No.15. – pp.434-474. King V. A faster deterministic maximum flow algorithm. / V. King, S. Rao, R. Tarjan. // In Proceedings of the 3rd
Annual ACM-SIAM Symposium on Discrete Algorithms (Orlando, Fla., Jan. 27-29). ACM, New York, 1992. –
pp.157-164. King V. A faster deterministic maximum flow algorithm. / V. King, S. Rao, R. Tarjan. // J.
Algorithms. –1994. –No.17. – pp.447-474.
11 Goldberg A.V. Beyond the Flow Decomposition Barrier/ A.V. Goldberg, S. Rao/ Journal of the ACM. –Vol.45.
–No. 5. –1998. – pp.783-797.
12 Nugurney A. A Supply Chain Network Economics. Dynamics of Prices, Flows and Profits//EE Publishing Ltd., 2006, pp.412
экономике следует отметить докторскую диссертацию А.Г. Коваленко13. В нашей работе под теорией потоков в сетях мы понимаем е как соответствующий раздел дискретной математики.
Цель исследования. Настоящая работа посвящена, в основном, нестандартной достижимости на ориентированных графах и задачам поиска кратчайших путей, случайным блужданиям и потокам в сетях. Нестандартная достижимость на графах естественным образом возникает именно в прикладных задачах.
Поясним сказанное примером. Рассмотрим телекоммуникационную сеть. Будем интерпретировать е как граф, вершины которого соответствуют пунктам приема/ передачи информации. Дуги соответствуют каналам связи, по которым передается информация между пунктами. Известно, что в процессе передачи сигнала по каналу связи с ним могут происходить изменения – сигнал может затухать и если его уровень понизится до уровня естественного шума, то возникает его потеря. Имеется два типа основных средств борьбы с этим: пассивные и активные. Пассивные средства предполагают улучшение физических характеристик каналов, что обеспечивает более низкий уровень затухания сигнала и снижение уровня естественного шума в канале. Последним достижением в этой области являются оптоволоконные каналы связи, получившие в настоящее время широкое распространение. Активные средства предполагают повышение уровня сигнала с помощью разного рода усилителей, которые комбинируются со средствами фильтрации. Такая комбинация позволяет отфильтровать сигнал от шума и повысить его уровень. Таких активных улучшений сигнала во время его передачи по каналам связи может быть несколько, а может и не быть вовсе, все зависит от трассы, по которой передается сигнал (имеются ли на ней активные участки). Активные средства улучшения качества сигнала последнее время получили широкое распространение. Переломным моментом в развитии активных средств явился переход от аналоговых систем передачи информации к цифровым системам. Цифровые системы позволяют лучше и легче решать задачу
13 Коваленко А.Г. Развитие математических моделей и методов теории гидравлических сетей и их применение для моделирования рассредоточенного рынка// автореферат диссертации на соискание ученой степени доктора ф.-м. наук, Москва, 2006
фильтрации сигналов от шума, а также позволяют поднимать его уровень (усиливать), не внося искажений в отфильтрованный поток информации.
В нашей модели телекоммуникационной сети возникает естественное разбиение множества дуг на три типа: пассивные или нейтральные, прохождение сигнала по которым не влияет на его качество, активные («хорошие»), прохождение сигнала по которым улучшает его качество, регрессивные («плохие»), прохождение сигнала по которым существенно снижает его уровень.
Если бы мы находились на первоначальном этапе развития телекоммуникационных сетей, то все дуги следовало бы рассматривать как плохие. Ясно, что в этом случае минимальный ущерб качеству передачи будет получен в случае использования кратчайшей трассы, из имеющихся трасс между пунктами передачи и приема информации.
Современный этап развития телекоммуникаций характерен тем, что большинство дуг являются либо нейтральными, либо активными, однако полное избавление от регрессивных дуг в ближайшее время не представляется возможным. Более того – требования к качеству передачи информации возрастают. Это приводит к тому, что часть дуг из первых двух категорий приходится «переводить» в третью (моральный износ), такой перевод может быть связан и с неизбежным физическим износом.
В случае наличия дуг трех типов далеко не всегда лучшей для передачи информации является кратчайшая трасса. Действительно, если она состоит только из регрессивных дуг, то затухание сигнала может оказаться таким, что он утонет в естественном шуме. Ясно, что задача выбора оптимальной трассы для передачи информации становится нетривиальной. Речь идет о выборе кратчайшего пути не из всего множества путей, имеющихся на нашем графе, а из некоторого подмножества путей. Эти пути нельзя рассматривать как пути на некотором частичном графе, т.е. когда, например, регрессивные дуги просто удалены.
Существенным при определении того, какой путь можно рассматривать, а какой путь нельзя, является не то - какие дуги участвуют в его формировании, и не то - какие дуги не участвуют. Определяющим, в нашем случае, является следующее: в какой комбинации дуги разных типов встречаются в последовательности дуг пути (улучшенный сигнал можно пропустить и через регрессивные дуги; регрессивные дуги не могут встречаться в последовательности дуг пути таким образом, что уровень сигнала понижается до недопустимого для дальнейшего прохождения уровня).
Характерной особенностью задач на графах с нестандартной достижимостью является неприменимость напрямую классических алгоритмов, поскольку все они предполагают, что все возможные пути на графе являются допустимыми. Это относится и к задаче о кратчайших путях, и к задаче о случайных блужданиях по графу, и к задаче о максимальном потоке в сети. Графы с нестандартной достижимостью – первый известный пример, когда мультиграфы (графы с кратными дугами) приходится рассматривать по существу. Задача, исходно поставленная на мультиграфе, не может быть сведена к задаче на обычном графе заменой кратных дуг на кратчайшую из них (в задаче о кратчайших путях), дугой с суммарной вероятностью перехода (в задаче о случайных блужданиях) или дугой с суммарной пропускной способностью (в потоковых задачах). Это связано с тем, что кратные дуги могут быть разных типов. В связи со сказанным мы можем определить:
Цель и задача исследования. Разработать общую теорию графов и сетей с нестандартной достижимостью, которая позволяла бы решать задачи о кратчайших путях, случайных блужданиях и потоковые задачи в тех ситуациях, когда классические алгоритмы неприменимы. Эта теория должна существенно расширить класс возможных приложений теории графов.
Объект исследования – ориентированные графы и сети с нестандартной достижимостью.
Предмет исследования – задачи о кратчайших путях и случайных блужданиях и потоковые задачи на таких графах и сетях.
Гипотеза исследования. Круг приложений теории графов и класс рассматриваемых задач настолько расширились, что необходимо расширить и наши представления об исходных объектах: графах и сетях. Такое расширение должно позволить рассматривать и решать задачи, к которым раньше аппарат теории графов был неприменим.
Методы исследований. В работе использованы методы дискретной математики, в том числе методы теории графов, комбинаторного анализа, дискретной оптимизации, а также методы алгебры и математического анализа.
Степень разработанности проблемы и новизны. Изучение графов с нестандартной достижимостью началось сравнительно недавно, первые ра-
боты в этой области принадлежат Я.М.Ерусалимскому и Е.О.Басанговой ([25, 27-29]). В работах [25, 27] рассматривались частично-ориентированные графы, т.е. такие, которые содержат ориентированные дуги и неориентированные ребра.
Рассмотрение частично-ориентированных графов в этих работах было вызвано задачей, связанной с теорией базисов в пространствах Кте. Существенным моментом в этих работах было ограничение на множество рассматриваемых путей – неориентированные рбра не могли встречаться на путях подряд, они должны были прореживаться дугами графа. В работе [28] было впервые сформулировано понятие «ориентированный граф со смешанной достижимостью», состоящее в следующем – множество дуг такого графа представляет собой объединение попарно непересекающихся множеств UN и UZ . Смешанным путем на таком графе называется путь, на котором по дугам из множества UZ нельзя проходить более одного раза подряд. Граф, на котором рассматриваются только смешанные пути, мы назвали графом со смешанной достижимостью. Основным методом для решения задач на таких графах оказалось построение развртки - вспомогательного графа, путям на котором соответствуют допустимые пути на графе со смешанной достижимостью. В последующем нами (автором настоящей работы и его учениками) было введено более широкое понятие – граф с нестандартной достижимостью.
Полученным в этой области результатам и посвящена диссертационная работа. В не мы вынесли только наиболее общие вопросы этой теории, не рассматривая алгоритмы решения задач о кратчайших путях, случайных блужданиях и потоках, поскольку разработке и обоснованию алгоритмов для конкретных видов нестандартной достижимости были посвящены кандидатские диссертации учеников автора: Е.О. Басанговой, С.Ю. Логвинова, В.А. Скороходова, А.Г. Петросяна, М.В. Кузьминовой, Н.Н. Водолазова. Таким образом, все известные в настоящее время результаты в этой области принадлежат либо лично автору настоящей работы, либо получены им совместно с учениками.
Теоретическая и практическая значимость. Работа носит теоретический и прикладной характер, поскольку в ней рассматриваются по существу новые математические объекты – графы и сети с нестандартной достижимостью и динамические графы и сети. Одновременно с этим на них ставятся и решаются классические задачи о кратчайших путях, случайных блуждани-
ях и потоках в сетях. Широкая практическая применимость этих задач общеизвестна, поэтому результаты, полученные в работе, могут расширить класс известных приложений теории графов и сетей, поскольку позволят учесть факторы, которые классическая теория не описывает.
Апробация работы и внедрение результатов. Основные результаты диссертации докладывались и обсуждались на семинаре кафедры алгебры и дискретной математики Южного федерального университета, на семинаре кафедры математического моделирования Южного федерального университета, на семинаре математического департамента Средне-Восточного технического университета (METU, Анкара, Турция), на семинаре института математических наук университета г. Халл (HIMSA, University of Hull, UK), международном конгрессе математиков (Мадрид, 2006), на Кишинвском и Одесском семинарах по графам и гиперграфам проф. А.А.Зыкова, на международной конференции «Математическое моделирование в экологии и численные методы» (EMMNA 99, Ростов-на-Дону, 1999), III всероссийской школе-семинаре «Математическое моделирование и биомеханика в современном университете» (Ростов н/Д, 2007), на весенней Воронежской математической школе «Понтрягинские чтения – ХХ (Воронеж, 2009), на весенней Воронежской математической школе «Понтрягинские чтения – ХХI (Воронеж, 2010), на заседаниях Ростовского математического общества, на весенней Воронежской математической школе «Понтрягинские чтения – ХХII (Воронеж, 2011), на IV-й Международной конференции «Современные проблемы прикладной математики, теории управления и математического моделирования» (Воронеж, 2011), на семинаре кафедры математической кибернетики ВМК МГУ (ноябрь, 2011).
Исследования по графам и сетям с нестандартной достижимостью были поддержаны грантом конкурсного центра Минобразования РФ по разделу естественные науки (проект Е02-01-231 Нестандартная достижимость на ориентированных графах) и грантом ведомственной программы Минобрнау-ки РФ «Развитие научного потенциала высшей школы» (подпрограмма №3, раздел 3.3 – поддержка исследований, проводимых молодыми учеными, проект 7857 – Графы и сети с нестандартной достижимостью). Последние два года работа выполнялась в рамках НОЦ «Биоинженерия и биоинформатика» ЮФУ и поддержана ФЦП «Научные и научно-педагогические кадры инновационной России на 2009-2013 годы», госконтракт №14.740.11.0006 «Создание биоинформационной технологии поиска взаимосвязанных сценариев
организации в геномах животных и человека некодирующей ДНК и кодирующей белок ДНК».
Результаты работы включены в спецкурс «Алгоритмы на графах и сетях», читаемый на факультете математики, механики и компьютерных наук ЮФУ и в учебное пособие [15, 16].
Основные положения, выносимые на защиту:
-
Новые объекты – графы и сети с нестандартной достижимостью.
-
Общая теория графов и сетей с нестандартной достижимостью, основанная на построении разверток графов и сетей с нестандартной достижимостью.
-
Методы решения задач о кратчайших путях и случайных блужданиях на графах с нестандартной достижимостью.
-
Теория потоков в сетях с нестандартной достижимостью.
-
Новые объекты - динамические графы и сети, структура которых меняется в дискретном времени и графы со связанными дугами, т.е. такими для которых нельзя говорить о пропускной способности дуги, а только о суммарной пропускной способности связанных дуг.
-
Новые результаты о динамических потоках в сетях, в том числе о всплеске потока и его связи со средним значением потока, емкостью сети и пропускной способностью ближайшего к стоку разреза.
-
Теория семейств функций Гранди ориентированных и неориентированных графов.
-
Аддитивное представление факториала и тождества для степеней натуральных чисел и их полиномиальные аналоги.
Основные результаты, полученные в работе:
-
Конструкции разверток для различных видов нестандартной достижимости и теоремы о сводимости задачи о кратчайшем пути на графе с нестандартной достижимостью к соответствующей задаче о кратчайшем пути во множество вершин на развртке.
-
Доказана сводимость немарковского процесса случайного блуждания частицы по вершинам графа с нестандартной достижимостью к марковскому процессу случайного блуждания по вершинам развертки (теоремы 2.1, 2.2, 2.3).
-
Найден предел последовательности величин максимальных потоков семейства сетей с барьерной достижимостью при неограниченном росте высоты барьеров (теоремы 3.1, 3.2).
-
Теорема о разложении динамического потока на временном интервале в сумму потоков специального вида (теорема 4.1), позволившая получить оценку сверху величины динамического потока на промежутке через величину максимального стационарного потока и длину временного промежутка (теорема 4.2).
5. Оценка сверху средней величины динамического потока через
величину максимального стационарного потока в этой сети (тео
рема 4.3)
-
Установлена связь между максимальным всплеском динамического потока в сети, емкостью сети, пропускной способностью разреза, прилежащего к стоку в виде набора неравенств (теорема 4.4)
-
Необходимые и достаточные условия того, что функция Гранди частичного орграфа является функцией Гранди исходного орграфа (теоремы 6.1, 6.2) и теорема о бесконтурной ориентации неориентированного графа, сохраняющей функцию Гранди (теорема 6.3).
-
Аддитивное представление факториала и тождества для степеней натуральных чисел и их полиномиальные аналоги (прил. 1).
Степень достоверности полученных результатов. Достоверность и обоснованность полученных в диссертационном исследовании теоретических результатов обеспечивается корректным применением математического аппарата и строгим математическим обоснованием предложенных методов и алгоритмов. Во всех случаях, когда полученные результаты являются обобщением известных, имеет место корректное вложение.
Публикации по теме исследования. Всего по теме диссертации опубликовано 36 работ, из них в изданиях из списка ВАК, рекомендованных для опубликования результатов диссертационных исследований – 12 наименований, статей в международных реферируемых изданиях – 1, монографий – 2, учебных пособий – 2
Личный вклад автора. Все результаты, изложенные в диссертации, получены либо автором самостоятельно, либо при его непосредственном ак-
тивном творческом участии. В совместных работах, опубликованных со своими учениками, автору принадлежит постановка и решение общих задач теории графов с нестандартной достижимостью и осуществление непосредственного руководства. Диссертационные работы учеников (Басангова Е.О., Логвинов С.Ю., Скороходов В.А., Петросян А.Г., Кузьминова М.В., Водолазов Н.Н.) посвящены в основном алгоритмам решения задач о кратчайших путях, случайных блужданиях, потоках в сетях на графах и сетях с конкретными видами нестандартной достижимости. В настоящей работе рассмотрена общая теория графов и сетей с нестандартной достижимостью.
Структура и объм диссертации. Работа состоит из введения, шести глав и приложения на 144 стр., список литературы содержит 90 наименований.
