Вершинне покриття графа — це множина вершин така, що кожне ребро графа інцидентне хоча б одній вершині цієї множини. Задача знаходження найменшого вершинного покриття є класичною задачею оптимізації в інформатиці і типовим прикладом NP-складної задачі оптимізації, для якої відомий апроксимаційний алгоритм. Її версія у вигляді проблеми вибору, задача вершинного покриття, була однією з 21 NP-повної задачі Карпа і, отже, класичною NP-повною задачею в теорії складності обчислень.
Задачу найменшого вершинного покриття можна сформулювати як напівцілочисельну задачу лінійного програмування чия дуальна лінійна програма є задача найбільшого парування.
Означення
Формально, вершинне покриття неорієнтованого графа це підмножина V′ множини вершин V така, що для кожного ребра (u, v) графа G або u у V′, або v у V′, або обидві вершини. Кажуть, що множина V′ «покриває» ребра G. Наступні зображення показують приклади вершинних покриттів в двох графах (і множина V′ позначена червоним).
Найменше вершинне покриття це покриття з найменшого можливого розміру. Число вершинного покриття це розмір найменшого такого покриття. Наступні зображення показують приклади найменших вершинних покриттів у наведених вище графах.
Приклади
Множина всіх вершин є вершинним покриттям. Вершини з будь-якого найбільшого парування утворюють вершинне покриття. Повний двочастковий граф має найменше вершинне покриття розміру .
Властивості
Множина вершин є вершинним покриттям тоді і тільки тоді, якщо його доповнення є незалежною множиною. Тому, кількість вершин у графі дорівнює кількості вершин у його найменшому вершинному покриттю плюс найбільшій незалежній множині.
Обчислювальна задача
Задача найменшого вершинного покриття це задача оптимізації щодо знаходження найменшого вершинного покриття певного графа. ПРИМІРНИК: Граф ВИХІД: Найменше число таке, що має вершинне покриття розміру . Якщо задача сформульована як проблема вибору, її називають задача вершинного покриття: ПРИМІРНИК: Граф і додатне ціле число . ПИТАННЯ: Чи має вершинне покриття розміру не більше
Задача вершинного покриття — це NP-повна задача: вона була серед задач Карпа. В теорії складності обчислень часто використовується як відправна точка для доведення NP-складності.
Формулювання у термінах ЦЛП Припустимо, що кожна вершина має пов'язану вартість Задачу найменшого зваженого вершинного покриття можна сформулювати як таку цілочисельну програму (ЦЛП). {| | мінімізувати | colspan="2" |
| (мінімізувати підсумкову вартість) |- | за умов | | для всіх | | (покрити кожне ребро графа)
| для всіх . | | (кожна вершина або належить до вершинного покриття, або ні) |} ЦЛП належить до загальнішого класу ЦЛП задач покриття.
Апроксимаційний алгоритм
Незважаючи на те, що ми не знаємо як знайти оптимальне/найменше вершинне покриття у графі за поліноміальний час, ми можемо ефективно знайти вершинне покриття, яке буде близьким до оптимального. Наведемо алгоритм, який повертає вершинне покриття гарантовано не більше ніж вдвічі більше за розміром порівняно з оптимальним покриттям.
НАБЛИЖЕНЕ-ВЕРШИННЕ-ПОКРИТТЯ
поки нехай буде довільним ребром з
видалити з кожне ребро інцидентне до чи повернути За умов використання списків суміжності час виконання цього алгоритму
Див. також Задача про покриття множини Реберне покриття
Примітки
Джерела
Посилання