Домінівна множина

У теорії графів, домінівна множина для графу ${\displaystyle G=(V,E)}$ — така підмножина ${\displaystyle D}$ множини вершин ${\displaystyle V,}$ що кожна вершина не з ${\displaystyle D}$ є суміжною зі щонайменше однією вершиною з ${\displaystyle D.}$ Число домінування ${\displaystyle \gamma (G)}$ — число вершин у найменшій домінівній множині для ${\displaystyle G.}$

Домінівні множини (червоні вершини).

Задача домінівної множини займається дослідженням чи ${\displaystyle \gamma (G)\leq K}$ для певного графу ${\displaystyle G}$ і заданого ${\displaystyle K;}$ це класична NP-повна проблема вибору в теорії складності обчислень (Garey та Johnson, 1979). Отже вважають, що не існує алгоритму з поліноміальним часом виконання, який знаходить найменшу домінівну множину для заданого графу.

Зображення (a)–(c) праворуч, наводять три приклади домінівних множин на графі. У кожному прикладі, кожна біла вершина є суміжною хоча б з однією червоною вершиною, у такому випадку кажуть, що червоні вершини домінують над білими. Число домінування цього графу є 2: Приклади (b) і (c) показують, що існують домінівні множини з 2 вершинами, і можна перевірити, що для цього графу немає домінівної множини, що складається з 1 вершини.