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

Перейти к навигацииПерейти к поиску

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

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

В произвольном графе без изолированных вершин число рёберного покрытия может быть найдено с помощью алгоритма Эдмондса для паросочетаний за время и последующего добавления рёбер, покрывающих не насыщенные наибольшим паросочетанием вершины.

В графе без изолированных вершин число рёберного покрытия связано с числом паросочетания вторым тождеством Галлаи: , из которого, в свою очередь, следует неравенство . Если в графе существует совершенное паросочетание, то .

Также для графа без изолированных вершин справедливо неравенство , где число независимости графа . В двудольном графе , вследствие Теоремы Кёнига, .

Ссылки

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