Дискретно-непрерывная математика (стр. 75 )

Обозначим число фигур через k, и пусть ni—число

допустимых положений i-й фигуры. Рассмотрим граф G, имеющий вершин, соответствующих всем возможным положениям фигур. Будем считать, что в графе G вершины v и w являются смежными тогда и только тогда, когда соответствующие положения оказываются совместными в названном смысле. Легко видеть, что каждое решение исходной головоломки соответствует полному подграфу из k вершин и наоборот. Таким обра­зом, задача нахождения всех решений головоломки эк­вивалентна нахождению всех полных подграфов из k вершин.

Пусть, наконец, А, В, ..., Z обозначают фигуры, а Ai означает некоторое положение (т. е. вершину) фигу­ры А. Жульен предложил последовательность преобра­зований, позволяющую получить из исходного графа не­который конечный граф, вершины которого представля­ют собой различные решения, т. е. полные подграфы исходного графа.

На первом шаге удаляются все вершины, соответст­вующие фигурам А и В (в качестве А и В могут вы­бираться любые фигуры). Они заменяются вершинами типа ABij при условии, что рассматриваемые комбинации Ai и Вj) являются совместимыми. Кроме того, ABij сое­диняется со всеми положениями фигур С, D, ..., Z, ко­торые оказываются совместимыми как с Аi так и с Вj. Легко видеть, что существует взаимнооднозначное соот­ветствие между полными подграфами с k вершинами в исходном графе и полными подграфами с (k—1) вер­шинами в новом графе.

Повторяя названную процедуру, в конечном итоге мы получим граф, вершины которого имеют вид ABC... Zij... q. При этом Ai, Bj, . . ., Zq обозначает полный под­граф исходного графа.

ПАРОСОЧЕТАНИЯ

5.14. Максимальные паросочетания

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

Пусть G=(V, E) — граф, не имеющий петель. Множе­ство ребер M E называется паросочетанием графа G, если в М нет двух смежных ребер. Таким образом, каж­дая вершина G инцидентна самое большее одному реб­ру М. Говорят, что вершина покрыта (или не покрыта) относительно М, если она инцидентна (или нет) ребру в М. Пустое множество образует (хотя и неинтересный) случай паросочетания, относительно которого каждая вершина является непокрытой.

Паросочетание графа G будем называть максималь­ным, если не существует паросочетания большей мощ­ности.

В случае, когда каждая вершина покрыта, гово­рят, что паросочетание — совершенно. Совершенное па­росочетание иногда называют

1-факторным. Если существует совершенное паросочетание для G, то, оче­видно, оно является максимальным. (Заметим, что coвершенное паросочетание не может существовать, если |V|—нечетное.) Татт выделил множество графов, обладающих совершенными паросочетаниями.

Основная цель данного раздела состоит в описании алгоритма, предложенного Эдмондсом для нахож­дения максимального паросочетания в произвольном графе.

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

Предположим, что G— двудольный граф, в котором существует такое разбиение вершин {V1, V2}, что каждое ребро соединяет вершину в V1 с вершиной в V2. Задачи о паросочетаниях часто возникают в двудольных графах, особенно, когда вершины в V1 и V2 представля­ют различные типы объектов (например, мужчины — женщины, мужчины — работы — машины). При этом часто требуется «попарно связать» или «отобразить» раз­ные типы объектов друг на друга таким образом, чтобы осталось как можно меньше несвязанных объектов (т. е. непокрытых вершин). Структура исходного графа ис­пользуется для выделения всех допустимых парных он единений.

Пусть М — паросочетание графа G=(V, E). Тогда простая цепь С в G называется чередующейся цепью относительно М, если ее ребра (при прохождении цепи от одного конца до другого) являются поочередно реб­рами паросочетания (ребрами М) и ребрами непаросочетания (ребрами Е—М). Допустим, что дано паросочетание М и чередующая цепь С. Рассмотрим множест­во ребер М'=М С, состоящее из ребер, принадлежащих М или С, но не одновременно обоим множествам. Таким образом, М' получается вычеркиванием из М ребер па-росочетания, входящих в С, и добавлением к М ребер, не входящих в паросочетание, но принадлежащих С. Так как число ребер в С, принадлежащих паросочетанию, отличается от числа ребер, не принадлежащих паросочетаниго, самое большее на 1, число ребер в М и М' также различается самое большое на 1.

Для иллюстрации сделанных замечаний рассмотрим паросочетание М, выделенное жирными линиями на рис. 5.29, а.

Рис. 5.29.

Множество М'=М С, показанное на рис. 5.29, с, получается при использовании чередующей­ся цепи С, проведенной на рис. 5.29, b. Если, как в пред­шествующем примере, конечные точки чередующейся цепи С не покрыты ребрами М, то легко видеть, что М' обязательно является паросочетанием и |М'|=|М|+1. По этой причине чередующаяся цепь, обе конечные точ­ки которой не покрыты, называется чередующимся рас­ширением. Существование чередующегося расширения (или просто расширения) является необходимым и до­статочным условием того, что М не является максималь­ным паросочетанием. Сказанное можно сформулировать в виде следующей теоремы, предложенной Бержем и доказанной на основе идей Эдмондса.

Теорема 5.9. Паросочетание М в графе G является максимальным тогда и только тогда, когда G не содер­жит чередующегося расширения относительно М.

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

G'=(V, MM'), содержащий только те ребра, которые встречаются в М или М', но не в обоих одно­временно.

В графе G' не существует вершины v степени боль­ше чем 2, так как вершине v инцидентно самое большее одно ребро в М и одно в М'. Компоненты G', исключая изолированные вершины, соответствуют чередующимся цепям и чередующимся простым циклам относительно М (и М'). Каждый из циклов содержит одинаковое чис­ло ребер из М и из М'. Следовательно, должна быть, по крайней мере, одна компонента, которая соответству­ет чередующейся цепи и в которой число ребер, при­надлежащих М', на единицу больше числа ребер, принадлежащих М. Конечные точки такой цепи обяза­тельно останутся непокрытыми ребрами М. Теорема доказана.

На основе предыдущей теоремы можно решать зада­чу нахождения максимального паросочетания, если най­ти удобный метод поиска чередующегося расширения в том случае, когда оно существует. Действительно, мы могли бы начать с «пустого» паросочетания М0, найти чередующую цепь C1 (единственное ребро в этом слу­чае) и определить M1 = M0C1. В общем случае, можно также определить Mi=Mi-1 Ci, где Сi — чередующаяся цепь, соединяющая две вершины, непокрытые относи­тельно М. В конечном счете мы придем к некото­рому i-му этапу, на котором чередующееся расширение Ci+1 не существует. Тогда Mi — максимальное паро­сочетание.

Известно несколько эффективных алгоритмов нахож­дения максимальных паросочетаний в двудольных гра­фах. Алгоритм, описанный ниже, применим для любых графов. Он основан на си­стематическом поиске чередующихся расширений и по­следовательном расширении паросочетаний. В процессе его функционирования находятся определенные области графа (соответствующие так называемым венгерским деревьям), которые могут быть удалены при дальнейшем поиске без опасности потери каких-то чередующих­ся расширений. Алгоритм может также стягивать опре­деленные подграфы (связанные с соответствующими циклами нечетной длины) в одну «псевдовершину», уп­рощая тем самым процедуру поиска.

Перед тем как переходить к описанию алгоритма, введем несколько вспомогательных понятий. Чередую­щееся дерево — это дерево, вершины которого разбиты на два класса (называемые внутренними и внешними вершинами) так, что каждая внутренняя вершина имеет степень 2 и каждое ребро соединяет внутреннюю верши­ну с внешней. (Заметим, что все «конечные» вершины, т. е. вершины степени 1, обязательно внешние.) Пример чередующегося дерева показан на рис. 5.30, а (зачернен­ные вершины соответствуют внешним).