Відкрити головне меню

Вершинне покриття графа  — це множина вершин така, що кожне ребро графа інцидентне хоча б одній вершині цієї множини. Задача знаходження найменшого вершинного покриття є класичною задачею оптимізації в інформатиці і типовим прикладом NP-складної задачі оптимізації, для якої відомий апроксимаційний алгоритм. Її версія у вигляді проблеми вибору, задача вершинного покриття, була однією з 21 NP-повної задачі Карпа і, отже, класичною NP-повною задачею в теорії складності обчислень.

Задачу найменшого вершинного покриття можна сформулювати як напівцілочисельну задачу лінійного програмування чия дуальна лінійна програма є задача найбільшого парування.

ОзначенняРедагувати

Формально, вершинне покриття неорієнтованого графа   це підмножина V′ множини вершин V така, що для кожного ребра (u, v) графа G або u у V′, або v у V′, або обидві вершини. Кажуть, що множина V′ «покриває» ребра G. Наступні зображення показують приклади вершинних покриттів в двох графах (і множина V' позначена червоним).

 

Найменше вершинне покриття це покриття з найменшого можливого розміру. Число вершинного покриття   це розмір найменшого такого покриття. Наступні зображення показують приклади найменших вершинних покриттів у наведених вище графах.

 

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

  • Множина всіх вершин є вершинним покриттям.
  • Вершини з будь-якого найбільшого парування утворюють вершинне покриття.
  • Повний дводольний граф   має найменше вершинне покриття розміру  .

ВластивостіРедагувати

  • Множина вершин є вершинним покриттям тоді і тільки тоді, якщо його доповнення є незалежною множиною.
  • Тому, кількість вершин у графі дорівнює кількості вершин у його найменшому вершинному покриттю плюс найбільшій незалежній множині.

Обчислювальна задачаРедагувати

Задача найменшого вершинного покриття це задача оптимізації щодо знаходження найменшого вершинного покриття певного графа.

ПРИМІРНИК: Граф  
ВИХІД: Найменше число   таке, що   має вершинне покриття розміру  .

Якщо задача сформульована як проблема вибору, її називають задача вершинного покриття:

ПРИМІРНИК: Граф   і додатне ціле число  .
ПИТАННЯ: Чи має   вершинне покриття розміру не більше  

Задача вершинного покриття — це NP-повна задача: вона була серед задач Карпа. В теорії складності обчислень часто використовується як відправна точка для доведення NP-складності.

Формулювання у термінах ЦЛПРедагувати

Припустимо, що кожна вершина має пов'язану вартість   Задачу найменшого зваженого вершинного покриття можна сформулювати як таку цілочисельну програму (ЦЛП).[1]

мінімізувати      (мінімізувати підсумкову вартість)
за умов   для всіх   (покрити кожне ребро графа)
  для всіх  . (кожна вершина або належить до вершинного покриття, або ні)

ЦЛП належить до загальнішого класу ЦЛП задач покриття.

Апроксимаційний алгоритмРедагувати

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

НАБЛИЖЕНЕ-ВЕРШИННЕ-ПОКРИТТЯ  

  1.  
  2.  
  3. поки  
  4.  нехай   буде довільним ребром з  
  5.  
  6.  видалити з   кожне ребро інцидентне до   чи  
  7. повернути  

За умов використання списків суміжності час виконання цього алгоритму  

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

  1. Vazirani, 2001, с. 122–123

ДжерелаРедагувати

  • Vazirani, Vijay V. (2001). Approximation Algorithms. Springer-Verlag. ISBN 3-540-65367-8. 

ПосиланняРедагувати