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

У теорії графів, домінівна множина для графа  — така підмножина множини вершин що кожна вершина не з є суміжною зі щонайменше однією вершиною з Число домінування  — число вершин у найменшій домінівній множині для

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

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

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

МежіРедагувати

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

  • Одна вершина може домінувати не більше ніж над   інших вершин; отже  
  • Множина всіх вершин є домінівною множиною для будь-якого графа; отже  
  • Якщо   не містить ізольованих вершин, тоді в   існують дві неперетинні домінівні множини; докладніше дивись у доматичне число. Отже, в будь-якому графі без ізольованих вершин  

Див. такожРедагувати

ПриміткиРедагувати