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