Тема: Сетевые модели (стр. 2 )

Улицы представляются дугами некоторого графа. За­дача почтальона заключается в том, чтобы найти марш» рут обхода всех дуг графа минимальной длины.

Задача строительства дорог. Имеется п городов, кото­рые нужно соединить между собой новыми дорогами (не обязательно каждые два города должны быть связаны друг с другом непосредственно). Известна стоимость про­кладки дороги между любыми двумя городами. Тре­буется составить проект строительства дорог минималь­ной стоимости.

Очевидно, что каждый город представляется верши­ной графа, а дорога –дугой, соединяющей вершины. Каж­дой дуге ставится в соответствие число, равное стоимости строительства соответствующей дороги. Требуется по­строить некоторое «покрытие» графа минимальной стои­мости.

Матрицы графов

Граф может быть задан разными способами: рисунком, перечислением вершин и ребер (или дуг) и т. д. Одним из самых удобных способов является задание графа с помощью матрицы. Пусть некоторый граф G имеет n вершин p1, p2, ..., pn и m ребер α1, α2, ..., αm.

Построим матрицу, имеющую n строк и m столбцов. Каждая строка матрицы будет соответствовать вершине, а столбец – ребру графа. В столбце α j все элементы, кроме двух, будут равны нулю. Для ориентированного графа в строке, соответствующей начальной вершине дуги αj, ставят число +1, а в строке, соответствующей конечной вершине, – число -1. Для неориентированного графа в строчках матрицы, соответствующих концевым вершинам ребра αj ставят 1, а в остальных строчках – 0. Для графов, изображенных на рис. 1.12 и 1.9, матрицы имеют соответ­ственно следующий вид:

	α1	α2	α3	α4	α5			α1	α2	α3	α4	α5	α6
p1	1	0	-1	1	0		p1	1	1	0	0	0	0
p2	-1	1	0	0	0		p2	0	1	1	0	1	1
p3	0	-1	1	-1	1		p3	0	0	0	0	0	1
p4	0	0	0	0	-1		p4	0	0	0	1	1	0
							p5	1	0	1	1	0	0

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

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

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

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

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

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

где A(p) – множество дуг, выходящих из вершины р, а B(p) – множество входящих в нее дуг.

Вершины, в которых , называются источниками потока f, а вершины, в которых − его стоками.

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

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

1) на всех дугах ;

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

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

Из предыдущего следует, что

Если M=0 , то поток называется циркуляцией. В против­ном случае M≠0 вершина s является источником по­тока, а вершина t – стоком. Число М > 0 называется мощностью потока f.

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

Если рассматриваемая сеть G содержит параллельные дуги, то нужно рассмотреть новую сеть G' с теми же вершинами, что и G, в которой параллельные дуги α и β склеены. Пропускная способность полученной при этом дуги у есть . После получения решения f для сети G' оно разбивается на сумму где .

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

Пусть заданы сеть G и какой-то поток f на этой сети. Дуги α, в которых , называются увеличивающими, так как поток через эти дуги можно увеличить на величину . Множество увеличивающих дуг обозначается .

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

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

Пример. Рассмотрим сеть, изображенную на рис. 1.13, и некоторый поток f. Возьмем цепь (s, p, r, m, n, t) соединяющую вершины s и t. Вдоль этой цепи можно увеличить поток на минимальную из величин

Очевидно, что мощность потока возрастет на 1 (рис. 1.14).

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

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

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

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

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

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

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

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