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

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

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

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

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

Межі

Нехай $G$ буде графом з $n\ge 1$ вершин і нехай $\mathrm{\Delta }$ буде найбільшим степенем графа. Тоді відомі такі обмеження на $\gamma (G)$ Шаблон:Harv:

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

Див. також

• Домінівна множина ребер

Примітки

• Шаблон:Citation, p. 190, problem GT2.
• Шаблон:Citation.