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

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

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

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

Межі[ред. | ред. код]

Нехай $G$ буде графом з $n\geq 1$ вершин і нехай $\Delta$ буде найбільшим степенем графа. Тоді відомі такі обмеження на $\gamma (G)$ (Haynes, Hedetniemi та Slater, 1998a, Chapter 2):

Одна вершина може домінувати не більше ніж над $\Delta$ інших вершин; отже $\gamma (G)\geq n/(1+\Delta ).$
Множина всіх вершин є домінівною множиною для будь-якого графа; отже $\gamma (G)\leq n.$
Якщо $G$ не містить ізольованих вершин, тоді в $G$ існують дві неперетинні домінівні множини; докладніше дивись у доматичне число. Отже, в будь-якому графі без ізольованих вершин $\gamma (G)\leq n/2.$