Реберное покрытие

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

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

		Пример
		Рис.2.9.7. Реберное покрытие
	Меры

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

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