11.1.3. Связь чисел независимости и покрытий

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

ТЕОРЕМА Для любого нетривиального связного графа

«о + А> = р = ai + /3i

доказательство

Покажем, что имеют место четыре неравенства, из которых следуют два требуе­мых равенства.

«о +Р

Пусть Мо — наименьшее вершинное покрытие, то есть \М₀ = а₀. Рассмотрим V\M₀. Тогда V\M₀ — независимое множество, так как если бы в множестве V\M₀ были смежные вершины, то М₀ не было .бы покрытием. Имеем |V \ М₀| ^ /3₀, следовательно,

«о + А) ^ Р '• Пусть nq — наибольшее независимое множество вершин, то есть \N₀\= /3₀. Рассмотрим V\N₀. Тогда V\N_Q — вершинное покрытие, так как нет ребер, инцидентных только вершинам из N₀, стало быть, любое ребро инцидентно вершине (или вершинам) из V\M₀. Имеем \V \ N₀ Js а₀, следовательно, р = \N₀\ + \V\ N₀\ ^ /3₀ + а₀.

&i+pi ^ Р '• Пусть mi — наименьшее реберное покрытие, то есть |Mi = a\. Множество mi не содержит цепей длиной больше 2. Действитель­но, если бы в mi была цепь длиной 3, то среднее ребро этой цепи можно было бы удалить из М\ и это множество все равно осталось бы покрытием. Следовательно, mi состоит из звезд. (Звездой на­зывается граф, диаметр которого не превосходит двух, D(G) < 2.) Пусть этих звезд т. Имеем |Mi| = YSiLi ^пг> ^гД^{е п}г ~ число ребер в г-й звезде. Заметим, что звезда из щ ребер покрывает п» + 1 верши­ну. Имеем: р = Y^Li(ⁿi + 1) = "г + Y^=i ^пг - ^то + l-^il- Возьмем по одному ребру из каждой звезды и составим из них множество X. Тогда \Х\ = т, множество X — независимое, то есть \Х\ < (3\. Следовательно, р = \М_г \ + т = \М_г + \Х\ ^ qi + /З_ь

^Qi + /?i ^ Р '• Пусть ni — наибольшее независимое множество ребер, то есть \Ni = fa. Построим реберное покрытие Y следующим образом. Множество ni покрывает 2\Ni\ вершин. Добавим по одному ре­бру, инцидентному непокрытым р - 2\Ni\ вершинам, таких ребер p-2\Ni\. Тогда множество У" — реберное покрытие, то есть \Y\ < ai n\Y\ = \Ni +p- 2\Ni\ = р - \Ni\. Имеем:

\ = \Y\

Р = Р -

ЗАМЕЧАНИЕ -

Условия связности и нетривиальности гарантируют, что все четыре инварианта определе­ны. Однако это условие является достаточным, но не является необходимым. Например, для графа К_п U К_п заключение теоремы остается справедливым, хотя условие не выпол­нено

ОТСТУПЛЕНИЕ

Задача отыскания экстремальных независимых и покрывающих множеств возникает во многих практических случаях. Например, пусть есть множество процессов, использующих неразделяемые ресурсы. Соединим ребрами вершины, соответствующие процессам, кото­рым требуется один и тот же ресурс. Тогда f3o будет определять количество возможных параллельных процессов.