Elementy_teorii_grafov_2

ассмотрим следующий пример. Необходимо спроектировать крат-

íåîáчайшуюодимоòåëåèç ïîëíоннуюãîñåòü, связывающуюKn заданнымиn абонедлинамиòîâ.

реберВ этом случае

ñâоих ребер. Этот подгра ,

îá

является деревом, выбратьак к к

язный остовной по

имеющий наименьшую суммарную длину

öèêë , è ï

циклэтом гра остан тсязательносвязным

остовным, но суммар ая

иначе есть

и, след вательно, можно

далить любое ребро этого

ïîäãðà есть дерево, но дере о, имеющее

наименьшую длину.

äëèí åãî ðебер станет меньше. Таким образом, кратчайший остовíîé

лить его кратчайший остовной подгра D(X,V), тНеобходимо. . такой, что

Постановк з дачи. Дан

язный

G(X,U).

âûäå-

X

l(V ) = i2V li

подгра ов.

для всех связных остовных

минимальна1. В к честве начального подгра а D берем пустой подгра D(X; ;)

Для решения

задачи есть несколько

. Но наиболее

простым

широкэтойиспользуемым является алгоритмовКраскала

.

2

упорядочиваем множество ребер U гра а G(X; U) по возраста-

íèþ ä èí.

ребро из U

дящее к циклу

2. Доб вляем к D

ребра 2

(ïðè

ости,привок торым принад-

надлежатдобавлениидной омпоненте связности,

добавление

такого

при этом ребра помечаемкратчайшееак вычåркнутые.

конца ребра

л жат концы ребра, сливаютсяомпонентыдну;

åñëè æ

ребра

приводит

циклу).

Добавл нное ребрто

или пропущенные

3. Повторяем пункт 2 до тех пор, пока число добавленных р бер

V не станет равным n 1. Полученный гра D(X; V ) и есть

кратчайшее остовное дерево.

при выполнении алго-

Обоснование. Покажем сначàëà, ÷òî

2 Алгоритм Прима являетсявляетсболее э ективнымполученыйтрудоемкости, но более сложным.

ритма гра D(X; V )

я деревом и что это дерево кратчайшее.

11

остоит из k (k > 1) к

связности, каждая из которых

èìå

етвязностициклов,

потомуребраявля. Безтсяоградеревомчения. Пусть k1

(k1

можноk) êомпонентсч ать,

что это первые k

ê

ñâÿçíости. k общности> 1, ак как в прот вном

случае получаимеют1прîтивор ч

å:

k

1

=

1, то эта компонент

содер-

n 1 ребро

ершин, и зна÷èò íå

построомпонентèю еслименьше, чем n

житмо ет быть деревпом. Число m ребер гра а D раâíî

k

k

n 1 = m =

X

mi

=

X

i=1

i=1

(ni 1) n k1 < n 1:

П лученное противоречие показыва

÷òî D

я с язным гра

îм. D не имеет циклов и, с

едовательно, являетсвляетс

âîì.

2. Допустим, что D не яв яется кратчайшим

деревом. Пусть сна-

чала все ребра имеют

различную

длину. Пусть D1(X; V1) является

кратчайшим

.

по возраст нию длин и перенуме

Упорядочим ребра множества V1

уем их. Такждеревомпоступим

ребрами множества V . Пусть v1

первое

ðебро дерева D , не совпадающее

ñ

ðåáði

v

. Çà

что l(vi)1< l(v1). Добавим ребро vi

дереву D1. В этîì

i

i

ä

жит добавлен-

зов м его G1, появится единстве ный цикл. Он

метим,íое бро и, по крайней мере, одно

ребро v1

íîìåðîì j

ãðài òàêå,

ак предыдущие ребра

j

алисоответствующимдереву D, не содержащему

циклов.

áðî v1. ðà , íàç

åì

D2, ïðè

Удалим теперь из гра а G1

j

â,

. åãî. D

ÿâëÿ-

э ом останется связнымпринадлежне бу т содержать цикл

2

òся деревом. При это

l(D

)

< l(D

2

), что противîречит тому,

D

я ляется кратчайшим

1

ие док зывает, ÷òî

1

деревом. Это протиâîð

дерево D, полученное алгоритмом, является крат÷àéø ì.

Пусть теперь ребра из множества U могут иметь одинаковую дли-

ну. Обозначим Жi

= l(ui+1) l(ui) (i 2 1; m 1); Æ0 =

Æ >0

Жi. Положим

" = minf0:5; Æ

=2g. Изменим

множест а,

длины ребер это

óâå è÷èâ

0

äëè

min-ãî ребра âå

упорядоченной

личину "

m i

. При этом порядоктеперьбер

упорядочеíной по их длинам

не изменипоследовательностия, се ребра будут

иметь

азлич-

последовательностиную длину, гра G будет иметь единственное кратчайшее деðåâî D.

12

оставаться кратчайшим. Поэтому в пределе мы получим, что D явля

реберåòñÿПримеркратчайшимкратчайшеевыполнениядеревомостовноеалгоритма. Çàìäåð òèì,Краскаламожет÷òî âíåслучаеприбытьотыскеäèíаковостиственнымании кратчайäëèí. -

шего остовного дерева приведенворазделе 3.

2

Транспортныеток

сети и задача о наибольшем по-

2.1

Определение сети

Сетью называется связный гра с выделенными вершинами, ко

торые называются полюсами сети.

1 полюс. Мы

äåì àñ

Так, корневое дере о это сеть, содерж

сматривать

акие сети, которые являютсащая

букотоðûõ

каждый полюс это вершина оргра а, обладающаяоргра амидним из следу-

þùèõ

свойств:

1. Множество входящих дуг в вершину пусто; такой полюс назы-

вается входом.

2. Ìíîæ

тво выходящих дуг из вершины пусто; такой полюс на-

çûâà

ñÿ âûõî îì.

íà ðèñ. 5.

Пример сети приведен

x

x6

x1

x3

5

Здесь fx

x2

x4

èñ. 5

; x

x7

; x

g ì

æå òâî âõîäîâ, fx

g множество выходов.

1

2

6

7

2.2 Транспортная сеть и зада÷à о наибольшем потоке

Òð

с тью называется связный оргра G(X; U) с д

ним вхнспортнойдом и дним выходом, каждой дуге u которого отнесено неîò-

13

äóãè.

се и называют исто нико

è

áîç

Обычно вхо

÷àþò ÷å åç x ,

вых д называют стоком и обозначают через z. На

рис. 6 приведен0

примертранспортной ртной сети с пропу

способно-

стями, указанными около каждой дуги (не в круглыхскнымиобках).

5

(5)

x1

3

2(2)

x4

(3)

(1)

4

x2

1

4

(3)

4

5 (5) 3(3)

x0

(3)

z

3

(3)

2(0)

x5

(3)

x3

+

èñ. 6

x,

через

Обозначим через Ux

жество дуг, вх дÿùèõ â

U

множество дуг, выхмнодящих из x. Потоком '

ñåòè

x

G(X; U) пропускными способностями (u), вх домòðàвершинуxнспортнойвых дом z

0

называетñя целочисленная ункция, определенная на множестве дуг

U и удовлетворяющая свойствам:

1)2

U :

'(u) 0 неотрицательность потока;

8u 2 U :

'(u) (u) ограниченность пропускными способно-

стями;

; zg :

P

'(u) = P

+ '(u) неразрывность

3) 8x 2 X n fx

потока.

0

u2Ux

u2Ux

' можно интерпретировать как пот к вещества, идущий от

Потоквх да к выходу по трубам-дугам сети. Из свîйства 3 следует

X+ '(u) =

X

'(u) 'z

:

u2Uz

u2Ux

Ýò

величина '

0

z

называется величиной потока. На р с. 6 в круглых

скобках около дуг указан поток по этим дугам, велèчина которого

равна 11.

14

Дана транспортная сеть. Найти поток ', имеющий наибольшую

2величину.3

'z.жения задачи

наибольшем поток

делью мно-

Прилоча наибольшем потоке является

дискретной

гихЗадаскрет ых оптими

ч. Мы рассмотрим

две такие

задачè: òð

òíóþ

ционныхзадачуачу

о назначениях.

2.3.1

задача

(iпроизводят2 1; n) авна p .

изводитТранспоåльностьðòíàÿ

на предприятии P

Ïîñòàíîâê

задачи. Предприятия P ; P ; : : : ; P

.íåêî-

торый продукт,

рый требуется на рûíêàõ R ; R ; : : :; R

Потребность в продуктедукта рынке R

1

2

n

i

(j 2 1; m) i

àâíà r .

дороги, ведущей от предприÿòèя P к рынкуÏропускнаяR , авна

(i 2 1; n;

j 2 1; m). Можно ли

i

1

2

m

âñåõ

j

организовàть перев зки d

(i 2 1;удовлетворитьn; j 2производимый1; m) этопотрåáíîлучае?сти

способнрынков îñòê,ü

j

j

чтобы использовалñÿ âåñü

продукт? Как

ij

ij сеть, образовав для каждого прåäïриятия

P

Построим

x

(i 2 1; n)

и для каждого рынка R (j

2 1; m) верши-

сточник x

вершинуединим его с каждой

j

x

(i 2 1; n) дугой

i

i

. Добавим

íó y

. Соединимтранxñïîðтнуюy дугой пропу

способности

ij

j

0

i

j

. Добавим

ò

i

пропускной споñîбности p

z соединим с ним каждую

из вершин y

i

r

. Полученная

j

(j 2 1; m) дугой пропускнскнойверспособностишиной

j

транспортная сеть изображенà íà ðèñ. 7.

y

x1 1m

11

n1

1

p1

12

1

22

y2

x0

p2

x2

r2

z

pn

. 21m

.

rm

xn

nm2

ym

èñ. 7

15

количество продукта, которое перевозится от i-го ïðîèçâîäèòåëÿ ê j-

му рынку. Т да выполняются следующие условия:

ðàâíà ïðî-

1) сумма

îò

аждого ïðîизводителя ïðîäóêò

изведенномувывозимогопро

Pm

dij

= pi

(i 2 1; n);

2)

j=1

умма доставляемогодуктуаждому рынку продукта равна потребно-

ñòè ðûíê

Pn

dij = rj (j 2 1; m);

3)

ропускная

i=1

ü äî

ги, ведущей от P

ê R

, позволяет

способно

i

ïеревезти

êоличеñòво продукта d

ij

ij

.

j

транспортной

Построèì ïî ýòîìó решению поток ' для

'(x

; y

сети. Для этого положим '(x

; x

) = p

;

) = d

ij

;

'(y

; z) =

r

(i 2 1; n;

j 2 1; m).

0

i

i

i

j

j

j

вышеполученнойсловия (1)-(3)

беспечи

вают все свой тва потока: неотрицательность, огра иченн сть про-

пускными способностями

неразрывность.

Величина

поток

' =

Pm

rj =

Pn

pi

является наибольше возможной. Таким образом,z

j=1

i=1

ет наибольший поток в

-

решение транспортнойПеречисленныезада

портной сети.

теперь

х димыеиндуцирус овия решения

транспортной

çà

÷è. Åñëè çàäà

имеет решение, то

äëÿ

использования всего произ

âîäимого

дуктчанеобхнеобдимо, ч обы его количество

ñóì-

марнойассмотримпот ебности всех рынков,

ò. е. должно выполнятьсравнялосьравенство:

n

m

X

X

(1)

i=1 pi

= j=1 rj:

Для того чтобы дороги, ведущие к

íêàì

ажд го производителя,

п зволили вывести весь производимый

äóêò,

åîбх димо выполне-

ние условия на достаточную суммарнуюпрîïóскную способность этих

дорог:

m

X

ij pi

(i 2 1; n):

(2)

j=1

Для того чтобы дороги, ведущие к каждому рынку

производителей,

позволили привезти весь потребный продукт, необхотдимо выполнение

16

ðîã:

n

ij rj

(j 2 1; m):

(3)

Xi=1

Если эти условия выполнены, то оказываåòñÿ, ÷òî

çà

äà÷à

егда имеет решение. Это решение может бытьтранспортнаянайдено наи

большему потоку для транспортной сети. Пусть '

поток

тран портной

сети. Тогда его величина '

z

=

Pm

íàèár ольшийсилу нераз-

рывности поток

(à

j=1

j

=

Pn

=

акже выполнения слîâèé (1)-(3)) 'z

i=1 pi

n

Pm

' xi; yj). Положим

величину перевозки от

дителя

i=1

j=1

,

âíîé d

= '(x

; y

) (i 2 1; n; j 2 1; mпроизво). Вып лнение

Pк рынку R

ij

i

j

ã

i

j

условий (1)-(3)

ет, что такие перевозки возможны и дают

решение транспортной задачи.

òî ëèáî

Если какое-либорантируиз ловий (1)-(3) не

äóêò ìîæ

ти рынка, либо

весь производимый про-

áûòü использован èëè

. Íî

ýòèõ

яхнельзяакж

р шение задачи

наибольшем потокперевезендает возможн сть орг низова

ревозки

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

случдовле вориòü

потребности рынковпотребно(п их сумме). Таким

образом,

транспортная за-

дачадовлетможâîðèтьбыть сведена к задаче о наибольшем потоке.

2.3.2

Задача о назначениях

(i 2 1; n)

m работ

Постановк

задачи. Даны n работников X

i

Y

(j 2 1; m). Каждый работник X

ëèøü íåêî-

j

i

способен выполнÿòü

работы

Yi1; : : :; Yik

. Êàê

èÿ

îâ

i

аботы был назначен 1

ð

è

торыена аботы, чтобы для каждой

чтобы каждый

аб тник был занятпроизвести1 аб той?

íà îáà

Ясно, что необходимым у

положительного ответ

вопроса является

авенство m = n, но это

неравенство не г р

рует решение:

например,

3 работысловием гут вып лнять лишь аботник2 ð íòè-

(нехватка работ иков) или 3

м гут выполнять лишь 2

êàкие-то определенные работы (нехваткработникрабîт). Поэтому возможны
постановки задачи:
1. При n m можно ли обеспечить каждую работу работником
следующиекак это делать?	17

ешениеêàê ýòîзадачисделать?назначеíèÿõ будем выражать

âèäå áóëåâîé ìàò

ðèöû D = fd

ij

g (i 2 1; n; j 2 1; m), ãäå

X

i

(i 2 1; n) назна-

(j 2 1; m) в том иработниктольк в

ñëó÷àе, когда

чается на работу Y

j

d = 1. Â êаждой стðîêå ýòîé ìàòрицы есть не болеетомäíîé единицы,

èijâ êàæä

столбце

àêæå.

каждого работн ка

Построим

сеть, образовав для

y . Соединимвершинутранспортнуюx каждой вершиной y

(j 2 fi ; : : :; i

g) äó

X (i 2 1; n)

x äëÿ каждой работы Y

(j 2 m) âåðøèíó

бавим стоквершинойz соединимспособностиним каждую из вершин y

(j 2 1; m) дугой

j

i

i

i

j

j

1

k

гой пропускной

1. Добавим источ ик x

i

x

соединим его

с каждой

(i 2 1; n) дугой пропуск ой

способнîñòè

1. Äî

i

0

пропускной способности 1. Полученнаÿ òранспортнаjя сеть изображе-

íà íà ðèñ. 8.

x1

1

1

1

y1

1

x

1

y2

x0

xn2

.

1111

.

ym

1

z

1

èñ. 8

Пусть сначала n m и задача

íàçíàчениях имеет решением т-

ðèöó D, äëÿ

оторой в каждом ее

столбце имеется р вно 1 единица, а в

êàæä é åå

строке не больше 1 единицы. Образуем пîток ' следуþùèì

образом:

m

n

'(xi; yj) = dij

; '(x0; xi) =

X

X

(i 2 1; n; j 2 1; m(4):

j=1 dij; '(yj; z) =

i=1 dij

Нетрудно видеть, что для ' выполнены условия неотрèöàò

ьности,

транспортíîй сети. Так как все назначения для работ оïðåделены, то

ограничен

сти неразрывности, что делает ее потоком по данной

18

øóþ â

чину (максимальный). В

ê

äà n m

çà

÷à î

единицы,строкназначенияхимеетсимеетровноем потокрешением1 единица,' равенствамиматрицуслучае,каждомD(4)äëÿ. Èååкоторойвстолбцеэт м случаеâíåкаждойбольшедля åå'1

ыполненыобразусловия не

рицательности,

ограниченности

íåð çðûâ-

ности, что делает ее

потоком по данной

транспортной сети. Т

êàê

âñå

назначения для

ов определены, то n = Pn

Pm

dij =

Pn

'(x0; xi) = 'z,

. е. поток имеет наибольшую

i=1

j=1(ìàêñè-

i=1

мальный). Поэтому работникв их случаях решение задавеличинуназначениях

индуцируåò íаибольший поток в

строенной транспортной

ñåòè.

Пусть теперь ' наибольший поток

в транспортной сети с величи-

íîé '

z

= m. Образуем матрицу D = fd

ij

g, положив d

ij

= '(x

; y

) (i 2

i

j

1; n; j 2 1; m): Матрица D является

задачи о назна

öà,

ри n m, поскольку

каждом столбцерешениемее

еется лишь 1

ä

â

ее строк

более 1 единицы, что следуåò èç âåë

íû

потокаждойусл

неразрыв

ости потока. В случае, когда ' макси

мальный

ïîòîâèÿê

транспортной сети с

= '(x

; y

' = n, такжчåíèÿобрах

çóåì

матрицу D = fd

ij

g, положив d

ij

) (iz

2 1; n; j 2 1; m):

D является

i

j

ê

üêó

задачи

назначе ях при n m, по

каждой ее

решениемстрок имеется лишь 1

öà, à â

åå

Матрицаñ îëáöå

более 1 диницы, что следует из

äèíè÷ íû

аждомусло

âèÿ

потока. Таким об азом,величинойобоих слу аях

решение

задачи

наибольшем

потоке индуциðует решение задапоток÷è

назначе

íèÿõ.

мым мы показали, что задача

назначениях сводитс

ê çà-

Òåì

֌

ибольшем потоке. Позж

ìû

покажем, как

случае,

îãäà

азначениях не им ет решения,

при помощи

ìå-

заданеразрывности÷ на большем

потоке можно найти так

называе

ûå

ñòà

причины, по к

задача

азначениях не поискìеетузкиерешения.

2.4

Алгоритм Ф оторымда Фалкерсона

решения задачи о наи-

большем

å

ä è

Авторы теориипотîтоков американские математики Л. .

Д. . Фалкерсон дали следующий алгоритм решения задачиФорнаи-

19

I. Получение полного п тока,

. å.

ого потока, что для

zпути, найдется[x0; z дуга,, ведущегодля которойиз источникпотокакxпо0 транспортнойней равен ее пропускнсетилюбогов ст йк

способности.

меток.

II. Увеличение пот ка

Для получения полного потокалгоритмовыполняем следующий алгоритм:

1. Все дуги транспортной сети не помечены, роме дуг, к

èìå

нулевые пропу

способности (x; y) = 0, которыеоторые рас

сматриваются. Назначается нулевой

ïîò ê

' = 0 на каждой дуге

2.

(он допустим, акскныеак для него выполняются условия неотрица-

любой путь из входа

неразрывностиx вых д z. Если его нет, то пере-

тельности, ограниченности и

потока).

Ищемоди к п. 4 алгоритма.

0

( ) äóã ïóòè

3. Находим минимальн ю пропускную способность

min

и на дугах этого пóти увеличиваем поток на эту

величину:( )

8 x; y : (x; y) 2 ! '(x; y) = '(x; y) +

Удаляем

(отмечаем)

дуги пути, имеющие

акую пропускную спо

min

собность, уменьшаем (временно, в пределах части I алг ритма)

íèå

минимальной пропускной способности пути . Переходим к

4.

ропускную способность остальных дуг этого пути на этî значе-

ï. 2.

анавливаем исходные пропускные способности дуг и пере-

Восстх дим к п. 5 (часть II алгоритма).

Описание алгоритма пометок:

если они имели место.

5.

âñå

Стираем. 6

вершину x

ой {+0}вершин,вы лня

с повторени-

ï. 7, ïîê

0это возможно. Если

ïîмечена

вершина z,

Помечаемперех дим к предыдущиепометки. 8, а иначе перех дим к п. 9.

20