6. Задача о покрытии
Задача о покрытии наименьшей мощности (ЗПНМ) была сформулирована во введении, и она состоит в нахождении такого множества 
ребер графа 
что число ребер в 
минимально и каждая вершина из 
является концевой вершиной по крайней мере одного ребра из 
Теперь, основываясь на следующей теореме, мы покажем, что ЗПНМ и ЗНПС эквивалентны.
Теорема 6. Если 
наименьшее покрытие и если для каждой вершины 
со степенью 
удалить все ребра, инцидентные 
за исключением одного, то оставшееся множество ребер 
будет наибольшим паросочетанием.
Доказательство. Так как в вышеприведенной конструкции то никакие два ребра в 
не будут смежными и 
является паросочетанием. Поэтому достаточно показать, что 
наибольшее паросочетание. Допустим, что 
не максимально. Тогда по теореме 1 существует некоторая аугментальная цепь из какой-нибудь экспонированной вершины 
; (т. е. вершины с 
к другой экспонированной вершине 
Так как 
то отсюда вытекает, что по крайней мере одно ребро, ведущее от 
к другой вершине 
можно удалить, и то же относится к вершине 
Пусть одно из удаленных ребер, инцидентных 
будет 
а одно из удаленных ребер, инцидентных 
будет 
Пусть 
аугментальная цепь 
ребрами) от 
Если теперь удалить из 
ребра из 
принадлежащие цепи 
и два ребра 
то оставшееся множество (скажем, 
все еще будет покрытием, так как каждая вершина из 
будет концевой для некоторого ребра из множества 
Но 
получено удалением из 
ребер и добавлением 
ребер; следовательно, 
Это противоречит предположению о том, что 
наименьшее покрытие. Значит, 
построенное в соответствии с теоремой, является наибольшим паросочетанием.
Следующая теорема аналогична теореме 6 и точно так же доказывается [30].
Теорема 7. Если 
наибольшее паросочетание графа 
и для каждой экспонированной вершины 
добавить ребро,
инцидентное 
то получившееся множество ребер 
будет наименьшим покрытием графа 
Общая ЗПО, когда каждому ребру приписана некоторая стоимость, здесь обсуждаться не будет. Она может быть решена с помощью алгоритма, очень похожего на алгоритм для ЗМП. Подробили алгоритм для ЗПО дал Уайт [301.
7. Задачи
(см. скан)
