Федоров В.Н. - Введение в теорию графов (1023556), страница 12

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 12)

Если такая единица есть, то число выделенных полужирным шрифтом единиц можно увеличить. В противном случае ищем 1 в помеченной строке, по 1, выделенной шрифтом, в этой строке ищем…

Если не можем больше найти столбца, с помощью которого можно увеличить число выделенных шрифтом 1, то единицы, выделенные полужирным шрифтом, дают максимальное паросочетание.

В рассматриваемом примере столбец y₇ не помечен. Он содержит 1 в клетке (x₃,y₇). В строке x₃ единица, выделенная полужирным шрифтом, стоит в клетке (x₃,y₆). В столбце y₆ в клетке (x₅,y₆) стоит 1 и соответствующая ей строка x₅ не помечена. Следовательно, возможно увеличить число единиц, выделенных полужирным шрифтом. Выделяем полужирным шрифтом 1 в клетке (x₃,y₇), а перед этим запишем обычным шрифтом 1 в клетку (x₃,y₆), и выделяем полужирным шрифтом 1 в клетке (x₅,y₆) табл. 12.8.

Таблица 12.8

	y1	y2	y3	y4	y5	y6	y7
x1	1	1	0	0	1	0	0
x2	1	1	0	1	0	1	0
x3	0	0	1	0	0	1	1
x4	0	0	1	0	0	1	0
x5	0	0	0	0	0	1	0
x6	0	0	1	0	0	0	1

Нетрудно проверить, что процедуру нельзя продолжить. Единицы, выделенные полужирным шрифтом, дают максимальное паросочетание

V₀ = {(x1,y2), (x2,y1), x3,y7), (x5,y6), (x6,y3)}.

Н
а рис. 12.5 приведен граф, соответствующий матрице табл. 12.8, на котором максимальное паросочетание выделено толстыми линиями.

Рисунок 12.5

В общем случае может быть несколько возможных решений.

12.3. Контрольные вопросы

1. Какой граф называется двудольным? Сколько красок требуется для раскраски вершин двудольного графа? А для раскраски его ребер (дуг)? Приведите пример двудольного графа и представьте его в матричной форме.

2. Что такое покрытие двудольного графа? Чем отличается реберное покрытие от вершинного покрытия?

3. Приведите алгоритм получения минимального реберного покрытия графа с использованием матрицы инцидентности. Сколько минимальных покрытий может быть у графа?

4. Найдите минимальное вершинное покрытие графа, показанного на рис. 12.3, применив алгоритм с использованием матрицы инцидентности.

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

6. Что такое паросочетание двудольного графа? Каково условие существования паросочетания? Что показывает дефицит двудольного графа?

7. Приведите алгоритм определения максимального паросочетания двудольного графа.

8. Покажите на рис. 12.5 другие возможные максимальные паросочетания.

13. Сети

Сеть N есть связный ориентированный (не обязательно) граф, который не имеет петель и удовлетворяет следующим условиям:

1. Существует только одна вершина с нулевой полустепенью захода; эта вершина называется источником и обозначается через s.

2. Существует только одна вершина с нулевой полустепенью исхода; эта вершина называется стоком и обозначается через t.

3. Каждой дуге e = (i, j) в сети N сопоставлено неотрицательное вещественное число, называемое пропускной способностью дуги и обозначаемое через с(е) или c(i, j), где i и j вершины сети. Если не существует дуги е, ориентированной из i в j, то c(e) = 0.

Сеть представляет собой, например, модель сети передачи информации от источника до потребителя через связывающие их информационные каналы.

Пропускная способность дуги может рассматриваться как максимальный допустимый объем информации, передаваемый по дуге в единицу времени.

Потоком f в сети N является функция, сопоставляющая каждой дуге e = (i, j) вещественное число f(e) = f(i, j) так, что удовлетворяются следующие условия:

1. 0 f(i, j) c(i, j) для любой дуги (i, j) в N.

2. суммы берутся по всем j для всех .

Значение потока f(e) в дуге е можно рассматривать как фактический объем информации, передаваемый через е в единицу времени, при потоке в сети f.

Условие 1, называемое ограничением по пропускной способности, требует, чтобы объем фактически передаваемой информации через дугу не превосходил ее пропускной способности и был положительным.

Условие 2, называемое условием сохранения, требует, чтобы для каждой вершины i, исключая источник и сток, объем поступающей информации в вершину в единицу времени был равен объему, удаляемому из нее.

П
ример сети N с потоком f представлен на рис. 13.1. На нем рядом с каждой дугой е приведены пропускная способность с(е) и поток f(e) в указанном порядке.

Рисунок 13.1

Величина потока в сети f, обозначаемая через val(f), определяется выражением

,

где сумма берется по всем дугам, выходящим из источника s.

Используя условие сохранения, можно записать

=

Это подтверждение интуитивно очевидного факта, что ввиду условия сохранения общее количество информации, выходящей из источника, равно общему количеству информации, входящей в сток.

Говорят, что поток f* в сети N максимален, если не существует такого потока f в N, что val(f)>val(f*).

13.1. Максимальный поток в минимальном разрезе

Будем говорить, что разрез < > в сети N разделяет источник s и сток t, если . Такой разрез будем называть s–t разрезом. (Здесь и подмножества вершин сети, причем = V\S.)

Пропускная способность разреза K = < > определяется выражением

с(K) = с( ) = .

Здесь начала дуг принадлежат подмножеству S, а концы подмножеству . Отметим, что пропускная способность дуг, которые ориентированы из в S, не влияет на пропускную способность разреза K = < >.

Обозначим через f( ) сумму потоков в дугах, ориентированных из S в . Величина f( ) определяется аналогично.

Например, рассмотрим разрез K = < > в сети, изображенной на рис. 13.1, где S = {а, b, с, s} и ={d, t}.

Дугами, ориентированными из S в , являются дуги e₃, e₄, e₈.

Из в S ориентирована только дуга e₉. Следовательно, пропускная способность разреза будет равна

c( ) = с(e₃) + с(e₄) + с(e₈) = 3+2+6 = 11,

поток через разрез в прямом направлении будет равен

f( ) = f(e₃) + f(e₄) + f(e₈) = 2+2+4 =8,

поток через разрез в обратном направлении будет равен

f( ) = f(e₉) = 2.

Для любого потока f и любого s–t разреза < > в сети N величина потока через разрез равна

val(f) = f( ) – f( ) и val(f) c( ).

Для нашего примера

val(f) = f( ) – f( )= 8 – 2 = 6.

Дугу (i, j) будем называть насыщенной, если f(i, j) = c(i, j), и ненасыщенной в противном случае (всегда f(i, j) c(i, /)).

Дуга будет положительной, если f(i,j) > 0, и нулевой, если

f(i, j) = 0 (всегда f(i,j) 0).

Пусть последовательность

P: s, e₁, u₁, e₂, u₂,…, e_k, u_k = v

является цепью в сети N из источника s в какую–либо вершину v.

Отметим, что Р – необязательно ориентированный путь.

Дуга e_i цепи Р называется прямой дугой, если она ориентирована из u_i–1 в u_i. Иначе она называется обратной дугой цепи Р.

В общем случае дуги в цепи могут быть как прямыми, так и обратными. Если в цепи все дуги прямые, то цепь называется путем.

Для каждой дуги e_i цепи Р определим величину

Поставим в соответствие цепи Р неотрицательное число , определяемое выражением

Характеристики

Список файлов книги