11.9. матрицы графов

11.9. матрицы графов

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

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

Для неориентированного графа в строках матрицы, соответствующих концевым вершинам ребра а., ставят 1, а в остальных строках — 0.

Для ориентированного графа в строке, соответствующей начальной вершине дуги ос., ставят число +1, а в строке, соответствующей конечной вершине, — число -1.

316

Для графов, изображенных на рис. 11.9 и 11.12, матрицы имеют соответственно следующий вид:

Построенные матрицы называются матрицами инциденций графа.

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

11.10. Максимальные потоки в сети

Поток на графе — это совокупность однородных объектов, пересылаемых из одной вершины в другую по его дугам. Если вершины р и q соединены дугой а = (р, q), то поток из/? в я обозначается fip, q). Таким образом, поток — это некоторая функция, заданная на дугах графа.

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

Дивергенцией потока f в вершине р называется разность выходящих и входящих потоков:

tivf(p)= X f(P>9)~ X f(r,P), (П-5)

(p,q)eA(p) (г,р)єВ(р)

где А(р) — множество дуг, выходящих из вершины р, а В(р) — множество входящих в нее дуг.

Вершины, в которых dif(p) > 0, называют источниками потока /, а вершины, в которых dif(p) < 0, — его стоками.

Сложим дивергенцию потока / во всех вершинах графа. Очевидно, что

D = ^diwf(p) = 0. (11.6) р

317

Пусть задана сеть, в которой выделены две вершины: ли/. Рассмотрим такие потоки /(а), что:

1) 0 < /(а) < С(а) на всех дугах а;

2) drvjip) 0 при всехр, кроме, быть может, р = s ир = t.

Вершины s и t называются полюсами сети, а остальные вершины — внутренними.

Из (11.4) следует, что diwf(s) -divy(0 М. Если МО, то поток называется циркуляцией. В противном случае (М Ф 0) вершина s является источником потока, а вершина t — стоком. Число М > 0 называется мощностью потока /

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

Если заданная сеть G содержит параллельные дуги, нужно рассмотреть новую сеть G', у которой будут те же вершины, что и у G, но параллельные дуги аир склеены. При этом пропускная способность склеенной дуги у есть С(у) = С(сх) + С(Р). После получения решения / для сети G' оно разбивается на сумму /(у) = fy+f2, где 0£/і£С(а),0£/2£С(Р).

Увеличивающая цепь. Пусть заданы сеть Си какой-то поток/на этой сети. Дуги а, в которых /(а) < С(сс), называются увеличивающими, так как поток через эти дуги можно увеличить на величину Д/(ос) = С(ос) /(ос). Множество увеличивающих дуг обозначают А+.

Дуги а, в которых /(а) > 0, называются уменьшающими, так как поток через эти дуги можно уменьшить на величину /(ос). Множество уменьшающих дуг обозначают А~.

Заметим, что дуга ос может принадлежать одновременно множествами и А~.

О Пример. Рассмотрим сеть, изображенную на рис. 11.13, и некоторый поток/. Пусть C(s,p) = 9, С(р, г) = 4, С(и, t) = 4. Возьмем цепь (s,p, г, т, п, t), соединяющую вершины s и t. Вдоль этой цепи можно увеличить поток на минимальную из величин

ДЖ/>) = 9-7 = 2, Д/(р,г) = 4-2 = 2,

f(m,r) = , f(n,m) = 1, Д/(«, 0 = 4-3 = 1.

Очевидно, что мощность потока возрастет на единицу (рис. 11.14). •

318

Рис. 11.13

Рис. 11.14

Рис. 11.15

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

Максимальный дополнительный поток 8, который можно переслать вдоль такой цепи, равен минимуму из всех Л/(ос) для прямых дуг а и всех /(а) для обратных дуг а.

Алгоритм нахождения увеличивающей цепи:

Находят множество дуг А+ и А~.

Отмечают вершину s (источник).

Далее отмечают некоторые дуги и вершины сети G: если вершина р отмечена, а вершина q не отмечена и дуга а = (р, q) є А+ либо а (q, р) є А~, то отмечают дугу а и вершину q.

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

Замечание. Приведенный алгоритм не указывает, в каком порядке нужно просматривать дуги. Например, можно сначала просмотреть все дуги, инцидентные s, отметить некоторые вершины в соответствии с правилами; затем просмотреть все дуги, инцидентные отмеченным вершинам, и т.д. В другом варианте всякий раз просматривают дуги, инцидентные последней отмеченной вершине, и т.д. Этот алгоритм позволяет получить увеличивающую цепь из S в t.

О Пример. Применим алгоритм построения увеличивающей цепи к графу, изображенному на рис. 11.15.

Для любой отмеченной вершины будем просматривать все инцидентные ей дуги. Отмечаем источник s. Дуги (s,p), (s, и) отмечаем как выходящие увеличивающие, а дугу (г, s) — как входящую уменьшающую (рис. 11.16).

319

В скобках указаны вершины, соединенные с новыми вершинами отмеченными дугами. Далее просматриваем дуги, инцидентные р (рис. 11.17). Дугу {р, г) не рассматриваем, поскольку вершина гуже отмечена. Далее, просматривая дуги, инцидентные п, отмечаем дугу (и, f), вершину іи дугу (и, /я), вершину т (рис. 11.18).

На этом просмотр заканчиваем, так как отмечен сток t. Идя в обратном направлении, получаем увеличивающую цепь (s, и, t). •

Алгоритм отыскания максимального потока в сети. Данный алгоритм, использующий увеличивающие цепи, называется алгоритмом Форда. Он состоит из следующих шагов:

Выбирают некоторый поток /(ос) из s в t (например,

До0 = 0).

Находят классы увеличивающих (А+) и уменьшающих (А ) дуг.

Применяют алгоритм поиска увеличивающей цепи из s в t. Если такой цепи нет, то поток / — максимальный. Если цепь С найдена, то переходят к шагу 4.

Находят тіл (Д/(ос)), min /(а).

аєА*пС аєА rC

Пусть 8 > 0 — наименьшее из этих чисел.

Увеличивают поток вдоль цепи С на 8 и переходят к шагу 2.

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

До0<С(ос),

div^(p) = 0 при рфь,рфі.

Этот поток является максимальным. Если начальные данные целочисленны, то выполнение алгоритма Форда завершается за конечное число шагов.

320