9. Покрытия и раскраски

В предыдущих главах мы определили несколько полезных характеристик, связанных с графом: ранг, цикломатическое число, связность, число паросочетания и т. д. Как было упомянуто ранее, ранг и цикломатическое число используются при изучении электрических цепей, связность — при изучении сетей связи. В этой главе мы изучаем другие важные характеристики графа: число независимости и число вершинного и реберного покрытий, хроматический индекс и хроматическое число. Мы начинаем обсуждение с числа независимости и числа вершинного и реберного покрытий. Эти характеристики мы связываем с числом паросочетания, определенным в предыдущей главе, и устанавливаем эквивалентную формулировку теоремы Холла. Затем мы изучим хроматический индекс и хроматическое число, которые связываем со свойствами вершинной и реберной раскрашиваемости графа.

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

9.1. Независимые множества и вершинные покрытия

Рассмотрим граф . Подмножество называется независимым множеством графа G, если никакие две вершины 5 не смежны в графе G. Независимое множество называется также внутренне устойчивым множеством.

Независимое множество S графа G максимально, если граф G не содержит такого независимого множества S, что Число вершин в максимальном независимом множестве графа G называется числом независимости (числом внутренней устойчивости) графа G и обозначается через

Например, в графе на рис. 9.1 множества являются независимыми множествами. Из них — не наибольшие независимые множества; — наибольшее, но не максимальное; — максимальное.

Подмножество К множества вершин V является вершинным покрытием, если любое ребро графа G имеет хотя бы одну концевую вершину в подмножестве К. Если рассматривать вершину как покрывающую

все инцидентные ей ребра, тогда вершинное покрытие графа G есть подмножество V, которое покрывает все ребра графа G.

Вершинное покрытие К графа G минимально, если граф G не имеет такого вершинного покрытия К, что Число вершин в минимальном вершинном покрытии графа G называется числом вершинного покрытия графа G и обозначается через

Например, в графе на рис. 9.1 множества являются вершинными покрытиями. Из них — не наименьшие; — наименьшее, но не минимальное; — минимальное.

Рис. 9.1.

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

Независимые множества и вершинные покрытия — тесно связанные понятия, как мы показываем в следующей теореме.

Теорема 9.1. Рассмотрим граф . Подмножество является независимым множеством графа G тогда и только тогда, когда его дополнение 5 подмножества S в V (т. е. ) является вершинным покрытием.

Доказательство. По определению S — независимое множество графа G тогда и только тогда, когда никакое ребро G не содержит в подмножестве S обеих концевых вершин. Другими словами, S — независимое множество тогда и только тогда, когда любое ребро графа G имеет по крайней мере одну концевую вершину в дополнении S подмножества S в V. Тогда по определению вершинного покрытия теорема верна.

Следствие 9.1.1. Для простого графа на вершинах

Доказательство. Рассмотрим максимальное независимое множество S и минимальное вершинное покрытие К графа . Тогда

Согласно теореме 9.1, - вершинное покрытие, независимое множество. Поэтому Объединив эти неравенства, получим

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

В общем случае равенство в выражении (9.1) не всегда имеет место. Однако в следующей теореме мы показываем, что если G — двудольный граф.

Теорема 9.2. Число ребер в максимальном паросочетании двудольного графа равно числу вершин минимального вершинного покрытия, т. е.

Доказательство. Пусть М — максимальное паросочетание, минимальное вершинное покрытие двудольного графа .

Рассмотрим произвольное подмножество . Каждое ребро графа G инцидентно вершине в подмножестве А или в подмножестве Кроме того, любое ребро, инцидентное вершине в подмножестве А, инцидентно также вершине в множестве вершин , смежных с вершинами подмножества А. Таким образом, множество является вершинным покрытием графа G и, следовательно, по теореме Холла 8.13

Теперь, объединяя выражения (9.1) и (9.2), получаем . Эта теорема принадлежит Кёнигу [9.1].

В теореме 8.20 мы дали характеризацию максимального паросочетания, используя понятие чередующейся цепи. Поскольку независимое множество — это вершинный аналог паросочетания, можно ожидать, что существует также подобная характеризация для максимального независимого множества. Это действительно так, и далее мы получим такую характеризацию. Будем следовать трактовке Бержа [9.2].

Сначала определим чередующуюся последовательность как вершинный аналог чередующейся цепи.

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

2) вершина смежна хотя бы с одной вершиной из множества

3) вершина не смежна ни с одной вершиной из

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

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

Рассмотрим дерево Т. Напомним (упражнение 2.2), что оно является двудольным графом, т. е. множество V его вершин можно разбить на такие два подмножества X и Y, что

3) X и Y — независимые множества в дереве.

Будем называть (X, Y) двудольным разбиением множества вершин дерева Т, а вершины подмножеств X и Y-вершинами соответственно.

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

Лемма 9.1. Пусть (X, Y) — двудольное разбиение множества вершин дерева Т. Если то подмножество X содержит по крайней мере висячих вершин дерева Т.

Доказательство. Доказательство проводим индукцией по числу вершин дерева Т. Ясно, что лемма справедлива для . Пусть этот результат имеет место для всех деревьев, имеющих менее вершин

Рассмотрим дерево Т на вершинах с Пусть у — висящая вершина дерева Т и Заметим, что Т—дерево на вершине.

Предположим, что -вершина. Если то у — требуемая Х-вершина дерева Т. В противном случае по индуктивному предположению не менее висячих верши» дерева Т являются Х-вершинами. Эти вершин висячие и в дереве Т, и, следовательно, они вместе с вершиной v являются требуемыми -вершинами дерева Т.

Доказательство следует немедленно, если -вершииа.

Лемма 9.2. Пусть (X, К) — двудольное разбиение множества вершин дерева Т.

1. Если или тосуществуег чередующаяся последовательность в которой каждая вершина дерева Т используется точно один раз.

2. Если то существует максимальная чередующаяся последовательность нечетной длины в которой используется точно один раз каждая вершина подмножества

Доказательство.

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

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

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

Теперь, согласно результату части 1 леммы, существует максимальная чередующаяся последовательность нечетной длины, в которую входят все вершины дерева Т, а следовательно, все F-вершины дерева Т.

Например, в дереве на рис. 9.2 — чередующаяся последовательность, в которую входят все К-вершины дерева Т.

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

Теорема 9.3. Независимое множество Y графа G максимально тогда и только тогда, когда в графе G не существует чередующейся последовательности нечетной длины по отношению к множеству

Доказательство. Необходимость. Рассмотрим граф . Пусть Y — максимальное независимое множество в графе G и X—V—Y.

Рис. 9.2.

Допустим, что существует максимальная чередующаяся последовательность о нечетной длины по отношению к множеству Y и , где

Заметим, что, поскольку последовательность а имеет нечетную длину, и последняя вершина последовательности а является Х-вершиной. Кроме того, поскольку а — максимальна, никакую вершину нельзя добавить в последовательность о без нарушения условия (2) определения чередующейся последовательности.

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

Достаточность. Пусть X — максимальное независимое множество, независимое множество с Покажем, что существует чередующаяся последовательность нечетной длины по отношению к множеству У.

Пусть — порожденный подграф графа G на множестве вершин Если несвязный, тогда пусть будут компонентами подграфа причем множество вершин - есть Заметим, что Так как то

Поэтому для некоторого t существует неравенство Не нарушая общности, допустим, что

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

Заметим, что X- и У-вершины последовательности а принадлежат соответственно. Рассмотрим произвольную У-вершину не входящую в последовательность о. Возможны два случая.

Случай 1.

В этом случае вершина не смежна с Х-вершинами. В частности, она не смежна ни с одной Х-вершиной последовательности

Случай 2.

В этом случае вершина не принадлежит графу поскольку последовательность а содержит все К-вершины графа Следовательно, вершина не смежна ни с одной вершиной графа . В частности, она не смежна ни с какой Х-вершиной последовательности а.

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

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