3.6. Доминирующие множества графа

Подмножество S множества вершин V графа G называется доминирующим множеством графа G, если выполняется условие S  N(S)  V, где N(S) , а N(v)  множество вершин, смежных с вершиной v. Другими словами, множество S является доминирующим, если каждая вершина из множества V \ S смежна с некоторой вершиной из S. Если S является доминирующим множеством некоторого графа G, то всякое множество вершин S  S этого графа также является доминирующим. Поэтому представляет интерес задача нахождения минимальных доминирующих множеств, т. е. таких, у которых ни одно собственное подмножество не является доминирующим. Доминирующее множество, имеющее наименьшую мощность, принято называть наименьшим. Эта мощность называется числом доминирования графа G и обозначается символом μ(G).

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

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

Нетрудно видеть, что наименьшими доминирующими множествами графа G (рис. 3.5) являются {v₃, v₇}, {v₅, v₇} и {v₆, v₇}. Его матрица смежности, дополненная единицами на главной диагонали, имеет вид

Каждое из соответствующих множеств строк рассматриваемой матрицы покрывает все ее столбцы.

e₃

e₁

e₂

e₆

e₉

Рис. 3.5. Граф G