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

Графы превратились в невероятно сильное средство моделирования и получения данных из соцсетей, веб-страниц и ссылок, а также определения местоположения и маршрутов в GPS. Любой набор объектов, которые связаны друг с другом, можно сейчас представить с помощью графа...