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

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

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

Означення

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

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

Приклади

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

Властивості

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

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

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

ПРИМІРНИК: Граф

G

ВИХІД: Найменше число

k

таке, що

G

має вершинне покриття розміру

k

.

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

ПРИМІРНИК: Граф

G

і додатне ціле число

k

.

ПИТАННЯ: Чи має

G

вершинне покриття розміру не більше

k?

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

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

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

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

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

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

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

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

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

Див. також

Примітки

Vazirani, 2001, pp. 122–123

Джерела

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

Посилання

Weisstein, Eric W. Вершинне покриття(англ.) на сайті Wolfram MathWorld.
Weisstein, Eric W. Найменше вершинне покриття(англ.) на сайті Wolfram MathWorld.
Weisstein, Eric W. Число вершинного покриття(англ.) на сайті Wolfram MathWorld.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Vazirani, 2001, pp. 122–123