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

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

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.

 

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

Страница: | 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 |