Глава 3. НЕЗАВИСИМЫЕ И ДОМИНИРУЮЩИЕ МНОЖЕСТВА. ЗАДАЧА О ПОКРЫВАЮЩИХ МНОЖЕСТВАХ

1. Введение

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

Эти числа и связанные с ними подмножества вершин описывают важные структурные свойства графа и имеют разнообразные непосредственные приложения при ведении проектного планирования исследовательских работ [3], в кластерном анализе и численных методах таксономии [36, 2], параллельных вычислениях на ЭВМ [17], при размещении предприятий обслуживания, а также источников и потребителей в энергосистемах [66, 56].

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