Число рёберного покрытия

Число рёберного покрытия графа $G$ — размер наименьшего рёберного покрытия в нём.

Если в графе $G$ есть изолированные вершины (т.е. вершины со степенью 0), то рёберного покрытия не существует, поэтому и число рёберного покрытия не определено.

В произвольном графе без изолированных вершин число рёберного покрытия может быть найдено с помощью алгоритма Эдмондса для паросочетаний за время $O(|E||V|^{2})$ и последующего добавления рёбер, покрывающих не насыщенные наибольшим паросочетанием вершины.

В графе $G=(V,E)$ без изолированных вершин число рёберного покрытия $\rho (G)$ связано с числом паросочетания $\nu (G)$ вторым тождеством Галлаи: $\nu (G)+\rho (G)=|V|$ , из которого, в свою очередь, следует неравенство $\rho (G)\geq \nu (G)$ . Если в графе существует совершенное паросочетание, то $\rho (G)=\nu (G)=|V|/2$ .

Также для графа без изолированных вершин справедливо неравенство $\rho (G)\geq \alpha (G)$ , где $\alpha (G)$ — число независимости графа $G$ . В двудольном графе $G$ , вследствие Теоремы Кёнига, $\rho (G)=\alpha (G)$ .