Лекция: Реберное покрытие

Реберным покрытием называется подмножество ребер U` графа G=(V,E), U`ÍE, такое, что всякая вершина графа G инцидентна ребру из U`.

Минимальное реберное покрытие — минимальное среди всех возможных подмножеств реберных покрытий.

· r(G) – число реберного покрытия. Равно размеру |U`| минимального реберного покрытия.

Проблема нахождения реберного покрытия относится к NP-полным, а вычисление числа реберного покрытия – к NP-тяжелым.