Содержание к диссертации
Введение
Глава 1. Нестандартные достижимости на ориентированных графах 16
1.1. Ограниченные магнитные достижимости 16
1.2. Ограниченные монотонные достижимости 22
1.3. Динамические графы 30
Глава 2. Построение вспомогательного графа как метод сведения задач на графах с нестандартной достижимостью к задачам на обычных орграфах 37
2.1. Построение вспомогательного графа для случая ограниченных магнитных достижимостей 37
2.2. Построение вспомогательного графа для случая ограниченных монотонных достижимостей 39
2.3. Построение вспомогательного графа для периодических динамических графов 41
Глава 3. Задача о максимальном потоке на периодических динамических графах и на графах с ограниченными магнитными и монотонными достижимостями 46
3.1. Постановка задачи. Основные определения 46
3.2. Потоки в сетях с ограниченными магнитными достижимостями 47
3.3. Потоки в сетях с ограниченными монотонными достижимостями 59
3.4. Максимальный поток в периодической динамической сети
61
Глава 4. Задача о кратчайшем пути на периодических динамических графах и на графах с ограниченными магнитными и монотонными достижимостями 78
4.1. Кратчайшие пути на графах с ограниченными магнитными достижимостями 79
4.2. Кратчайшие пути на периодических динамических графах 89
Глава 5. Случайные блуждания на периодических динамических графах и на графах с ограниченными магнитными и монотонными достижимостями 96
5.1 Задача о случайных блужданиях на графах с ограниченными магнитными достижимостями 96
5.2 Задача о случайных блужданиях на периодических динамических графах k 108
5.3 Графовые модели в логистике 114
Заключение 119
Приложение 120
Литература
- Ограниченные монотонные достижимости
- Построение вспомогательного графа для случая ограниченных монотонных достижимостей
- Потоки в сетях с ограниченными магнитными достижимостями
- Кратчайшие пути на периодических динамических графах
Введение к работе
Теория графов предоставляет эффективные средства формализации задач из самых различных областей: экономики, физики, химии, планово-производственной практики, управления производством, сетевого и календарного планирования, информационных систем, и многих других. Одним из таких средств является ориентированный граф. Существует большое количество задач, решаемых на орграфах. Чаще всего рассматриваются задачи о достижимости (т.е. о существовании пути, связывающем две заданные вершины), о нахождении путей, обладающих какой-либо экстремальной характеристикой (например, кратчайший, или наиболее надежный путь), о случайных блужданиях, потоковая задача. Все они хорошо изучены и разработаны эффективные алгоритмы их решения. При этом предполагается, что все пути на графе являются допустимыми, т.е. не накладывается никаких ограничений на достижимость. Наиболее известные работы в этой области принадлежат Кристофидесу Н., Басакеру Р.Д., Харари Ф., Бержу К., Дейкстре Э., Флойду Р., Замбицкому Д.К., Оре О., Саати Т., Ерусалимскому Я.М., Фалкерсону Д.Р., Форду Л.Р.([2, 10-19, 23, 34, 42, 45-46]).
В отличие от классического подхода, Басанговой Е.О. и Ерусалимским Я.М. было введено понятие ориентированных графов с нестандартной достижимостью, т.е. орграфов, в которых на допустимые пути накладываются какие-либо ограничения ([3-6, 11]). В обычном ориентированном графе, для того чтобы одна вершина была достижима из другой, необходимо существование пути, связывающего две эти вершины. В случае же орграфов с нестандартной достижимостью требуется, кроме того, чтобы этот путь удовлетворял некоторому условию (ограничению). Понятно, что в этом случае классические алгоритмы решения задач на графах непосредственно неприменимы.
В работах Ерусалимского Я.М., Басанговой Е.О., Логвинова С.Ю., Скороходова В.А., Петросяна А.Г. ([3-6, 11-18, 35-37, 39-41]) описаны
5 различные виды ограничений на достижимость. Так, Ерусалимским ЯМ. и Басанговой Е.О.([3-6, 11]) рассмотрено несколько видов достижимости на частично-ориентированных графах, на которых присутствуют ориентированные и неориентированные ребра. Введено понятие смешанной цепи, на дуги и звенья которой накладываются различные условия, в зависимости от вида ограничений. Например, рассмотрены случаи, когда в смешанной цепи два неориентированных ребра не могут следовать непосредственно друг за другом, или дуги и звенья строго чередуются.
В работах Скороходова В.А. рассмотрены орграфы с накоплением неубывающей магнитности к - го уровня ([40-41]). На таких графах допустимым является магнитно-накопительный путь порядка к с неубывающей магнитностью, т.е. такой путь, что если на т - м шаге величина накопленной магнитности не меньше к и среди выходящих дуг есть хотя бы одна магнитная, то т +1 - я дуга пути должна быть магнитной. Другой вид достижимости - вентильно-накопительная. В этом случае множество дуг графа представляется в виде U = U0 и С/, и...и(7А.. В
допустимом пути прохождение по дуге множества Uj (j = 1,2,...) делает
доступными для прохождения дуги множества UJ+l (j = 1,2,...,A:-і). Также
рассмотрены условия накопления-исчезания и возрастания-убывания магнитности, вентильная достижимость с возрастанием-убыванием доступа и энергии на пути, механическая достижимость.
Петросяном А.Г. определена барьерная достижимость, при которой множество дуг разбивается на три попарно непересекающихся подмножества: дуг, увеличивающих барьерный показатель, дуг барьерного перехода и нейтральных дуг ([35—37]). С каждым отрезком пути связана числовая характеристика — барьерный показатель частицы. Путь допускает барьерный переход уровня к>\, если к некоторому шагу он накопил величину барьерного показателя, не меньшую к. Еще один вид ограничений - биполярная магнитность. В этом случае определяется величина накопления
биполярной магнитности. Путь считается допустимым, если он удовлетворяет условию биполярной магнитности уровня к.
Общим подходом к решению задач на орграфах с ограничениями на достижимость является построение вспомогательного графа, имеющего большее количество вершин, и обладающего следующим свойством: допустимому пути на исходном графе с ограничениями соответствует некоторый путь на вспомогательном графе, а недопустимому пути не соответствует ни один путь ([3-6, 11—18, 35-37, 39-41]). Алгоритм построения такого графа зависит от вида вводимых ограничений. На вспомогательном графе, таким образом, все пути являются допустимыми, а дуги - равноправными, и его можно рассматривать как обычный ориентированный граф. Для графов с нестандартными достижимостями описанных видов рассмотрены классические задачи о кратчайшем пути из вершины в вершину, о максимальном потоке в сети с нестандартной достижимостью и о случайных блужданиях на таких графах. Наибольшую сложность вызывают две последние задачи, так как при построении вспомогательного графа увеличивается не только количество вершин, но и количество дуг. При этом необходимо правильно распорядится весами дуг, по которым строится несколько дуг на вспомогательном графе. Серьезного осмысления каждый раз требует и перенос соответствующего результата с вспомогательного графа на основной граф.
В настоящей работе рассмотрены ориентированные графы с различными типами ограничений на достижимость и решаются задачи о случайных блужданиях, о кратчайших путях и о максимальном потоке на таких графах. В частности, введено четыре типа магнитной достижимости: на начальном и конечном отрезках пути с параметром п0, на отрезке [«,,w2]N и магнитная достижимость, возникающая после п0 шагов. Описаны орграфы с
монотонной достижимостью, которая является обобщением магнитной. Кроме того, рассмотрены динамические и периодические динамические графы, т.е. такие ориентированные графы, для которых вводится дискретное
7 время и задается функция активности дуг — дуги на графе существуют не в любой момент времени, а только в свои промежутки активности. Ясно, что такие задачи могут рассматриваться как математические модели транспортных или информационных сетей, в которых в определенные моменты времени функционируют не все участки сети. Для каждого вида ограничений разработаны алгоритмы построения вспомогательного графа, что позволяет свести решение указанных выше задач на исходном графе к задачам на вспомогательном графе без ограничений на достижимость. Доказаны теоремы о взаимнооднозначном соответствии между исходным и вспомогательным графами.
В первой главе введено три типа нестандартной достижимости на ориентированных графах: ограниченные магнитные достижимости, ограниченные монотонные достижимости и периодические динамические графы.
Ограниченные магнитные достижимости. Рассматриваются ориентированные графы, множество дуг которых представляет собой объединение двух непустых непересекающихся подмножеств, которые называются множеством магнитных и множеством немагнитных дуг. Такие графы называются графами с магнитными ограничениями (или с магнитной достижимостью). Путь на таком графе является допустимым при выполнении условия: если предыдущая дуга пути была магнитной и есть исходящие магнитные дуги, то следующая дуга пути также должна быть магнитной.
В отличие от магнитных достижимостей, описанных в [3-6, 11-18, 38-37, 40-41], в настоящей работе рассмотрены случаи, когда магнитные ограничения действуют не на всем протяжении пути, а лишь на некотором его отрезке. Такие достижимости названы ограниченными магнитными достижимостями. Рассмотрены три вида достижимостей - на начальном отрезке пути длины п0, на конечном отрезке пути длины «0, магнитная достижимость, возникающая после щ шагов и магнитная достижимость на
8 отрезке натурального ряда [w,,h2]n. Соответствующие графы обозначаются
с(вдд ($СВДД ЗДВДЛ и с^СВДЛ
Ограниченные монотонные достижимости. Монотонная достижимость является обобщением магнитной достижимости на случай, когда множество дуг графа разбивается на R +1 попарно непересекающихся
подмножеств и = и0 \J({JU,). Путь на графе с монотонной достижимостью
является допустимым, если подпоследовательность индексов дуг пути (не учитывая дуги множества UQ) не убывает (индекс дуги — номер
подмножества дуг, которому она принадлежит).
Рассмотрено четыре типа монотонной достижимости: на начальном и конечном отрезках пути длины п0, монотонная достижимость, возникающая
после п0 шагов, и монотонная достижимость на отрезке [«i,»2]N- Графы с соответствующим типом достижимости обозначаются (\jnonS^>U,Jj, 4bjnoA&U9f)t Ощ+тоХ,и>/) и Gfo^lmolXU,/). Сформулирована теорема о связи достижимости на графах Ц|,шо, и G)OT0;.
Периодические динамические графы. Для обыкновенных ориентированных графов вводится дискретное время N, и рассматриваются динамические графы. Динамическим графом называется ориентированный граф вида G(X,C/,/, г), множество дуг которых представляет собой
объединение двух непустых непересекающихся подмножеств, которые называются множеством обычных и множеством временных дуг, г -функция активности. Временные дуги графа доступны для прохождения не в любой момент времени, а только в периоды активности. Путь на динамическом графе является допустимым, если все его дуги активны в момент прохождения их путем.
Пути на динамических графах, в отличие от путей на обыкновенных орграфах, не обладают, вообще говоря, свойством транзитивности. Сформулировано и доказано достаточное условие транзитивности пути на динамическом графе.
Теорема 1.4.1. Пусть С?(Х,/,/, т) - динамический граф, х,у,гєХ.
Пусть //[/(]: [і, «і ]N -> U - путь из вершины х в вершину у, ju^ : [l, w2]N -> U
— путь из вершины у в вершину z. Тогда для того, чтобы существовал путь
из вершины х в вершину z, достаточно выполнения условия t2 =tl+n1.
Также рассмотрены периодические динамические графы GT(X,U,f, г), для дуг которых промежутки активности отличаются на
некоторое натуральное число Г, называемое периодом.
Во второй главе описаны алгоритмы построения вспомогательных графов для графов с ограниченными магнитными, монотонными достижимостями и для периодических динамических графов. Построение вспомогательного графа является методом сведения достижимости на графах с ограничениями к достижимости на обыкновенных ориентированных графах. Вспомогательный граф имеет больше вершин и дуг, но его можно рассматривать как обычный орграф со стандартной достижимостью.
Для графов с ограниченными магнитными достижимостями доказаны теоремы о взаимнооднозначном соответствии между допустимыми путями на исходном графе с ограничениями и путями на вспомогательном графе:
Теорема 2.1.1. Пусть GM\X9U9f) — граф с магнитной достижимостью, G*{X\U\f*) — граф, построенный по графу GM. На графе GM существует допустимый путь из вершины х є X в вершину у є X тогда, и только тогда, когда на графе G' существует путь из вершины хєХ' в одну из вершин
уеХ' или у + ШєГ.
10 Теорема 2.2.1. На графе G(X,U,f) с монотонной достижимостью
существует допустимый путь из вершины х є X в вершину у є X тогда, и
только тогда, когда на графе G'^A^t/',/1) существует путь из вершины х в
подмножество вершин у + к- \Х\,к = 0,1,...,Я -1.
Для периодических динамических графов получена теорема о соответствии между дугами на исходном и вспомогательном графах:
Теорема 2.3.1. На вспомогательном графе G(X\U\f) дуге u(=U:f(u)=(i,j) в момент времени t є N: r(u,t) = 1 соответствует дуга и'є/', такая, что
/{и') = (/ + (/ - l)x\, j + t\x\), если 1 t < кТ;
о /(М')= (i + (t0 -l)x\,J + t0\x\), если 3neZ+:t = t0 + nT,kT
/(«*) = (/ + ((к + \)Т - ^Х\, j + кТ\х\), если Эти є Z+ : t = (А: + і)Г + mT.
Справедливость теоремы следует из правила построения
вспомогательного графа G,{x\U\f).
Из алгоритма построения вспомогательного графа следует, что в случае периодических динамических графов дискретное время N можно разделить на два промежутка: конечный «подготовительный», и бесконечный периодический.
Третья глава посвящена задаче о максимальном потоке для графов с введенными типами ограничений. Для таких графов введено понятие сети, потока, магнитного и монотонного разрезов.
Доказаны теоремы, являющиеся аналогами теоремы Форда-Фалкерсона для графов с ограниченными магнитными и монотонными достижимостями:
Теорема 3.2.1. Величина максимального потока в сети GM{X,U,f,c)
равна пропускной способности минимального магнитного разреза, т.е. существует поток fl , такой что d{fl*)= maxd(jl)=min с(р).
Теорема 3.3.1. Величина максимального потока в сети GMon(X,U,f,c) равна пропускной способности минимального монотонного разреза, т.е. существует поток fl , такой что d(jl* )= max d(fl) = min c(p).
На графах с ограниченными магнитными и монотонными достижимостями не все пути являются допустимыми, поэтому классические алгоритмы поиска максимального потока ([2, 10, 19-21]) к таким графам неприменимы. Для решения потоковой задачи на таких графах предлагается искать максимальный поток на вспомогательном графе. Для каждого вида достижимости приведены соответствующие алгоритмы.
В процессе построение вспомогательного графа возникает вопрос о переносе пропускной способности дуги исходного графа на порожденные ею дуги вспомогательного графа. Если положить пропускную способность каждой порожденной дуги равной пропускной способности исходной дуги, то возможна ситуация, когда по дуге исходного графа проходит поток, величина которого больше, чем пропускная способность данной дуги. Для решения этой проблемы в [36] введено понятие множества связанный дуг (т.е. дуг, порожденных одной и той же дугой исходного графа), и вместо пропускных способностей отдельных дуг рассматривается суммарная пропускная способность множества связанных дуг. Для решения задачи о максимальном потоке для графов со связанными дугами в [36-37] описан алгоритм прорыва.
Показано что алгоритм поиска максимального потока с применением вспомогательного графа является более эффективным, чем поиск максимального потока без использования вспомогательного графа.
Для периодических динамических графов введены определения периодической динамической сети и динамического потока. Определена величина динамического потока, исходящего из источника в момент времени tQ
12 Определение 3.4.3. В периодической динамической сети GjiXyUyf, т,с) величиной динамического потока, исходящего из источника
s* в момент времени t0eN, в сток ? называется d[to]= ^flfato)'
Vnet/ro, (»)=*'
г(",'оН
Максимальным динамическим потоком, исходящим из источника s' в момент времени t0 eN, в сток f называется динамический поток, для
которого величина d^ = ^fl(u, t0 ) максимальна (обозначим ее d^max).
Vaet/ip, («)=*' ф,/оН
Определение 3.4.4. В периодической динамической сети Gt(X)U,/,t,c) величиной динамического потока из источника s\
приходящего в сток ? в момент времени tx є N, называется ^- 2 flfa* 'і ) Максимальным динамическим потоком из источника 5',
г(н,'іН
приходящим в сток ? в момент времени txeN, называется динамический поток, для которого величина d* = ^fl{u,tx) максимальна (обозначим
г(м,/,Н d[tllmax).
Различие между этими величинами заключается в том, что в первом случае источник рассматривается в одно и то же время /0, тогда как в сток
динамический поток может «прийти» в любой момент времени t > t0. Во втором случае, наоборот, известен момент tx, в который динамический поток «приходит» в сток, но начальные моменты времени при этом могут быть различными.
Описаны модифицированные алгоритмы Форда-Фалкерсона для поиска указанных величин максимальных потоков на исходном динамическом графе, а также алгоритм нахождения этих величин на вспомогательном графе. Получены теоремы о постоянстве величин максимальных потоков на периодическом участке:
13 Теорема 3.4.1. Пусть GT(X,U,f, т,с) - периодическая динамическая
сеть с характеристикой к, s\f — источник и сток в сети GT. Тогда
ЧТП — 1,2,...,1 «[i74m],max = "[*Г+/п+лГ],тзх >П = 1»2,...
Теорема 3.4.2. Пусть выполняются условия теоремы 3.4.1. Тогда
Vm = l,2,...,r d[tT+mlm" = [і7Чл,+пГІта\л = 1,2,....
Введено понятие суммарных максимальных потоков и формулируются теоремы о постоянстве этих величин на периодическом участке.
В четвертой главе рассмотрена задача о кратчайших путях для периодических динамических графов и графов с ограниченными магнитными и монотонными достижимостями. Так как не все пути на графах с указанными видами ограничений являются допустимыми, предлагается искать кратчайшие пути на вспомогательном графе, который можно рассматривать как обыкновенный ориентированный граф. Доказаны теоремы о соответствии между кратчайшими путями на исходных графах с ограничениями и путями на соответствующих им вспомогательных графах.
Теорема 4.1.1. Кратчайшему пути длины п < п0 на графе G^(X,U,f,l) из вершины seX в вершину teX соответствует кратчайший путь из вершины s в подмножество вершин |f,/ + jxj} на вспомогательном графе
&{х\и\г).
Приведены алгоритмы поиска кратчайших путей на вспомогательном графе для каждого вида ограничений. Показано, что кратчайшие пути на графах с описанными ограничениями, вообще говоря, не обладают свойством экстремальности и транзитивности. Показано что алгоритм поиска кратчайшего пути с применением вспомогательного графа является более эффективным, чем поиск кратчайшего пути без использования вспомогательного графа.
Сформулировано и доказано достаточное условие экстремальности кратчайшего пути на периодическом динамическом графе:
14 Теорема 4.2.1. Пусть //jy j:[l,w]N -+U (t0&N) - кратчайший путь из
некоторой вершины х, є X в некоторую вершину х2еХ с началом в
момент времени t0 eN на периодическом динамическом графе
Gr(X,/,/, г,/). Рассмотрим отрезок этого пути //у :[w,,722]N ->U (ґ, eiVj,
СОеДИНЯЮЩИЙ ВерШИНЫ у1 И у2. ДЛЯ ТОГО, ЧТОбы ОТреЗОК //[/(] являлся
кратчайшим путем из ух в у2, достаточно выполнение условия tx = /0 + и, -1. Для периодических динамических графов введены понятия кратчайшего пути из вершины х в вершину у с началом в момент времени
t0 є N и кратчайшего пути из вершины х в момент времени ґі в вершину у в момент времени /2. Доказана теорема о постоянстве длины кратчайшего
пути с начальным моментом времени, принадлежащим периодическому участку.
Теорема 4.2.3. На графе G1 для всех значений tn =/0 +nT:t0 <=[кТ + \,(к+i}r]N,n = 0,1,2,... длина кратчайшего пути с начальным моментом времени tn между любыми двумя вершинами есть величина постоянная.
В пятой главе рассмотрена задача о случайных блужданиях частицы на графах с ограниченными достижимостями. В силу вводимых ограничений на достижимость процесс блуждания частицы по вершинам графов с ограниченными магнитными и монотонными достижимостями не является марковским. Предлагается рассматривать процесс блуждания на вспомогательном графе, на котором все пути допустимы. Приведены формулы пересчета вероятностей перехода для вспомогательного графа с целью сведения данного процесса блуждания к марковскому.
Получены теоремы о том, что вероятности перехода из одной вершины в другую на исходном графе с ограничениями соответствует вероятность перехода из заданной вершины в некоторое подмножество вершин на
15 вспомогательном графе. Показано, что для периодических динамических графов по стохастической матрице вспомогательного графа можно получить матрицу вероятностей перехода на исходном графе в любой заданный момент времени t0eN с учетом поставленных ограничений на
достижимость.
Показано, что графы с описанными видами достижимости могут быть использованы для моделирования логистических процессов.
В заключении приведены основные результаты диссертационной работы.
В приложении приведены листинги программы и описание работы программного комплекса.
Ограниченные монотонные достижимости
Монотонная достижимость является обобщением магнитной достижимости в случае, когда множество дуг графа разбивается на R +1 (R Є N) попарно непересекающихся подмножеств.
Определение 1.2.1. Пусть G(X,i7,/) - ориентированный граф, для которого / = /„ (J (U ) U,nUk =0 Vi,k = 0..N,i k, Ui,Ф 0 Vi = 1.JV. Дуги множества U0 называются обычными, дуги множеств Ul,U2,...,UR — монотонными. Путь //:[l,«]N -»f/ на графе G(X,U,f) называется допустимым, если он удовлетворяет следующему условию. Пусть /=1 - последовательность дуг пути. Рассмотрим ее подпоследовательность {ju(jk)}Ll С=Ы/)}"=1: //(лЬи / = U,...,/ , то есть такую, в которой отсутствуют дуги из множества U0. Для любого к-\ 2,...,р каждому индексу jk поставим в соответствие индекс sk, такой, что ju(jk)eUSk (к = 1,2,...,р). Для того, чтобы путь являлся допустимым, требуется, чтобы последовательность индексов {s lLi была неубывающей. Назовем достижимость такого вида монотонной, а граф G — графом, с монотонной достижимостью. Монотонная достижимость на начальном отрезке пути с параметром п0 Пусть G(X,U,f) - граф с монотонной достижимостью, n0eN натуральное число. Путь //: [l, «]N - U на графе G является допустимым, если монотонное ограничение действует только на начальном отрезке [і,и0]дг. Достижимость такого вида назовем монотонной достижимостью на начальном отрезке пути с параметром «0. Граф с описанными ограничениями обозначим попЛЛ/). Пример 1.2.1. Рассмотрим ориентированный граф moA f) 24 Рис. 1.2.1 /(и,) = (1,2) /(и2 ) = (1,4) f(„3 ) = (2,3) /(и4)= (2,4) /(«5) = (3,6) Ди6) =(4,5) /(и7)=(5,3)/(«,) = (5,б) С/2 = {M15W5,W8}, U3 = {и7}
Рядом с дугой указан тип подмножества дуг Ut,i = 0..R, которому она принадлежит. Так как п0 = 2, то допустимыми для данного графа будут, например, пути fix - {и2, и6,щ} и ju2 = {и15 ы6,м7,и5}. Путь //3 = {»!, w4 M6 Mg} при и0= недопустим, поскольку последовательность индексов {2,1} не является неубывающей (щ GU2,U4 Є UX).
Монотонная достижимость на конечном отрезке пути с параметром щ
Пусть G(X, С/, /) — граф с монотонной достижимостью. Зададим число w0-eJV. Путь //:[l,w]N-»/ на графе G является допустимым, если монотонное ограничение действует на отрезке [n-n0+l,n]N, т.е. на конечном отрезке пути длины п0. Достижимость такого вида назовем монотонной достижимостью на конечном отрезке пути с параметром п0. Граф с описанными ограничениями обозначим Задачу о монотонной достижимости на конечном отрезке пути можно свести к задаче о достижимости на начальном отрезке той же длины. Для этого необходимо поменять направления всех дуг графа щ топ на противоположные, а также изменить тип дуги: о если ueUk:f(u)={i,j\k = \,2,...,R, то считаем, что МІЄ Л- +Г-/І(МІ)=(ЛО; о если и є U0 : /(и) = (г, Д то UXGUQ: fx (и,) = (j, і) . Граф, полученный с помощью таких преобразований, обозначим п0,топ Докажем теорему о связи достижимостей на графах щ,топ и п0,топ Теорема 1.2.1. Вершина у є X достижима из вершины х є X на графе ГК щ оп тогда, и только тогда, когда вершина х є X достижима из вершины уеХ на графе G . Необходимость. Пусть вершина у є X достижима из вершины х є X на графе Тогда существует допустимый путь /л: [l, n]N - U: Рі(м(І))=х, Р2(м(п))=У- Рассмотрим граф G }n(X,Uиfx) и построим путь jS:[l,/i]N-»tflf такой, что если f(ju(i))=(i0,j0\i0,j0 єХ, то /j(//(w-i +1)) = (J Q,/0) Vz є [l,n]N. При этом у - начальная вершина пути р,, а х - конечная. Покажем, что этот путь допустим.
Построение вспомогательного графа для случая ограниченных монотонных достижимостей
Пусть G(X,t/,/) - граф с монотонной достижимостью, Л U = Uo\J UUi)- Построим граф &(Х\и\Г\ такой, что Х = Д-Х, а множество U строится по следующим правилам: 1. если /(«)= {i,j\ и є /0, то к множеству U1 добавляются дуги uk: f{uk) = (i + k \X\9j + k-\X\\ = 0,1,..., Д-1; 2. если /(и) = (/, j\ и є UR, то добавляется дуга и: fiu)=(i + (R-l).\X\,j + (R-l).\X\); 3. если f(u) = (i,j\ иєІ/т, т = 1,2,...,Л -1, то добавляются дуги «Л: /(И)=(Ї+(Ш-І).4У+(И-І)-М); ( )=(/,7 + ( + -1)-14)1 = 0,1,...,/2-2; / (MJ = (/+(A:-l)-47+( + w-l)-X), АГ = 0,1,..., -2. Если для дуги и графа G(X,U,f) определено значение некоторой весовой функции с(и), то полагаем вес всех дуг, порожденных этой дугой, равным с(и). Сложность построения графа (7 (л ,/,/) равна 0(пг), где п = \Х\.
Пример 2.2.1. Рассмотрим граф G(X,U,f) с монотонной достижимостью, изображенный на рис.2.2.1 (рядом с дугой указан номер подмножества дуг, которому она принадлежит.): »- — 1 Ьт - 1 2 \ Xs 6 Рис.2.2.1 /(Wl) = (l,2) /(и2) = (2,3) f(u3)=(2,4) /(«4) = (2,5) /(и5)=(3,5) /к)=(4,5) /(«7)=(5,б) U0={u5}, и{ = {щ}, C/2 = {wl5w6}, t/3={w2K 4=К М7} Вспомогательный граф G (X ,U\f) изображен нарис.2.2.2: Рис. 2.2.2 Теорема 2.2.1. На графе G(X,U,f) с монотонной достижимостью существует допустимый путь из вершины х є X в вершину у єХ тогда, и только тогда, когда на графе Gf{X\U\f%) существует путь из вершины JC в подмножество вершин у + к \Х\,к = 0,1,...,R -1. Доказательство теоремы следует из алгоритма построения вспомогательного графа G {/C9U,j). 2.3 Построение вспомогательного графа для периодических динамических графов Пусть GT(X,U,/,T) - периодический динамический граф с периодом Т. Построим для него вспомогательный граф G (x\U ,/ ). Пусть \/щ єU(і = 1,2,...) Мщ = \J[at + п T,bt +п-Т]. Найдем bmax = max{&,.}. 71=0,1,2,... /=1,2,...
Пусть существует целое число к 0, такое, что 6тах є [к Т + \,(к +1)- г]. Назовем число к характеристикой графа GT. Тогда для вспомогательного графа G Х = (А: + і)-Г-Х, а множество дуг / строится по следующим правилам: для всех дуг иєи, таких, что f(u) = (і, j) V/w = l...(k + 1) -1 если ф,/я) = 1,то t/ t/ UJM jt}, где /-( )=(/+( -1)-14/+ -1 Если т(и,(к + і)-Т) = \,то Lr=U \J{u%rnQ fiu )=(i + ((k + l) T-l).\X\j + k.T-\X\). Если для дуги ueU исходного графа GT(X,U,f,T) задано значение некоторой весовой функции с(и) (например, длины дуги, или пропускной способности), то всем дугам графа G , порожденным дугой и, также присваивается вес с(и). Сложность построения графа Gr\JC,U,f) равна 0(п2),гдеп = \Х\. Сформулируем теорему, устанавливающую связь между графами GT и G . Теорема 2.3.1. На вспомогательном графе G (X , / ,/ ) дуге ueU: f(u)= (/,у) в момент времени t є N: r(u,t)-1 соответствует дуга w ef/ , такая, что /(м )=(/ + (/-і).х,у+ґ-Х),если1 ґ А:.Г; /И = (/ + ( о -l)-\X\,j + t0 -\Х\), если 3neZ+:t = tQ+n T,k t0 (k + l)-l; f(u )=(i + ((k + l)-\)-\X\,j + k-\x\), если 3meZ+ :t = (k + l) + m. Справедливость теоремы следует из правила построения вспомогательного графа G (Х ,/ ,/ ).
Замечание 2.3.1. Вершины вспомогательного графа G (X\ / ,/ ) можно разделить на несколько «слоев», в каждом из которых находится по \Х\ вершин. Запись /0=/ + /72-1 1(//2 = 0,1,...) означает, что вершина /0 на вспомогательном является «двойником» вершины /єіи расположена в (w + l)- м «слое». Число т + 1 соответствует моменту времени, в который рассматривается вершина / и все исходящие из нее дуги.
Пример 2.3.1. Рассмотрим граф G5(X,U,fyv) (рис.2.3.1): [1 + 5/1,3 + 5«],. ..[2 + 5/J,4 + 5W] і Ul І І "з і [8 + 5w,ll + 5w] І и2 и4 [5 + 5И,7 + 5И] Рис. 2.3.1 /(«,)= (1,2) /(«2)=(1,3) /(«3)= (2,4) /(«4)=(3,4) Uo=0, UT = {щ,и2,и3іщ} r(«„f) = l V/e[l + 5w,3 + 5w]N r(w2,/)=l V/e[8 + 5w,ll + 5«]N r(u3,t) = l Vf є [2 + 5л,4 + 5/1 г(н4, ) = 1 6(5 + 5/ ,7 + 5/ я = 1,2,...
Рассмотрим, например, путь /ij2] = {ultu3}. Он удовлетворяет условию (1.4.1) и является допустимым для графа G5. Действительно, т(щ,2) = 1, т(м2,3) = 1. Другой путь, /І ] = 2 М4}» не является допустимым, так как г(и2,5)=0. Вспомогательный граф для графа G5(X,/,/,r) представлен на рис.2.3.2: Допустимому пути ju[2] соответствует путь 5- 10-»16 (представлен в виде последовательности вершин). Путь /лщ не является допустимым, поэтому на графе G этот путь не представлен. Из алгоритма построения вспомогательного графа следует, что дискретное время N можно разделить на два этапа: конечный «подготовительный» этап, и бесконечный периодический. На рис.2.3.2 они разделены двойной пунктирной линией, слева указаны моменты времени. Подготовительному этапу соответствует промежуток времени [l,fc- r]N, т.е. к периодов длины Т, а периодическому - бесконечное множество промежутков длины Т: [(к Т +1)+п Т, (к +1) Т + п т]ы, п = 1,2,.... Таким образом, начиная с момента времени t = k + l, можно наблюдать установившийся периодический режим, т.е. в моменты времени tn =t0 + п-Т, k t0 (& + і)«Г-1,л = 1,2,... активно одно и то же множество дуг. Для графа, рассмотренного в примере 2.3.1, к = 2,Т = 5.
Подготовительный этап занимает 2 периода длины 5 (на рис.2.3.2 они разделены одной пунктирной линией), т.е. отрезок [l,10]N. Периодическому этапу соответствуют отрезки [і 1 + 5«, 15 + 5w]N, и = 1,2,....
В данной главе описаны алгоритмы построения вспомогательных графов для ограниченных магнитных и монотонных достижимостей и периодических динамических графов. Доказаны теоремы о соответствии между допустимыми путями на графах с ограничениями и путями на вспомогательных графах.
Потоки в сетях с ограниченными магнитными достижимостями
Рассмотрим задачу о нахождении максимального потока в периодической динамической сети. В классической постановке задачи ([2, 10, 19-21]) вводятся понятия сети, источника и стока, потока, и т. д. Поскольку для динамических графов введено понятие времени, оно должно быть отражено в этих определениях.
Определение 3.4.1. Периодической динамической сетью назовем взвешенный периодический динамический граф Gr(Z,/,/, г, с), на котором выделены две вершины: источник s e X: deg+(s ) = 0 Vr eN и сток t eX :dQg _(f) = 0\/t GN (здесь deg+(jc) и degl(x) - полустепень захода в вершину х и полустепень исхода из вершины х в момент времени t є N соответственно). Весовая функция c.UxN- Z+ определяет пропускную способность дуг графа GT в каждый момент времени t GN . Будем считать, что Vt є N: т(и, /) = 1 с(и, t) = const. Если 3? є N: т(и, t ) = 0, то полагаем с(и,?)=0. Определение 3.4.2. Динамическим потоком в периодической динамической сети GT{X,U,f, г,с) из источника s1 в сток f называется неотрицательная функция fl :UxN — R+, такая, что выполняются следующие условия: 1, \ft є N У і є X fl(u, і) = Л y?(v, t +1) (условие сохранения); VueU:p2{u)=i Vve/:p[(v)=; г(н,г)=1 r(v,r+l)=l 2. V7 є iV 0 fl(u,t) c(u,t) Vw є С/ (условие ограниченности). Определение 3.4.3. В периодической динамической сети GT(X,U,f, т,с) величиной динамического потока, исходящего из источника s в момент времени tQ&N, в сток f называется dxtQ\ — fliuJo). T(u,t0)=l Максимальным динамическим потоком, исходящим из источника s в момент времени t0eN, в сток / называется динамический поток, для которого величина d = ХЖм о) максимальна (обозначим ее d m2&). г(и,/„Н Определение 3.4.4. В периодической динамической сети GT(X,U,/,T,C) величиной динамического потока из источника s\ приходящего в сток / в момент времени /j є N, называется d = Г (и, ). Максимальным динамическим потоком из источника s\ V«e[/:p2(u)=/ г(м,Н приходящим в сток / в момент времени /t є N, называется динамический поток, для которого величина Р" = fliu x) максимальна (обозначим VueU:p2 («)=/ r(«,r,)=l Г hi max ).
Таким образом, можно рассматривать задачи о нахождении величин [/0],тах и і тах. Различие между ними заключается в том, что в первом случае источник рассматривается в одно и то же время /0, тогда как в сток динамический поток может «прийти» в любой момент времени t t0. Во второй задаче, наоборот, известен момент tx, в который динамический поток «приходит» в сток, но начальные моменты времени при этом могут быть различными. Определение 3.4.5. Пусть що]{я\?) — некоторая цепь с началом в момент времени t0 EN , соединяющая источник s и сток f в периодической динамической сети GT(x,U,f, г,с). Назовем дуги этой цепи, направленные от источника к стоку, прямыми, а дуги, направленные от стока к источнику -обратными. Цепь rj {s\t ) называется увеличивающей, если для каждого момента времени t t0(teN) на прямых дугах этой цепи значение динамического потока меньше пропускной способности (т.е. fl{u,i) c{u,t), если дуга а — прямая), а на обратных дугах значение динамического потока положительно {fl{u,i) О, если и -обратная).
Рассмотрим алгоритм Форда-Фалкерсона ([36-37]) для поиска максимального потока в обыкновенном ориентированном графе. Он сводится к последовательному нахождению увеличивающих цепей из источника в сток. Но, так как на графе GT(X,U,f, г, с) допустимыми являются лишь цепи, все дуги которых активны в соответствующие моменты времени, то непосредственно применять этот алгоритм к периодическому динамическому графу нельзя. Приведем два алгоритма, являющихся модификациями алгоритма Форда-Фалкерсона для случая периодических динамических графов. Модификация заключается в том, что к основному набору меток вершин добавляется еще одна метка для обозначения времени - Г/и, и рассматриваются только допустимые увеличивающие цепи.
Кратчайшие пути на периодических динамических графах
Рассмотрим граф изображенный на рис.4.1.2 в условиях магнитной достижимости на отрезке [2,3]N. Найдем кратчайший путь из вершины 1 в вершину 8. Вспомогательный граф приведен на рис.4.1.3. Из вершины 5 = 1 на графе G[2,3] существуют пути длины щ -1 = 1 в вершины 3 (длины 5) и 5 (длины 4), т. е. Т0 = {3,5}. На графе G существуют пути длины п2-пх+\-2 из подмножества {3,5,11,13} в вершины 7 и 15, т.е. Г 0 = {7,15}. Из вершины 7, соответствующей подмножеству Т\ на графе Сг[2,з] существует кратчайший путь {7-8} длины 2 в вершину ґ = 8. Таким образом, кратчайшим путем из вершины s — 1 в вершину t - 8 на графе Gr2 3] с учетом магнитных ограничений на отрезке [2,3]N, является путь {l-»2-»5-»6-»7-»8} длины 11.
Для графов с ограниченными монотонными достижимостями алгоритмы поиска кратчайшего пути аналогичны соответствующим алгоритмам для графов с ограниченными магнитными достижимостями.
Кратчайший путь в обычном ориентированном графе, как известно, обладает свойством экстремальности, т.е., любой отрезок кратчайшего пути также является кратчайшим путем. Для графов с ограниченными магнитными и монотонными достижимостями это свойство не всегда справедливо. Рассмотрим пример: Пример 4.1.6. Пусть G (X,U,f) - граф с магнитными ограничениями на начальном отрезке пути длины п0 = 2 (рис.4.1.6). Рис. 4.1.6 /(щ)=(1,2) /(и2)=(2,3) /(«з) = (2,5) /(и4)=(2,4) Л«5)-(3,5) /к)=(4,5) Ж) = (5,6) /(«,) = 1 /(и2)=1 /(и3)=4 /(w4) = l /(ns) = l /(w6) = 2 /(%) = !
Кратчайшим путем из вершины 1 в вершину 6 является путь // = { , 3,%} Длины 6. Но отрезок этого пути //0 = {и3} длины 4 не является кратчайшим путем между вершинами 2 и 5. Действительно, кратчайшим путем из 2 в 5 является путь //j = { 25 5} Длины 2. С другой стороны, путь {ttj,w2,w5,M7} не является кратчайшим путем между вершинами 1 и 6, так как щ є UM, и2 є UH, т.е. нарушается условие допустимости.
Отметим также, что на графах с ограниченными магнитными и монотонными достижимостями пути не обладают не только свойством экстремальности, но и свойством транзитивности (т.е. если существует путь из вершины х в вершину у и существует путь из вершины у в вершину Z, то существует путь из вершины х в вершину z, проходящий через у). Кратчайшие пути обладают свойством экстремальности и транзитивности на вспомогательном графе, так как он является обыкновенным ориентированным графом без ограничений на достижимость. Вследствие этого, задача о нахождении кратчайшего пути без построения вспомогательного графа может быть решена только полным перебором путей графа. Сложность такого перебора равна o(([max{deg+(jc)}j,j. Сложность алгоритма поиска кратчайшего пути с построением вспомогательного графа равна 0[п2). Таким образом, алгоритм поиска кратчайшего пути с применением вспомогательного графа является более эффективным. Пусть GT(X,U,f,r,l) - взвешенный периодический динамический граф, где /: U -» (0, + оо) - функция, определяющая длину дуги. Определение 4.2.1. Кратчайшим путем с началом в момент времени t0 eN из вершины хєХ в вершину уєХ назовем допустимый путь //[r]:[l,w]N -»С/, соединяющий эти вершины, такой, что сумма длин входящих в него дуг минимальна, т.е. ][ (/4 0](г ))- mm Определение 4.2.2. Пусть ju :[l,w]N — путь на периодическом динамическом графе GT(X,U,f,T,l). Отрезком пути //у называется отображение ju :[иІ5и2]м - U {\. пх п2 п, /, єN), такое, что / (0 = / ,)(0 Vie[w,,/i2].
Для периодических динамических графов, как и для графов с ограниченными магнитными и монотонными достижимостями, свойство экстремальности не всегда справедливо. Рассмотрим пример:
В пунктирной рамке рядом с дугой указана ее длина. Найдем кратчайший путь из вершины 1 в вершину 5 с началом в момент времени /0=1. Таким путем будет jul. :1- 2- 4- 5 длины 17. Рассмотрим отрезки этого пути ц1 :1- 2 и ц1 :2- 4-»5. Они являются кратчайшими путями между вершинами 1 и 2 в момент времени 1 и вершинами 2 и 5 в момент времени 2 соответственно. Но если рассмотреть, например, путь 2 - 4 -» 5 в момент времени / = 5, то он не будет являться кратчайшим путем из 2 в 5, так как при t — 5 дуга и4 неактивна. Кратчайшим путем длины 1 в этом случае будет дуга щ.
Таким образом, справедливость свойства экстремальности отрезков кратчайшего пути для периодического динамического графа зависит от момента времени, в который рассматриваются эти отрезки. Сформулируем теорему: Теорема 4.2.1. Пусть // : [l,/i]N - t/ (t0eN) - кратчайший путь из некоторой вершины х, є X в некоторую вершину х2єХ с началом в момент времени t0 є N на периодическом динамическом графе GT(X,U,f,r,l). Рассмотрим отрезок этого пути //[,]:[HJ,«2]N-»/fo є JV), СОеДИНЯЮЩИЙ ВерШИНЫ ух И У2ЄХ. ДЛЯ ТОГО, ЧТОбы ОТреЗОК JU[t] являлся кратчайшим путем из ух в у2, необходимо и достаточно выполнение условия ?!=f0 + «,-l (4.2.1) которое означает, что начальным моментом времени для отрезка пути //у ДОЛЖеН быТЬ Ґ0+Л,-1, Т.Є. ТОТ МОМеНТ, В КОТОРЫЙ ИСХОДНЫЙ Путь JU[t] проходит дугу M[t0)M-
