Наряду с задачей отыскания максимального потока большое практическое значение имеет задача экономичного распределения потока по дугам транспортной сети, получившая название транспортной задачи. Поскольку транспортная сеть во многих случаях представляет собой схему организации перевозок каких-либо грузов, то решение транспортной задачи позволяет определить наиболее рациональный план перевозок, т.е. такое распределение маршрутов, которое обеспечивает, например, минимальную стоимость перевозок или доставку грузов к потребителю в кратчайшее время.
Первая задача получила название транспортной задачи по критерию стоимости, а вторая — по критерию времени.
Для каждой дуги (xi, xj) введём ещё один вес - стоимость прохождения единицы потока по ней - и обозначим его dij.
Транспортную задачу по критерию стоимости в терминах теории графов можно сформулировать следующим образом. Даны транспортная сеть с наибольшим потоком jmи поток jz, который должен быть пропущен по этой транспортной сети. Требуется найти такое распределение потока jz по дугам, которое обеспечивает минимальную стоимость прохождения потока. При этом для каждой дуги должно выполняться соотношение j(xi, xj)£ cij, а стоимость прохождения потока j(xi, xj) по дуге (xi, xj) равна dijj(xi, xj).
Для решения этой задачи будем рассматривать величины dijкак длины соответствующих дуг. В этом случае стоимость прохождения потока j по какому-либо пути m от xx0 до z будет равна произведению длины этого пути на величину потока j и задача минимизации стоимости прохождения потока сведется к решению рассмотренной ранее задачи нахождения кратчайшего пути в графе от xx0 до z. При отсутствии ограничений на пропускную способность дуг, кратчайший путь является путем, который обеспечивает минимальную стоимость прохождения потока.
При наличии ограничений на пропускную способность дуг задача решается в несколько этапов, путем нахождения частичных потоков на каждом этапе. Общий путь решения задачи состоит в следующем.
В графе G1 = (X, R), изображающем транспортную сеть с длинами дуг dij = l(xi, xj)l, ищется кратчайший путь m1от xx0 до z. Пусть c1 — пропускная способность этого пути. По нему пропускается поток
jz, если jz£с1;
j1=
с1, если jz>c1.
Если jz £ c1, то задача решена и путь m1 является наиболее экономичным для потока jz.
Если jz > c1, то поток j1 рассматриваем как частичный и переходим к графу G2, который получается из графа G1 путем замены пропускных способностей дуг cij на c’ij из соотношения
cij-c1 для uÎ m1;
c`ij=
с1 для u Ï m1.
При этом дуги, у которых c’ij = 0, исключаются из рассмотрения. Поток, распределение которого ищется в графе G2, принимаем равным j`1=jz-j1.
Теперь возникает первоначальная задача отыскания наиболее экономичного распределения потока j’z, но уже по отношению к графу G2. Ее решение дает путь m2с пропускной способностью c2, через который пропускается частичный поток
j`z, если j`z£с2;
j2=
с2, если j`z>c2.
Если j’z£ c2, то задача решена и наиболее экономичным распределением потоков в графе G1 будет прохождение потока j1по пути m1и потока j2 по пути m2.
Если j’z> c2, то следует перейти к новому графу G3 и найти новый частичный поток j3. Этот процесс повторяется до тех пор, пока сумма частичных потоков не достигнет значения jz. Эти частичные потоки, пропущенные по графу G1, и дают оптимальное распределение потока jz.
Для иллюстрации описанного метода рассмотрим наиболее часто встречающийся вариант транспортной задачи по критерию стоимости.
Однородный груз имеется на станциях х1,...,xтв количествах a1,...,am. Его требуется доставить на станции y1, ..., уr в количествах b1, ..., br. Предполагается, что общее количество требуемого груза равно имеющимся запасам: S ai=S bj.
Стоимость перевозки груза со станции xi на станцию уi равна dij. Требуется найти наиболее экономичные маршруты перевозки грузов. Исходные данные удобно записывать в виде табл. 3.4.
Таблица. 3.4
b1
…
br
A1
d11
…
d1r
…
…
…
…
am
dm1
…
dmr
Транспортная сеть для этой задачи строится следующим образом. Вход x0 соединяется с каждой из вершин xi дугой с пропускной способностью с(x0, xi) = ai. Каждая из вершин yi соединяется с выходом z дугой с пропускной способностью с(yi, z) = bj. Стоимость прохождения потока по дугам (x0, xi) и (yi, z) считается равной нулю. Наконец, каждая вершина xi соединяется с каждой вершиной yi дугой с бесконечной пропускной способностью, стоимость прохождения единицы потока по которой равна dij. Далее к этой транспортной сети применяется рассмотренный метод.
Пример. Найти наиболее экономичные маршруты для транспортной задачи, заданной табл. 3.5
Таблица. 3.5
Применяя описанный выше метод к транспортной сети, построенной по табл. 3.5 (рис. 3.12), находим частичные потоки и маршруты, перечисленные в табл. 3.6 в порядке их получения.
Таблица 3.6
Номер маршрута
Маршрут (хi, yj)
Частичный поток jk, ед.
dij
Стоимость перевозки dijjk, ед.
(х3, y1)
(х2, y2)
(х1, y4)
(х3, y4)
(х3, y3)
(х2, y3)
Всего
–
–
Рис. 3.12
Следовательно, разобранный метод решения транспортной задачи дает, по существу, способ нахождения величин частичных потоков j(xi, yj), минимизирующих указанную сумму.
Решение транспортной задачи по критерию времени рассмотрим на примере транспортной сети, заданной табл. 3.6, в которой величины dijбудем теперь трактовать как время, необходимое на перевозку груза из пункта xiв пункт yj и обозначить далее через tj. С подобными задачами можно столкнуться три транспортировке скоропортящихся продуктов, при доставке средств помощи в районы стихийных бедствий, при вывозе зерна нового урожая в заготовительные пункты и т. п. Во всех этих задачах стоит требование доставки всех грузов в пункты назначения за возможно более короткий промежуток времени.
Рассмотрим общий путь решения этой задачи. Предположим, что каким-либо методом найдено некоторое распределение потока jzв графе G, изображающем рассматриваемую транспортную сеть. Выделим из графа G частичный граф G', в который включим только дуги, участвующие в передаче потока jz. Пусть m — некоторый путь, ведущий из x0 в z, aa tm — время прохождения потока по этому пути. Очевидно, что время, необходимое на перевозку всех грузов из x0 в z, будет определяться путем, имеющим наибольшую продолжительность прохождения потока, так как перевозка грузов по остальным путям закончится раньше. Следовательно, время Т, требуемое на перевозку всех грузов, будет равно T=maax tm.
Решение транспортной задачи по критерию времени сводится, таким образом, к тому, чтобы выделить из графа G такой частичный граф G’, который был бы способен пропустить весь поток jz и в котором длительность наиболее продолжительного пути была бы минимальной по сравнению со всеми другими подобными графами.
Задача решается последовательным улучшением графа G' путем удаления из него наиболее продолжительных путей и введения более коротких, но не примененных ранее, и соответствующего перераспределения потока jz.
Обратимся к рассматриваемому примеру. В качестве первого приближения к наилучшему решению примем решение, полученное на основе критерия стоимости. Распределение потоков для этого случая показано на рис. 3.12. Из этого рисунка видим, что время прохождения потока по наиболее продолжительному маршруту (х2, yз) равно 6. Однако оказались неиспользованными менее продолжительные маршруты (х1, y2), (х2, y1), (х1,yз). Возможно, что использование какого-либо из этих маршрутов позволит исключить маршрут (х2, yз).
Построим частичный граф G', в который включим только дуги графа G, имеющие tij < 6 и в котором распределение потока останется тем же, что и в графе G. Граф G' показан на рис. 3.13, где для удобства вершины yj обозначены через xm+j = x3+j. Поток j’z через этот граф равен 45 ед., т. е. меньше, чем первоначальный поток jz = 50 ед. Этот поток является полным, так как в графе G' все пути из х0 в zz содержат насыщенные дуги. Однако возможно, что он не является наибольшим.
Если наибольший поток в графе G' равен jz, то найдется распределение этого потока, при котором наиболее продолжительный путь будет иметь время tm < 6 ед. Следовательно, дальнейшее решение задачи сводится к определению наибольшего потока в графе G'.
На рис. 3.13 произведена разметка вершин графа G' в соответствии с алгоритмом Форда и Фалкерсона. Разметка вершин указывает на существование пути (х0, х2, х4, х3, х6, z), на котором поток в направлении от х0к z может быть увеличен на 5 ед.
Рис. 3.13.
Таблица 3.7
Маршрут, ед.
Частичный поток
Время прохождения потока
(х2, y2)
(х1, y4)
(х3, y4)
(х2, y1)
(х3, y3)
–
jz = 50
Tmax = 4
Этот добавочный поток показан стрелками. Как видим, наибольший поток в графе G' равен jz = 50 ед. и наиболее продолжительный маршрут имеет время 4 ед. Дальнейшего уменьшения времени прохождения потока добиться невозможно, так как к вершине yз(х6) не идут маршруты со временем, меньшим 4 ед.
Окончательное распределение частичных потоков по маршрутам, дающее решение транспортной задачи по критерию времени, приведено в табл. 3.7.
3.5.8.Цикломатическое число графа
Пусть в графе m - число ребер, n- число вершин, p -число компонент связности. Величина r=n-p называется коцикломатическим числом. Цикломатическим числом графа называют число n=m-n+p.
Формально понятие независимых циклов вводится следующим образом. Введём в графе произвольную ориентацию ребер. Рассмотрим некоторый произвольный цикл и сопоставим ему вектор, который содержит m компонент, сопоставленных рёбрам по правилу: значение компоненты
rij= r+ij – r--ij, где r+ij- число проходов по циклу по направлению ребра, r--ij –число проходов против направления ребра.
Введем две операции на множестве всех векторов: сложение векторов как покомпонентное сложение их компонент и умножение вектора на число как умножение каждой компоненты на это число.
Множество векторов называется линейно независимым, если равенство a1r1+a2r2...+aкrк=0 выполняетсятолько при a1=a2.=...=aк=0. Множество векторов с введенными операциями образуют линейное пространство. Множество, содержащее максимальное число его линейно независимых векторов, называется базисом пространства, число элементов базиса называется размерностью пространства. В этом пространстве любой вектор может быть выражен как сумма произведений базисных векторов на константы.
Теорема. В графе число n определяет число независимых циклов в нем.
Доказательство проводится по индукции. Предположим, что теорема справедлива для числа рёбер m, и покажем, что тогда она справедлива и для m`=m+1. Добавим в граф G ещё одно ребро (a,b), тогда возможны два случая:
1. В G вершины aи b связаны цепью, тогда в расширенном графе G’ добавится еще один цикл, т.е. будет m’=m+1, p’=p, n’=n+1.
2. В Gвершины a и b цепью не связаны, тогда в расширенном графе G’ уменьшится на единицу число компонент связности, т.е. m’=m+1, p’ = p -1, n ’= n.
Для любого графа проделаем такую процедуру: удалим из него все ребра и затем введём их по одному. Для графа без ребер утверждение теоремы верно (число циклов и число ребер равно 0, число вершин равно числу компонент связности). Каждое новое ребро будет приводить к описанным выше двум случаям, т.е. будет выполняться утверждение теоремы.
Если графу сопоставить электрическую сеть, то r – наибольшее число независимых разностей потенциалов в сети между ее узлами, n – число независимых круговых токов, которые могут протекать в этой сети.
Плоскими графами называют графы, которые можно так расположить на плоскости, чтобы ребра пересекались только в вершинах графа. Графы, которые расположены на плоскости без пересечения, называют планарными. Планарные графы, получающиеся один из другого непрерывной деформацией плоскости, не считаются различными.
Часть плоскости, ограниченная ребрами и не содержащая внутри себя ни вершин, ни ребер, называется гранью. Одна из граней является внешней. Грани, разделенные ребрами, называются смежными.
Для планарного графа число граней f cвязано с числом его вершин n и числом его ребер m формулой Эйлера n-m+f=2.
В справедливости формулы можно убедиться следующим образом. Граням сопоставим циклы из ребер, их ограничивающих. Число граней больше на единицу числа независимых циклов (за счет внешней грани), т.е. с учетом формулы для n f-1=m-n+1, откуда непосредственно следует формула Эйлера.
Можно убедиться, что минимальным неплоским графом по числу элементов будет граф К5(рис 3.14,а), по числу ребер–максимальный двудольный граф с числом вершин 6 (такой граф обозначается как К3,3, рис.3.14,б). Если такой граф входит в G, то G становится неплоским.
а б
Рис.3.14
Граф G’ называют гомеоморфным графу G, если он может быть получен из G заменой некоторых цепей на ребра.
Условие планарности графа определяет теорема Понтрягина-Куратовского:
Граф G будет плоским тогда и только тогда, когда он не содержит графов, гомеоморфных графам К5 и К3,3.
Теорема Понтрягина-Куратовского определяет условия того, что граф является плоским, но не даёт конструктивного способа организации проверки этого свойства (кроме полного перебора).
К практическим задачам, связанным с расположением графа на плоскости, можно отнести такие задачи, как
расположение графа на плоскости с минимальным числом пересечений его рёбер;
выделение минимального числа рёбер, удаление которых делает граф плоским;
разбиение графа на минимальное число плоских подграфов.
jz, если jz£с1;
cij-c1 для uÎ m1;
