Введение
Подмножество рёбер графа, к каждому узлу которого инцидентно хотя бы одно ребро. В теории графов, покрытие рёбер графа — это набор рёбер, такой что каждая вершина графа инцидентна хотя бы одному ребру из этого набора. В информатике, задача о минимальном покрытии рёбер — это задача поиска покрытия рёбер минимального размера. Это задача оптимизации, относящаяся к классу задач покрытия и решаемая за полиномиальное время.
In graph theory, an edge cover of a graph is a set of edges such that every vertex of the graph is incident to at least one edge of the set. In computer science, the minimum edge cover problem is the problem of finding an edge cover of minimum size. It is an optimization problem that belongs to the class of covering problems and can be solved in polynomial time.
Определение
Формально, краевое покрытие графа G — это множество ребер C, такое что каждая вершина в G инцидентна хотя бы одному ребру из C. Говорят, что множество C покрывает вершины G. На рисунке ниже приведены примеры краевых покрытий в двух графах (множество C выделено красным цветом). Минимальное краевое покрытие — это краевое покрытие наименьшего возможного размера. Число краевого покрытия ρ(G) — это размер минимального краевого покрытия. На рисунке ниже приведены примеры минимальных краевых покрытий (снова множество C выделено красным цветом). Обратите внимание, что фигура справа является не только краевым покрытием, но и сопоставлением. В частности, это совершенное сопоставление: сопоставление M, в котором каждая вершина инцидентна ровно одному ребру из M. Совершенное сопоставление (если оно существует) всегда является минимальным краевым покрытием.
Примеры
Множество всех ребер является покрытием ребер, при условии, что вершин степени 0 нет. Полный двудольный граф Km,n имеет число покрытия ребер равное max(m, n).
Алгоритмы
Наименьшее покрытие рёбер можно найти за полиномиальное время, найдя максимальное паросочетание и жадно расширяя его, чтобы покрыть все вершины. На следующем рисунке максимальное паросочетание отмечено красным цветом; дополнительные рёбра, добавленные для покрытия непокрытых вершин, отмечены синим. (На рисунке справа показан граф, в котором максимальное паросочетание является полным; следовательно, он уже покрывает все вершины, и дополнительные рёбра не требуются.) С другой стороны, связанная задача поиска наименьшего вершинного покрытия является NP-трудной задачей. Рассматривая изображение, уже становится очевидным, почему: для заданного минимального покрытия рёбер и максимального паросочетания, пусть *m* и *n* будут количеством рёбер в минимальном покрытии рёбер и максимальном паросочетании соответственно, то: Действительно, минимальное покрытие рёбер содержит максимальное паросочетание, поэтому рёбра минимального покрытия рёбер можно разложить на рёбра максимального паросочетания, покрывающие *n* вершин, и остальные рёбра, каждое из которых покрывает ещё одну вершину. Таким образом, поскольку минимальное покрытие рёбер покрывает все вершины, мы получаем желаемое равенство.