Имя материала: Справочник по математике для экономистов

Автор: В.И. Ермаков

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

 

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

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

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

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

 

316

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

 

 

«і

ot2

«3

«4

«5

«6

 

 

«i

oc2

oc3

«4

«5

Pi

1

1

0

0

0

0

 

Pi

1

0

-1

1

0

Pi

0

1

1

0

1

1

 

Pi

-1

1

0

0

0

Pi

0

0

0

0

0

1

 

Ръ

0

-1

1

-1

1

Pa

0

0

0

1

1

0

 

Pa

0

0

0

0

-1

Ръ

1

0

1

1

0

0

 

 

 

 

 

 

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

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

 

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

Страница: | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | 51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 | 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 | 71 | 72 | 73 | 74 | 75 | 76 | 77 | 78 | 79 | 80 | 81 | 82 | 83 | 84 | 85 | 86 | 87 | 88 | 89 | 90 | 91 | 92 | 93 | 94 | 95 | 96 | 97 | 98 | 99 | 100 | 101 | 102 | 103 | 104 | 105 | 106 | 107 | 108 | 109 | 110 | 111 | 112 | 113 | 114 | 115 | 116 | 117 | 118 | 119 | 120 | 121 | 122 | 123 | 124 | 125 | 126 | 127 | 128 | 129 | 130 | 131 | 132 | 133 | 134 | 135 | 136 | 137 | 138 | 139 | 140 | 141 | 142 | 143 | 144 | 145 | 146 | 147 | 148 | 149 | 150 | 151 | 152 | 153 | 154 | 155 | 156 | 157 | 158 | 159 | 160 | 161 | 162 | 163 | 164 | 165 | 166 | 167 | 168 | 169 | 170 | 171 | 172 | 173 | 174 | 175 | 176 | 177 | 178 | 179 | 180 | 181 | 182 | 183 | 184 | 185 | 186 | 187 | 188 | 189 | 190 | 191 | 192 | 193 |