Нестандартная достижимость на ориентированных графах и сетях тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

На правах рукописи

Ерусалимский Яков Михайлович

Нестандартная достижимость на ориентированных графах и сетях

Специальность 01.01.09 - дискретная математика и математическая кибернетика

Автореферат диссертации на соискание ученой степени доктора физико-математических наук

1 ?. .*ПР 2012

Ярославль - 2012

005019884

Работа выполнена в федеральном государственном автономном образовательном учреждении высшего профессионального образования «Южный федеральный университет»

Официальные оппоненты:

Сапоженко Александр Антонович, доктор физико-математических наук, профессор, Московский государственный университет, профессор

Соколов Валерий Анатольевич, доктор физико-математических наук, профессор, Ярославский государственный университет им. П.Г. Демидова, заведующий кафедрой

Язенин Александр Васильевич, доктор физико-математических наук, профессор, Тверской государственный университет, заведующий кафедрой

Ведущая организация: Воронежский государственный университет

Защита состоится «25» мая 2012 г. в 14 ч. 00 мин. на заседании диссертационного совета Д 212.002.03 при Ярославском государственном университете им. П.Г. Демидова по адресу: 150008, г. Ярославль, ул. Союзная , 144, аудитория 426

С диссертацией можно ознакомиться в библиотеке Ярославского государственного университета им. П.Г. Демидова

Автореферат разослан 2012 г.

Ученый секретарь диссертационного совета

Яблокова С.И.

Общая характеристика работы

Настоящая работа посвящена ориентированным графам с нестандартной достижимостью и некоторым смежным вопросам дискретной математики. Ключевых слов в этом предложении несколько. Во-первых, «ориентированным» - автор не разделяет суждения о том, что по-настоящему математическими объектами являются неориентированные графы. Действительно, если к графам подходить как к объектам, изучаемым методами алгебраической топологии, то этот так и есть, но в приложениях чаще встречаются и более естественны для использования именно ориентированные графы. Класс ориентированных графов более широк и интересен, в большинстве случаев неориентированный граф можно считать симметрическим ориентированным графом. Вторым ключевым словом или фразой в первом предложении является «граф с нестандартной достижимостью». Именно эти объекты мы в основном и будем рассматривать в нашей работе.

В прикладных задачах, как правило, изучается не сам граф, а процессы на нем. Большинство из них связано с перемещениями по путям на графе. В классическом определении путь - это последовательность дуг графа, в которой каждая следующая дуга начинается в вершине, в которой заканчивается предыдущая дуга пути. Соединимость одной вершины путём, ведущим из другой вершины, называется достижимостью одной вершины из другой. Три основных задачи прикладной теории графов и не только прикладной, а точнее сказать, алгоритмической теории графов связаны с достижимостью на графах. Это сама задача о достижимости и нахождении кратчайшего пути, задача о случайных блужданиях по вершинам графа и задачи о потоках в сетях. Поток можно считать перемещением (транспортировкой) вещества (материи, товаров, жидкости, энергии и т.п.) из источника в сток по путям, ведущим из источника в сток.

Когда мы говорим о графе с нестандартной достижимость, то это означает, что допустимыми на нём являются не все пути, а пути, удовлетворяющие определенному условию (это условие называется типом или видом нестандартной достижимости). Как правило, тип нестандартной достижимости возникает после того, как задано некоторое разбиение множества дуг графа, а ограничения на достижимость формулируются с помощью (в терминах) этого разбиения. Почему мы считаем, что графы с нестандартной достижимостью являются по существу новыми объектами, по сравнению с обычными графами? Во-первых, графы можно считать графами с нестандартной достижимостью (тривиальной), но главное не в этом. Как оказалось

([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 Mathematical Soc., 1956, #7, p. 48

5 Форд Jl., Фалкерсон Д. Потоки в сетях. М.: Мир, 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. Среди учёных, внесших основной вклад в развитие этого направления, необходимо назвать Г. Данцига, Е. Диница, Дж. Эдмонтса, X. Габова, А. Гольдберга, Р. Карпа, В. Кинга, Р. Тарьяна, С. Pao. Если говорить о развитии общих подходов к теории сетей, то следует особо выделить работу А. Гольдберга и С. Pao11.

Следует отметить то различие, которое имеется в понимании и подходах к теории сетей, которое существует. С точки зрения дискретной математики теория сетей занимается изучением транспортной способности сетей (классическая теория Форда-Фалкерсона, основанная на понятии допустимый поток). Второй подход к теории сетей - изучение побудительных причин наличия потока в сети, изучение закономерностей динамики таких потоков, связан в основном с приложениями сетей в других науках: теория электрических цепей, берущая свое начало от работ Г. Кирхгофа, теория гидравлических сетей, сетевая логистика, сетевые методы в экономике и финансах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. http://drops.dagstuhl.de/opus/volltexte/2009/2190

KarpKM. 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.

" 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//££ Publishing Ltd., 2006. pp.412

экономике следует отметить докторскую диссертацию А.Г. Коваленко13. В нашей работе под теорией потоков в сетях мы понимаем её как соответствующий раздел дискретной математики.

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

Поясним сказанное примером. Рассмотрим телекоммуникационную сеть. Будем интерпретировать её как граф, вершины которого соответствуют пунктам приема/ передачи информации. Дуги соответствуют каналам связи, по которым передается информация между пунктами. Известно, что в процессе передачи сигнала по каналу связи с ним могут происходить изменения - сигнал может затухать и если его уровень понизится до уровня естественного шума, то возникает его потеря. Имеется два типа основных средств борьбы с этим: пассивные и активные. Пассивные средства предполагают улучшение физических характеристик каналов, что обеспечивает более низкий уровень затухания сигнала и снижение уровня естественного шума в канале. Последним достижением в этой области являются оптоволоконные каналы связи, получившие в настоящее время широкое распространение. Активные средства предполагают повышение уровня сигнала с помощью разного рода усилителей, которые комбинируются со средствами фильтрации. Такая комбинация позволяет отфильтровать сигнал от шума и повысить его уровень. Таких активных улучшений сигнала во время его передачи по каналам связи может быть несколько, а может и не быть вовсе, все зависит от трассы, по которой передается сигнал (имеются ли на ней активные участки). Активные средства улучшения качества сигнала последнее время получили широкое распространение. Переломным моментом в развитии активных средств явился переход от аналоговых систем передачи информации к цифровым системам. Цифровые системы позволяют лучше и легче решать задачу

13 Коваленко А.Г. Развитие математических моделей и методов теории гидравлических сетей и их применение дня моделирования рассредоточенного рынка// автореферат диссертации на соискание ученой степени доктора ф,-м. наук, Москва, 2006

фильтрации сигналов от шума, а также позволяют поднимать его уровень (усиливать), не внося искажений в отфильтрованный поток информации.

В нашей модели телекоммуникационной сети возникает естественное разбиение множества дуг на три типа: пассивные или нейтральные, прохождение сигнала по которым не влияет на его качество, активные («хорошие»), прохождение сигнала по которым улучшает его качество, регрессивные («плохие»), прохождение сигнала по которым существенно снижает его уровень.

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

Современный этап развития телекоммуникаций характерен тем, что большинство дуг являются либо нейтральными, либо активными, однако полное избавление от регрессивных дуг в ближайшее время не представляется возможным. Более того - требования к качеству передачи информации возрастают. Это приводит к тому, что часть дуг из первых двух категорий приходится «переводить» в третью (моральный износ), такой перевод может быть связан и с неизбежным физическим износом.

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

Существенным при определении того, какой путь можно рассматривать, а какой путь нельзя, является не то - какие дуги участвуют в его формировании, и не то - какие дуги не участвуют. Определяющим, в нашем случае, является следующее: в какой комбинации дуги разных типов встречаются в последовательности дуг пути (улучшенный сигнал можно пропустить и через регрессивные дуги; регрессивные дуги не могут встречаться в последовательности дуг пути таким образом, что уровень сигнала понижается до недопустимого для дальнейшего прохождения уровня).

Характерной особенностью задач на графах с нестандартной достижимостью является неприменимость напрямую классических алгоритмов, поскольку все они предполагают, что все возможные пути на графе являются допустимыми. Это относится и к задаче о кратчайших путях, и к задаче о случайных блужданиях по графу, и к задаче о максимальном потоке в сети. Графы с нестандартной достижимостью - первый известный пример, когда мультиграфы (графы с кратными дугами) приходится рассматривать по существу. Задача, исходно поставленная на мультиграфе, не может быть сведена к задаче на обычном графе заменой кратных дуг на кратчайшую из них (в задаче о кратчайших путях), дугой с суммарной вероятностью перехода (в задаче о случайных блужданиях) или дугой с суммарной пропускной способностью (в потоковых задачах). Это связано с тем, что кратные дуги могут быть разных типов. В связи со сказанным мы можем определить:

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

Объект исследования - ориентированные графы и сети с нестандартной достижимостью.

Предмет исследования - задачи о кратчайших путях и случайных блужданиях и потоковые задачи на таких графах и сетях.

Гипотеза исследования. Круг приложений теории графов и класс рассматриваемых задач настолько расширились, что необходимо расширить и наши представления об исходных объектах: графах и сетях. Такое расширение должно позволить рассматривать и решать задачи, к которым раньше аппарат теории графов был неприменим.

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

Степень разработанности проблемы и новизны. Изучение графов с нестандартной достижимостью началось сравнительно недавно, первые ра-

боты в этой области принадлежат Я.М.Ерусалимскому и Е.О.Басанговой ([25, 27-29]). В работах [25, 27] рассматривались частично-ориентированные графы, т.е. такие, которые содержат ориентированные дуги и неориентированные ребра.

Рассмотрение частично-ориентированных графов в этих работах было вызвано задачей, связанной с теорией базисов в пространствах Кёте. Существенным моментом в этих работах было ограничение на множество рассматриваемых путей - неориентированные рёбра не могли встречаться на путях подряд, они должны были прореживаться дугами графа. В работе [28] было впервые сформулировано понятие «ориентированный граф со смешанной достижимостью», состоящее в следующем - множество дуг такого графа представляет собой объединение попарно непересекающихся множеств UN и 1]г. Смешанным путем на таком графе называется путь, на котором по дугам из множества Uz нельзя проходить более одного раза подряд. Граф, на котором рассматриваются только смешанные пути, мы назвали графом со смешанной достижимостью. Основным методом для решения задач на таких графах оказалось построение развёртки - вспомогательного графа, путям на котором соответствуют допустимые пути на графе со смешанной достижимостью. В последующем нами (автором настоящей работы и его учениками) было введено более широкое понятие - граф с нестандартной достижимостью.

Полученным в этой области результатам и посвящена диссертационная работа. В неё мы вынесли только наиболее общие вопросы этой теории, не рассматривая алгоритмы решения задач о кратчайших путях, случайных блужданиях и потоках, поскольку разработке и обоснованию алгоритмов для конкретных видов нестандартной достижимости были посвящены кандидатские диссертации учеников автора: Е.О. Басанговой, С.Ю. Логвинова, В.А. Скороходова, А.Г. Петросяна, М.В. Кузьминовой, H.H. Водолазова. Таким образом, все известные в настоящее время результаты в этой области принадлежат либо лично автору настоящей работы, либо получены им совместно с учениками.

Теоретическая и практическая значимость. Работа носит теоретический и прикладной характер, поскольку в ней рассматриваются по существу новые математические объекты - графы и сети с нестандартной достижимостью и динамические графы и сети. Одновременно с этим на них ставятся и решаются классические задачи о кратчайших путях, случайных блуждани-

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

Апробация работы и внедрение результатов. Основные результаты диссертации докладывались и обсуждались на семинаре кафедры алгебры и дискретной математики Южного федерального университета, на семинаре кафедры математического моделирования Южного федерального университета, на семинаре математического департамента Средне-Восточного технического университета (METU, Анкара, Турция), на семинаре института математических наук университета г. Халл (HIMSA, University of Hull, UK), международном конгрессе математиков (Мадрид, 2006), на Кишинёвском и Одесском семинарах по графам и гиперграфам проф. А.А.Зыкова, на международной конференции «Математическое моделирование в экологии и численные методы» (EMMNA 99, Ростов-на-Дону, 1999), III всероссийской школе-семинаре «Математическое моделирование и биомеханика в современном университете» (Ростов н/Д, 2007), на весенней Воронежской математической школе «Понтрягинские чтения - XX (Воронеж, 2009), на весенней Воронежской математической школе «Понтрягинские чтения - XXI (Воронеж, 2010), на заседаниях Ростовского математического общества, на весенней Воронежской математической школе «Понтрягинские чтения - XXII (Воронеж, 2011), на IV-й Международной конференции «Современные проблемы прикладной математики, теории управления и математического моделирования» (Воронеж, 2011), на семинаре кафедры математической кибернетики ВМК МГУ (ноябрь, 2011).

Исследования по графам и сетям с нестандартной достижимостью были поддержаны грантом конкурсного центра Минобразования РФ по разделу естественные науки (проект Е02-01-231 Нестандартная достижимость на ориентированных графах) и грантом ведомственной программы Минобрнау-ки РФ «Развитие научного потенциала высшей школы» (подпрограмма №3, раздел 3.3 - поддержка исследований, проводимых молодыми учеными, проект 7857 - Графы и сети с нестандартной достижимостью). Последние два года работа выполнялась в рамках НОЦ «Биоинженерия и биоинформатика» ЮФУ и поддержана ФЦП «Научные и научно-педагогические кадры инновационной России на 2009-2013 годы», госконтракт №14.740.11.0006 «Создание биоинформационной технологии поиска взаимосвязанных сценариев

организации в геномах животных и человека некодирующей ДНК и кодирующей белок ДНК».

Результаты работы включены в спецкурс «Алгоритмы на графах и сетях», читаемый на факультете математики, механики и компьютерных наук ЮФУ и в учебное пособие [15,16].

Основные положения, выносимые на защиту:

1. Новые объекты - графы и сети с нестандартной достюкимостыо.

2. Общая теория графов и сетей с нестандартной достижимостью, основанная на построении разверток графов и сетей с нестандартной достижимостью.

3. Методы решения задач о кратчайших путях и случайных блужданиях на графах с нестандартной достижимостью.

4. Теория потоков в сетях с нестандартной достижимостью.

5. Новые объекты - динамические графы и сети, структура которых меняется в дискретном времени и графы со связанными дугами, т.е. такими для которых нельзя говорить о пропускной способности дуги, а только о суммарной пропускной способности связанных дуг.

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

7. Теория семейств функций Гранди ориентированных и неориентированных графов.

8. Аддитивное представление факториала и тождества для степеней натуральных чисел и их полиномиальные аналоги.

Основные результаты, полученные в работе:

1. Конструкции разверток для различных видов нестандартной достижимости и теоремы о сводимости задачи о кратчайшем пути на графе с нестандартной достижимостью к соответствующей задаче о кратчайшем пути во множество вершин на развёртке.

2. Доказана сводимость немарковского процесса случайного блуждания частицы по вершинам графа с нестандартной достижимостью к марковскому процессу случайного блуждания по вершинам развертки (теоремы 2.1,2.2,2.3).

3. Найден предел последовательности величин максимальных потоков семейства сетей с барьерной достижимостью при неограниченном росте высоты барьеров (теоремы 3.1, 3.2).

4. Теорема о разложении динамического потока на временном интервале в сумму потоков специального вида (теорема 4.1), позволившая получить оценку сверху величины динамического потока на промежутке через величину максимального стационарного потока и длину временного промежутка (теорема 4.2).

5. Оценка сверху средней величины динамического потока через величину максимального стационарного потока в этой сети (теорема 4.3)

6. Установлена связь между максимальным всплеском динамического потока в сети, емкостью сети, пропускной способностью разреза, прилежащего к стоку в виде набора неравенств (теорема 4.4)

7. Необходимые и достаточные условия того, что функция Гранди частичного орграфа является функцией Гранди исходного орграфа (теоремы 6.1, 6.2) и теорема о бесконтурной ориентации неориентированного графа, сохраняющей функцию Гранди (теорема 6.3).

8. Аддитивное представление факториала и тождества для степеней натуральных чисел и их полиномиальные аналоги (прил. 1).

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

Публикации по теме исследования. Всего по теме диссертации опубликовано 36 работ, из них в изданиях из списка ВАК, рекомендованных для опубликования результатов диссертационных исследований - 12 наименований, статей в международных реферируемых изданиях - 1, монографий - 2, учебных пособий - 2

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

тивном творческом участии. В совместных работах, опубликованных со своими учениками, автору принадлежит постановка и решение общих задач теории графов с нестандартной достижимостью и осуществление непосредственного руководства. Диссертационные работы учеников (Басангова Е.О., Логвинов С.Ю., Скороходов В.А., Петросян А.Г., Кузьминова М.В., Водолазов H.H.) посвящены в основном алгоритмам решения задач о кратчайших путях, случайных блужданиях, потоках в сетях на графах и сетях с конкретными видами нестандартной достижимости. В настоящей работе рассмотрена общая теория графов и сетей с нестандартной достижимостью.

Структура и объём диссертации. Работа состоит из введения, шести глав и приложения на 144 стр., список литературы содержит 90 наименований.

Содержание работы

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

В главе I «Нестандартная достижимость различных видов. Кратчайшие пути на графах с нестандартной достижимостью» мы определили несколько видов нестандартной достижимости на графах, описали построение развёрток - вспомогательных графов, позволяющих решать задачу о кратчайших путях на графах с нестандартной достижимостью.

Первый вид нестандартной достижимости - смешанная достижимость.

Графы со смешанной достижимостью

Пусть G(X,U,f) - орграф. Множество дуг графа представлено следующим образом: U = UR и Uz, UR * 0, Uz Ф 0. Дуги множества UR будем называть нейтральными, а множества Uz - запрещенными.

Определение 1.2. ▲ Смешанным путем на графе G(X,U = URuUz,f) будем называть путь //:[1;/?]л, ->£/, удовлетворяющий условию:

V/ (е [1; п - 1]Л. )(М0 //(/ + 1)е^).А

Определение 1.3. Графом со смешанной достижимостью будем называть граф С(Х,и = !/„ и[/2,/), на котором допустимыми являются только смешанные пути (см. определение 1.2).

На графах со смешанной достижимостью нарушается основное свойство путей на обычных графах, которое мы называем аддитивным: «Если существует путь //Л>,, соединяющий вершину х с вершиной у, и существует

путь , соединяющий вершину у с вершиной 2, то существует путь //г,

соединяющий вершину хс вершиной г, получаемый склейкой имеющихся путей». На этих графах также нарушается экстремальное свойство кратчайшего пути: «Любой отрезок кратчайшего пути соединяющего две вершины графа является кратчайшим путем между вершинами, которые он соединяет». Это не позволяет напрямую применять для графов со смешанной достижимостью алгоритмы нахождения кратчайших путей.

Для преодоления возникших сложностей строится вспомогательный граф (развёртка) и устанавливается соответствие между множеством допустимых путей на графе со смешанной достижимостью и множеством путей на развертке.

Заметим, что «геометрия» графа со смешанной достижимостью существенно отличается от «геометрии» этого графа без ограничения на достижимость.

Опишем построение развёртки для графа со смешанной достижимостью С(Х,и = их Множеством вершин этого графа является множество Х<иХ', где X'- дубликат множества X, т.е. каждой вершине хеХ соответствует х' еX'. Если ие11я, /(и) = (х,у), на развёртке ей соответствует две дуги, первая соединяет вершину х с вершиной у, а вторая дуга начинается в вершине х' и заканчивается в вершине у. Если и е 1/., /(и) = {х,у), на развёртке ей соответствует дуга, которая соединяет вершину х с вершиной у'.

Пример 1.1. Рассмотрим граф, изображенный на рис. 1.1.

8

Рис. 1.1.

На рисунке запрещенные дуги обозначены пунктиром. Ясно, что путь, проходящий через вершины 1-7-5-6 не является смешанным, также не является смешанным путем 1-2-3-4-5-6. Единственный смешанный путь, соединяющий вершину 1 с вершиной 6 проходит через вершины1-8-4-5-6.

На рис. 1.2 приведена развёртка - С для графа рис. 1.1:

3' 4'

6'

7'

Рис. 1.2.

Имеют место теоремы: Теорема 1.1. Вершина у достижима из вершины х на графе со смешанной достижимостью С(Х,11 = и к и и г,/) тогда и только тогда, когда на развёртке С существует путь из вершины х во множество вершин {у,у'} ■

▲ Справедливость этой теоремы следует из конструкции развёртки. ▼

Если на исходном графе заданы длины дуг, то развёртку тоже считаем взвешенным графом, полагая длины её дуг равными длинам породивших их дуг исходного графа.

Теорема 1.2. Длина кратчайшего пути из вершины х в вершину у на графе со смешанной достижимостью С(Х,и = ик и112,/) равна длине кратчайшего пути из вершины х во множество вершин {у, у'} на развёртке С. Этот кратчайший смешанный путь может быть восстановлен по кратчайшему пути из вершины х во множество вершин {у, у'} на развёртке С.

Ясно, что этот кратчайший путь на графе С может быть найден с помощью алгоритма Дейкстры.

В этой главе рассмотрен ещё один вид нестандартной достижимости -магнитная, которая сильно отличается от смешанной достижимости, поскольку ограничения на множество рассматриваемых (допустимых) путей на таком графе носят уже не локальный, а глобальный характер.

Графы с накоплением неубывающей магнитности Определение 1.4. ▲ Пусть дан граф С(Х,и,<р), V = V,, и I]м, ин Г\1/м = 0. Множество ии называется множеством магнитных дуг, а и„ - множество немагнитных дуг. Пусть И - путь, состоящий из п дуг. С

каждым отрезком [кЛх (1<г<у<и) пути Ц свяжем числовую характеристику

)

Л/ (ь Л = 11 Ыт)} г*им |, (2)

т=г

равную количеству магнитных дуг этого отрезка, при этом каждая магнитная дуга считается столько раз, сколько раз она встречается в пути. Характеристика Л^О'»/) называется величиной накопленной неубывающей намагниченности на отрезке [*;./]# пути № Т

Определение 1.5. Путь № называется магнитно-накопительным путем порядка к{> 1) состоящим из п {п е N) дуг с неубывающей намагни-ченностьюностью на графе С, если выполняется следующее условие:

0т) > к)(и (Ср2 ° / о м)(т)) п им * 0) => (/фи +1)е1/м).

Другими словами, если к / -му шагу от своего начала путь М накопил намагниченность ^(0, большую либо равную к, и среди дуг, выходящих из концевой вершины г -й дуги, есть хотя бы одна магнитная, то следующая О +1) -я дуга магнитно-накопительного пути порядка к обязана быть дугой из множества им.

Определение 1.6. Граф в{Х,11 ,(р) ,и = 1)н и им „а котором рассматриваются только магнитно-накопительные пути порядка к, будем называть графом с накоплением неубывающей намагниченностью порядка к.

Для графов с накоплением неубывающей намагниченности порядка к построена развертка.

Пример 1.2. Рассмотрим граф С , изображенный на рис. 1.6. Множество магнитных дуг им = {(а,Ь),(Ь,с)} (помечены буквой «М»), множество немагнитных дуг £/„ = {(а,с),(Ь,с]),(с,с})} (помечены буквой «Н»). Порядок магнитности графа С равен к = 1. Развёртка С для графа С? изображена на рис. 1.7.

Ь

Рис. 1.6. Граф С

Рис. 1.7. Граф С

При отсутствии условия намагниченности путь {(а, 6), (6, с)} является допустимым, однако, на рис. 1.7 видно, что с добавлением условия намагниченности такой путь становится недопустимым.

Ясно, что имеют место теоремы аналогичные теоремам 1.1 и 1.2.

Завершает главу I рассмотрение ещё одного типа нестандартной достижимости - барьерной достижимости. Она также как и магнитная достижимость определяется не локально, а глобально (на отрезках пути).

Барьерная достижимость на графах

Пусть 0{Х,1],/) - граф, ^ = и и , множества £/+ и

ив попарно не пересекаются. Множество - множество нейтральных дуг, Vг

- множеством дуг, увеличивающих барьерный показатель (множество увеличивающих дуг), ив - множество дуг барьерного перехода (множество барьерных дуг).

Определение 1.7. ▲ С каждым отрезком [0;/]2 (где 0 < г < и) пути //из п дуг свяжем числовую характеристику Рр (/), определенную индуктивно следующим:

1. /?Д0) = 0.

/?„('). если ¿1(1) е II0;

2. /?^(г' + 1) = ^/?А(г') + 1, если //(г) е

0, если //(г) е V п.

Характеристика Рм(!) называется величиной накопленной энергии

на отрезке [0; г\2 пути . ▼

Определение 1.8. Графом с барьерной достижимостью высоты Ъ (к е Л7) будем называть граф С(Х,и ~иоии^ все пути //

на котором удовлетворяют условию:

М)*ив=>рм{1-\)>ь (3)

Другими словами, если к т -му шагу путь ¡л от своего начала накопил величину барьерного показателя /Зм(т — 1), большую либо равную /г, то на последующем шаге становятся допустимыми для прохождения дуги из множества ив.

Пример 1.3. На рис. 1.8 изображен граф с барьерной достижимостью. Знаком «+» помечена дута множества , буквой Ъ- дуга множества Будем считать, что Ь = 1.

а 1

-"О

3 Ь

Рис. 1.8.

Ясно, что на этом графе путь 1 —> 2 —> 3 —> 4 отсутствует, а путь 1 -^2—>3—»6—»5—>2—>3—»4является барьерным путем с высотой барьеров равной единице. Если взять барьерный показатель А = 2, то этот путь уже не является допустимым. Допустимым барьерным путем с высотой барьера 2 является путь 1-»2->3-»6->5-»2-»3->6-»5-»2-»3->4.

Для графов с барьерной достижимостью построена развёртка. Ясно, что справедливы теоремы аналогичные теоремам 1.1 и 1.2.

В гл. II. «Случайные блуждания на графах с нестандартной достижимостью» мы определяем ещё несколько видов нестандартной достижимости и рассматриваем задачу о случайных блужданиях по вершинам графов с нестандартной достижимостью. Специфика решенных задач состоит в том, что на исходном графе с нестандартной достижимостью они не являются Марковскими. Переход к вспомогательным графам позволяет сводить немарковский процесс к Марковскому. Роль памяти о предыстории блуждания выполняет сам вспомогательный граф.

В § 2.1 рассмотрена задача о случайном блуждании по вершинам графа со смешанной достижимостью.

Пример 2.1. Рассмотрим граф, изображенный на рис. 2.1. Пунктиром на нем обозначены запрещенные дуги. Будем считать, что вероятность перехода на каждой дуге и, выходящей из вершины х, определена формулой:

р(и) =

РМ

(4)

Рис. 2.1.

Развёртка графа, изображенного на рис. 2.1 приведена на рис. 2.2.

Рис.2.2. Развертка графа рис.2.1. Если на дуги вспомогательного графа перенести вероятности перехода с исходного графа, то произойдёт нарушение основного вероятностного соотношения:

(5)

(например, в вершине 1'), на этом графе появились и тупиковые вершины (например, вершина 3'). Осуществим перенормировку полученных переходных вероятностей так, чтобы выполнялось соотношение (5), для этого будем

считать, что переходные вероятности р' на дугах, выходящих из вершины х на вспомогательном графе, определены формулой:

тт- (6)

иеи+{х)

Ясно, что для графа рис. 2.2. р'((1,2))= р'((1,8'))= р'((П))=~,

Построение развёртки и указанный выше перенос на неё переходных вероятностей с исходного графа позволяет доказать следующую теорему:

Теорема 2.1. Вероятность попасть из вершины хъ вершину у на графе (7 со смешанной достижимостью за п шагов равна вероятности попасть из вершины х во множество вершин {у,у'} за п шагов на развёртке С.

В § 2.2. определен новый тип нестандартной достижимости - монотонная достижимость.

Графы с монотонной достижимостью Определение 2.1. Пусть С(Х,и,/)) - граф и и = ио и(/, и и 2 и ■ • ■ и I! т, множества и1 - непустые попарно непересекающиеся. Множество и0 будем называть нейтральным, а множества и¡, / = 1,2,.. .,т- монотонными уровня г.

Определение 2.2. Пусть путь ->£/ на графе

и¿7, и112 и-иУя,/). Свяжем с ним числовую последовательность {a¡(p)}"=l,a/(¿l) = j\/l^(i)eUJ, т.е. последовательность номеров

множеств, которым принадлежат дуги пути.

Определение 2.3. ▲ Путь на графе

С(Х,и = и{) и(/, иО', и ■ • ■ и и,„, /) будем называть монотонным, если подпоследовательность положительных элементов последовательности {о,(//)}"=| является неубывающей. Таким образом, монотонность пути означает следующее, если он на каком-то шаге прошел по дуге из множества с номером к, то на любом из последующих шагов он не может проходить по дугам множеств с номерами 1,2,..., к -1. ▼

Определение 2.4. ▲ Граф О{Х,и~и0 и[/', и£/2 и — иС^,,/), на котором допустимыми считаются только монотонные пути, будем называть графом с монотонной достижимостью. Т

Пример 2.2. Рассмотрим граф, изображенный на рис. 2.4.

3

5

о >аГ _„о 6

1 2

о

4

Рис. 2.4.

На рис 2.4. сплошными линиями обозначены дуги из множества £/0, пунктиром - дуги множества ¿7,, точечными линиями - дуги множества 1/2 ■ Ясно, что путь 1-2-3-5-6 не является монотонным путём, а путь 1-2-4-5-6 таковым является.

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

В § 2.3. введён в рассмотрение ещё один вид нестандартной достижимости, которую мы назвали вентильной.

Графы с вентильной достижимостью Определение 2.5. ▲ Пусть £/,/)) - граф

и11 =и0 и У] и[/2 и-и(/я, множества I/,- - непустые попарно непересекающиеся. Множество и0 будем называть нейтральным, а множества иI, I = 1,2,..., т вентильными уровня г. Т

Определение 2.6. ▲ Путь ц ->{/ на графе

= С/0 и ии2 и •••и С/,,,,/) будем называть вентильным, если выполнено условие

М(1)еик ^/ф'-= 1,▼ (?)

Таким образом, вентильность пути означает следующее, если он на каком-то шаге прошел по дуге из множества с номером А;-1, то на любом из по-

следующих шагов он может проходить по дугам множеств с номерами 1,2,...,*.

Определение 2.7. ▲ Граф С(Х,и = и0и1/] и1/2 и---и£/)И,/), на котором допустимыми считаются только вентильные пути, будем называть графом с вентильной достижимостью. ▼

Пример 2.2. Рассмотрим граф, изображенный на рис. 2.14.

3

Рис. 2.14.

На рис 2.14 сплошными линиями обозначены дуги из множества 110, пунктиром - дуги множества и], точечными линиями - дуги множества II2 ■ Ясно, что путь 1-2-3-5-6 не является вентильным путём, а путь 1-2-4-5-6 таковым является.

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

Завершает главу II пример бесконечного графа с вентильной достижимостью, представляющий собой конструкцию, которую мы назвали пространственно-временным фракталом. Ниже на рис 2.21 приведен пример такой структуры. Цифры около дуг - номера множеств, которым они принадлежат, дуги множества {/0 не имеют надписей, на малых фрагментах соответствующие надписи опущены. Вероятности перехода по дугам, выходящим из вершины, равны в каждый момент времени единице, деленной на количество дуг, которые доступны для прохождения в данный момент времени из данной вершины. Штриховая кривая справа означает «продолжение» конструкции вправо.

Рис. 2.21. Пространственно-временной фрактал

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

В главе III «Потоки в сетях с нестандартной достижимостью» мы начинаем изучение потоков в сетях с нестандартной достижимостью и динамических потоков в сетях. Основные трудности рассмотрения этих задач возникают из-за наличия так называемых связанных дуг, т.е. таких для которых нельзя говорить о пропускной способности дуги, а приходится говорить об их суммарной пропускной способности. Более того, нам пришлось пересмотреть базовые понятия теории потоков в сетях (поток, величина потока и т.п.), поскольку они никак не учитывали особенностей, связанных с рассмотрением графов и сетей, на которых допустимыми являются не все пути.

Приведем соответствующий пример:

Рис.3.1.

Граф со смешанной достижимостью изображён на рис. 3.1. Будем считать, что пропускная способность любой дуги равна единице, пунктирные дуги - запрещенные.

Построим развёртку этого графа.

Рис. 3.2. Развёртка графа рис.3 Л. Перенесем на полученный граф пропускные способности дуг исходного графа. Добавим фиктивный источник (0) и фиктивный сток (8). Получим сеть, изображенную на рис. 3.3.

О

О

©

8

Рис. 3.3.

Ясно, что максимальный поток на этом графе имеет величину 2. Если «вернуть» этот поток на исходный граф, то мы получим поток, который не является допустимым, поскольку на дуге, соединяющей вершину 3 с вершиной 7, этот поток имеет величину 2, а пропускная способность этой дуги равна 1.

Нейтральным дугам на развёртке соответствует по две дуги, у каждой из которых пропускная способность равна пропускной способности породившей их дуги. Это приводит к возникновению на развёртке потоков, которые не являются потоками на исходном графе. Выход из сложившейся ситуации был предложен в [16]. В этой работе введено понятие графов со связанными дугами. Связанными являются такие подмножества дуг, для каждой из которых не определена пропускная способность, вместо этого определена суммарная пропускная способность дуг из подмножества связанных между собой дуг. В нашем случае связанными являются пары дуг, полученных на вспомогательном графе из одной нейтральной дуги исходного графа. Их суммарная пропускная способность равна пропускной способности породившей их дуги. Если бы мы заранее знали - как распределить суммарную пропускную способность между связанными дугами, то задача поиска максимального потока была бы тривиальной - её нужно было бы решить на развёртке и перенести полученное решение на исходный граф.

В работе Я.М. Ерусалимского и А.Г. Петросяна [17] был предложен эвристический алгоритм «прорыва», который в большинстве случаев позволяет определить - как должны быть розданы пропускные способности по связанным дугам, чтобы возникал максимальный поток. Этот алгоритм состоит в

следующем: на вспомогательном графе находится простой путь из источника в сток. Этот путь насыщается потоком, после чего пропускные способности обычных дуг, принадлежащих этому пути, уменьшаются на величину потока, также уменьшаются суммарные пропускные способности связанных дуг, по которым проходит найденный путь. Затем дуги нулевой пропускной способности удаляются из графа, и всё повторяется заново.

Ещё более ярко указанные особенности проявляются на графах с барьерной достижимостью. Рассмотренные в § 3.1 примеры показали, что необходимо четко разобраться с понятием «поток» на графе с нестандартной достижимостью. Классическое определение потока как функции, определенной на множестве дуг, не содержит в себе никаких требований на пути, по которым транспортируется поток и, значит, не учитывает нестандартную достижимость. Определение потока на сети с нестандартной достижимостью как потока на развертке в силу наличия на ней связанных дуг тоже не совсем корректно. Приведем определения, которые лежат в основе нашего подхода к теории потоков в сетях с нестандартной достижимостью.

Определение 3.1. ▲ Пусть С(Х,и,/,с)- сеть с нестандартной достижимостью, с - пропускная способность дуг, т.е. с: II -> (0,+=о). ц - допустимый путь из источника в сток. С каждой дугой и, через которую проходит путь /и свяжем характеристику - кратность дуги и на пути //, опре-

делённую равенством:

^(«0=|л-'({и})| .Т (8)

Определение 3.2. ▲ Пусть С(Х,Ь\/,с) - сеть с нестандартной достижимостью, /у - допустимый путь из источника в сток. Потоком по пути ц будем называть такую постоянную (рм е(0,со), которая удовлетворяет условию

ум(и)-^<с(и) (9)

для любой дуги пути Т

Определение 3.3. Поток по пути ¡и называется насыщающим этот путь, если существует такая дуга пути ц, для которой в соотношении (9) выполнено равенство.

Определение 3.4. А Пусть С(Х,1/,/,с) - сеть с нестандартной достижимостью. Потоком в такой сети будем называть множество *Р, элементами которого являются пары вида {¡л\(р^), где ¡л - допустимый путь из ис-

точника в сток, (ри - поток по пути /л, при этом для каждой дуги графа выполнено условие

У уи{и)-<ри<с{и) Т. (10)

Определение 3.5. ▲ Пусть б(Х,£/,/,с) - сеть с нестандартной достижимостью, Ч* - поток в такой сети. Величиной потока 1Р на дуге и будем называть величину определенную равенством:

Аг}.

М") = т- (и)

Определение 3.6. ▲ Пусть С(Х,С/,/,с) - сеть с нестандартной достижимостью, у - источник, /- сток, У - поток в такой сети. Величиной потока ¥ будем называть характеристику

<Рт= 1<М")> (12)

ие£/_(0

равную суммарному потоку по всем дугам, заканчивающимся в стоке. Т

Определение 3.7. Максимальным потоком в сети с нестандартной достижимостью называется такой поток Ч/тах, для которого выполнено

и», =шахюш (13)

т тшах 1

В случае графов и сетей с нестандартной достижимостью меняется не только такое базовое понятие как «поток», но и понятие «разрез».

Определение 3.8. А Пусть С(Х,г/,/,с) - сеть с нестандартной достижимостью, 5 - источник, г - сток, Ч'тах - максимальный поток в такой сети. Разрезом сети будем называть такое подмножество дуг графа, удаление которого разрывает все пути потока *Ртах. Пропускной способностью разреза будем называть величину потока через этот разрез Т

Заметим, что таким образом определенный разрез может вообще не являться разрезом в обычном понимании, поскольку пути, которые не являются допустимыми, он может и не разрывать.

Завершает главу параграф 3.3, в котором рассмотрено семейство сетей с барьерной достижимостью (й - высота барьеров сети):

и = и0 и Щ и ив, /, /г)}, Л е N. - источник, / - сток,

1*1 <00, \и\«х>.

Для каждой сети семейства можно говорить о её максимальной пропускной способности (2>тах(Л), тогда мы имеем числовую последовательность |(зтах (Л)}, Л е Л'. Доказаны теоремы:

Теорема 3.1. Для любого семейства сетей с барьерной достижимостью имеет место:

<Рт ах (0 > 4>т ах (2) > ••• > (/)>••• (14)

Теорема 3.2.

Пусть {(?(Х,С/ = ио<ии^ии д./.Л^ЛеЛ^у-источник,I-сток

семейство сетей с барьерной достижимостью, тогда

{О, если множество безбарьерных путей пусто;

максимальному потоку в сети, протекающему через оезоарьерные пути.

В главе IV «Динамические потоки в сетях» мы рассматриваем задачи о динамических потоках, т.е. таких, которые могут меняться в дискретном времени. В ней речь не идет о нестандартной достижимости, но техника рассмотрения динамических потоков (временная развертка графа) очень похожа на технику, используемую в случае нестандартной достижимости. В этой главе нами доказана теорема о разложении динамического потока:

Теорема 4.1. Пусть <р(и,1) динамический поток в сети С(Х,и,/,с), равный нулю на всех дугах сети при КО, тогда для произвольного TeN, существуют такие потоки (р{(и,!), (р2{и,1), для которых выполнены следующие условия:

1. Потоки #>¡(¡/,7), ср2(и,() равны нулю на всех дугах сети при к 0;

2. Поток <р\ (г;,/) равен нулю на всех дугах графа при Г>Т;

3. ф,г)=Г(я4/б[0;Г];

4. К(<р2,г) = 0,/е[0;Г];

5. <р(и,1) = <р1(и,г) + ф2(и,1),

Г2

Здесь У(<р,[1\',Т2])= 2 2 (•?(<?,/), т.е. суммарный поток 1=Т1иеи_(г)

приходящий в сток за временной промежуток [Г,;Г2].

Обозначим через утах величину максимального стационарного потока сети. Доказана оценка величины динамического потока:

Теорема 4.2. Пусть <р(и,!) динамический поток в сети £7(Х,£/,/,с) равный нулю на всех дугах сети при с<0, тогда для произвольного Т е N имеет место оценка

ф,[0;Г])<утах-Г. (14)

Всплеском потока будем называть такое значение потока, которое превосходит утах. Обозначим через н(О) - максимальный всплеск в сети, а через с(в) - емкость сети, т.е. максимальное количество «вещества», которое может находиться в сети одновременно в результате действия какого-то динамического потока, тогда справедлива теорема: Теорема 4.3. Имеют место следующие оценки:

1. w(G)>Vmm;

2. м<С)< 1ф);

3. м/((})<Е{0);

4. е(в)< 1ф).

и^и

В главе V «Динамические графы и сети» мы вводим в рассмотрение новые объекты - динамические графы, структура которых меняется в дискретном времени. В определении динамического графа присутствует функция активности дуг, которая и определяет изменяющуюся во времени структуру графа. Показано, что динамические графы также являются графами с нестандартной достижимостью. Этот вид нестандартной достижимости принципиально отличается от рассмотренных до этого тем, что для него отсутствует разбиение множества дуг графа. Вспомогательный граф для этого вида достижимости представляет собой временную развёртку и уже по этой причине является бесконечным графом. Завершает эту главу рассмотрение периодических динамических графов, для которых временная развертка является лишь формально бесконечным графом.

В Главе VI «Функции на графах» мы рассмотрели семейства функций Гранди ориентированных и неориентированных графов. Доказанные в этой главе утверждения являются необходимыми и достаточными и позволяют находить эти семейства. Они являются обоснованием алгоритмов нахождения этих семейств.

Теорема 6.1. Пусть g - функция Гранди графа С(Х,Г), содержащего контуры, тогда существует такой бесконтурный частичный граф С(Х,Г') , имеющий туже самую функцию Гранди g.

Следствие из теоремы 6.1. Пусть g - функция Гранди графа в(Х,Т), содержащего контуры, тогда существует максимальный по вложению

бесконтурный частичный граф С(Х,Г') , имеющий ту же самую функцию Гранди ^.

Теорема 6.2. Пусть g - функция Гранди частичного графа С(Х,Т') графа С(А',Г). Для того, чтобы g была функцией Гранди графа С(Х,Т) необходимо и достаточно, чтобы для любых двух вершин .г, у несоединенных дугой на графе С(Х,Г') и соединенных дугой на графе С(Х,Г) выполнялось условие:

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

Теорема 6.3. Пусть С(Л\Г) - неориентированный граф, g - его функция Гранди, тогда существует такая ориентация его дуг, что полученный ориентированный граф не содержит контуров и g является функцией Гранди полученного ориентированного графа (причём единственной).

В приложении 1 «Некоторые сведения о конечных множествах в 2 и Ш содержатся сведения о строении конечных множеств в 2 и N необходимые для рассмотрения динамических периодических графов, а также некоторые тождества для степеней чисел и факториалов, содержащие биномиальные коэффициенты, в том числе аддитивное представление для факториала.

Теорема П. 1. Пусть а<Ь, а,Ъ е Z (Л'), тогда

Теорема П. 1 означает, что в 2 и N, фактически, не существует открытых или полуоткрытых промежутков.

Теорема П. 2. Любое непустое ограниченное подмножество А в 2 ( И) представляет собой замкнутый промежуток или конечное объединение попарно непересекающихся замкнутых промежутков, т.е.

1=1

Определение П. 1. Характеристику 1{А), фигурирующую в формуле (16) назовем числом связности множества А.

Теорема П.З. Для любого А - ограниченного подмножества (А с \тА;п ,\) множества 2 (Л') справедлива оценка:

£(х) * ЯМ •

(М),¥ =[я;&)Л, =(0;б]д: =[а + 1;6-1]Л.) '

(15)

(16)

1(А)<

+ 1 (17)

"а ~ тл 2

Теорема П.4. Для любых ограниченных попарно непересекающихся подмножеств Л,-, (г = 1,2,...,К) множества 1 {Я) имеет место равенство:

{у^Фй). (18)

Теорема П.5. Для любого пеЛ' имеют место равенства:

пт = £ (-1)м С„ (п - 0", 1 < т < п -1.

¿=1

Теорема П.6. Для любого п е Л' имеет место:

и!=и"-1(-1)нс;(»-о".

1=1

Теорема П.7. Для любого п е N и любого к € имеет место равенство:

п\ = {п + к)п -с\-{11 + к-\)п +с1 -{п + к-2)"-

...+и)" • с»- (к+о" = Д(-1)' • 4 • (И+к- о«. (19)

Утверждению теоремы П.7 можно придать следующий «функциональный» смысл. Рассмотрим многочлены, 1п(х), заданные формулами:

= (20)

1=0

тогда имеет место следующая теорема.

Теорема П. 8. Многочлен 1п(х)принимает в точках п,п + \,п + 2,■■■

одно и тоже значение равное и!, т.е.

и! =/11(и) = /,(и + 1) = /.(я + 2) = - . (21)

Из этой теоремы следует, что имеет место, тождество:

И¡=¿(-1)'<.(*-;)" V*.

1=0

Теорема П. 9. Для любых п,к <е А', хеН (С) имеет место равенство:

= С, .(х-1 У-С1к - (х-2)" н— + (-1)"+*~' ■С::11(х-(п + к)У. (22) Теорема П.10. Для любых г е 2, т,к е Ы, 1 < к < т -1 имеет место равенство:

= С\- (г -1)* - С; • (г - 2)к + • ■ ■■ + (-1Г"1 • С; (г - т))'. (23)

Публикации автора по теме диссертации

Публикации в изданиях из перечня ВАК РФ российских рецензируемых научных журналов:

1. Ерусалимский Я.М, Логвинов С.Ю. Некоторые задачи достижимости на графах с ограничениями на прохождения по дугам// Известия вузов. Северо- Кавказский регион. Ест.науки.1996.№2(94).С. 14-17

2. Ерусалимский Я.М. Общий метод решения задач о достижимости на ориентированных графах// Известия вузов. Северо-Кавказский регион. Ест. Науки. 2000. №3. С. 62-63

3. Ерусалимский Я.М. Отображения конечных множеств и треугольник Паскаля// Известия вузов. Северо-Кавказский регион. Ест. Науки. 2001. Математическое моделирование. С. 68-69

4. Ерусалгшский Я.М., Скороходов В.А. Графы с вентильной достижимостью. Марковские процессы и потоки в сетях// Известия вузов. Северо-Кавказский регион. Ест. Науки. 2003. №3. С. 3-5

5. Ерусалимский Я.М., Скороходов В.А. Достижимость на графах с условиями затухания и усиления// Известия вузов. Северо-Кавказский регион. Ест. Науки. 2004. Математика и механика сплошной сре-ды.С.110-112

6. Ерусалимский Я.М., Скороходов В.А. Общий подход к нестандартной достижимости на ориентированных графах// Известия вузов. СевероКавказский регион. Ест. Науки. 2005 .Псевдодифференциальные уравнения и некоторые проблемы математической физики. С. 64 -67

7. Ерусалимский Я.М. Биномиальные коэффициенты в тождествах для натуральных чисел, факториалов и многочленов// Известия вузов. Северо-Кавказский регион. Ест. Науки. 2008. №5(147). С. 27-29

8. Ерусалимский Я.М., Светлов Г.Г. Бимосты, библоки, точки бисочле-нения орграфов //Кибернетика. 1980. №1. С. 37-39

9. Ерусалимский Я.М. Натанзон Л.В. Графы бимостов, библоков и точек бисочленения //Известия вузов. Северо-Кавказский регион. Ест.науки. 1998. №4. С. 9-12;

10. Ерусалимский Я.М., Водолазов H.H. Нестационарный поток в сети/ /Вестник ДГТУ. 2009. т.9, №3. С. 402-409

11. Ерусалгшский Я.М., Водолазов H.H. Максимальный всплеск в сети и максимальный объём сети// Известия вузов. Северо-Кавказский регион. Ест. науки. 2010. № 6. С. 9-13;

12. Ерусатшский Я.М. Потоки в сетях с нестандартной достижимостью// Известия вузов. Северо-Кавказский регион. Ест. науки. 2012. № 1. С.5-7

Статьи в реферируемых международных изданиях:

13 .Erusalimsky I.M. Family of Grandy functions for oriented graphs// Turkish Journal of Mathematics. 1995. v.19, №3. P.269-273 Монографии, учебники и учебные пособия:

14. Ерусатшский Я.М. Графы с нестандартной достижимостью: задачи, приложения/Скороходов В.А., Петросян А.Г. Кузьминова М.В. /Ростов н/Д: Южный федеральный ун-т, 2009.-195 с.

15. Ерусатшский Я.М. Нестандартная достижимость на ориентированных графах. Модели и алгоритмы/Скороходов В./ LAMBERT Аса-demic Publishing (LAP , Saarbrücken, Germany), 2010. 188 р., ISBN 9783-8433-0592-1

16. Ерусалимский Я.М. Дискретная математика: теория, задачи, прило-жения//М.: «Вузовская книга», 1998.- 280 с.

17. Ерусатшский Я.М. Дискретная математика: теория, задачи, приложения/ 5-е изд. перераб. и дополи. //М.: Вузовская книга, 2002,-268 с.

Статьи в приложениях к изданиям из перечня ВАК РФ российских рецензируемых научных журналов:

18. Ерусалимский Я.М., Скороходов В.А. Прибыль от потоков с обратной связью в орсетях с ограничениями на достижимость// Известия вузов. Северо-Кавказский регион. Ест. науки. 2003. Приложение №8. С.3-8

19.Ерусалимский Я.М, Скороходов В.А. Потоки в сетях со связанными дугами// Известия вузов. Северо-Кавказский регион. Ест. науки. 2003. Приложение №8. С. 9-12

20. Ерусатшский Я.М., Петросян А.Г. Случайные процессы в сетях с биполярной магнитностью//Известия вузов. Северо-Кавказский регион. Ест. науки. 2005. Приложение №11. С.10-16

Материалы международных и всероссийских конференций:

21. Ерусалимский Я.М. Биномиальные коэффициенты в тождествах для натуральных чисел// Современные методы теории краевых задач. Материалы воронежской весенней математической школы «Понтрягин-ские чтения - XVII»,- Воронеж: ОАО «Центральное Черноземное книжное издательство», 2006. С. 63-64

22. Erusalumskiy Y.M. Binomial Coefficients in Equalities for Natural Numbers // International Congress of Mathematicians, Madrid 2006, Abstracts. p.480

23. Ерусалимский Я.M., Кузьмипова М.В. Динамические периодические графы // Математическое моделирование и биомеханика в современном университете. Труды III всероссийской школы-семинара, Из-во «Терра Принт», Ростов н/Д, 2007. С.39-40

24. Ерусалимский ЯМ., Водолазов Н.Н. Нестационарный и случайный поток в сети// Материалы Воронежской весенней математической школы «Понтрягинские чтения - XX, Из-во ВГУ, Воронеж, 2009. С. 56-57

25. Ерусапшский Я.М., Водолазов Н.Н. NP-полнота задачи нахождения максимального потока в графах с дополнительными ограничениями на достижимость// Современные методы теории краевых задач: материалы Воронежской весенней математической школы «Понтрягинские чтения - XXI», Воронеж: ВГУ, 2010 (доп. выпуск). С.14-15

26. Ерусалимский Я.М., Водолазов Н.Н. Полиномиальные алгоритмы нахождения максимального потока в сетях с некоторыми видами нестандартной достижимости// Современные методы теории краевых задач: материалы Воронежской весенней математической школы «Понтрягинские чтения - XXII», Воронежский государственный университет, Московский государственный университет им. М.В. Ломоносова, математический институт им. В.А. СтекловаРАН, - Воронеж: Издательско-полиграфический центр Воронежского государственного университета. 2011. С. 62-63

27. Ерусалимский Я.М. Пространственно-временные фракталы //материалы IV международной конференции «Современные проблемы прикладной математики, теории управления и математического моделирования», Воронеж: Издательско-полиграфический центр Воронежского государственного университета. 2011. С. 62-63

Другие публикации:

28. Ерусалимский Я.М., Басангова Е.О. Смешанная достижимость на частично-ориентированных графах//Деп. В ВИНИТИ, № 5892-82

29. Ерусалимский ЯМ. О функции Гранди графа// Деп в ВИНИТИ, № 1576-81

30. Ерусалимский ЯМ., Басангова Е.О. Смешанная достижимость на частично-ориентированных графах// Вычислительные системы и алгоритмы, Ростов н/Д.: ИРУ, 83. С. 19-24

31. Ерусалимский Я.М., Басангова Е.О. Частично-ориентированные графы и различные виды смешанной достижимости // Алгебра и дискретная математика, Элиста.: 1985. С. 70-75

32. Ерусалимский Я.М. Эйлеровость графов со смешанной достижимостью// Модели, графы и алгебраические структуры, Элиста, 1989 . С. 45-48

33. Ерусалимский Я М Смешанная достижимость на графах (общий подход). Эйлеровость графов со смешанной достижимостью // ВИНИТИ, № 2640-В88

34. Ерусалимский Я.М. Пути с задержками в вершинах на орграфах// Дискретные модели и структуры, Элиста, 91, - С. 57-62

35. Ерусалимский Я.М.,Гаряева С.А. О функции Гранди орграфов и ядрах его подграфов// Модели и дискретные структуры, Элиста, 93. С. 32-37

36. Ерусалимский Я.М., Водолазов H.H. Поток на графах с ограничениями на достижимость// Труды научной школы И.Б.Симоненко. Ростов-на-Дону: Изд-во ЮФУ, 2010. С. 44-57

Подписано в печать 16.02.2012 г. Формат 60*84 7|б • Бумага офсетная. Печать офсетная. Усл. печ. л. 2,09. Уч.-изд. л. 1,62. Тираж 150 экз. Заказ № 2213.

Отпечатано в типографии ЮФУ. 344090, г. Ростов-на-Дону, пр. Стачки, 200/1 .Тел. (863) 247-80-51.

Введение.4 стр.

Глава I. Нестандартная достижимость различных видов. Кратчайшие пути на графах с нестандартной достижимостью.18 стр.

§1.1. Основные определения.18 стр.

§ 1.2. Смешанная достижимость на орграфах.20 стр.

§ 1.3. Магнитная достижимость на орграфах.24 стр.

§ 1.4. Барьерная достижимость на графах.28 стр.

1. Адельсон-Вельский Г.М., Диниц Е.А., Карзанов A.B. Потоковые алгоритмы //М.: Наука. 1975

2. Ахо А. Построение и анализ вычислительных алгоритмов / А. Ахо, Дж. Хопкрофт, Дж. Ульман. // -М.: Мир, -1979, 536с.

3. Басакер Р. Конечные графы и сети / Р. Басакер, Т. Саати; пер. с англ.// -М.:Наука, 1973.-368с.

4. Басангова Е.О. Алгоритм нахождения максимального потока в частично-ориентированной сети / Е.О. Басангова, Я.М. Ерусалимский // Дискретные структуры и их приложения. -Элиста: КГУ, -1988. С.23-28.

5. Басангова Е.О. Различные виды смешанной достижимости / Е.О. Басангова, Я.М. Ерусалимский // Алгебра и дискретная математика: сб. -Элиста: КГУ. -1985. С.70-75.

6. Басангова Е.О. Смешанная достижимость на частично-ориентированных графах / Е.О. Басангова, Я.М. Ерусалимский // Вычислительные системы и алгоритмы: сб. -Ростов-на-Дону: РГУ, -1983. С.135-140.

7. Басангова Е. О. Смешанная достижимость на частично-ориентированных графах./Е.О. Басангова, Я.М. Ерусалимский// Деп. в ВИНИТИ. -1982. №5892-82.

8. Водолазов H.H. Об особенностях потока в сетях с барьерной достижимостью // Вестник ДГТУ. -2008 -Т.8. -№2 (37). С. 127-136.

9. Водолазов H.H. Об особенностях потока в сетях с барьерной достижимостью // Современные методы теории краевых задач: материалы Воронежской весенней математической школы «Понтрягинские чтения-XIX». Воронеж: ВГУ, 2008. - С.64-66.

10. Диниц Е.А. Метод поразрядного сокращения невязок и транспортные задачи.// Исследования по дискретной математике. -М.:Наука, -1973.

11. Евстигнеев В.А. Применение теории графов в программировании.//-М.: Наука, 1985.

12. Ерусалимский Я.М. Графы с вентильной достижимостью. Марковские процессы и потоки в сетях. / Я.М. Ерусалимский, В.А. Скороходов // Изв. вузов. Сев-Кав. регион. Естественные науки. -2003. -№2. С.3-5.

13. Ерусалимский Я.М. Графы с нестандартной достижимостью. Задачи, приложения: моногр. / Я.М. Ерусалимский, В.А. Скороходов, М.В. Кузьминова, А.Г. Петросян// -Ростов-на-Дону: ЮФУ, 2009. 195с.

14. Ерусалимский Я.М. Динамические периодические графы / Я.М. Ерусалимский, М.В. Кузьминова. // Математическое моделирование и биомеханика в современном университете: тр. III-й всероссийской школы-семинара. Ростов-на-Дону: Терра Принт, 2007. - С.39-40.

15. Ерусалимский Я.М. Дискретная математика: теория, задачи, приложения. 4-е издание. //-М.-Вузовская книга, 2001. 280с.

16. Ерусалимский Я.М. Достижимость на графах с условиями затухания и усиления / Я.М. Ерусалимский, В.А. Скороходов // Изв. вузов. Сев.-Кав. регион. Естественные науки. -2004. Спецвыпуск. Математика и механика. С. 110-112.

17. Ерусалимский Я.М. Многопродуктовые потоки в сетях с нестандартной достижимостью. / Ерусалимский Я.М., Петросян А.Г. // Изв. вузов. Сев.-Кав. регион. Естественные науки. Прил. -2005. -№6. С.8-16.

18. Ерусалимский Я.М. Некоторые задачи достижимости на графах с ограничениями. / Я.М. Ерусалимский, С.Ю. Логвинов // Изв. вузов. Сев.-Кав. регион. Естественные науки. -1996. -№2. С.14-17.-L

19. Ерусалимский Я.М. Бимосты, библоки, точки бисочленения орграфов /Ерусалимский Я.М., Светлов Г.Г.//Кибернетика №1(1980), стр.37-39

20. Ерусалимский Я.М. Графы мостов, блоков и точек сочленения. Графы бимостов, библоков и точек бисочленения/Ерусалимский Я.М., Натанзон Л.^//Известия вузов.Северо-Кавказский регион. Ест.науки, 1998, №4, с

21. Ерусалимский Я.М. Нестационарный и случайный поток в сети/ Я.М. Ерусалимский, H.H. Водолазов // Современные методы теории краевых задач: материалы Воронежской весенней математической школы «Понтрягинские чтения-ХХ». -Воронеж: ВГУ, 2009. С.56-57.

22. Ерусалимский Я.М. Нестационарный поток в сети / Я.М. Ерусалимский, H.H. Водолазов // Вестник ДГТУ. -2009. -Т. 9. -№3(42). С.402-409.

23. Ерусалимский Я.М. Потоки в сетях со связанными дугами / Я.М. Ерусалимский, В.А. Скороходов //Изв. вузов. Сев.-Кав. регион. Естественные науки. -2003; прил. № 8. с.9-12.

24. Ерусалимский Я.М. Прибыль от потоков с обратной связью в орсетях с ограничениями на достижимость / Я.М. Ерусалимский, В.А. Скороходов // Изв. вузов. Сев.-Кав. регион. Естественные науки. Прил. -2003. -№8. -С.3-8.

25. Ерусалимский Я.М. Случайные процессы в сетях с биполярной магнитностью / Я.М. Ерусалимский, А.Г. Петросян // Изв. вузов. Сев.-Кав. регион. Естественные науки. Прил. -2005. -№11. С. 10-16.

26. Ерусалимский Я.М. Эйлеровость графов со смешанной достижимостью // Модели, графы и алгебраические структуры: сб. -Элиста, -1989. С.45-48.eí ib int in ti ■■ iiiiii h i на i in tm n ■■ ■■ i ■ ■ i

27. Ерусалимский Я. M. Дискретная математика: теория, задачи, приложения//М.: Вузовская книга, 4-е издание. 2001.- 280с.

28. Ерусалимский Я.М. Дискретная математика для биоинформа-тиков//Ростов н/Д: Изд-во ЮФУ. 2011, 122с.

29. Зыков A.A. Основы теории графов. //-М.: Вузовская книга , 2004. -664 с.

30. Кристофидес Н. Теория графов. Алгоритмический подход// -М.:Мир, 1978.-432с.

31. Кузьминова М.В. Динамические периодические графы. / М.В. Кузьминова // Современные методы теории краевых задач: материалы Воронежской весенней математической школы «Понтрягинские чтения XVIII». -Воронеж, -2007. С.97-98.

32. Кузьминова М.В. Ограниченные магнитные достижимости на ориентированных графах // Изв. вузов. Сев.-Кав. регион. Естественные науки. Прил. -2006. -№6. с.12-26.

33. Ope О. Теория графов. 2-е изд. // -М.: Наука, 1980. 336с.

34. Петросян А.Г. Многопродуктовые потоки в сетях с ограничениями на достижимость // Математические методы в современных и классических моделях экономики и естествознания: сб. -Ростов-на-Дону, -2005.С.136-138.

35. Петросян А.Г. Потоковая задача в многопродуктовых сетях с нестандартной достижимостью // Современные проблемы математического моделирования: сб. -Ростов-на-Дону, -2005. С.334-340.

36. Петросян А.Г. Потоки в сетях с биполярной достижимостью// Изв. вузов. Сев.-Кав. регион. Естественные науки. Прил. -2006. -№3. С.32-37.

37. Применение теории графов в химии/под ред. Н.С. Зефирова и С.И. Кучанова/'/Новосибирск: Наука, 1988

38. Рейнгольд Э., Нивергельд Ю., Део Н. Комбинаторные алгоритмы. Теория и практика// -М.: Мир, 1980

39. Самуйлов К.Е., Чукарин A.B. К расчету плана маршрутизации сети системы сигнализации №7 // Системы телекоммуникаций и моделирование сложных систем. -М.: ПАИМС, 2001

40. Свами М. Графы, сети и алгоритмы / М. Свами, К. Тхуласираман/ пер. с англ. М.:Мир, 1984. - 455с.

41. Скороходов В.А. Устойчивость и стационарное распределение на графах с нестандартной достижимостью // Изв. вузов. Сев.-Кав. регион. Естественные науки. -2007. -№4. С. 17-21.

42. Скороходов В.А. Графы с магнитной достижимостью. Марковские процессы и потоки в сетях//Деп. в ВИНИТИ. -2003. №410-В2003.

43. Скороходов В.А. Случайные блуждания и потоки в сетях с магнитной достижимостью // Модели и дискретные структуры: сб. -Элиста, -2002. -С.93-100.

44. Солтан П.С., Замбицкий Д.К., Присакару К.Ф. Экстремальные задачи на графах и алгоритмы их решения//Кишинев: Штиинца, 1973

45. Форд Л. Р. Потоки в сетях. / JI. Р. Форд, Д.Р. Фалкерсон//; пер. с англ. -М.:Мир, 1966.-276с.

46. Харари Ф. Теория графов. //—М.: Мир, 1973. 300с.

47. Химические приложения топологии и теории графов/под. ред. Р.Кинга, пер. на русск. под ред. Ю.А.Жданова//М.: Мир, 1978

48. Ahuja R. K. A fast and simple algorithm for the maximum flow problem. / R.K. Ahuja, J.B. Orlin. // Oper. Res. -1989. -No.37. pp.748-759.

49. Ahuja R. K. Improved time bounds for the maximum flow problem. / R.K. Ahuja, J.B. Orlin, R.E. Tarjan. // SIAM J. Copmut. -1989. -No. 18. pp.939954.

50. AlonN. Generating pseudo-random permutations and maximum flow algorithms. / N. Alon // Inf. Proc. Lett. -1990. -No.35. pp.201-204.

51. Aronson J.E. A survey of dynamic network flows. / J.E. Aronson // Annals of Operations Research. -No. 20. -1989. pp.1-66.

52. Bang-Jensen J., Gutin G. Digraphs: Theory, Algoritms and Applications//London; Berlin; Heidelberg; New York; Barcelona; Hong Kong; Milan; Singapore; Tokyo: Springer, 2000

53. Dantzig G.B. Application of the simplex method to a transportation problem. / G.B. Dantzig // In Activity Analysis and Production and Allocation. -New York: Wiley, 1951.-pp. 359-373.

54. Dijkstra E.W. A Note in two problems in connection with graphs, Numtrische Mathematic ,1959, #1, p.269

55. Dinic E.A. Algorithm for Solution of a Problem of Maximum Flow in Networks with Power Estimation. / E.A. Dinic // Sov. Math. Dokl. -1970. -Noll, -pp.1277-1280.

56. Edmonds J. Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems. / J. Edmonds, R.M. Karp //Journal of the Association for Computing Machinery. Vol. 19. - No. 2, -1972. - pp.248-264.

57. Even S. On the Complexity of Timetable and Multicommodity Flow Problems. / S. Even, A. Itai, A. Shamir. // SIAM J. Comput. -Vol. 5. -No. 4. -1976. pp.691-703.

58. Ford Jr. L.R. Maximal flow through a network. / L.R. Ford Jr., D.R. Fulkerson. // Canad. J. Math. -1956. -No. 8. pp.399-404.

59. Ford L.R. Constructing Maximal Dynamic Flows from Static Flows. / L.R. Ford, D.R. Fulkerson // Operations Research. -1958 -Vol.6 pp.419-433.

60. Gabow H.N. Scaling algorithms for network problems. / H.N. Gabow // J. Comput. Syst. Sei. -1985. -No.31. -pp.148-168.

61. Galiil Z. An 0(EV log2 V) algorithm for the maximal flow problem. / Z. Galiil, A. Naamad. // J. Comput. Syst. Sei. -1980. -No.21. pp.203-217.5 2

62. Galil Z. An 0(F3£3) algorithm for the maximal flow problem. / Z. Galil // Acta Inf. -1980. -No.14. -pp.221-242.

63. Goldberg A. V. A new approach to the maximum-flow problem. / A.V. Goldberg, R.E. Tarjan. //J. ACM. -1988. -Vol.35. -No.4. pp.921-940.

64. Goldberg A. V. A New Approach to the Maximum-Flow Problem. / A.V. Goldberg, R.E. Tarjan // Journal of the Association for Computing Machinery. -Vol.35. -No. 4. -1988. pp.921-940.

65. Goldberg A. V. A new max-flow algorithm. / A.V. Goldberg // Tech. Rep. MIT/LCS/TM-291, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, Mass., Jan. 1985.

66. 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.

67. Golombic M.C. Algorithmic Graph Theory and Perfect Graphs//New York: Academic Press, 1980

68. Grady L., Polimeni J. Discrete Calculus: Applied analysis on Graphs for Computational Science// Springer Publishig Company, Inc., NY, 2010, p. 366

69. Graves S.C. A Minimum Concave-Cost Dynamic Network Flow Problem with an Application to Lot-Sizing. / S.C. Graves, J. B. Orlin // Networks -Vol.15. -1985 -pp.59-71.

70. Helmberg C. Network Models with Convex Cost Structure like Bundle Methods. / C. Helmberg // Models and Algorithms for Optimization in Logistics, Dagstuhl Seminar Proceedings. http://drops.dagstuhl.de/opus/volltexte/2009/2190

71. 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.

72. 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.

73. 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.

74. King V. A faster deterministic maximum flow algorithm. / V. King, S. Rao, R. Tarjan. //J. Algorithms. -1994. -No. 17. -pp.447-474.

75. Kruskal J.B. On the shortes spannig subtree of a graph and the traveling salesman problem, Proc. American Mathematical Soc., 1956, #7, p. 48

76. Lewis T. Network Science: Theory and Applications// Wiley Publ., Hoboken, NJ, 2009. p. 524

77. Lawler E.L. Combinatorial optimization: networks and matroids. / Lawler E.L. -New York: Holt, Rinehart and Winston, 1976. -p.374.

78. Malhorta V.M. An 0(\ V |3) algorithm for finding maximum flows in networks. / V.M. Malhorta, Pramodh Kumar M., S.N. Maheshwari // Inf. Process. Lett. -1978. -No.7. pp.277-278.

79. Newman M. Networks: an Introduction//Oxford University Press, Inc., New York, NY,2010. p.720

80. NingXuanxi. The Blocking Flow Theory and its Application to Hamiltonian Graph Problems. / Ning Xuanxi, Ning Angelika. -Germany, Aachen: Shaker Verlag GmbH, 2006. 249p.

81. Orlin J.B. Maximum-throughput dynamic network flows. / J.B. Orlin // Math. Progr. -1983. -Vol.27, -pp.214-231.

82. Phillips S. Online load balancing and network flow. / S. Phillips, J. Westbrook. // In Proceedings of the 25th Annual ACM Symposium on Theoryof Computing (San Diego, Calif., May 16-18). ACM, New York, 1993. -pp.402-411.

83. Skutella M. An Introduction to Network Flows Over Time. / M. Skutella / Research Trends in Combinatorial Optimization. Berlin: Springer Berlin Heidelberg, -2009. pp.451-482.

84. Sleator D.D. A data structure for dynamic trees. / D.D. Sleator, R.E. Tarjan. / J. Comput. Syst. Sci. -1983. -No.26. pp.362-391.

85. Tarjan R.E. A simple version of Karzanov's blocking flow algorithm // Oper. Res. Lett. -1984. -No.2. -pp.265-268.

86. Ерусалимский Я.М. О функции Гранди орграфов и ядрах его подграфов /Гаряева С.А./ Модели и дискретные структуры, Элиста,93, с.32-37132