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

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

Граф может быть задан разными способами: рисунком, перечислением вершин и ребер (или дуг) и т. д. Одним из самых удобных способов является задание графа с помощью матрицы. Пусть некоторый граф G имеет л вершин ру,рг,ряит ребер аи <хг, Ом. Построим матрицу, имеющую л строк и т столбцов. Каждая строка матрицы будет соответствовать вершине, а столбец — ребру графа. В столбце щ все элементы, кроме двух, будут равны нулю. Для ориентированного графа в строке, соответствующей начальной вершине дуги щ, ставят число +1, а в строке, соответствующей конечной вершине, — число — 1. Для неориентированного графа в строках матрицы, соответствующих концевым вершинам ребра а,-, ставят 1, а в остальных строках — 0. Для графов, изображенных на рис. 11.12 и 11.9, матрицы имеют соответственно следующий вид:

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

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

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

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

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

Дивергенцией потока f в вершине р называется разность выхо-! дящих и входящих потоков: div»= J fip.q)- £ /(rljP),

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

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

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

р

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

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

2) div/(p) = 0 при всех р, кроме, быть может, p=s np=t.

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

Из предыдущего следует, что div/(s)= — div/(0=A/. Если М=0, то поток называется циркуляцией. В противном случае (МФІУ) вершина s является источником потока, а вершина / — стоком. Число М>0 называется мощностью потока/

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

Если рассматриваемая сеть G содержит параллельные дуги, то нужно рассмотреть новую сеть (?' с теми же вершинами, что н G, в которой параллельные дуги а и /? склеены. Пропускная способность полученной при этом дуги у есть С(у)=С(а) + C(fi). После получения решения/для сети G' оно разбивается на сумму № =fi +/а, где 0 </; С (а), 0 </г ^ С (fi).

Нахождение увеличивающей цепи

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

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

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

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

Af(s,p)=9-1 = 2, ДДр,г)=4-2~2, f(m, r)= 1, f(n, m)= 1, ДДп, 0=4-3 = 1.

Очевидно, что мощность потока возрастет на 1 (рис. 11.14). \% В общем случае вдоль некоторой цепи, соединяющей вершины sat, можно увеличить поток, если ее прямые дуги — увеличивающие, а все обратные — уменьшающие.

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

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

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

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

Далее отмечают некоторые дуги и вершины сети G. Именно: если вершина р отмечена, а вершина q — нет и дуга а—{р.

q)eA + , то отмечают дугу а и вершину q. Если вершина р отмечена, а вершина q не отмечена и дуга a~(q, р)єА~, то отмечают дугу а и вершину q.

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

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

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

Для любой отмеченной вершины будем просматривать все

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

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

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

Алгоритм отыскания максимального потока в сети

Данный алгоритм, использующий увеличивающие цепи, называется алгоритмом Форда. Он состоит из следующих шагов. 1. Выбирают некоторый поток /(а) из jb t (например,/(а)=0).

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

(А~) дуг.

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

Находят min (Af(a)), min f(a).

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

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

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

/(а)^с(а),

d'ivf(p)=0 при р Фs, рф t.

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