Теория Задачи Инструменты Социум Интересно

Личный Кабинет

Войдите или зарегистрируйтесь
Лаборатория LMatrix
Лаборатория Lmatrix занимается оптимизацией транспортных задач. Сюда можно отнести задачи поиска кратчайшего пути в ориентированных графах, применимые как к масштабам города и страны, классическую задачу обхода (коммивояжера), задачи оптимизации доставки грузов, задачи трехмерной упаковки.
Новости проекта

31.05.2013 - Универсиада. Маршрут по России и Татарстану. Официально и математически.

Огонь Универсиады приближается к финишу в Казани, но прежде пройдет по 43 городам республики Татарстан. Все об маршрутах огня в нашем анонсе.

Тематические статьи

26.07.2013 - Монитор в автомобиле будет дублировать экран смартфона

Водители смогут увидеть точную копию экрана своего смартфона на мониторе бортовой системы автомобиля. О сотрудничестве в этом направлении договорились разработчик ПО для удаленного управления устройствами RealVNC и производитель процессоров Texas Instruments.

29.03.2013 - Facebook на днях анонсирует собственный смартфон на Android

На следующей неделе Facebook собирается представить собственный смартфон с кастомизированной версией Android, утверждают источники. Ранее глава компании Марк Цукерберг опровергал слухи о выпуске собственного смартфона.

29.03.2013 - Основатель Facebook М.Цукерберг создает политическую организацию

Основатель социальной сети Facebook Марк Цукерберг создает политическую организацию, которая займется такими вопросами, как реформа образования, иммиграция и научные исследования, передает Associated Press со ссылкой на анонимный источник.

Задача о вершинном покрытии

22 июля 2011 года в 18:07   Просмотров: 2985

В Информатике, задача о вершинном покрытии является NP-полной задачей в области теории графов. Также часто используется в теории сложности для доказательства NP-полноты более сложных задач.

Определение

 
Задача о вершинном покрытии
 

Вершинное покрытие для неориентированного графа G = (V,E) это множество его вершин S, такое что, у каждого ребра графа хотя бы один из концов входит в S.


Размером (size) вершинного покрытия называется число входящих в него вершин.

Пример: Граф, изображённый вверху имеет вершинное покрытие {1,3,5,6} размера 4. Однако оно не является наименьшим вершинным покрытием, поскольку существуют вершинные покрытия меньшего размера, такие как {2,4,5} и {1,2,4}.

Задача о вершинном покрытии требует указать минимально возможный размер k вершинного покрытия для заданного графа.

На входе: Граф G.
Результат: k - размер наименьшего вершинного покрытия S графа G.

Также вопрос можно ставить, как эквивалентную задачу о разрешении:

На входе: Граф G и положительное целое число k.
Вопрос: Существует ли вершинное покрытие S для G размера k?

Задача о вершинном покрытии сходна с задачей о независимом наборе. Множество вершин S является вершинным покрытием тогда и только тогда, когда его дополнение \bar S = V \setminus S является незавимимым набором.

Это следует из того, что граф с n вершинами имеет вершинное покрытие размера k тогда и только тогда, когда данный граф имеет незавимимый набор размера nk. В этом смысле обе проблемы равнозначны.

NP-полнота

Поскольку задача о вершинном покрытии является NP-полной, то, к сожалению, неизвестны алгоритмы для её решения за полиномиальное время. Однако, существуют алгоритмы, дающие «приближённое» решение этой задачи за полиномиальное время — можно найти вершинное покрытие, в котором число вершин не более чем вдвое превосходит минимально возможное.

Оставить комментарий

Пожалуйста, введите символы, показанные на рисунке.

Примеры решений задачи коммивояжера (TSP)
design by lmatrix
О проекте | Написать письмо | Ссылки | Литература | Карта сайта