Вопросы для самопроверки

1. Какие графы называются двудольными ?

2. Что собой представляет паросочетание в неориентированном графе ?

3. Что понимается под термином чередующаяся цепь ?

4. Когда паросочетание в двудольном графе наибольшее ?

Задание на лабораторную работу

1. По заданному алгоритму 2.1 написать и отладить программу нахождения наибольшего паросочетания методом Хопкрофта-Карпа.

2. Продемонстрировать работающую программу преподавателю и получить отметку о ее выполнении.

3. Провести анализ полученного алгоритма на сложность.

4. Оформить отчет о проделанной работе. Он должен включать в себя:

– цель работы;

– ответы на вопросы для самопроверки;

– схему обрабатывающего алгоритма и описание его работы;

– распечатки экранных форм, полученных в результате работы программы.

Лабораторная работа № 3

Жадные алгоритмы для матричного матроида

и матроида трансверсалей

Цель работы – написать и отладить программу генерирования всех k-элементных подмно­жеств множества {1, ..., n} в лексикографи­ческом порядке.

Теоретическая часть

Жадные алгоритмы решения оптимизационных задач. Рассмотрим следующую матрицу с действительными неотри­цательными коэффициентами:

Решим следующую оптимизационную задачу.

Задача 1. Найти такое подмножество элементов матрицы, что

(а) в каждом столбце находится не более одного выбран­ного элемента и

(б) сумма выбранных элементов является наибольшей из возможных.

Попробуем решить эту задачу следующим образом: будем выбирать элементы последовательно, причем каждый раз бу­дем выбирать наибольший из элементов, которые мы можем добавить, не нарушая условия (а). Будем действовать так вплоть до момента, пока добавление произвольного элемента не нарушит условия (а). Алгоритм такого типа мы будем на­зывать жадным.

Для задачи 1 и матрицы жадный алгоритм находит под­множество

которое действительно дает наибольшую возможную сумму.

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

Рассмотрим несколько иную задачу.

Задача 2. Найти такое подмножество элементов матрицы, что

(а) в каждом столбце и в каждой строке находится не бо­лее одного выбранного элемента и

(б) сумма выбранных элементов является наибольшей из возможных.

На этот раз применение жадного алгоритма к задаче 2 и матрице дает подмножество

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

имеет сумму 13. Следовательно, на втором шаге не следо­вало бы быть жадным, мы выигрываем в конечном результате, выбирая несколько меньший элемент (3 вместо 4).

Возникает вопрос: когда выгодно быть жадным? Сформули­руем это более строго.

Мы будем рассматривать оптимизационные задачи следую­щего типа.

Задача 3. Даны конечное множество , семейство его под­множеств и функция , где обозначает множество вещественных неотрицательных чисел. Найти под­множество с наибольшей суммой .

Как задача 1, так и задача 2 являются частными случаями задачи 3. В обоих случаях есть множество позиций матрицы, a ставит в соответствие позиции матрицы число . Для задачи 1

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

а в случае задачи 2

каждый столбец и каждая строка содержит не более одной позиции

из множества .

Теперь мы можем сформулировать наш вопрос следующим образом: при каких условиях относительно семейства жад­ный алгоритм правильно решает задачу 3 для произвольной функции ?

Оказывается, что на этот вопрос можно найти простой от­вет. А именно, достаточно, чтобы пара образовывала так называемый матроид.

Матроиды и их основные свойства. Матроиды были введены Уитни в работе [73] в совершенно ином контексте, нежели жадные алгоритмы, а именно в иссле­дованиях абстрактной теории линейной зависимости. Суще­ствует много эквивалентных определений матроида. Для нас наиболее удобным будет следующее определение:

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

и если

Для произвольных , таких что

существует элемент такой что

(Условие исключает вырожденный случай

Множества семейства мы будем называть независимыми множествами, а остальные подмножества из  зави­симыми множествами матроида . В этом проявляется уже упомянутая связь матроидов с теорией линейной зависимости: аксиомы матроидов выбраны таким образом, чтобы они отра­жали наиболее характерные свойства независимых множеств линейного пространства, точнее говоря, независимых подмно­жеств, содержащихся в некотором конечном подмножестве этого пространства (вспомним, что подмножество линейного пространства называется независимым, если не су­ществует набора скаляров , не всех равных нулю, такого что . В самом деле, очевидно, что произвольное подмножество независимого множества линей­ного пространства независимо. Если для линейно независимых подмножеств линейного пространства, то порождает пространство размерности , которое может со­держать не более чем элементов множества . Следовательно, существует элемент не принадлежащий этому подпространству. Множество порождает подпространство размерности и, следовательно, является линейно независимым.

Будем говорить, что два матроида и изоморфны, если существует взаимно однозначное отображение множества на множество , такое что тогда и только тогда, когда . Часто мы не будем делать различия между изоморфными матроидами.

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

Теорема 3.1. Пусть  конечное множество,  семейство его подмножеств, удовлетворяющих условию . При этих предположениях является матроидом тогда и только тогда, когда удовлетворяется условие

Для произвольного подмножества каждые два максимальных

подмножества множества имеют одинаковую мощность.

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

Напротив, предположим, что выполняются условия и , Выберем такие произвольные подмножества , что и обозначим . Допустим, что не суще­ствует такого элемента , что . Это означа­ло бы, что является максимальным независимым подмножеством множества . Расширяя до максимального независи­мого подмножества , мы имели бы вопреки условию . Следовательно, условия и влекут за собой условие . ■

Из теоремы 3.1 следует, что условия и образуют эквивалентную систему аксиом для матроидов.

Мощность максимального подмножества множества называется рангом этого множества и обозначается через :

Очевидно, что подмножество является независимым тогда и только тогда, когда . Каждое максимальное независимое множество матроида будем называть (по аналогии с линейными пространствами) базой этого мат­роида, а ранг , являющийся аналогом размерности линейного пространства, рангом матроида. Отметим важное след­ствие теоремы 4.1.

Следствие 3.1. Каждые две базы матроида имеют одинако­вое число элементов. ■

Отметим также, что каждое независимое множество можно расширить до базы ; достаточно поочередно до­бавлять в новые элементы, присоединение которых не нару­шает независимости, вплоть до момента, когда таких элемен­тов больше не существует. Полученное множество будет максимальным независимым множеством, а, следовательно, базой. Аналогично, произвольное независимое множество мож­но расширить до максимального независимого подмножества множества .

Отметим некоторые свойства рангов.

Теорема 3.2. Для произвольных имеем

,

если , то ,

,

,

если , то .

Доказательство. Свойства R1 и R2 очевидны. Докажем R3. Пусть  максимальное независимое множество в . Расширим его до максимального независимого множества , а затем до максимального незави­симого множества . Имеем , а, следовательно,

Условие очевидно. вытекает из :

■

Продолжая аналогию с линейными пространствами, будем говорить, что элемент зависим от множества , если , и будем обозначать через множество всех элементов, зависимых от :

Множество называется подпространством матроида, если , т. е. если для произволь­ного .

Теорема 3.3. Для произвольных имеем

,

,

,

. ■

Доказательство. Условие очевидно: если , то , т. е. . Для доказательства восполь­зуемся . Предположим, что и . Тогда

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

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

(4.1)

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

Отсюда индукцией по i получаем требуемое равенство (3.1). Доказательство включения теперь просто. Предполагая , т.е. , имеем т.е. .

Наконец, свойство вытекает из определения зависимости элемента от множества: предположив и , имеем

а отсюда , т. е. . ■

Отметим, что из свойства следует, что является подпространством матроида. Будем называть его подпростран­ством, натянутым на множество .

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

Теорема 3.4. Для произвольных циклов выполняются условия:

Если , то ,

Если и , то существует цикл .

Доказательство. Условие выражает просто свойство ми­нимальности, содержащееся в определении цикла. Докажем теперь . Множества и независимые, а следо­вательно, и . В силу условия

(4.2)

Множество независимое, так как оно является собствен­ным подмножеством обоих циклов. Отсюда и неравенство (4.2) можно переписать как

(4.3)

Предположим теперь, что не существует цикла , о котором идет речь в условии . Тогда множество незави­симое, и в результате вопреки неравенству (4.3).

Отметим важное следствие из свойства .

Следствие 3.2. Если  независимое множество, то для про­извольного множество содержит не более одного цикла.

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

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

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

Другой пример получаем, рассматривая произвольное раз­биение множества и определяя

для .

Отметим, что если и , то должен су­ществовать такой индекс , что . Элемент можно «перенести» в и получить множе­ство . Это доказывает справедливость условия . Матроид , определенный таким образом, будем на­зывать матроидом разбиений.

Теорема Радо-Эдмондса. Вернемся к жадным алгоритмам. Сформулируем сначала общую схему алгорит­мов этого типа. Мы будем рассматривать конечное множество , функцию и семейство . Значение называется весом элемента .

Вес подмножества определяется следующим образом:

Алгоритм 3.1. (Жадный алгоритм).

1 begin

2 упорядочить множество по убыванию весов так, чтобы , где ;

3 ;

4 for i: = 1 to n do

5 if then

6 end

Теорема 3.5 (Радо, Эдмондс). Если есть матроид, то множество , найденное жадным алгоритмом, является независимым множеством с наибольшим весом. Напротив, если не является матроидом, то существует такая функция , что не будет незави­симым множеством с наибольшим весом.

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

Стоит отметить, что множество оптимальное в очень сильном смыс­ле. У него не только максимальна сумма элементов, но также в любом независимом множестве вес i-го по величине эле­мента не больше веса i-го по величине элемента в . Этот факт мы будем называть оптимальностью по Гейлу. Таким образом, в матроиде нельзя выбрать независимое мно­жество, состоящее из «меньшего числа больших по величине (по весу) элементов».

Отметим также, что при обращении упорядочения элемен­тов жадный алгоритм выберет множество , которое не только имеет наименьший вес, но и i-й по величине элемент (считая от наименьшего) будет не больше i-го по величине элемента произвольной базы. Теперь мы можем посмотреть на примене­ние жадного алгоритма к задаче 1 с об­щей точки зрения: мы имели там дело с матроидом разбиений, порожденным разбиением позиций матрицы на столбцы.