11.9. матрицы графов
11.9. матрицы графов
Граф может быть задан разными способами: рисунком, перечислением вершин и ребер (или дуг) и т. д. Одним из самых удобных способов является задание графа с помощью матрицы. Пусть некоторый граф G имеет л вершин ру,рг,ряит ребер аи <хг, Ом. Построим матрицу, имеющую л строк и т столбцов. Каждая строка матрицы будет соответствовать вершине, а столбец — ребру графа. В столбце щ все элементы, кроме двух, будут равны нулю. Для ориентированного графа в строке, соответствующей начальной вершине дуги щ, ставят число +1, а в строке, соответствующей конечной вершине, — число — 1. Для неориентированного графа в строках матрицы, соответствующих концевым вершинам ребра а,-, ставят 1, а в остальных строках — 0. Для графов, изображенных на рис. 11.12 и 11.9, матрицы имеют соответственно следующий вид:
«1 | <h | «а | «3 | *1 | 0(3 | *+ | «5 | «6 | |||
Pi | 1 | 0 | -1 | 1 | о; Pl | і | 1 | 0 | 0 | 0 | 0 |
Pi | -1 | 1 | 0 | 0 | 0 A | 0 | 1 | 1 | 0 | 1 | 1 |
Pi | 0 | -1 | 1 | -1 | 1 Ръ | 0 | 0 | 0 | 0 | 0 | 1 |
р*. | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | |
Pi | 1 | 0 | 1 | 1 | 0" | 0 |
Построенные матрицы называются матрицами инциденций графа.
Матричное представление графа является наиболее удобной формой задания графа при вычислениях на машине.
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.
Этот поток является максимальным. Если начальные данные целочисленны, то выполнение алгоритма Форда завершается за конечное число шагов.
Обсуждение Справочник по математике для экономистов
Комментарии, рецензии и отзывы