Нахождение наименьшего вершинного покрытия

Нахождение наименьшего вершинного покрытия

Нахождение наименьшего вершинного покрытия

По этой ссылке вы найдёте полный курс лекций по математике:

Решение задач по математике

Вновь ограничимся случаем двудольного графа. Оказывается, изложенный выше алгоритм Л нахождения наибольшего паро-сочетания заодно позволяет обнаружить и наименьшее вершинное покрытие. Пусть — множества помеченных вершин обеих долей графа G(V], V2) по окончании работы алгоритма Л. Обозначим Теорема 12. Множество A U В является минимальным вершинным покрытием графа G{VUV2).

Пусть М — наибольшее паросочетание в графе G{VU V2), посфоенное в результате работы алгоритма Л. Ребра, входящие в А/, как и ранее, мы называем черными; а остальные ребра графа для нас белые. Доказательство теоремы разобьем на три этапа. 1. Докажем, что концы любого черного ребра либо оба помечены, либо оба не помечены. Возьмем произвольное черное ребро ии, где и € Vi, v € V2.

Если вершина v помечена, то на шаге 4 алгоритма А пометку получит и вершина и.

Рассмотрим теперь случай, когда вершина и не помечена. Тогда непомеченной будет и вершина и. Действительно, и, будучи насыщенной вершиной не помечается на 2-м шаге. Но и на 4-м шаге вершина и не получает пометку, так как она инцидентна единственному черному ребру — uv, а другой его конец не помечен. Утверждение доказано. 2.

Проверим, что — вершинное покрытие графа. Возьмем в графе G{V\, V2) произвольное ребро -Докажем, что и 0 А или v € В. Если это не так, то и € А (то есть и — помеченная вершина) и v £ В (v — непомеченная вершина). Тогда в силу утверждения 1 ребро е не может быть черным. Но оно и не белое, поскольку при помеченной вершине и и белом ребре uv на 3-м шаге алгоритма Л вершина v получила бы пометку. Противоречие получено. 3.

Возможно вам будут полезны данные страницы:

Форматы чертежей по ГОСТ
Некоторые виды уравнений, интегрируемых в квадратурах
Распространение тепла в конечном стержне
Расчет цилиндрической косозубой передачи

Заметим, что (благодаря утверждению 1) 1) количество черных ребер с помеченными концами равно |Л| — количеству помеченных вершин из доли Vj (каждая из них инцидентна одному черному ребру); 2) количество черных ребер с непомеченными концами равно |Л| — количеству непомеченных вершин из доли V\ (любая такая вершина насыщенная, и из нее также исходит ровно одно черное ребро). Нахождение наименьшего вершинного покрытия Таким образом, то есть вершинное покрытие A U В равномощно наибольшему паросочета-нию.

В силу венгерской теоремы это

означает минимальность вершинного покрытия. Как отмечалось в § 3, дополнение к наименьшему вершинному покрытию графа является его наибольшим независимым множеством вершин. Значит, множество АиВ — наибольшее независимое. Стало быть, алгоритм Л (имеющий, как мы выяснили, полиномиальную трудоемкость) позволяет наряду с наибольшим паросочетанием в двудольном графе найти также наименьшее вершинное покрытие и наибольшее независимое множество.

Известно, что задачи определения наименьшего вершинного покрытия и наибольшего независимого множества для произвольного графа являются ^УР-полными, другими словами, для них нет эффективных алгоритмов решения (по крайней мере, они пока не известны науке). Очень важно, что для двудольных графов, возникающих во многих практичесжга задачах, полиномиальные алгоритмы решения указанных задач существуют! Пример. На рис. 5 изображен граф, в котором выделено наибольшее паросочетание и расставлены пометки, возникающие по окончании v рис 5 работы алгоритма А. Имеем . Значит, вершины 4, 5, 6 и 7 образуют минимальное вершинное покрытие, а вершины 1, 2, 3, 8, 9, 10 — наибольшее независимое • множество.