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

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

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

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

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

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

Ссылки

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