Разработка и исследование методов решения экстремальных задач на графах и сетях с ограничениями на достижимость тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат наук Ерусалимский, Яков Михайлович

• Ерусалимский, Яков Михайлович
• кандидат наук
• 2015

Оглавление диссертации кандидат наук Ерусалимский, Яков Михайлович

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ

1. ОГРАНИЧЕНИЯ НА ДОСТИЖИМОСТЬ РАЗЛИЧНЫХ ВИДОВ, КРАТЧАЙШИЕ ПУТИ НА ГРАФАХ С ОГРАНИЧЕНИЯМИ НА ДОСТИЖИМОСТЬ

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

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

ЬЗ-Магнитная достижимость- на-орграфах ..--

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

1.5. Обсуждение результатов главы 1

1.6. Выводы по главе 1

2. СЛУЧАЙНЫЕ БЛУЖДАНИЯ НА ГРАФАХ С ОГРАНИЧЕНИЯМИ НА ДОСТИЖИМОСТЬ

2.1. Случайные блуждания на графах со смешанной достижимостью

2.2. Случайные блуждания на графах с монотонной достижимостью

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

2.4. Случайные блуждания по графу-решётке

2.5.Заключение к главе 2

2.6. Выводы по главе 2

3. ПОТОКИ В СЕТЯХ С ОГРАНИЧЕНИЯМИ НА ДОСТИЖИМОСТЬ

3.1. Примеры потоков в сетях с ограничениями на достижимость

3.2. Основные определения теории потоков в сетях с ограничениями на достижимость

3.3. Вычислительный эксперимент

3.4. Заключение к главе 3

3.5. Выводы по главе 3

4. СМЕШАННАЯ ДОСТИЖИМОСТЬ ПОРЯДКА к. СТУПЕНЧАТАЯ ДОСТИЖИМОСТЬ. ОГРАНИЧЕНИЯ НА ДОСТИЖИМОСТЬ В ТЕРМИНАХ ВЕРШИН

4.1. Ступенчатая достижимость смешанная

достижимость порядка к

4.2. Смешанная достижимость порядка к

4.3. Ограничения на достижимость различных видов, определяемые в терминах вершин графа

4.4.Маршрутизация в информационных сетях. Достижимость с затуханиями на дугах и усилением в вершинах

4.5.Выводы по главе 4

5. ДИНАМИЧЕСКИЕ ПОТОКИ В СЕТЯХ

5.1 Основные определения

5.2. Ограничения на величину динамического потока

5.3. Временная развертка графа

5.4. Всплеск динамического потока, ёмкость сети

5.5. Выводы по главе 5

6. ДИНАМИЧЕСКИЕ ГРАФЫ И СЕТИ

6.1. Динамические графы. Определение и примеры

6.2.-Временная развертка-динамического графа

6.3. Периодические динамические графы

6.4. Построение развёртки периодического динамического графа

6.5. О потоках в динамических сетях

6.6. Заключение к главе 6

6.7. Выводы по главе 6

7. СЕМЕЙСТВА ФУШЦИЙ ГРАНДИ

7.1. Семейство функций Гранди ориентированного графа

7.2. Семейство функций Гранди неориентированного

графа

7.3. Выводы по главе 7

ЗАКЛЮЧЕНИЕ

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

Приложение 1. Некоторые комбинаторные и полиномиальные

тождества

Приложение 2. Примеры решения задач на графах с ограничениями на достижимость

Приложение 3. О способах задания графов сограничениями на

достижимость и сетей со связанными дугами

Приложение 4. Акты об использовании результатов работы

Введение диссертации (часть автореферата) на тему «Разработка и исследование методов решения экстремальных задач на графах и сетях с ограничениями на достижимость»

ВВЕДЕНИЕ

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

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

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

достижимость являются по существу новыми объектами, по сравнению с обычными графами? Обычные графы можно считать графами с тривиальными ограничениями на достижимость, но главное не в этом. Как оказалось [38], для большинства известных видов ограничений на достижимость задача о максимальном целочисленном потоке в такой сети является NP-полной в отличие от классической задачи о максимальном целочисленном потоке в сети.

Графовые методы и алгоритмы на графах в настоящее время активно используются в различных областях науки и техники. Их широкая применимость стала и мощным стимулом для их развития. Новый этап развития теории графов можно назвать алгоритмическим, поскольку широкая применимость всегда связана с алгоритмами, позволяющими решать массовые задачи. Сам термин «теория графов» стали заменять термином «Прикладная теория графов» или «Алгоритмическая теория графов» [96, 171, 195]. Всюду в дальнейшем в нашей работе под теорией графов мы понимаем термин «теория графов» именно в этом смысле.

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

Важным инструментом тестирования, анализа программ и автоматического распараллеливания является управляющий граф программы (В.В. Воеводин, В.А. Евстигнеев, В.Н. Касьянов, C.B. Огородов, JI. Лампорт, Р. Аллэн, К. Кэннеди, М. Вольф и др.)

Среди алгоритмов на графах следует особо выделить алгоритм Е.Дейкстры [178] нахождения кратчайших путей на графах, фактически первый динамический алгоритм, и алгоритм Д. Краскала [205] нахождения легчайшего покрывающего дерева.

Ещё одним выдающимся достижением алгоритмической теории графов стала теория потоков в сетях, созданная JI. Фордом и Д. Фалкерсоном (см. [159] и [185,186]). В настоящий момент теория потоков в сетях находит все большее применение в связи с развитием телекоммуникаций (Internet, мобильная связь, глобальные компьютерные сети, облачные вычислительные системы и т.п. [143-145]), логистики, теории нейронных сетей, биоинформатики (см. напр.[45]). Вот что говорится во введении в книгу М.Ньюмана «Сети: введение» [209]: «Современная теория сетей стала прототипом междисциплинарных исследований: социология, компьютерные науки, химия, экономика, энергетика, транспорт, управление бизнесом и, сравнительно недавно, социальные сети и биоинформатика. Целям и задачам все этих наук служит эта теория». Современное состояние теории сетей изложено в книге Т. Левиса «Сетевая наука: теория и приложения» [207]. Следует отметить, что с точки зрения общих подходов к теории сетей, то они мало изменились по сравнению с подходом основоположников этой теории Л.Форда и Д.Фалкерсона (см. [159] и [185,186]). В основном её развитие связано с разработкой и совершенствованием алгоритмов решения потоковых задач в сетях (см.[167-170], [179, 180], [187-193], [202-204]). Среди учёных внесших основной вклад в развитие этого направления необходимо назвать Г.Данцига, Е.Диница, Дж. Эдмонтса, X. Габова, А. Гольдберга, Р. Карпа, В. Кинга, Р. Тарьяна. Если говорить о развитии общих подходов к теории сетей, то следует особо выделить работу А.Гольдберга и С.Pao [194] и работы О.П. Кузнецова и Л.Ю. Жиляковой по ресурсным сетям [64-72], [97-106].

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

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

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

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

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

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

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

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

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

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

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

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

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

Для достижения поставленной цели в диссертационной работе решаются следующие задачи:

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

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

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

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

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

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

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

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

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

Изучение графов с ограничениями на достижимость началось сравнительно недавно. Первые результаты в этой области принадлежат Я.М.Ерусалимскому и Е.О.Басанговой ([12 - 16]). В работах [12, 13, 15] рассматривались частично-ориентированные графы, т.е. такие, которые содержат ориентированные дуги и неориентированные ребра. В качестве допустимых путей на таких графах мы рассматривали смешанные пути двух типов. Первый тип — смешанная (3-достижимость. Допустимыми при О-достижимости являются только такие пути, которые не проходят подряд по дугам, т.е. дуги такого пути должны «прореживаться» ребрами. При достижимости допустимыми являются только такие пути, которые не проходят подряд по рёбрам частично-ориентированного графа. Рёбра допустимого пути в этом случае должны «прореживаться» дугами.

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

р'\ = 2\иы\ + \и2\ . (0.1)

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

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

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

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

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

Наиболее сложными оказались потоковые задачи. Они потребовали существенного пересмотра даже исходной постановки. Пришлось пересмотреть базовое понятие потока, поскольку определение Форда-Фалкерсона [185] учитывает только локальную структуру графа, и никак не учитывает -по каким путям транспортируется поток. Важной для нашего понимания стала работа [10], в которой приведена теорема о декомпозиции потока в виде набора потоков по путям.

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

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

1. Предложен метод построения разверток, представляющих собой вспомогательные графы, для которых имеет место соответствие между множеством допустимых путей на графе с ограничениями на достижимость и множеством путей на развертке. Метод характеризуется общностью для различных типов ограничений на достижимость в ориентированных графах и сетях - смешанной, магнитной, монотонной, вентильной, барьерной, ступенчатой - и отличается от известных аналогов, в частности от метода временной развертки динамического потока, учетом видов ограничений на достижимость, что позволяет эффективно решать оптимизационные задачи на графах широкого класса (стр. 28-29, 33-34, 53-55, 60-62, 100-103, 105106, 121-122).

2. Разработан метод решения задач нахождения кратчайших путей на графах при различных ограничениях на достижимость на основе перехода к задаче отыскания кратчайшего пути на развертке из вершины в подмножество вершин, что позволяет применять известный алгоритм Дейкстры, который непосредственно, без перехода к развертке, неприменим для решения задач в исходной постановке (стр. 27-39, 42-44).

3. Предложено преобразование задачи о случайных блужданиях по вершинам графа с ограничениями на достижимость, которая в исходной постановке не является Марковским процессом, к Марковскому процессу на развертке. Предложенное преобразование не имеет аналогов и позволяет находить вероятность попадания из вершины в вершину на исходном графе как вероятность попадания из вершины в подмножество вершин на развертке, при этом используя методы, которые без данного преобразования не применимы к процессам отличным от Марковских (стр. 46-64).

4. Синтезирован эвристический алгоритм нахождения максимального потока в сетях с ограничениями на достижимость в случае, когда

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

5. Дан конструктивный вывод балансового соотношения, доказана разложимость потока в сумму фронтальных потоков, а также его разложимость в сумму двух потоков специального вида для случая динамических потоков тождественно равных нулю при /<0, что позволяет дать оценку сверху средней величины динамического потока на временном промежутке величиной максимального стационарного потока (стр. 126-140).

6. Исследован эффект всплеска динамического потока в сети, даны необходимые и достаточные условия для топологии сети, при которых возможно возникновение всплесков, при этом максимальная величина всплеска в случае динамических потоков является, наряду с величиной максимального стационарного потока, параметром сети (стр. 149-163).

7. Предложен метод временной развёртки графов, имеющих нейтральные дуги и дуги, которые в различные временные промежутки могут присутствовать (промежутки активности) или отсутствовать (промежутки пассивности). Показано, что для графов с периодическим поведением активных дуг развертка является конечным графом, что делает алгоритмически разрешимыми задачи нахождения оптимальных путей и потоков в данном классе динамических графов (стр. 166-180).

8. Даны необходимые и достаточные условия существования функции Гранди графа, отличные от известных условий достаточности; для

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

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

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

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

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

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

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

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

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

Список литературы диссертационного исследования кандидат наук Ерусалимский, Яков Михайлович, 2015 год

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Адельсон-Вельский Г.М. Дискретная математика для инженера. - 2-е изд./О.П. Кузнецов, Г.М. Адельсон-Вельский/М.: Энергоатомиздат, 1980.-480 с.

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

3. Адигеев М.Г. Теоретико-графовая модель МВС с программируемой структурой//Модели и дискретные структуры/ Элиста: КГУ, 1999. -С.23-28

4. Алексеев В.В., Гаврилов Г.П., Сапоженко A.A. (ред.) Теория графов. Покрытия , укладки, турниры. Сборник переводов. - М.:Мир. 1974. -224 с.

5. Алексеев В.Е., Таланов В.А. Графы. Модели вычислений. Структуры данных// Нижний Новгород, Изд-во ННГУ, 2005. - 307 с.

6. Анфилатов B.C., Емельянов A.A., Кукушкин A.A. Системный анализ в управлении//М.: Финансы и статистика, 2002. - 368с.

7. Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика. Графы, матроиды, алгоритмы//Спб.: Лань, 2-е изд. испр.и доп.,2010. - 368с.

8. Асельдеров З.М., Донец Г.А. Представление и восстановление графов //Киев: Наукова думка, 1991. - 192с.

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

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

11. Басангова Е. О., Драгилев М.М.О пространствах Кёте с кратно-правильными базисами//Математические заметки. -т.39(1986), вып.5. -С.727-735.

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

13. Басангова Е.О. Об одной транспортной задаче на частично-ориентированном графах//Алгебра и дискретная математика: сб. -Элиста: КГУ, 1985. -С.61-70.

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

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

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

17. Биркгоф Г., Барти Г.Современная прикладная алгебра//М.:Мир, 1976. -400с.

18. Вентцель Е.С. Исследование операций//М.: Советское радио, 1972. 552с.

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

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

21. Галкина В. А Дискретная математика. Комбинаторная оптимизация на графах - М.: Издательство "Гелиос АРВ", 2003. — 232 с.

22. Григорьев В.В., Думбадзе Л.Г., Леонов В.Ю. Максимизация прибыли владельца сети при взятии кредита на развитие сети // Труды института системного анализа РАН. Динамика неоднородных систем. Вып.10(1). -М.: 2006. С.204-208.

23. Григорьев В.В., Думбадзе Л.Г., Тизик А.П. Максимизация прибыли оператора при ограниченных капиталовложениях на развитие сети //

Труды института системного анализа РАН. Динамика нелинейных систем. Вып. 17(1). -М.: 2005. - С.208-213.

24. Губанов Д.А., Новиков ДА. Модели унифицированного информационного управления в однородных социальных сетях//Управление большими системами. Спец. выпуск 30.1. «Сетевые модели управления» -М.: ИЛУ РАН, 2010. С. 722-742.

25. Губанов Д.А., Новиков Д.А., Чхартигивили А.Г. Социальные сети. Модели влияния, управления и социального противоборства//М.: Издательство физико-математической литературы, 2010.-238 с.

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

27. Думбадзе Л.Г., Тизик А.П. Многомерная задача о ранце специальной лестничной структуры // Известия РАН. Теория и системы управления. -1996.-№4.-С.119-122.

28. Думбадзе Л.Г., Тизик А.П., Тресков Ю.П. Задача эффективной эксплуатации сети связи // Известия РАН. Теория и системы управления. -2003.-№6.-С. 113-116

29. Думбадзе Л.Г., Тизик А.П., Тресков Ю.П. Эффективный метод анализа разветвленности сети // Известия РАН. Теория и системы управления. -2006. - №4. - С.65-69.

30. Думбадзе Л.Г., Тизик А.П. Алгоритмы нахождения кратчайших путей в оптимизационных задачах на сетях связи//Сб.научн.тр. Центр.науч. -исслед. ин-та связи. Цифровые системы передачи и интегральные сети. - 1988.-С.12-22.

31. Думбадзе Л.Г., Тизик А.П. Декомпозиционная методика решения одного класса задач линейного частично-целочисленного программирования // Декомпозиционные методы в математическом моделировании и информатике. Тезисы докладов 2-й Московской конференции (Москва, 21-24 июня 2004г.) - М.: Вычислительный центр им. A.A. Дородницына РАН.-2004.-С.53-55.

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

33. Ерзин А.И., Тахонов И.И. Задача поиска сбалансированного потока //Сибирский журнал индустриальной математики. - 2006. - т. IX, №4(28).-С. 50-63.

34. Ерзин А.И., Тахонов И.И. Равновесное распределение ресурсов в сетевой модели //Сибирский журнал индустриальной математики. -2005. -т. VIII, №3(23). - С.58-68.

35. Ерусалимскй Я.М., Куликовский А.Е. О всплесках динамического потока и минимальных разрезах// Материалы Воронежской весенней математической школы «Понтрягинские чтения XX»/ Воронеж: Из-во ВГУ, 2014. - С.64-65.

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

37. Ерусалимский Я.М. О гармонических функциях на графах с нестандартной достижимостью /Ерусалимский Я.Ы., Скороходов В.А./ Международная научная конференция «Современные методы и проблемы теории операторов и гармонического анализа и их приложения - IV», Тезисы докладов/ Ростов н/Д: Изд-во СКНЦ ВШ, 2014. - С. 88-89

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

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

Ya. M. Erusalimskii, G. G. Svetlov. Bijoin points, bibridges, and biblocks of directed graphs //Cybernetics, Plenum Publishing Corp, 1980, #1, - p.41-44

40. Ерусалимский Я.М. Всплески динамических потоков в сетях// Международная научная конференция «Современные методы и проблемы теории операторов и гармонического анализа и их приложения - III», Тезисы докладов. - Ростов н/Д: Изд-во СКНЦ ВШ, 2013. - С. 103-104.

41. Ерусалимский Я.М. Случайные блуждания по графу-решётке и комбинаторные тождества// Инженерный вестник Дона, №2 ч.2 (2015). -12 с. URL: www.ivdon.ru/ru/magazine/archive/n2p2y2015/2964

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

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

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

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

46. Ерусалимский Я.М. Дискретная математика: теория, задачи, приложения. 10-е издание. // -М.:Вузовская книга, 2009. - 288с.

47. Ерусалимский Я.М. Достижимость на графах с зависимостью ограничений от времени/ Я.М. Ерусалимский, В.А. Скороходов// материалы V международной конференции «Современные проблемы прикладной математики, теории управления и математического моделирования». -Воронеж: Издательско-полиграфический центр ВГУ, 2012. - С. 111— 112.

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

49. Ерусалимский Я.М. Задача о кратчайшем пути на графах с меняющейся длительностью при условии случайных задержек на дугах /Я.М.Ерусалимский, В.А. Скороходов// Современные методы теории краевых задач, Материалы Весенней воронежской математической школы «Понтрягинские чтения XXIV». - Воронеж: Изд.-полигр. центр ВГУ, 2013.-С. 79- 80.

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

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

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

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

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

55. Ерусалимский Я.М., Куликовский А.Е. О всплесках динамического потока и минимальных разрезах// Современные методы теории краевых задач. Материалы Весенней воронежской математической школы

«Понтрягинские чтения XXV». - Воронеж: Изд.-полигр. центр ВГУ, 2014.-С. 64-65.

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

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

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

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

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

61. Ерусалгшский Я.М. Уравнения математической физики на графах с нестандартной достижимостью/ Я.М. Ерусалимский, В.А. Скороходов/ Международная конференция «Современные методы прикладной математики, теории управления и компьютерных технологий», сборник трудов VI международной конференции. - Воронеж: Изд.-полигр. центр. ВГУ, 2013 . - С. 96-98

62. Ерусалимский Я.М. Эйлеровость графов со смешанной достижимостью // Модели, графы и алгебраические структуры: сб. -Элиста: Калм.ГУ -1989.-С.45^8.

63. Ерусалимский Я.М. Графы с ограничениями на достижимость и их приложение к задачам оптимизации технологических процессов // Современные проблемы науки и образования. -2014. - № 6. - 7 с. URL: www.science-education.ru/120-15477 .

64. Жилякова Л.Ю. Исследование эйлеровых ресурсных сетей //Управление большими системами. Вып. 41. - М.: ИПУ РАН.2013. - С. 28-50

65. Жилякова Л.Ю. Несимметричные ресурсные сети. II. Потоки при больших ресурсах и их стабилизация//Автоматика и телемеханика. -2012.- №6. -С. 103-118.

66. Жилякова Л.Ю. Несимметричные ресурсные сети. III. Исследование предельных состояний// Автоматика и телемеханика. -2012. - № 7. -С. 67-77.

67. Жилякова Л.Ю. Несимметричные ресурсные сети//Автоматика и телемеханика. - 2012. - №4. -С. 133-143.

68. Жилякова Л.Ю. Полные ресурсные сети. Случай одного приемника// Известия высших учебных заведений. Северо-Кавказский регион. Ест. науки. -2011. -№ 4. - С. 14-18.

69. Жилякова Л.Ю. Применение ресурсных сетей для моделирования распространения веществ в водной среде//Проблемы управления. - 2011. -№2.-С. 46-51.

70. Жилякова Л.Ю. Применение ресурсных сетей для моделирования распространения веществ в водной среде//Проблемы управления. - 2011. -№2.-С. 46-51.

71. Жилякова Л.Ю. Управление предельными состояниями в поглощающих ресурсных сетях //Проблемы управления. - 2013. - №3. - С.51-59.

72. Жилякова Л.Ю. Эргодические циклические ресурсные сети. I. Колебания и равновесные состояния при малых ресурсах / Управление большими системами. Выпуск 43. - М.: ИПУ РАН, 2013. - С. 34 - 54.

73. Жилякова Л.Ю. Алгоритм построения ассоциативной ресурсной сети // X международная научно-техническая мультиконференция. Актуаль-

ные проблемы информационно-компьютерных технологий, мехатрони-ки и робототехники. - 2009. - С. 232 - 236.

74. Жгтякова Л.Ю. Дискретные модели рассеяния на графах // Открытые семантические технологии проектирования интеллектуальных систем = Open Semantic Technologies for Intelligent Systems (OSTIS-2012): материалы Международной научно-технической конференции. - Минск: БГУИР, 2012.-С. 71 -76.

75. Жгтякова Л.Ю. Механизмы структурирования информации в ассоциативной модели памяти // Пятая международная конференция по когнитивной науке. - Калининград: -2012. - С. 802 - 803.

76. Жгтякова Л.Ю. Модели рассеяния на графах и их приложения // XII международная конференция им. Т.А. Таран Интеллектуальный анализ информации ИАИ-2012. - Киев: «Просвгга», 2012. - С. 181 - 187.

77. Жгтякова Л.Ю. Модель ассоциативной памяти, основанная на динамической ресурсной сети // 5-я Российская мультиконференция по проблемам управления (МКПУ-2012). «Управление в технических, эргатических, организационных и сетевых системах» (УТЭОСС-2012). - Санкт-Петербург: 2012. - С. 1160 - 1163.

78. Жгтякова Л.Ю. Организация памяти в ассоциативной ресурсной сети с переменной топологией // Научная сессия НИЯУ МИФИ-2010. Аннотации докладов. Том 3. М. Изд-во НИЯУ МИФИ, 2010. - С. 77.

79. Жгтякова Л.Ю. Поиск в ассоциативной модели памяти // IX международная конференция им. Т.А. Таран Интеллектуальный анализ информации ИАИ-2009. - Киев: «Просвгга», 2009. - С. 124 - 130.

80. Жгтякова Л.Ю. Процессы изменения проводимостей в ассоциативной ресурсной сети // X международная конференция имени Т. А. Таран Интеллектуальный анализ информации ИАИ-2010. - Киев: «Просвгга», 2010. - С. 85-91.

81. Жгтякова Л.Ю. Реализация рекурсивных запросов в динамической ассоциативной ресурсной сети // Двенадцатая национальная конференция

по искусственному интеллекту с международным участием КИИ-2010. Труды конференции, том 1. -М.: - Физматлит, 2010. - С. 335 - 343.

82. Жшякова Л.Ю. Рекурсивный поиск в динамической ассоциативной ресурсной сети // Открытые семантические технологии проектирования интеллектуальных систем = Open Semantic Technologies for Intelligent Systems (OSTIS-2011): материалы Международной научно-технической конференции. - Минск: 2011. - С. 155 - 160.

83. Жшякова Л.Ю. Ресурсная сеть как модель переноса вещества в водной среде// XI международная конференция им. Т.А. Таран Интеллектуальный анализ информации ИАИ-2011. -Киев: «Просвгга», 2011. - С. 196 -202.

84. Жшякова Л.Ю. Управление предельными состояниями в поглощающих ресурсных сетях // Проблемы управления. - 2013. - № 3. - С. 51 -59.

85. Жшякова Л.Ю. Управление распределением ресурса в неоднородных ресурсных сетях // Тринадцатая национальная конференция по искусственному интеллекту с международным участием КИИ-2012. Труды конференции. Т. 3. - Белгород: изд-во БГТУ, 2012. - С. 48 - 55.

86. Замбицкий Д.К., Лозовану Д.Д. Алгоритмы решения оптимизационных задач на сетях//Кишинёв: Штиинца, 1983. - 171 с.

87. Зутлер И.А. Выбор последовательными сравнениями как непрерывное марковское блуждание// Автоматика и телемеханика. - 2011. - № 12. -С. 60-74.

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

89. Зыков A.A. Теория графов// Итоги Науки. Алгебра, топология, 1962, ВИНИТИ, М.:1963. - С. 188 - 223.

90. Зыков A.A. Теория конечных графов// Новосибирск: Наука, 1969. -543 с.

91. Иванов Б. Н. Дискретная математика. Алгоритмы и программы//М.: Физматлит, 2007. - 408 с.

92. Камерон П., Ван Линт Дж. Теория графов. Теория кодирования и блок-схемы//М.:Мир, 1980. - 139 с.

93. Кемени Дж., Снелл Дж. Конечные цепи Маркова//М.: Наука. 1970. -272 с.

94. Климов Г.П. Теория вероятностей и математическая статистика//М.: МГУ, 1983.-394с.

95. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализам. :МЦНМО, 2002. - 960 с.

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

97. Кузнецов О.П. Ресурсные сети и процессы рассеяния на графах/ Жиля-кова Л.Ю., Кузнецов О.П./Теория активных систем: труды международной научно-практической конференции (14-16 ноября 2011г., Москва, Россия). Том 1. - С. 55-58.

98. Кузнецов О.П. Однородные ресурсные сети. I. Полные гра-фы//Автоматика и телемеханика. -2009. -№11. -С. 136-147.

99. Кузнецов О.П. Полные ресурсные сети с произвольными пропускными способностями/ О.П.Кузнецов, Л.Ю. Жшякова / Управление большими системами: сборник трудов. -2010. - № 30-1. - С. 640-664.

100. Кузнецов О.П. Ресурсные сети и процессы рассеяния на графах. / О.П.Кузнецов, Л.Ю. Жшякова/ Теория активных систем: труды международной научно-практической конференции (14-16 ноября 2011 г., Москва, Россия). -Том I. - С. 55 - 58.

101. Кузнецов О.П. Управление предельным состоянием в ресурсных се-тяхЮ.И. Кузнецов, Л.Ю. Жилякова /Материалы конференции «Управление в технических, эргодических, организационных и сетевых системах». Под редакцией С.Н. Васильева, И.А. Каляева, Д.А. Новикова, Г.Г. Себрякова. - Санкт-Петербург, 2012. - С. 1176-1179.

102. Кузнецов О.Я. Двусторонние ресурсные сети. Новая потоковая модель/ О.П.Кузнецов,Л.Ю. Жилякова/ Доклады РАН. - 2010. -Т. 433. № 5. - С. 609-612.

103. Кузнецов О.П., Жилякова Л.Ю. Исследование эргодичности ресурсных сетей с произвольной проводимостью // X международная конференция им. Т.А. Таран «Интеллектуальный анализ информации» ИАИ-2010. -Киев: «Просвгга», 2010. - С. 106 - 112.

104. Кузнецов О.П., Жилякова Л.Ю. Процессы стабилизации в динамических ресурсных сетях // Труды Научной сессии НИЯУ МИФИ-2010. В 6 томах. Том V. Информационно-телекоммуникационные системы. Проблемы информационной безопасности. - М.: НИЯУ МИФИ, 2010. -С. 53 -56.

105. Кузнецов О.П., Жилякова Л.Ю. Ресурсные сети и их приложения в информационных технологиях. // Открытые семантические технологии проектирования интеллектуальных систем = Open Semantic Technologies for Intelligent Systems (OSTIS-2011): материалы Международной научно-технической конференции. - Минск, 2011. - С. 147- 154.

106. Кузнецов О.П., Жилякова Л.Ю. Ресурсные сети: предельные состояния и потоки. Материалы 4-й Всероссийской мультиконференции по проблемам управления МКПУ-2011, Т. 1. - Таганрог: изд. ТТИ ЮФУ 2011. -С. 62-66.

107. Кузнецов О.П., Жилякова Л.Ю. Управление предельным состоянием в ресурсных сетях // 5-я Российская мультиконференция по проблемам управления (МКПУ-2012) . «Управление в технических, эргодических, организационных и сетевых системах» (УТЭОСС-2012). - Санкт-Петербург, 2012.-С. 1176- 1179.

108. Кузнецов О.П.Сетевые модели: ресурсы, влияния, конфликты /О.П. Кузнегрв, Л.Ю. Жилякова, Д.А.Губанов, С.Г. Куливец / Системный анализ и семиотическое моделирование: материалы первой всероссийской

конференции с международным участием (SASM-2011). - Казань: Изд-во «Фэн» Академии наук РТ, 2011. - С. 225 - 232.

109. Кузнецов 0.77. Сетевые модели в социально-экономической сфере /О.П. Кузнецов, Л.Ю. Жилякова, Д.А.Губанов, С.Г. Куливец II XI международная конференция им. Т.А. Таран «Интеллектуальный анализ информации» ИАИ-2011. -Киев: «Проыита», 2011. - С. 233 - 240.

110. Кузовлев Д. И. Декомпозиционный алгоритм для решения транспортной задачи с ограниченными пропускными способностями / Д. И. Кузовлев, А. П. Тизик, Ю. П. Тресков/ Мехатроника, автоматизация, управление.-2012.-№ 1.-С.45-48

111. Кузьминов Р.Н. Ограниченные магнитные достижимости на ориентированных графах / Р.Н. Кузьминов, М.В. Кузьминова / Современные методы теории краевых задач: материалы Воронежской весенней математической школы «Понтрягинские чтения XVIII». -Воронеж: Изд.-полигр. центр ВГУ, -2007. - С.98-99.

112. Кузьминова М.В. Динамические периодические графы. Задача о максимальном потоке // Сборник материалов докладов 5-й всероссийской научно-практической конференции студентов, аспирантов и молодых ученых «Молодежь XXI века - будущее российской науки». В 2 т. -Т.1. - Ростов-на-Дону: Изд-во ООО «ЦВВР», 2007. - С.99-100.

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

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

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

116. Кузьминова M.B. Периодические динамические графы. Задача о максимальном потоке// Известия вузов. Северо-Кавказский регион. Ест. науки.-2008. - №1. - С. 14-19.

117. Кузьминова М.В. Периодические динамические графы. Задачи о случайных блужданиях и о кратчайших путях// Известия вузов. СевероКавказский регион. Ест. науки. -2008. - №5 - С. 16-20.

118. Куссуль Н., Соколов А. Адаптивное обнаружение аномалий в поведении пользователей компьютерных систем с помощью марковских цепей переменного порядка. 4.2: Методы обнаружения аномалий и результаты экспериментов//Проблемы управления и информатики. -2003- №4. - С.83-88.

119.Лазарев A.A., Гафаров Е.Р. Теория расписаний. Исследование задач с отношениями предшествования и ресурсными ограничениями// Научное издание. Вычислительный центр им. A.A. Дородницына РАН. 2007. - 80 с.

120. Липский В. Комбинаторика для программистов//М.:, Мир,1988. - 213 с.

121. Ловас Л., Ппаммер М. Прикладные задачи теории графов. Теория па-росочетаний в математике, физике, химии//пер. с англ.- М.: Мир, 1998. - 653 с.

122. Майника Э. Алгоритмы оптимизации на сетях и графах// пер. с англ.-М.:Мир, 1981,- 328 с.

123. Матряшин Н.П., Макеева В.К. Математическое программирование //Харьков: «Вища школа», 1978. - 180 с.

124. Мелихов А.Н. Ориентированные графы и конечные автоматы//М.: Главная редакция физико-математической литературы изд-ва «Наука», 1971,- 416с.

125. Мину М. Математическое программирование. Теория и алгоритмы. Пер. с фр. и предисловие А.И. Штерна. - М.: Наука. Главная редакция физико-математической литературы, 1990. - 416с.

126. Миркин Б.Г., Родин С.И. Графы и гены//М.: Наука, 1977. -236с.

127. Новиков Д.А. Сетевые структуры и организационные системы//М.: ИЛУ РАН, 2003.

128. Ope О. Графы и их применение//М.: Мир, 1965. - 176 с.

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

130. Ope О. Теория графов. Пер. с англ.- М.:Наука,1980. - 334 с.

131. Панюкова Т.А. Комбинаторика и теория графов//М.: Либроком, 2012.-210 с.

132. Панюкова Т.А. Маршруты с локальными ограничениями: алгоритмы и программная реализация/ И.О. Алферов, Т.А. Панюкова/ Прикладная информатика. -2010. - №1(43). - С.49-57

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

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

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

136. Прим Р.К. Кратчайшие связывающие сети и некоторые обобщения // Киберн. сб. - 1961,-№2.-С. 95-107.

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

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

139. Роберте Ф.С. Дискретные математические модели с приложениями к социальным, биологическим и экологическим задачам//М.: Наука, 1986. -496 с.

140. Романовский В.И. Дискретные сети Маркова//Государственное изд-во научно-технической литературы. Москва-Ленинград, 1949. - 436 с.

141. Романовский И.В. Алгоритмы решения экстремальных задач//М.: Наука, гл. ред. физ.-мат. литературы, 1977. - 352 с.

142. Романовский И.В. Циклические варианты моделей сетевого графика//-в книге «Исследование операций и статистическое моделирование, 1», Л.: Изд-во ЛГУ, 1972. - С. 145 - 152.

143. Самуйлов К.Е. Задача маршрутизации трафика на графе сети MPLS с одноадресными соединениями / М.В. Лузгачев, К.Е. Самуйлов / Вестник РУДН. Серия «Математика. Информатика. Физика». -2009. - № 1. - С. 23-33

144. Самуйлов К.Е. Новый этап развития математической теории телетрафика / Г.П. Башарин, К.Е. Самуйлов, Н.В.Яркина, И.А./ Автоматика и телемеханика. - № 12. -Академиздатцентр «Наука» РАН, - С. 16 -28

145. Самуйлов К.Е. Теория телетрафика мультисервисных сетей: Монография. / Наумов В.А., Самуйлов К.Е., Яркина Н.В./ М.: Изд-во РУДН, 2007.- 191 с.

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

147. Седжвик Р. Фундаментальные алгоритмы на С++. Алгоритмы на гра-фах//ДиасофтЮП, 2002. - 304 с.

148. Скороходов В. А. Задача о перераспределении ресурсов на графах с нестандартной достижимостью// Известия вузов. Северо-Кавказский регион. Ест. науки. - 2010. - №6. - С. 22 - 25.

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

150. Скороходов В. А. Достижимость на графах с ограничением на прохождение по дугам и зависимостью весов дуг от времени// Известия вузов. Северо-Кавказский регион. Ест. науки. -2009. - №6. - С. 14 - 16.

151. Скороходов В.А. Потоки в сетях с меняющейся длительностью прохождения// Известия вузов. Северо-Кавказский регион. Ест. науки. - 2011. -№1.-С. 21 -26.

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

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

154. Скороходов В.А., Чеботарева A.C. Графы с зависимостью некоторых характеристик от времени: достижимость, случайные процессы// Известия вузов. Северо-Кавказский регион. Ест. науки. - 2012. - №3. - С. 13-17

155. Скороходов В.А., Чеботарева A.C. Задача Дирихле на графах с зависимостью длительностей прохождения по дугам от времени начала движения по ним// Современные методы прикладной математики, теории управления и компьютерных технологий (ПМТУКТ-2013), сборник трудов VI международной конференции. - Воронеж: Изд.-полигр. центр ВГУ, 2013. - С. 223-224.

156. Скороходов В.А.Задача Дирихле на графах с нестандартной достижимостью // Вестник Воронежского государственного университета. Серия: Физика. Математика. -2013. - № 1. -С. 210-221.

157. Скороходов В.А.Потоки в обобщенных сетях со связанными дугами // Моделирование и анализ информационных систем. - 2012. - Т. 19, № 2. -С. 41-52.

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

159. Tamm У. Теория графов //М.:Мир, 1988. -424с.

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

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

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

163. Чеботарева A.C. Гармонические функции на графах с зависимостью длительностей прохождения по дугам от времени начала движения по ним// Известия вузов. Северо-Кавказский регион. Ест. науки. -2013. -№6.-С. 35-38.

164. Чеботарева A.C. Оценка максимального потока в сети с зависимостью длительностей прохождения по дугам от времени// Современные методы теории краевых задач, Материалы Весенней воронежской математической школы «Понтрягинские чтения XXIV». - Воронеж: Изд.- по-лигр. центр ВГУ, 2013. - С. 216.

165. Шевелев М.В., Скороходов В.А. Задачи о потере потока в ориентированных сетях //Современные методы прикладной математики, теории управления и компьютерных технологий (ПМТУКТ-2013), сборник трудов VI международной конференции. - Воронеж: Изд.-полигр. центр ВГУ, 2013.- С. 275-277.

166. Штейнберг Р. Б. Использование решетчатых графов для исследования многоконвейерной модели вычислений// Известия вузов. СевероКавказский регион. Ест. науки. - 2009. - №2. - С. 18-21.

167. Ahiija R. К. A Fast and Simple Algorithm for the Maximum Flow Problem/ R.K. Ahuja, J.B. Orlin/ Oper. Res. -1989. -No.37. - P.748-759.

168. 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. - P. 939-954.

169. Alon N. Generating Pseudo-Random Permutations and Maximum Flow Algorithms. // Inf. Proc. Lett. -1990. -No.35. - P. 201-204.

170. Aronson J.E. A Survey of Dynamic Network Flows // Annals of Operations Research. -No. 20. -1989. - P. 1-66.

171. Bang-Jensen J., Gutin G. Digraphs: Theory, Algoritms and Applictions //London; Berlin; Heidelberg; New York; Barcelona; Hong Kong; Milan; Singapore; Tokyo: Springer, 2008, 2 ed. - 798 p.

172. Bellmann R.E. A Markovian decision process//J. Math. And Mech., 1958, #6.

173. Berge С. Theorie des Graphes et Ses Applications//Dunod, Paris, 1958, пер. на русск.: Теория графов и её применения/ М.: ИЛ, 1962, - 319 с.

174. Dantzig G.B. All shortes routes in a graph// Theorie des Graphes , Paris, Dunod, 1967.-P. 91-92.

175. Dantzig G.B. Application of the Simplex Method to a Transportation Problem // In Activity Analysis and Production and Allocation. -New York: Wiley, 1951.-P. 359-373.

176. De Sousa J.F., Rossi R. (Eds.) Computer-based Modelling and Optimization in Transportation// Springer Cham Heidelberg New York Dordrecht London, 2014. XI,- 489 p.

Ml.Derman C. Finite state Markovian decision processes//N.Y., Acad. Press, 1970.- 159 p.

178. Dijkstra E.W. A Note in Two Problems in Connection with Graphs //Numerische Mathematic ,1959, No.l, pp. 269-271

179. Dinic E.A. Algorithm for Solution of a Problem of Maximum Flow in Networks with Power Estimation. // Sov. Math. Dokl. -1970. -No.ll. -P.1277-1280.

180. 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. -P. 248-264.

181. Erusalimskiy I. On the Dynamic Flows in Networks//Universal J. of Communications and Network, 2014, v2, No. 6, -P. 101 - 105, DOI: 10.13189

182. Erusalimsky I.M. Family of Grandy Functions for Oriented Graphs// Turkish Journal of Mathematics, v. 19, №3,1995, -P.269-273

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

184. 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.-P. 691-703.

185. Ford Jr. L.R. Maximal flow through a network. / L.R. Ford Jr., D.R. Fulker-son/ Canad. J. Math. -1956. -No. 8. - P. 399^104.

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

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

188. Galiil Z. An 0(EV\og2V) Algorithm for the Maximal Flow Problem / Z. Galiil, A. Naamad/ J. Comput. Syst. Sei.-1980.-No.21.- P. 203-217.

5 2

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

190. Goldberg A. V. A New Approach to the Maximum-Flow Problem. / A.V. Goldberg, R.E. Tarjan/ J. ACM. -1988. -Vol.35. -No.4. - P. 921-940.

191. Goldberg A. V., Harrelson C. Computing the Shortest Path: A Search Meets Graph Theory/ Proc. 16th ACM-SIAM Symposium on Discrete Algorithms, 2005.-P. 156-165.

192. 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. - P. 921-940.

193. Goldberg A. V. A New Max-Flow Algorithm // Tech. Rep. MIT/LCS/TM-291, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, Mass., Jan. 1985.

194. Goldberg A. V. Beyond the Flow Decomposition Barrier/ A.V. Goldberg, S. Rao/ Journal of the ACM. -Vol.45. -No. 5. -1998. - P.783-797.

195. Golombic M.C. Algorithmic Graph Theory and Perfect Graphs//New York: Academic Press, 2004, 2 ed. 2nd ed., - 340 p.

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

197. 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 -P. 59-71.

198. Haight F.A. Mathematical Theories of Traffic Flow//Elsevier, Academic Press Inc., 1963.-255 p.

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

200. Hoffman A.J., Winograd S. Finding all shortest distances in a directed network// IBM J. Res. Devel., 1972, No.6. - P.414-416

201. Karp R.M. Reducibility among Combinatorial Problems// Complexity of Computer Computations; R. E. Miller and J. W. Thatcher (editors). -New York: Plenum, 1972. - P. 85-103.

202. Karzanov, A. V. Determining the Maximal Flow in a Network by the Method of Preflows // Sov. Math. Dokl. -1974. -No. 15. - P. 434^174.

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

204. 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. - P.157-164.

205. Kruskal J.B. On the Shortes Spannig Subtree of a Graph and the Traveling Salesman Problem// Proc. American Mathematical Soc., 1956, No.7, - P. 48-50

206. Lawler E.L. Combinatorial Optimization: Networks and Matroids// Lawler E.L. -New York: Holt, Rinehart and Winston, 1976. -374 p.

207. Lewis T. Network Science: Theory and Applications// Wiley Publ., Hobo-ken, NJ, 2009. - 524 p.

208. Malhorta V.M. An 0{\Vf) Algorithm for Finding Maximum Flows in Networks. / V.M. Malhorta, Pramodh Kumar M., S.N. Maheshwari / Inf. Process. Lett. -1978. -No.7. - P. 277-278

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

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

211. OlegP. Kuznetsov, Ludmila Yu. Zhilyakova. Flows and Limit States in Bidirectional Resource Networks // Preprints of the 18th IF AC World Congress. Milano (Italy) August 28 - September 2, 2011. - P. 14031 - 14035.

212. Oleg P. Kuznetsov, Ludmila Yu. Zhilyakova. Nonsymmetric resource networks. The study of limit states. // Management and Production Engineering Review. Volume 2, No. 3, September 2011. - P. 33-39

213. Orlin J.B. Maximum-throughput dynamic network flows// Math. Progr. -1983.-Vol. 27. - P.214-231

214. Phillips S. Online Load Balancing and Network Flow /S. Phillips, J. Westbrook / In Proceedings of the 25th Annual ACM Symposium on Theory of Computing (San Diego, Calif., May 16-18). ACM, New York, 1993.-P. 402-411

215. Potts R.B., Oliver R.M. Flows in Transportation Networks. Academic Press,

New York. 1972.- 192 p. 216.7?. Geisberger, P. Sanders, D. Schultes, and D. Delling. Contraction hierarchies: Faster and simpler hierarchical routing in road networks. /WEA, 2008. -P. 319-333.

217. Rice M., Tsotras V.J. Graph Indexing of Road Networks for shortest Path Queries with Label Restrictions!¡Proceedings of VLDB Endowment, Vol.4.4, #2(2010).-P.69-80.

218. Riordan J. Combinatorial Identities//John Wiley &Sons, Inc., New York-London-Sidney, 1968 (пер. на русск.: Риордан Дж. Комбинаторные тождества/ М.: Наука,ФМ. 1982)

219. Rosen, Kenneth Н. Discrete Mathematics and Its Applications. McGraw-Hill, Inc., 2 ed., ISBN 0-07-053744-5.

220. Samouylov K. Tool for the Routing Planning in a Large-scale Signaling Network /Chukarin A.,Samouylov К./ Proc. of the 7th Int. Conf. on Telecommunications, ConTEL 2003, Zagreb. - June 2001, -P. 579 - 586

221..Samouylov К Telecommunication Signalling. /Martikainen O., Naoumov V., Samouylov К./ Wiley Encyclopedia of Electrical and Electronics Engineering. V. 21 (John .G. Webster, Editor). - John Wiley & Sons, 1999, - P. 426-432.

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

223. Sleator D.D. A Data Structure for Dynamic Trees. / D.D. Sleator, R.E. Tarjan / J. Comput. Syst. Sci.,1983. -No.26. - P.362-391.

224. Smith C.A.B., Tutte W.T. On unicursal paths in a network of deree All Amer. Math. Monthly, 48, 1941. -P. 233-237.

225. Tarjan R.E. A Simple Version of Karzanov's Blocking Flow Algorithm //

Oper. Res. Lett., 1984, No.2. - P.265-268

226. Tutte W. The Rotor Effect with Generalized Electrical Flows//Ars

Combinatoria, 1,(1976) - P. 3-31.