§ 3. Независимое множество вершин графа

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

Множество вершин графа называется независимым (внутренне устойчивым), если они попарно не смежны.

Внутренне устойчивое множество вершин графа называется пустым подграфом, если при добавлении хотя бы одной вершины, не принадлежащей этому множеству, образуется хотя бы одно ребро (дуга).

Пример. В графе G (рис. 5.6 ) выделить внутренне устойчивое множество и пустой подграф

Рис. 5.6

□ Внутренне устойчивыми множествами вершин для графа G являются множества вершин {1,3,5} и {1,3}, указанные на рис. 5.7а,б. Внутренне устойчивое множество {1,3,5} является пустым подграфом, т.к. добавление любой вершины графа G, не вошедшей в множество {1,3,5}, приводит к образованию ребер. Например, добавление вершины 4 приводит к образованию ребер ( 3,4 ) и ( 4,5 ) (рис. 5.7в ). Внутренне

устойчивое множество вершин {1,3} не является пустым подграфом, т.к. добавление вершины 5 не приводит к образованию ребра (рис. 5.7г).

Граф G имеет и другие пустые подграфы и внутренне устойчивые множества.

Рис. 5.7 ■

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

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

Пример. Найти вершинное число независимости графа G , изображенного на рис. 5.8

Рис. 5.8

□ В графе G вершины 4 и 8 имеют минимальную степень, равную 2. Возьмем, например, вершину 4 и внесем ее в пустой подграф: Е = {4}. Удаляем вершину 4 и смежные с ней вершины 1 и 5 в результате получим граф

В графе возьмем, например, вершину 6 и внесем ее в пустой подграф: Удаляем эту вершину и смежные ей вершины 3 и 7. Получим граф :

Выбираем, например, вершину 8 и вносим ее в пустой подграф: . Вершина 2 , смежная вершине 8 , удаляется. Вершин больше нет – пустой подграф построен. Мощность этого пустого подграфа равна вершинному числу независимости графа G , т.е.

■

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

В указанном алгоритме используются понятия окрестностей и .

Окрестностью вершины v₀ графа G называется подграф , носитель которого совпадает с окрестностью единичного радиуса этой вершины, , а сигнатуру U₀ образуют ребра графа G, соединяющие вершины из V₀.

Неокрестностью вершины v₀ графа G называется подграф , носитель которого , а сигнатура состоит из ребер графа G , соединяющих вершины из .

Пример. Указать и вершины v₀ графа G

□ Согласно определениям окрестности и неокрестности вершины v₀ графа G будем иметь :

= , где

= , ;

= , где = ,

. ■