Що таке проблема мінімального покриття?
Мінімум
є основна задача комбінаторної оптимізації. Для неорієнтованого графа мета полягає в тому, щоб визначити підмножину вершин, яка охоплює всі ребра, щоб кількість вершин у підмножині була мінімізованою.
У задачі мінімального покриття циклу (MCCP) нам задано неорієнтований повний граф G = ( V , E ) і метричну вагову функцію w : E → N, яка є невід’ємною, симетричною та підкоряється нерівності трикутника, мета полягає в тому, щоб знайти покриття циклу вартістю не більше λ з мінімальною кількістю циклів.
У задачі покриття мінімального набору ентропії одному надається набір з k наборів, які разом охоплюють основний набір з n елементів. Можливим розв’язком проблеми є розбиття основної множини на частини таким чином, що кожна частина входить до деякої з k заданих множин.
Проблема мінімально зваженого покриття вершин (MWVC) містить додатну вагу w : V → R+ для кожної вершини, і проблема полягає в тому, щоб знайти покриття вершини, де Pu∈C w(u) мінімізується. Версія рішення MVC була однією з початкових 21 NP-повних проблем Карпа, і, таким чином, MVC є NP-складним [13].
Покриття ребра в графі — це такий підграф, що кожна вершина має принаймні одне ребро, що інцидентне з нею в підграфі. Якщо ребра зважені, то крайове покриття, яке мінімізує суму ваг своїх країв є мінімальною вагою краю покриття.
Проблема мінімального покриття вершин є оптимізаційна задача знаходження найменшого вершинного покриття в заданому графі. Проблема покриття вершин є NP-повною проблемою: це була одна з 21 NP-повної задачі Карпа.Він часто використовується в теорії складності обчислень як відправна точка для доказів NP-твердості.