Учебно-методический комплекс по дисциплине «Теория конечных графов и ее приложения» Алексеев В. Е, Захарова Д. В

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

Паросочетания и реберные покрытия

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

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

Теорема о паросочетаниях и реберных покрытиях. Для любого графа G с n вершинами, не имеющего изолированных вершин, справедливо равенство .
Из решения одной задачи легко получить решение другой. Пусть М – наибольшее паросочетание в графе G, не имеющем изолированных вершин. Для каждой вершины, не принадлежащей никакому ребру паросочетания, выберем какое-нибудь ребро, инцидентное этой вершине и добавим все выбранные ребра к множеству М. Полученное множество ребер будет наименьшим реберным покрытием. Обратно, пусть C – наименьшее реберное покрытие графа G. Тогда в подграфе, образованном ребрами этого покрытия, каждая компонента связности является звездой (звезда – полный двудольный граф, у которого одна доля состоит из одной вершины). Выбрав по одному ребру из каждой компоненты, получим наибольшее паросочетание.
Несмотря на такое сходство между “вершинными” и “реберными” вариантами независимых множеств и покрытий, имеется кардинальное различие в сложности соответствующих экстремальных задач. “Вершинные” задачи относятся кразряду неподдающихся, для реберных же известны полиномиальные алгоритмы.

Метод увеличивающих путей

Пусть G – граф, М – некоторое паросочетание в нем. Ребра паросочетания будем называть сильными, остальные ребра графа – слабыми. Вершину назовем свободной, если она не принадлежит ребру паросочетания. Чередующимся путем относительно данного паросочетания называется простой путь, в котором чередуются сильные и слабые ребра (т.е. за сильным ребром следует слабое, за слабым – сильное). Чередующийся путь называется увеличивающим путем, если он соединяет две свободные вершины. Если имеется увеличивающий путь относительно данного паросочетания, то можно построить большее паросочетание – нужно вдоль этого пути превратить слабые ребра в сильные, а сильные в слабые. Эту операцию назовем инверсией. В результате инверсии мощность паросочетания увеличивается на 1.
Теорема об увеличивающем пути. Паросочетание является наибольшим тогда и только тогда, когда относительно него нет увеличивающих путей.
Для решения задачи о паросочетании остается научиться находить увеличивающие пути или убеждаться, что таких путей нет. Это можно сделать, перебирая чередующиеся пути (подобно перебору путей при поиске гамильтонова цикла). Дело осложняется тем, что чередующихся путей может быть много (см. задачу 7.4). Оказывается, нет необходимости перебирать их все. Известны эффективные алгоритмы, которые ищут увеличивающие пути для произвольных графов. Рассмотрим простой алгоритм, решающий эту задачу для двудольных графов.

Паросочетания в двудольных графах

Пусть – двудольный граф c долями A и B, М – паросочетание в G. Всякий увеличивающий путь, если такой имеется, соединяет вершину из множества A с вершиной из B. Поэтому при поиске увеличивающего пути достаточно рассматривать чередующиеся пути, начинающиеся в свободных вершинах из доли А.

Зафиксируем некоторую свободную вершину . Дерево Т с корнем в вершине a назовем деревом достижимости для вершины а, если

1) Т является подграфом графа ;

2) каждый путь в дереве Т, начинающийся в корне, является чередующимся путем;

3) Т – максимальное дерево со свойствами 1) и 2).

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

Теорема о дереве достижимости. Пусть G – двудольный граф с заданным паросочетанием, Т – дерево достижимости для вершины а. Вершина x принадлежит дереву Т тогда и только тогда, когда в графе существует чередующийся путь, соединяющий вершины a и x.
Для построения дерева достижимости можно использовать слегка модифицированный поиск в ширину из вершины a. Отличие от стандартного поиска в ширину состоит в том, что для вершин из доли А (они находятся на четном расстоянии от вершины а) исследуются инцидентные им слабые ребра, а для вершин из доли В – сильные. Если в дереве появляется отличная от а свободная вершина b, это означает, что найден увеличивающий путь – это путь между а и b в дереве. Выполнив инверсию, получим большее паросочетание. После этого, если в доле А еще имеются свободные вершины, возобновляется поиск увеличивающего пути (т.е. строится новое дерево достижимости).

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

Допустим, дерево достижимости для вершины а построено и выяснилось, что нет увеличивающих путей, начинающихся в а. Затем было построено дерево достижимости с другим корнем, найден увеличивающий путь и построено увеличенное паросочетание. Нужно ли строить дерево достижимости для вершины а относительно нового паросочетания? Оказывается, нет. Назовем свободную вершину бесполезной для данного паросочетания, если нет увеличивающих путей, начинающихся в этой вершине. Пусть – паросочетание, полученное из паросочетания М инверсией относительно некоторого увеличивающего пути.
Утверждение. Если вершина а бесполезна для паросочетания М, то она бесполезна и для паросочетания .
Таким образом, каждая вершина может выступать в качестве корня дерева достижимости не более одного раза, т.е. всего будет построено не более n деревьев. Построение одного дерева выполняется за время и общее время работы алгоритма оценивается как .

Независимые множества в двудольных графах

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

Пусть – двудольный граф с долями А и В и требуется найти в нем наибольшее независимое множество. Найдем сначала наибольшее паросочетание М в этом графе. Пусть и соответственно множества свободных вершин в долях А и В. Найдем все вершины из А, достижимые чередующимися путями из , пусть – множество всех таких вершин. Аналогично, пусть – множество все вершин из В, достижимых чередующимися путями из . Обозначим через множество всех вершин из А, не достижимых чередующимися путями ни из , ни из (см. рисунок 10). Вершины из не смежны с вершинами из , так как иначе образовался бы увеличивающий путь. Вершины из тоже не смежны с вершинами из , иначе они были бы достижимы из . Значит, – независимое множество. Оно содержит все свободные вершины и по одной вершине из каждого ребра паросочетания. Отсюда следует, что это независимое множество – наибольшее. Паросочетание М состоит из ребер, а свободных вершин имеется ровно . Следовательно, . Так как , то справедливо следующее утверждение.
Теорема о числе вершинного покрытия двудольного графа. Для любого двудольного графа G выполняется равенство .

Рис. 10.

Задачи

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

, .
7.2. Сколько наибольших паросочетаний имеется в графе 1) ; 2) ; 3) ; 4) ;

5); 6) ?

7.3. Является ли показанное на рисунке паросочетание наибольшим?

7.4. Сколько имеется максимальных (не имеющих продолжения) чередующихся путей

относительно показанного на рисунке паросочетания, начинающихся в вершине а?

Есть ли среди них увеличивающий путь? Есть ли вообще для данного паросочетания

увеличивающий путь?

7.5. Проверьте, являются ли данные паросочетания наибольшими. Найдите в этих графах

наименьшие реберные покрытия и наибольшие независимые множества.

7.6*. Докажите утверждение о бесполезных вершинах.

8. Раскраски

Раскраска вершин

Раскраской вершин графа называется назначение цветов его вершинам. Раскраска называется правильной, если любые две смежные вершины имеют разные цвета. Задача о раскраске состоит в нахождении правильной раскраски данного графа G в наименьшее число цветов. Это число называется хроматическим числом графа и обозначается .

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

Однако хроматическое число может быть и строго больше кликового числа. Например, , а .

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

.

Тот же граф служит примером, когда это неравенство строгое.

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

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

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

Выберем в данном графе G две несмежные вершины x и y и построим два новых графа: , получающийся добавлением ребра к графу G, и , получающийся из G слиянием вершин x и y. Операция слияния состоит в удалении вершин x и y и добавлении новой вершины z и ребер, соединяющих ее с каждой вершиной, с которой была смежна хотя бы одна из вершин x, y.

Если в правильной раскраске графа G вершины x и y имеют разные цвета, то она будет правильной и для графа . Если же цвета вершин x и y в раскраске графа G одинаковы, то граф можно раскрасить в то же число цветов: новая вершина z окрашивается в тот цвет, в который окрашены вершины x и y, а все остальные вершины сохраняют те цвета, которые они имели в графе G. И наоборот, раскраска каждого из графов , , очевидно, дает раскраску графа G в то же число цветов. Поэтому

,

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

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

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

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

Раскраска ребер

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

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

Обозначим через максимальную степень вершины в графе. При правильной реберной раскраске все ребра, инцидентные одной вершине, должны иметь разные цвета. Отсюда следует, что для любого графа выполняется неравенство . Для некоторых графов имеет место строгое неравенство, например, , а . Следующая теорема показывает, что может отличаться от не более чем на 1.
Теорема Визинга [4]. Для любого графа G справедливо неравенство .

Задачи

8.1. Найдите хроматическое число графов , , , .

8.2. Найдите хроматическое число графа 1) ; 2) ; 3) .
8.3. Примените алгоритм раскрашивания, основанный на дереве решений, к графу из

задачи 6.9.

8.4. Примените алгоритм последовательной раскраски к графу, изображенному на

рисунке, если вершины упорядочиваются а) по возрастанию номеров; б) по убыванию

номеров.

8.5. Для каких из следующих графов алгоритм последовательной раскраски дает точный

результат при любом упорядочении вершин: , , , ,?

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

графу, всегда дает оптимальную раскраску?

8.7. Найдите хроматический индекс графов , , ,, , .

следующая страница >>