Вершинне покриття

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

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

Означення

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

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

Приклади

• Множина всіх вершин є вершинним покриттям.
• Вершини з будь-якого найбільшого парування утворюють вершинне покриття.
• Повний двочастковий граф ${\displaystyle K_{m,n}}$ має найменше вершинне покриття розміру ${\displaystyle \tau (K_{m,n})=\min(m,n)}$.

Властивості

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

Обчислювальна задача

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

ПРИМІРНИК: Граф ${\displaystyle G}$

ВИХІД: Найменше число ${\displaystyle k}$ таке, що ${\displaystyle G}$ має вершинне покриття розміру ${\displaystyle k}$.

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

ПРИМІРНИК: Граф ${\displaystyle G}$ і додатне ціле число ${\displaystyle k}$.

ПИТАННЯ: Чи має ${\displaystyle G}$ вершинне покриття розміру не більше ${\displaystyle k?}$

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

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

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

мінімізувати	${\displaystyle \sum _{v\in V}c(v)x_{v}}$			(мінімізувати підсумкову вартість)
за умов	${\displaystyle x_{u}+x_{v}\geq 1}$	для всіх ${\displaystyle \{u,v\}\in E}$		(покрити кожне ребро графа)
	${\displaystyle x_{v}\in \{0,1\}}$	для всіх ${\displaystyle v\in V}$.		(кожна вершина або належить до вершинного покриття, або ні)

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

Апроксимаційний алгоритм

Докладніше: Апроксимаційний алгоритм

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

НАБЛИЖЕНЕ-ВЕРШИННЕ-ПОКРИТТЯ ${\displaystyle (G)}$ ${\displaystyle C=\emptyset }$ ${\displaystyle E'=G.E}$ поки ${\displaystyle E'\neq 0}$  нехай ${\displaystyle (u,v)}$ буде довільним ребром з ${\displaystyle E'}$  ${\displaystyle C=C\cup \{u,v\}}$  видалити з ${\displaystyle E'}$ кожне ребро інцидентне до ${\displaystyle u}$ чи ${\displaystyle v}$ повернути ${\displaystyle C}$

За умов використання списків суміжності час виконання цього алгоритму ${\displaystyle O(V+E).}$

Див. також

• Задача про покриття множини
• Реберне покриття