§ 61. Простой граф. Покрытие. Паросочетание

Простой граф. Простым графом называют такой граф , что

Например, на рис. 427 изображен такой граф (на рис. 428 дано его представление с помощью булевой матрицы).

Простой граф можно определить также как многозначное отображение конечного множества X в конечное множество (возможно

Простой граф будем обозначать .

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

Для того чтобы простой граф обладал покрытием, необходимо и достаточно выполнение условий:

Например, множество

— покрытие простого графа на рис. 429 (на рис. 430 и 431 оно выделено).

Рис. 427

Рис. 428.

Рис. 429.

Рис. 430.

Рис. 431.

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

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

(кликните для просмотра скана)

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

Соединим вход с каждой вершиной дугой с пропускной способностью, равной 1, а каждую вершину с выходом дугой с пропускной способностью, также равной 1. Дугам припишем нулевую пропускную способность.

По методу Форда — Фалкерсона ищем минимальный поток от Решение может быть не единственным. Проиллюстрируем сказанное на примере (рис. 432—435). Предварительно строим некоторый поток, для которого (см. рис. 432).

Рис. 436 Другой пример.

Рис. 437 Мини гальное покрытие.

Затем, рассматривая пути, идущие к уменьшаем поток до тех пор, пока это возможно. Приходим к минимальному потоку на рис. 434 Дуги с ненулевым потоком дают минимальное покрытие (рис. 435).

В нашем случае в общем же случае

Например, для графа на рис 436, минимальное покрытие которого изображено на рис. 437, имеем

Описание алгоритма, использующего булево матричное представление. Опишем алгоритм (рассматривая одновременно пример) позволяющий получить минимачьчое покрытие простого графа , представленного в виде булевой матрицы размера (в нашем примере в качестве берется матрица на рис. 438).

1) Сопоставим каждой строке матрицы число равное сумме его элементов, и столбцу У — число равное сумме его элементов (на рис. 438 указаны справа, а внизу)

Рис. 433

Рис. 439

Очевидно, что

2) Если

то множество соответствующих единицам, дает минимальное покрытие Рели

то заменяем последовательно в произвольном порядке нулем каждую из единиц (условливаясь при этом писагь вместо 0), для которой

Рис. 440

Рис. 141

Например, заключая в квадратик 1 на местах в матрице на рис. 438, приходим к матрице на

рис. 439. Легко видеть, что эту операцию дальше продолжить нельзя.

3) В каждой строке с ищем такую неотмеченную 1, что в содержащем ее столбце найдется такая отмеченная 1, что в строке, содержащей эту 1, есть либо неотмеченная 1 с либо отмеченная 1. Если то появляется возможность увеличить число отмеченных единиц.

Рис. 442.

Рис. 443.

Если столбец содержит отмеченную 1, то в ее строке ищем неотмеченную 1, в столбце которой есть отмеченная 1, и т. д.

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

Рис. 444

Рис. 445.

В нашем примере мы переходим от рис. 439 к рис. 440, а от него к рис. 441 (пунктир показывает порядок действия по На рис. 442 и 443 представлен другой пример с В этих примерах для минимального покрытия Легко видеть, что для графа на рис. 436 это неверно.

Паросочетание простого графа. Рассмотрим простой граф и два таких подмножества что Взаимно однозначное отображение подмножества А на В такое, что

называется паросочетанием, отображающим или паросочетанием, отображающим А на В 1).

Например, на рис. 445 (рис. 447) изображено паросочетание простого графа на рис. 444 (рис. 446)

Рис. 446

Рис. 447.

Условие существования паросочетания. Теорема Кёнига — Холла. Пусть , где простой граф и

Рис. 448.

Рис. 449.

Паросочетание, отображающее существует тогда и только тогда, когда

Доказательство. Построим транспортную сеть, в качестве вершин которой возьмем элементы множеств добавив к ним вход и выход Соединим с каждой верши ной дугой с пропускной способностью, равной 1, каждую вершину дугой с пропускной

(кликните для просмотра скана)

способностью, также равной I, а каждую вершину дугой если с пропускной способностью, равной рис. 449 изображена транспортная сеть, соответствующая графу на рис. 448.)

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

Рис. 455.

Рис. 456.

Следовательно, отобразить возможно тогда и только тогда, когда (согласно

или, иначе,

Максимальное паросочетание. Максимальное паросочетание — это паросочетание с максимально допустимым числом дуг. Это число обозначают через

Отыскание максимального паросочетания. Для отыскания максимального паросочетания достаточно построить, как это мы сделали при доказательстве теоремы Кёнига — Холла, транспортную сеть с входом и выходом и найти максимальный поток по этой сети.

Пример (рис. 448). Ищем сначала все пути от (рис. 449, 450), каждый из которых содержит только ненасыщенные дуги (рис. 450). Затем ищем цепи, идущие от которые позволяют увеличить общий поток; для этого помечаем вершины, начиная с как это делали в § 60. Рассматривая цепь видим, что. поток можно увеличить. Окончательно получаем поток, равный 5, представленный на рис. 451. Дуги через которые проходят потоки, каждый равный 1, дают искомое максимальное паросочетание (рис. 452, 453).

В этом случае наибольшее подмножество множества X, которое отображается в совпадает с X, а для графа на рис. 454 оно имеет мощность С другой стороны, граф может обладать несколькими паросочетаниями, как, например, граф на рис. 454.

Рис. 457.

Рис. 458.

Отыскание максимального паросочетания простого графа, заданного в виде булевой матрицы. 1) Реализуем некоторое паросочетание, выделяя полужирным шрифтом одну и только одну 1 в строке и столбце (на нашем примере — паросочетание на рис. 457).

Рис. 459.

2) Помечаем косым крестиком любую строку и любой столбец, которые содержат 1, выделенную полужирным шрифтом (рис. 458).

3) Рассмотрим непомеченные столбцы. В непомеченном столбце выбираем 1, которая одновременно принадлежала бы помеченной строке. Находим в этой строке 1, выделенную полужирным шрифтом, и в соответствующем ей столбце ищем 1, которая принадлежала бы непомеченной строке. Очевидно, что если мы находим такую единицу, то число выделенных полужирным шрифтом единиц можно увеличить. В противном случае ищем 1 в помеченной строке; по 1, выделенной полужирным шрифтом, в этой строке ищем... Если мы не можем больше найти столбца, исходя из которого, можно увеличить существующее число единиц, выделенных полужирным шрифтом, то приходим к максимальному паросочетанию.

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

Следовательно, возможно увеличить число единиц, выделенных полужирным шрифтом. Выделяем полужирным шрифтом рис. 459 1 в клетке а перед этим запишем светлым шрифтом 1 в клетке и выделяем полужирным шрифтом 1 в клетке (рис. 459). Нетрудно проверить, что процедура не может быть повторена. Единицы, выделенные полужирным шрифтом, дают максимальное паросочетание. Легко заметить, рассматривая рис. 458, что существует несколько возможных решений.

Дефицит простого графа. Дефицитом простого графа называют число

(А = 0 не исключается).

В качестве примера вычислим дефицит графа на рис. 447. Имеем

Легко проверить, что все разности в (61.18) либо отрицательны, либо нули. Следовательно, является максимумом и Нетрудно проверить, что дефицит простого графа на рис. 454 равен 1, так как существует единственная положительная разность:

Другая формулировка теоремы Кёнига — Холла. Необходимое и достаточное условие

можно записать в виде

или, учитывая, что

т. е.

Таким образом, паросочетание, отображающее существует тогда и только тогда, когда дефицит простого графа равен нулю.

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

Например, множество опора графа на рис. 460.

Минимальная опора. Индекс разбрасывания. Минимальная опора простого графа это такая опора для которой минимально.

Рис. 460

Рис. 461.

Граф может обладать несколькими минимальными опорами.

Число называют индексом разбрасывания простого графа

Очевидно, что

Например, множество минимальная опора графа на рис. 461.

Прежде чем изложить алгоритм определения минимальной опоры простого графа, рассмотрим несколько теорем. Теорема Подграф где

a S - опора, не содержит дуг, т. е. .

Это следует из определения опоры.

Теорема Пусть Любое подмножество

— опора простого графа .

Действительно, так как конец любой дуги лежит в А или в то конец этой дуги лежит также в А или в .

Теорема III. Для любой минимальной опоры выполняется равенство

В самом деле, по теореме опора. Так как то

Следовательно,

Теорема IV. В простом графе наименьшее количество элементов опоры равно

Действительно,

Полагая

имеем

Например, для графа на рис, 460 имеем

Теорема Дефицит и число внутренней устойчивости простого графа связаны соотношением

Доказательство. Пусть опора и ее дополнение. По теореме внутренне устойчиво. Обратно, если внутренне устойчивое множество, то С — опора. Следовательно,

По определению С имеем

Учитывая (61.30), получаем

Напрчмер, для графа на рис. 460 a , так как (мы вычислили его. раньше).

Теорема VI (теорема Кёнига). Пусть Тогда минимальное число вершин в опоре графа

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

Доказательство теоремы будет все время иллюстрироваться примером (рис. 462 и 463).

Доказательство. Исходя из заданного простого графа , где будем строить транспортную сеть, как мы уже делали при доказательстве существования паросочетания (теорема Кёнига-Холла).

Рис. 462.

Рис. 463.

Присоединим к вершину и свяжем ее с каждой из вершин дугой с пропускной способностью 1. Затем во всех случаях, когда соединим вершину с вершиной дугой с пропускной способностью наконец, присоединим к вершину и свяжем каждую из дугой с пропускной способностью 1. Таким образом, мы получили транспортную сеть (см. рис. 462, 463).

Если значение потока на дуге равно 1, то его значения на и также равны 1 (т. е. обе эти дуги насыщены). Иначе говоря, в каждую вершину из X может входить (а также из каждой вершины может исходить) лишь одна дуга, на которой данный поток имеет значение 1. Как мы заметили ранее, значение максимального потока в построенной сети равно максимально возможному числу дуг в паросочетании, отображающем

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

Тогда

Но по теореме Форда — Фалкерсона (60.24) минимальный разрез равен максимальному потоку.

Отсюда получается, что

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

и

В нашем примере пусть это будут, например, (рис. 464).

Обозначим

и

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

Рис. 464.

Пусть подмножество вершин сети:

(в нашем примере см, рис. 464).

Рассмотрим разрез, определенный множеством т. е. множество дуг, исходящих из вершин, не принадлежащих и заходящих в вершины из

а) Единственными дугами, исходящими из вершин, не принадлежащих и оканчивающимися в являются дуги с началами в вершинах из Пропускная способность каждой такой дуги равна 1 и их общая пропускная способность равна (рис. 465).

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

в) связана с каждой вершиной из дугой с пропускной способностью 1. Общая пропускная способность дуг, исходящих из У о и оканчивающихся в вершинах из поэтому равна

Таким образом, пропускная способность разреза равна . В нашем примере

2) Покажем теперь, что всякому разрезу с конечной пропускной способностью можно сопоставить некоторую опору. Пусть разрез определяется множеством вершин (которое содержит и не содержит Множество вершин из принадлежащих обозначим соответственно через а их дополнения — через

Рис. 465

Пусть пропускная способность этого разреза конечна (как, например, для разреза, указанного на рис. 466); это означает, что он не содержит никакой дуги, соединяющей вершину из с вершиной из (в противном случае разрез содержал бы дугу с пропускной способностью Тогда никакие две вершины из подмножества не соединены дугой и, следовательно, по крайней мере один конец каждой дуги принадлежит е. это множество — опора.

Рис. 466.

Далее, как было показано выше, число вершин этой опоры равно пропускной способности разреза. Пусть теперь разрез с минимальной пропускной способностью. Ему соответствует минимальная опора с числом вершин равным По теореме Форда — Фалкерсона последнее число совпадает с максимальным потоком в сети, а он, как было сказано, равен числу дуг в максимальном паросочетанип, т. е. окончательно

что и требовалось доказать.

Справедлива и обратная теорема.

Пусть Предположив далее, что опора множество дуг паросочетания. Тогда

Пусть условия теоремы выполняются. Для минимальной опоры имеем а для множества дуг максимального паросочетания имеем Тогда по теореме Кенига и куда что и требовалось доказать.

Теорема VII теорема Кёнига В простом графе имеем

Доказательство. По теореме IV

а по теореме VI

т. е. имеем (61.50).

Мы дадим в дальнейшем алгоритм нахождения минимальной опоры. Для этого нам нужны еще некоторые определения.

Полное паросочетание. Пусть простой граф и

V — дуги паросочетания Если каждая дуга из является смежной для некоторой дуги из V, то V — нолное паросочетание. Например, паросочетание, указанное на рис. 467, полное.

В изложенном выше методе нахождения максимального паросочетания с помощью транспортной сети, построенной для простого графа, получают «полный поток», когда больше нельзя найти такого пути из который увеличил бы поток.

Принимая во внимание, что в некоторых случаях все-таки можно увеличить поток, рассматривая цепи между видим, что полный поток не обязательно максимален и полное паросочетание не обязательно максимальное (см., например, рис. 450 и 451). Напротив, максимальное паросочетание является полным.

Сильная дуга. Слабая дуга. Пусть V — множество дуг паросочетания простого графа Назовем сильной всякую дугу, принадлежащую V, и слабой всякую дугу, принадлежащую

Ненасыщенная вершина. Вершина простого графа называется ненасыщенной, если она не инцидентна какой-либо сильной дуге (на рис. 467 вершины ненасыщенные). Все остальные вершины называются насыщенными.

Пусть Обозначим через множество сильных дуг, концы которых являются также концами дуг, исходящих из начала Например, на рис. 467 для дуги множество состоит из дуг

Рис. 467

Обозначим через множество сильных дуг, концы которых являются также концами исходящих из ненасыщенной вершины. Например, на рис. 467

так как множество ненасыщенных вершин в X есть

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

Будем называть графом дуг паросочетания граф вершины которого — дуги V, а многозначное отображение задается А. Дадим несколько примеров таких графов.

На рис. 468 представлено полное, но не максимальное паросочетание; напротив, на рис. 469 и 470 паросочетания максимальны. Покажем, как был построен граф дуг паросочетания для графа на рис. 468.

Имеем также

Провести аналогичные построения для графов на рис. 469 и 470 предоставляется читателю в виде упражнения.

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

1) V является максимальным паросочетанием в простом графе .

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

3) В графе нельзя найти пути из вершины, принадлежащей в вершину, принадлежащую .

4) В графе можно пометить каждую вершину знаком или знаком так, что каждая вершина будет помечена знаком каждая вершина V - знаком и этом никакая вершина, помеченная знаком не будет соединена дугой с вершиной, помеченной знаком при

Рис. 468.

Рис. 469.

Рис. 470.

Будем доказывать теорему по схеме

1) - 2). Действительно, предположим, что цепь, о которой говорится в условии 2), существует. Обозначим ее ребра через Тогда паросочетание

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

2) - 3). Действительно, каждой цепи в графе дуг паросочетания, идущей от вершины из до вершины из ,

соответствует чередующаяся цепь, связывающая ненасыщенные верши в графе .

3) - 4). Отметим знаком все вершины в а знаком все рершины в Имеем так как ввиду 3) не существует пути из в , то т. е. из 3) следует 4).

4) - 1). В графе пометим сильные дуги знаками в соответствии с 4). Обозначим через множество начальных вершин сильных дуг, помеченных знаком и через множество конечных вершин сильных дуг, помеченных знаком Пусть имеем дугу и рассмотрим четыре показанных на рис. 471.

Рис. 471

а) не могут быть ненасыщенными, так как по предположению V — полное паросочетание.

б) не может быть ненасыщенной вершиной, так как тогда должна была бы (по опредетению быгь помеченной знаком «+».

в) не может быть ненасыщенной вершиной, так как тогда должна была бы (по определению быть помеченной знаком «-».

г) не могут обе быть насыщенными, так как тогда, вопреки 4), в графе существовала бы дуга от до

Таким образом, дуги не существует, и множество опора.

Имеем, кроме того,

По теореме, обратной теореме Кёнига, получаем, что V — максимальное паросочетание.

Нахождение минимальной опоры. Венгерский алгоритм. Этот процесс распадается на две части.

1) Нахождение максимального паросочетания. Для этого подходит метод, описанный ранее, но мы дадим другой способ.

2) Нахождение минимальной опоры.

Первая часть: нахождение максимального паросочетания. Для получения максиматьного паросочетания берут какое-нибудь паросочетание, образуют граф дуг паросочетания и опредетяют подмножества и . Если существует путь от до то взятое паросочетание не является максимальным. В этом случае можно найти цепь, состоящую поочередно из слабых и сильных ребер, и с ее помощью увеличигь число сильных дуг. Так продолжают до тех пор, пока не приходят к графу в котором нет путей от

Вторая часть: нахождение минимальной опоры. Чтобы, исходя из максимального паросочетания V, построить минимальную опору, находят подмножества Конечные вершины дуг, принадлежащих обозначаются через а начальные вершины дуг, принадлежащих через Множество

будет тогда минимальной опорой.

Пример 1 (рис. 472). Возьмем сначала паросочетание V, показанное на рис. 473. Найдем для пего граф дуг паросочетания и множестра и (рис. 474). Видим, что существуют пути из до V, а именно — петли в вершинах и Цепь позволяет_найти паросочетание с большим чистом дуг (рис. 475). Для него вновь строим граф и находим и (рис. 476). Здесь пути из в не существует, т. е. паросочетание на рис. 475 максимальное. Для определения минимальной опоры находим (подмножество, образованное элементами транзитивных замыканий элементов Имеем

и

Концы дуг множества дают

а начала дуг дают :

(рис. 477 и 478).

Пример 2 (рис. 479). На рис. 480 показано некоторое паросочетание. Оно не максимальное, что показывает граф на рис. 481. Увеличиваем на 1 число дуг в паросочетании, используя цепь

(кликните для просмотра скана)

(кликните для просмотра скана)

(рис 482) Как показывает граф дуг паросочетания на рис 483, можно увеличить число дуг в паросочетании еще на 1, если использовать цепь

Приходим к иаросочетанию на рис 484 Это паросочетание максимально, так как (рис 485) Далее — , поэтому и миниматьная опора есть

Нахождение минимальной опоры с немощью булевой матрицы Если максимальное паросочетание уже поточено, то действуем следующим образом

а) помечаем знаком 0 все строки, в коюрых выделенной полужирным шрпфом,

б) помечаем знаком 0 все столбцы, содержащие 1, не выделенные полужирным шрифтом в помеченных строках,

Рис. 486

Рис. 487

в) помечаем все строки, содержащие 1, выделенные полужирным шрифтом в помеченных столбцах,

г) повторяем б) и в) до тех пор, пока удается помечать новые столбцы или строки,

д) помеченные столбцы и непомеченные строки дают минимальную опору

Пример (рис 486, где воспроизведен результат, полученный на рис 459) Согласно описанной процедуре помечаем по порядку строку затем столбцы затем строки затем наконец, Помеченные столбцы и непомеченные строки дают минимальную опору (рис 487) Имеются и другие решения, так как максимальное паросочетание не единственно

Рис 487 иллюстрирует общий факт минимальная опора есть минимальное множество линий, содержащих все 1 Под линией понимаем здесь столбец или строку.

УПРАЖНЕНИЯ

(см. скан)