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

Число рёберного покрытия графа $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)$.

Ссылки

• László Lovász, Michael D. Plummer. Matching Theory. — North-Holland, 1986. — ISBN 0-444-87916-1.