Содержание к диссертации
Введение
1. Ограничения на достижимость различныхвидов, кратчайшие пути на графах с ограничениями на достижимость 24
1.1. Основные определения 24
1.2. Смешанная достижимость на орграфах 27
1.3. Магнитная достижимость на орграфах 32
1.4. Барьерная достижимость на графах 37
1.5. Обсуждение результатов главы 1 42
1.6. Выводы по главе 1 45
2. Случайные блуждания на графах с ограничениями на достижимость 46
2.1. Случайные блуждания на графах со смешанной достижимостью 48
2.2. Случайные блуждания на графах с монотонной достижимостью 52
2.3. Случайные блуждания по графам с вентильной достижимостью 59
2.4. Случайные блуждания по графу-решётке 66
2.5.Заключение к главе 2 78
2.6. Выводы по главе 2 79
3. Потоки в сетях с ограничениями на достижимость 80
3.1. Примеры потоков в сетях с ограничениями на достижимость 81
3.2. Основные определения теории потоков в сетях с ограничениями на достижимость 87
3.3. Вычислительный эксперимент 91
3.4. Заключение к главе 3 96
3.5. Выводы по главе 3 97
4. Смешанная достижимость порядка к. ступенчатая достижимость. ограничения надостижимость в терминах вершин 98
4.1. Ступенчатая достижимость смешанная достижимость порядка к 99
4.2. Смешанная достижимость порядка к 104
4.3. Ограничения на достижимость различных видов, определяемые в терминах вершин графа 108
4.4.Маршрутизация в информационных сетях. Достижимость с затуханиями на дугах и усилением в вершинах 120
4.5.Выводы по главе 4 125
5. Динамические потоки в сетях 126
5.1 Основные определения 126
5.2. Ограничения на величину динамического потока 131
5.3. Временная развертка графа 141
5.4. Всплеск динамического потока, ёмкость сети 149
5.5. Выводы по главе 5 165
6. Динамические графы и сети 166
6.1. Динамические графы. Определение и примеры 166
6.2. Временная развертка динамического графа 171
6.3. Периодические динамические графы 173
6.4. Построение развёртки периодического динамического графа 176
6.5. О потоках в динамических сетях 181
6.6. Заключение к главе 6 183
6.7. Выводы по главе 6 183
7. Семейства функций гранди 184
7.1. Семейство функций Гранди ориентированного графа 185
7.2. Семейство функций Гранди неориентированного
графа 191
7.3. Выводы по главе 7 193
Заключение 194
Библиографический список
- Магнитная достижимость на орграфах
- Случайные блуждания на графах с монотонной достижимостью
- Основные определения теории потоков в сетях с ограничениями на достижимость
- Ограничения на достижимость различных видов, определяемые в терминах вершин графа
Магнитная достижимость на орграфах
Вершина у достижима из вершины х на графе со смешанной достижимостью G(X,U = UR uUz,f) тогда и только тогда, когда на развёртке G существует путь из вершины х хотя бы в одну из вершин множества {у, у }. Между множеством допустимых путей из вершины х в вершину у на графе со смешанной достижимостью G(X,U = UR uUz,f) и множеством путей из вершины х во множество вершин {у, у } на развёртке существует взаимно однозначное соответствие.
Справедливость этого утверждения следует из конструкции развертки. Т Если на исходном графе заданы длины дуг, то развертку тоже считаем взвешенным графом, полагая длины его дуг равными длинам породивших их дуг исходного графа.
Утверждение 1.2. Т Длина кратчайшего пути из вершины х в вершину у на графе со смешанной достижимостью G(X,U = URuUz,f) равна длине кратчайшего пути из вершины х в вершины множества {у, у } на развёртке G . Этот кратчайший смешанный путь может быть восстановлен по кратчайшему пути из вершины х во множество вершин {у, у } на развёртке Ясно, что этот кратчайший путь на графе G может быть найден с помощью алгоритма что никакая модернизация алгоритма Дейкстры без перехода к развёртке невозможна.
Вернёмся к примеру 1.1 и найдем кратчайший смешанный путь из вершины 1 в вершину 6. На развёртке этого графа (рис. 1.2) кратчайший путь из вершины 1 во множество вершин {6,6 } имеет длину 4: 1 -» 8 -» 4 -» 5 -» 6 . Этот путь «восстанавливается» в смешанный путь длины 4 на исходном графе: 1 8 4 5 -6.
Замечание 1.1. Т Как уже было отмечено выше, графы со смешанной достижимостью таковы, что для них возможная мулътиграфовостъ неустранима. Однако, прежде чем решать задачу о кратчайшем пути можно произвести устранение мулътиграфовости для однотипных дуг, а именно, если из вершины х в вершину у ведет несколько дуг из множества UR (Uz), то можно оставить дугу наименьшей длины, сохранив её тип. Возможные приложения смешанной достижимости. Рассмотрим описание технологического процесса в виде графа. Вершины соответствуют различным состояниям изделия, в котором оно может находиться в процессе изготовления. Дуги графа соответствуют выполняемым операциям, переводящим изделие из одного состояния в другое.
Граф технологического процесса в этом случае представляет собой классическую сеть с одним входом (источником) и одним выходом (стоком). Если под длиной дуги, ведущей из вершины х в вершину у понимать стоимость выполнения операции, переводящей изделие из состояния х в состояние у, то мы получаем классическую задачу поиска оптимального по стоимости пути выполнения технологического процесса. Ясно, что для многих технологических процессов могут возникать дополнительные ограничения на возможные пути на графе технологического процесса. Например, при выполнении ряда операций изделие может нагреваться, а если такие операции выполняются непосредственно одна за другой, то возможен перегрев изделии и выход его из строя в процессе изготовления. Отнесение дуг, соответствующих таким операциям, к множеству Uz, а остальных дуг к множеству UR и рассмотрение графа технологического процесса как графа со смешанной достижимостью позволит найти оптимальный путь исполнения процесса с учетом технологических ограничений. 1.3. Магнитная достижимость на орграфах
В этом параграфе мы рассмотрим ещё один вид ограничений на достижимость - магнитную достижимость, которая сильно отличается от смешанной достижимости, поскольку ограничения на множество рассматриваемых (допустимых) путей на таком графе носят уже не локальный, а глобальный характер.
Определение 1.5. У Путь 1-і называется магнитно-накопительным путем порядка к( 1) длины п(п є N) с неубывающей магнитностъю на графе G, если выполняется следующее условие: \/т(Л (т) к\и ((р2 о / о MXm)) nUM 0) (М(т + l)eUM)_A Таким образом, эта достижимость означает следующее, - если к / -му шагу от своего начала путь // накопил значение магнитности лм (0, большее либо равное к, и среди дуг, выходящих из концевой вершины / -й дуги, есть хотя бы одна магнитная дуга, то следующая (i +1) -я дуга обязана быть дугой из множества UM . Определение 1.6. Т Граф G(X,U,(p),U = 17 uU на котором рассматриваются только магнитно-накопительные пути порядка k, будем называть графом с накоплением неубывающей магнитности порядка k. А Построение развёртки графа с накоплением неубывающей магнитности Каждой вершине графа ставится в соответствие к + 1 вершина
. Преобразование магнитных дуг Множество ={Х15Л;2,...,Л;И}5 и=Х называется /-ьш магнитным уровнем (і -ым уровнем магнитности). Таким образом, множество вершин развёртки состоит из вершин различных уровней магнитности. Ясно, что справедливо следующее утверждение: Утверждение 1.3. Т Для того, чтобы вершина у была магнитно-достижима при условии неубывающей магнитности порядка к из вершины х на графе G, необходимо и достаточно, чтобы на развёртке G] была достижима из вершины X хотя бы одна из вершин множества Vy={y ,...,у }. Между множеством допустимых путей из вершины х в вершину у на графе с неубывающей магнитностъю порядка к и множест 0 т/ вом путей из вершины X во множество вершин У у на развёртке существует взаимно однозначное соответствие. На основании этого строятся решения задачи поиска кратчайшего пути и задачи о случайном блуждании. В частности, справедливо утверждение: Утверждение 1.4. Т Кратчайшему пути на развёртке G] из вершины х в вершины множества Vy={y ,...,у } соответствует кратчайший магнитно-накопительный путь на графе G . А
Таким образом, для нахождения кратчайшего пути на графе с магнитной достижимостью можно на развёртке графа применить известный алгоритм нахождения кратчайшего пути, а затем по найденному на развертке кратчайшему пути восстановить кратчайший путь на исходном графе с магнитной достижимостью.
Случайные блуждания на графах с монотонной достижимостью
Отметим одну существенную особенность основного алгоритма нахождения кратчайшего пути из одной вершины графа в другую вершину - алгоритма Дейкстры ([178]). Этот алгоритм состоит из двух этапов. На первом этапе мы находим длины кратчайших путей из заданной вершины графа во все остальные вершины. На втором этапе мы находим сам кратчайший путь. Это восстановление происходит на основании исходной информации о дугах графа («начало дуги»; «конец дуги»; длина дуги) и найденного массива длин кратчайших путей. Кратчайший путь восстанавливается пошагово - определяется последняя дуга пути, а значит и предпоследняя вершина Эта процедура применяется до тех пор, пока мы не восстановим в качестве предшествующей вершины начальную вершину. Выполнение двух этапов будем называть полным алгоритмом Дейкстры. Выполнение только первого этапа будем называть неполным алгоритмом Дейкстры.
Предложенное в этой главе решение задачи о кратчайших путях с ограничениями на достижимость не является единственным из возможных. Поскольку графы, которые мы рассматриваем, конечны, то можно написать полнопереборный алгоритм нахождения всех путей из заданной вершины в заданную вершину в неубывающем порядке их длин. Каждый из найденных путей необходимо проверить на допустимость этим видом достижимости. Первый из удовлетворяющих этой проверке путь будет решением задачи. Ясно, что можно привести пример, в котором перебор будет глубоким, т.е., практически полным, более того - полный алгоритм Дейкстры будет применяться многократно - на каждом из шагов переборного алгоритма.
Значительно хуже при таком подходе будет обстоять дело, если нас будет интересовать решение другой задачи - нахождения длин кратчайших путей между всевозможными парами вершин при условии имеющихся ограничений на достижимость. Алгоритм полного перебора придётся применять ко всем упорядоченным парам вершин графа. Предложенный нами подход, использующий развёртку графа, позволит применить к ней матричный вариант неполного алгоритма Дейкстры (известный как алгоритм Шимбелла (см. напр. [1],[193]).
Гипотетически возможен и такой подход - для каждого из типов ограничений на достижимость строить уникальный алгоритм нахождения кратчайшего пути. Понятно, что для смешанной достижимости это возможно (нужна некая модификация алгоритма Дейкстры), для барьерной и магнитной достижимости модификация алгоритма Дейкстры уже вряд ли возможна, а какие другие идеи положить в основу таких алгоритмов (отличных от полного перебора) в случае магнитной и барьерной достижимостей совершенно не ясно.
Метод, основанный на построении развертки, представляется достаточно универсальным. Этап, на котором преодолеваются проблемы, - построение развертки. Этот этап зависит от типа достижимости. После построения развертки применяется общая схема перехода от исходной задачи к эквивалентной ей (но не совпадающей с ней) задаче на развертке.
Замечание 1.2. Выше мы писали о нахождении длин кратчайших путей между всевозможными парами вершинами графа, т.е. о нахождении матрицы длин кратчайших путей, удовлетворяющих имеющемуся ограничению на достижимость.
Отметим особенности такой матрицы, связанные с потерей, например, фундаментального свойства «Любой отрезок кратчайшего пути является кратчайшим путем между своими граничными вершинами».
Для графов без ограничений на достижимость имеет место важное свойство матрицы длин кратчайших путей графа, состоящее в следующем.
Для ориентированных графов со смешанной достижимостью можно рассматривать задачи и об их общей структуре (компоненты связности, бисвязности, мосты, блоки, точки сочленения, точки бисочлене-ния, бимосты, библоки (см. напр. [39])), но отсутствие транзитивного свойства для путей на графах с ограничениями на достижимость делает эти понятия малосодержательными, а их распознавание - трудоёмким. 1.6. Выводы по главе 1:
Случайные блуждания на графах - математическая модель, которая описывает различные стохастические процессы: распространения загрязнений, вирусов в компьютерных сетях, аномального поведения пользователей компьютерных сетей [118]; процессы формирования мнений в социальных сетях и т.п.[108, 109]. Появились исследования, посвященные применению задач о случайных блужданиях к анализу активности в сетях мобильных операторов, в том числе, позволяющие предсказывать динамику оттока клиентов из данной сети [24, 25].
В этой главе мы рассмотрим задачу о случайных блужданиях на графах с ограничениями на достижимость.
В классической постановке предполагается, что на дугах заданы вероятности перехода. Процесс рассматривается в дискретном времени. Обозначим U+(x) множество дуг, выходящих из вершиных. Если частица в момент времени t0 находится в вершине х, то в момент t0+\ она с вероятностью р(и) окажется в вершине, в которой заканчивается дуга и є U+(x). При этом предполагается, что
В процессе случайного блуждания частица движется по некоторому пути на графе (прокладывает путь на графе).
Ясно, что в случае ограничений на достижимость, когда частица имеет право перемещаться по дугам из вершины в вершину так, что формируется допустимый этим типом достижимости путь, процесс перестаёт быть Марковским. Даже в случае смешанной достижимости частица должна «помнить» - по какого типа дуге совершен предыдущий переход, а в случае монотонной или барьерной достижимости, частице необходимо «помнить» глубокую предысторию своего попадания в вершину. В задаче о случайных блужданиях по графам с нестандартной достижимостью мультиграфовость присутствует по существу, как и в задаче о кратчайших путях. В связи с этим для таких графов нельзя использовать такое понятие как матрица переходных вероятностей. Для таких графов возможно только частичное устранение мультиграфовости (внутри множеств однотипных дуг).
Основные определения теории потоков в сетях с ограничениями на достижимость
В 4.1, 4.2 этой главы определены ещё два типа ограничений на достижимость - ступенчатая и смешанная порядка к . Описано построение развёрток для графов с такими ограничениями на достижимость. Это означает справедливость для таких графов результатов, аналогичным результатам глав I-III.
В 4.3 определены новые типы ограничений на достижимость, которые, в отличие от рассмотренных, определяются в терминах вершин, а не дуг графа. Во многих прикладных задачах это более естественно. Например, когда мы строим блок-схемы алгоритмов и программ, вершины соответствуют шагам алгоритма и/или фрагментам программ (операторам, циклам и т.п.), а дуги графа соответствуют переходам от вершины к вершине. В этом случае вершины представляются более содержательной частью графа, чем его дуги.
В 4.4 рассмотрена задача маршрутизации в информационной сети, в которой имеются дуги, прохождение по которым понижает уровень сигнала, и вершины, в которых происходит усиление сигнала ([63]). Это приводит к рассмотрению еще одного вида ограничений на достижимость - с затуханием на дугах и усилением в вершинах. Задача маршрутизации в таких сетях эквивалентна задаче нахождения кратчайшего пути между вершинами графа с такими ограничениями на достижимость. Для этих графов построена развертка, это позволяет решать задачи о кратчайших путях, случайных блужданиях и максимальных потоках. 4.1. Ступенчатая достижимость
В главах I-II мы уже определили несколько видов ограничений на достижимость: смешанную, магнитную, барьерную, монотонную и вентильную. Как было отмечено, смешанная достижимость такова, что действие ограничения носит локальный характер. Все остальные виды достижимости таковы, что ограничения носят глобальный характер. Сейчас мы определим ещё один вид ограничений на достижимость - ступенчатую достижимость. Для этого вида достижимости трудно классифицировать ограничения - какой характер они носят: локальный или глобальный. Будет определена и смешанная достижимость порядка к как обобщение смешанной достижимости.
Поясним, что означает это определение (как оно сказывается на формировании ступенчатого пути). Первая дуга пути может быть из множества U0 или Ul. При этом, если эта дуга принадлежала множеству U0, то следующая дуга может принадлежать множествам и0 или Ul, а если она принадлежала множеству Ul, то разрешенными для прохождения становятся дуги множеств и0и и2. Прохождение по дуге из множества U0 не меняет множество разрешенных для прохождения дуг, а прохождение через дугу множества Uj меняет множество разрешенных для прохождения дуг на множество U0 Uj_x UJ+l.
Пути, проходящие по вершинам 1-3-5-7-9-11-12 и 1-2-4-6-8-3-5-7-9-11-12, являются ступенчатыми, а пути 1-2-11-12 и 1-2-4-6-8-10-12 таковыми не являются.
Построение развёртки для графов со ступенчатой достижимостью Опишем построение развёртки - вспомогательного графа G . Каждой вершине х исходного графа ставится в соответствие т + 1 вершина вспомо 101 гательного графа х ,х\...,хт. Каждой дуге иєи0,/(и) = (х,у) ставится в соответствие набор дуг (см. рис 4.2):
Поскольку мы построили развертку графа со ступенчатой достижимостью, то для решения задач о кратчайших путях, случайных блужданиях и потоках в сетях со ступенчатой достижимостью применима техника, описанная в главах I—III и, значит, для графов со ступенчатой достижимостью справедливы результаты, аналогичные результатам, полученным в главах I -III.
Определение 4.3. Т Пусть G(X,U,f) - орграф. Множество дуг графа U = UR JUZ,UR 0,UZ 0,URr Uz =0. Смешанным путем порядка к на графе G(X,U,f) будем называть путь, на котором дуги из множества Uz встречаются не более чем к раз подряд. Дуги множества UR будем называть разрешенными, а множества Uz запрещенными. Определение 4.4. Графом со смешанной достижимостью порядка к будем называть граф, на котором допустимыми являются только смешанные пути порядка к.
В теории неориентированных графов известно, что результат, полученный для вершин графа, легко переносится на ребра графа. Например, как выполняется переход от задачи о правильной раскраске вершин (смежные вершины окрашиваются в разные цвета) к задаче о правильной раскраске ребер графа? Для этого достаточно построить реберный граф исходного графа, объявив его вершинами ребра исходного графа. Вершины реберного графа смежны (соединены ребром), если породившие их ребра имели на исходном графе общую вершину. Если ребро графа, соединяющего вершины х иу, отождествить с двухэлементным множеством {х;у}, то реберный граф - это граф пересечений полученного семейства двухэлементных множеств (см. [161]).
Ограничения на достижимость различных видов, определяемые в терминах вершин графа
Занимаясь потоковыми задачами, нельзя не думать о возможных приложениях. Ясно, что дискретность динамического потока, рассмотренного нами, не позволит применить эти результаты к гидравлическим сетям. Автотранспортные сети по существу дискретны. Всплеск динамического потока в них можно рассматривать как «пиковое» увеличение пропускной способности (без возникновения «пробок»).
Поясним ещё раз смысл определений 5.11 и 5.12. Максимальный всплеск - это наибольшее количество вещества, которое может быть единовременно получено стоком из сети, ёмкость сети - это максимальное количество вещества, которое может единовременно находиться в сети (т.е. быть «закачано» в сеть из источника к какому-то моменту времени). Перейдем к истолкованию этих понятий на уровне возможных приложений. Будем считать, что наша сеть обеспечивает потребление вещества стоком. Максимальный всплеск - это максимальное мгновенное (разовое) (пиковое) потребление стоком, которое может быть обеспечено данной сетью. Ёмкость - это максимальное количество вещества, которое может быть потреблено из сети стоком, если подача вещества из истока, начиная с какого-то момента времени (аварийное отключение источника), прекращена. В каком-то смысле, подобная ситуация (аварийное отключение источника) наблюдалась в момент прекращения подачи газа западным потребителям через украинские транспортные сети. Это отключение они ощутили не сразу. Их потребление обеспечивалось около 36 часов тем газом, который находился в момент отключения источника в газотранспортной сети.
Пример 5.8. Рассмотрим сеть примера 5.3. (см. рис. 5.12). Ясно, что w(G) = 20. Возможные размещения вещества в сети, обеспечивающие эту ёмкость, изображены нарис. 5.25, 5.26 Рис. 5.25. 5
Перед тем, как решать задучу о нахождении этих характеристик нужно понять насколько корректно они определены, т.е. достижимы ли они на любой сети. Для того чтобы снять этот вопрос, заметим, что в прикладных задачах мы можем ограничиться сетими с рациональными пропускными способностями, а значит весь вопрос (с помощью приведения дробей к общему знаменателю) может быть сведён к сетям с целочисленными пропускными способностями и целочисленными потоками на таких сетях.
Мы не приводим здесь алгоритмы нахождения максимального всплеска и потока, обеспечивающего этот всплеск, и алгоритма нахождения максимального объема сети и потока, обеспечивающего максимальный объём в таких сетях. Они были получены совместно с Н.Н.Водолазовым [52-54], который провел обоснование и реализацию алгоритмов.
Изучены динамические потоки, тождественно равные нулю прш 0. Для них получено балансовое соотношение и доказана теорема о разложимости такого потока сумму фронтальных потоков и сумму двух потоков специального вида, первый из которых определяет поток на [0;T]Z, а второй на [Т + l;+oo)z.
Обнаружено и изучено явление, названное всплеском динамического потока. Получены необходимые и достаточные условия, которым должна удовлетворять сеть, при которых в ней возможно возникновение всплесков потока.
Предложены конструкции сетей, в которых величина всплеска превышает величину максимального стационарного потока на любую наперед заданную величину.
В этой главе мы определим новое понятие - динамический граф. Динамические графы - это графы, существующие в дискретном времени и меняющие свою структуру в дискретном времени.
В работах [43, 44] рассмотрены задачи нахождения максимального потока на динамических периодических графах. Для обыкновенных ориентированных графов вводится дискретное время Т, и рассматриваются динамические графы. Динамическим графом в [44] мы назвали ориентированный граф вида G(X,U,/,T), множество дуг которого представляет собой объединение двух непустых непересекающихся подмножеств, называемых множеством обычных и множеством временных дуг, г - функция активности. Временные дуги графа доступны для прохождения не в любой момент времени, а только в периоды активности.