в которой различные блоки соприкасаются в своих соединяющих вершинах. Соединяющие вершины блоков являются разделяющими вершинами графа. Разложение (6.13.2) листов на блоки Г(15)=рл4* Дозволяет теперь

уточнить структуру графа (рис. 6.37): каждый лист ГL. можно представить в виде кактусооб-разной схемы (рис. 6.41) составляющих его блоков Г{Щ1к).

6.13.3. Поиск блоков в глубину

Разложение графа на блоки и выделение их имеет важное практическое значение. Иногда недостаточно знать, что граф связен; может интересовать насколько сильно связен связный граф.

Рис. 6.42. Исходный граф (а); блоки графа (Ь); листы (с), (е) и один мост (d); точки сочленения: b, f, j, i

Например, удаляя вершину сочленения двух блоков (рис. 6.40) и инцидентных ей ребер, нарушим связность графа. Связность графа не нарушится, если удалить внутреннюю вершину блока и инцидентные ей ребра. Про такие компоненты графа говорят, что они двусвязные. Отыскание точек сочленения и блоков графа важно при изучении надежности коммуникационных и транспорт-

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

На рис. 6.42 в качестве примера изображен связный граф и его блоки (двусвязные компоненты). Здесь же показано разложение графа на листы.

Для нахождения блоков и точек сочленения применим известный метод поиска в глубину на неориентированном графе А= (X, U, Ф). Основу алгоритма выделения блоков и точек их сочленения легче понять, рассмотрев пример на рис. 6.43, где схематически изображен связный граф, состоящшг из шести блоков

i = 1,6, и четырех точек сочленения Xj, j = 1,4.

Рис. 6.43. Схематическое изображение графа с шестью блоками и четырьмя точками сочленения

Если начать поиск в глубину, скажем, из вершины s е А, то можем перейти из в :, проходя через вершину х(. Из свойства поиска в глубину, все ребра в Г, должны быть пройдены до того, как вернемся в Поэтому состоит в точности из ребер, которые проходятся между входом и выходом из вершины Для других блоков дело обстоит несколько иначе. Так, например, если уйти из в А, а оттуда - в Гь через х4, то окажемся в пройдя ребра из Г2, Г5 и Г6. Если хранить ребра в стеке, то во время прохождения назад из в через вершину все ребра будут на верху стека. После их удаления на верху стека останутся ребра и снова продолжим проход блока Таким образом, если можно распознавать точки сочленения во время то применяя поиск в глубину и храня ребра в стеке в той очередности, в которой они проходятся, можно также определить и блоки (двусвязные компоненты). Ребра, находящиеся на верху стека в момент обратного прохода через точку сочленения, составляют блок.

Реализация рассмотренного подхода выделения блоков графа представлена в алгоритме 6.17. В векторе MarkfxJ меток вершин х е Хграфа фиксируются порядковые номера обхода соответст-

вующих вершин. В этом случае метка вершины сочленения при входе в блок получит наименьший номер из всех остальных вершин блока. Таким образом, для определения точки сочленения выхода из блока достаточно найти вершину этого блока с минимальной меткой. Свойство циклической замкнутости блока позволяет это сделать лишь на основе вектора меток не привлекая дополнительной информации. На рис. 6.44 схематично представлен блок, где вершина w - точка входа в блок и точка сочленения. Вершина х - следующая обследованная вершина блока после w. Свойство циклической замкнутости блока позволяет утверждать, что существует по крайней мере еще одна вершина у, смежная м>. Рекурсивный характер алгоритма поиска в глубину на графе позволяет утверждать, что в этом случае ребро блока (у, w) будет пройдено как обратное, и, значит, метка МагкЩточмж сочленения блока будет доступна до выхода из блока по ребру входа (z, x). Поэтому, сохраняя минимальное значение меток обследованных вершин (включая и по обратным ребрам поиска в глуби-будем проверять при рекурсивном выходе из поиска в глубину совпадает ли это минимальное значение с меткой вершины выхода. Если ответ положительньгй, то найдена точка сочленения. В алгоритме значения минимальных меток фиксируются в векторе Virtual для каждой вершины х е X, как наименьшее значение из Магк[у], где у - вершины графа, которые достижимы из х при проходе графа в глубину.

Алгоритм 6.17. Выделение блоков графа

count = 0; Stack = 0;

for v eXdo MarkfvJ = 0; {Начальныеметки вершин) for v e XdoifMark[vf= 0 then Block(v, 0); Procedure Block(x, w) count=count+ 1;

Mark[x] = count; {Вершина исследована) Virtual[) = count; {Начальна) минимальная метка) for v e Adj[x]Xdo

ifMark\yY 0 then begin

Stack = Stacks (x, v);

Рис. 6.44

Block(v, х);

Virtual[x] = min( Virtual[x], Virtual[ v]); ij Virtually] > Virtual then begin

В этой точке х-либо корень дерева, либо точка сочленения. Образовать новый блок. состоящий из всех ребер стека, включая (х, v). end, end;

else ifMark[v] < Mark[x] andv*w then begin { (x, v) - обратноеребро) Stack = Stack и (x, v); Virtual[x] = min( Virtual[x], Virtual v]);

end;

end.

6.14. Двудольные графы

Определение. Граф (X, U,0) называется двудольным, если множество его вершин можно разбить на два независимых подмножества V-t таких, что Х= Vy u V2 и Vx гл V2 = 0. Такой граф будем обозначать как Г= (V{ u V2, U, Ф). На рис. 6.45 изображен типичный двудольный

граф. Двудольные графы играют заметную роль в Рис S.45 различных приложениях.

6.14.1. Условия существования двудольных

Теорема 6.14.1. Граф Г = (X, U, Ф) является двудольным тогда и только тогда, когда любой его простой цикл четной длины.

Доказательство. (->) Ясно, что данное условие для двудольного графа всегда выполняется. (<--) Разобьем граф компоненты связности Гу,Г2,...,Гт. Пусть Tk = (Хк, Uk, Ф) одна из них и а € Хк - произвольная вершина. Разобьем множество вершин на непересекающиеся и Vk2. где Кд, - вершины, расстояние до которых от а нечетно; I7. - вершины, расстояние до которых от а четно, а е Множества I и Vk- являются независимыми. Действительно, если предположить, что вершины b и с смежные и

се \к или се Vk2. то существовал бы у----

цикл нечетной длины, соответственно а

нечетная длина Ь длина единица с нечетная --

длина а или а четная длина Ъ длина единица ъ === с четная длина а , что противоречит условию. Рассмотренное разбиение вершин выполним для каждой компоненты Ги Г2,...,Гт v ---: v

связности. На рис. 6.46 показано объединение независимых компонент Vklm Ук2в не- Рис. 6.46 зависимые компоненты Vx =\\Vki и

6.14.2. Паросочетания

. Определение. Паросочетанием в двудольном графе /4KjU Vj. U, Ф) называется независимое подмножество ребер л с О, ребра л не имеют общих вершин. , . . , Для графа, изображенного на рис. 6.47, в качест- s21- --2 ве паросочетания можно взять множество ребер *з я = фь 1), (s2, 2)}, тс = {(s3, 1), (s2, 2)} и т.п. Рис. 6.47

Определение максимального паросочетания. Па-

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

6.14.3. Алгоритм определения максимального паросочетания

Пусть Г= (Vx и V2, U, Ф) - двудольный граф и тг - произвольное паросочетание. Множество вершин с Vx и А2 с (рис. 6.48). Чередующейся цепью относительно паросочетания я называется цепь С, в которой ребра пооче- к редно принадлежат и и которая начинается ребром, не принадлежащим п. Заметим, что ребра в цепи не повторяются. Пусть fljеАх - произвольная вершина и щ = (аь v2n) - ребро, инцидентное вершинам из Ах и V2k. Построим чередующуюся цепь С= (и1п1и2п2...

и допустим, что по такой цепи можно достичь вершины

Такую цепь С можно использовать для получения нового паросочетания я, которое содержит на одно ребро больше, чем исходное паросочетание я. Действительно, в я можно включить все ребра я, удалив щ,п2,..., я , идобавив и и2,..., ип ь ип. Полученное таким образом п содержит несмежные ребра, а значит, я - паросочетание. Говорят, что я получено из я чередующимся расширением.

Пример. Дан двудольный граф Г= (Щи V2, U, Ф), где ¥\= {sy, s2,..., s6}n V2= {1, 2,..., 6}. Соединение вершин Ууж К2задано соотношениями: sy -> {4}, s2 -> {1, 6}, j3 -> {4, 5, 6},j4 - {1, 3}, s5 - {2}, s6 -> {1, 3}. Найти максимальное паросочетание.

Выберем начальное паросочетание я таким образом, что вершину sy е Vy соединяем с вершиной/ е V2 первой незанятой ранее из списка соединений для Sy. На рис. 6.49 изображено исходное паросочетание я = {(sy,4), (s2,1), (s3, 5), (s4, 3), (s5, 2)}, я = 5. Вершины Sj и 6 не вошли в паросочетание. Попытаемся увеличить я, используя алгоритм чередующихся цепей. Обозначим-> переход по

ребрам графа из Vx в 2и--> переход по ребрам паросочетания я из V2 в Vy. Так, s6->{1,3}

означает, что из можно перейти в вершины 1 и 3, и {1,3} >{5-2,4 }означает, что из вершин 1 и 3 можно достичь по ребрам паросочетания вершин s2 и л4. По алгоритму исходной вершиной цепи является s6. Тогда множество всех чередующихся цепей, начало которых в s6, можно представить: s6-->{1,3}--->{,y2 s4} -т->{1,3,6}. Переходы следует закончить, если вершина 6 достигнута или подмножество вершин V2, доступных из s6, повторилось в чередующейся цепи. В последнем случае вершина 6 не доступна из6и, значит, исходное паросочетание л максимальное. В нашем случае вершина 6 оказалась доступной. Для выделения исходной чередующейся цепи из всего множества расширяющихся цепей выполним обратный ход: 6->s2->1->s6.Теперь новое паросочетание строим из старого, исключая из него ребро (s2, 1) и включая ребра (6,s2), (!,%) Процесс включения также показан на рис. 6.49. Максимальное паросочетание содержит ребра (slt 4), (s3, 5), (j4, 3), 05, 2), (s2, 6), (s6, 1) и я = 6.

Теорема 6.14.2 о максимальном паросочетании.

ПустьГ=(и V2, ГУ, Ф) - двудольный граф. Тогда количество ребер в максимальном паросочетании равно

П=Щ-тоы{\А\-\АЛ\), где \Л = е \\ Зх с: \\ л (х, у) е с

Доказательство. Пусть л - максимальное паросочетание в исходном двудольном графе (рис. 6.50). Паросочетание я позволяет рассматривать его как отображение я: - вершин множества в вершины множества по ребрам я.

Аналогично, под Д будем понимать ото-

бражение Д:

>V2вершин МНОЖе-

Рис. 6.50. Максимальное паросочетание л

ства V[ в вершины множества V2по ребрам С/графа. Вершины множеств со и Z

(рис. 6.50) несмежные, так как паросочетание я является максимальным.

Рассмотрим процесс насыщения множества Под со ->Лю, будем понимать последовательное выполнение двух отображений л(Д(ш)) с Vx множества со. Далее применим отображения Д и я к полученному множеству: А<лк ->Л(д(о,)г с и т. д. Ясно, что каждая пара отображений приводит к расширению исходного множества дсо^е (дсо^ )п Учитывая конечные размеры исходного графа, наступит момент, когда отображаемое множество перестанет расширяться. Таким образом, процесс насыщения отображаемого множества можно представить следующим образом:

со -> дй>п д(до)п) -► ЛСдсОЛ ~> - -* д(-д(дш >*-)п = Л.

Для множества А выполняется условие = АА\, в противном случае множество А можно было бы еще расширить. Следствием расширения множества в процессе его отображения является включение Дсо с ДА

Обозначим множество со иА=В. Покажем, что найденное множество В удовлетворяет условию (*) теоремы, т.е. к(Г) = Д, - - (\В - \АВ ). Имеем \АВ = Д(со иА)\ = (Aft и АА)\ = \АА] , следовательно, j v\ - (\В\ -\АВ \) = \ Vil - (о> \ + [А\ - \АА\) = \V{\ - = п([ >.

Покажем теперь, что VАс Р условие (*) теоремы записывается в следующем виде: п(Г)< \Vy\- (И - ЛЛ). Тогда ранее найденное множество В, для которого данное неравенство обращается в равенство, будет доказательством условия (*) теоремы. Пусть Ау = А(оз пЛ),тогдаА = (ю глА) иАу. Отметим, что ЧЛХ сЩ** глАу) выполняется неравенство \АХ\< Л/1 так как вершины множества РД(ю n Vx) составляют паросочетание. Тогда верно, что И|= + \АХ\< ю + \АХ\< ю + \ААу\< ш + \АА] или \А\- АА\< со.

Теперь количество ребер в максимальном паросочетании можно оценить: я(Г)=К[- со< \Vy\- (\А\ - Л/1). Теорема доказана.

6.14.4. Системы различных представителей

Рассмотрим пять множеств: Sy = {2, 3}, S2 = {1,2, 4}, S3 = {1,2, 5}, J4 = {3, 4, 5}, S5 = {3, 4, 5}. Требуется выбрать такие различные числа^, х2,х3, х4,х5, чтох,-е Sj,i = 1,2,...,5. Дляданногопримерах! = 2, х2 = 1, х3 = 5, х4 = 3, х5 =4. Однако если взять множества ={1,2}, Т2 = {1,2}, Г3={1,2}, 74={3,4,5}, Т5 = {3, 4,5}, то такой выбор оказывается невозможным.

Рассмотрим данную задачу в общем случае. Пусть S = {1, 2,..., и}. M(S) - система подмножеств Sy, S2,..., Sn множества S. Будем говорить, что M(S)имеет систему различных представителей, если для всех / 1,2,..., п существуют различные х,- е Щ.

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

Определим двудольный граф

Г= (Vy<uV2, U, Ф), соответствующий системе подмножеств. Пусть M(S) = {Su S2,..., Sn) - система подмножеств Sb S2,..., Sn множества S. Положим Sb S2,..., вершинами Vy графа, которые соединены ребрами со своими элементами - смежными им вершинами из К2(рис. 6.51). Рис- 6-51

Лемма 6.14.1. Двудольный граф Г= (Vy иК2Д Ф), отвечающий системе подмножеств = {Sy, S2,..., Sn}, имеет максимальное паросочетание из п ребер тогда и только тогда, когда M(S) имеет систему различных представителей. (Доказательство вытекает из определения построения двудольного графа, отвечающего системе различных представителей).

Теорема 6.14.3 Ф. Холла о существовании системы различных представителей. Система M(S)= {SUS2,..., S } имеет систему различных представителей тогда и только тогда, когда для любой подсистемы {St ,Sj ,...,S: } с М(S)выполняетсянеравен-

к 1

ство [)Sj >к, т.е. количество элементов в объединении лю-

И I

к подмножеств должно быть не менее к.

Необходимое условие теоремы следует из определения системы различных представителей. Каждое подмножество Sj е M(S содержит элемент дг е 5 , , отличный от

К

элементов других подмножеств, а значит I IS, > к.

Ф) соответству-

ющий системе подмножеств = {SS2,..., Sn). Покажем, что в данном графе существует максимальное паросочетание, количество ребер в котором равно п. Тогда из леммы 6.14.1 будет следовать достаточное условие теоремы. Из теоремы имеем, что число ребер в максимальном паросочетании равно = ii - -тах(Л|-А4), где/VI = {уе У: \3jcs 1, л (х, у) е U с В рамках принятой интерпретации A ={S Si2,...,S }, \A\ = к и к

АА = (J Sr . По условию теоремы \АА\ > к. Таким образом, У Ac Vx 7=1

\а\ - \аА\< О, а значит, тг(/) =Щ - тах(И -ДЛ) > VI Однако

;п/ ) < следовательно, гс( Г = Ii = л (достаточное условие доказано).

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

Существует множество задач, постановки которых укладываются в рамки задачи о назначениях. Рассмотрим две такие постановки.

Задача. Предположим, что вычислительная сеть объединяет п специализированных ЭВМ. На вход сети поступают задачи. Известно, что наибольшая производительность конкретной ЭВМ сети достигается на определенном классе задач. Это выражается коэффициентом использования ЭВМ при класса за-

дач. Найти оптимальное распределение задач по сети таким образом, чтобы эффективность ее использования была наибольшей.

Задача. Группа лиц может выполнить п видов работ. Эффективность использования лица на у -й работе определяется мерой ценности ,у. Найти оптимальную расстановку людей по видам работ.

Теорема 6.14.4 - алгоритм поискаоптималъной перестановки я.

Пусть А = \аЛ, i,j= \,n - матрица целых чисел. Тогда максимум

тах|х (6.14.1)

по всем перестановкам я равен минимуму

1=1 у=1 )

(6.14.2)

по всем числам и таким, что

щ + VjbOy, V/,y=l7n. (6.14.3)

Минимум суммы (6.14.2)достигается на перестановке я такой, что

Доказательство. Пусть я - произвольная перестановка. При изменении от 1 до л величины принимают все значения множества {1, 2,..., п). По условию +vt> Оц, V/,y= 1, п, а значит, и для у = ш,верно Ы; + у = %: .Установим связь сумм (6.14.1) и (6.14.2).

п Л Я А Я я

Shi +Svy =]Ел +Svt, =Zw( +vk, )Хам,

#=I y=l / 1 ;=1 Hi /=1

Таким образом, сумма (6.14.1)для любой перестановки я не больше суммы (6.14.2). Отсюда следует, что теорема будет верна, если мы найдем такие щ и Vj и перестановку я, что (6.14.1) и (6.14.2) совпадают.

Жаг 0. Поиск начальных и v;, удовлетворяющих ограничениям щ г + Vj > ay, V/,y = 1, п. Положим Vj = О и и, = max а у - максима-

льный элемент в /-й строке; условие (6.14.3) ut +V[ =maxo(;/ довыполняется. Для матрицы ценностей на рис. 6.52 справа и снизу указаны начальные значения, соответственно и