ОПРЕДЕЛЕНИЕ 30.Паросочетаниемв неориентированном графе называется семейство дуг, попарно не имеющих общих вершин.
Очевидно, что подмножество паросочетания также является паросочетанием. Паросочетание называется максимальным, если оно состоит из максимально возможного числа дуг. Число дуг в максимальном паросочетанииобозначим через p(Г).
ОПРЕДЕЛЕНИЕ 31.Семейство дуг (ребер) в неориентированном графе без изолированных вершин называется реберным покрытием, если каждая вершина графа инцидентна хотя бы одной из дуг этого семейства.
Расширение реберного покрытия также является реберным покрытием. Реберное покрытие называется минимальным, если оно содержит минимально возможное число дуг. Число дуг в таком покрытии обозначим через r(Г).
Между двумя введенными величинами существует тесная связь.
Теорема 24. Для неориентированного графа Г без изолированных вершин справедливо равенство p(Г)+r(Г)=p, где p как и прежде число вершин Г.
Доказательство. 1. Рассмотрим какое-нибудь максимальное паросочетание. Поскольку все его дуги инцидентны разным вершинам, то число вершин, не инцидентных дугам этого паросочетания, равно p-2p(Г). Выберем по одной дуге для каждой из этих вершин (они все разные, иначе паросочетание можно было бы расширить) и добавим к нему выбранное максимальное паросочетание. Тем самым, образовано реберное покрытие, в котором p(Г)+(p-2p(Г))=p-p(Г) дуг. Отсюда, r(Г)≤p-p(Г), т.е. r(Г)+ p(Г)≤p.
2. Выберем теперь какое-нибудь минимальное реберное покрытие. Соответствующий подграф является остовным. Если u – вершина этого подграфа со степенью, большей 1, то смежные с ней вершины имеют степень 1. Действительно, если бы в подграфе существовала цепь a-(a,b)-b-(b,c)-c-(c,d)-d, то после удаления дуги (b,c) получили бы реберное покрытие исходного графа с меньшим числом дуг, что противоречит минимальности избранного реберного покрытия. Тем самым, этот подграф состоит из нескольких связных компонент, у каждой из которых одна вершина может иметь степень, большую 1, а остальные имеют степень 1 (компоненты типа солнца). Выбрав из каждой компоненты по одной дуге, получим паросочетание. Пусть число этих компонент равно k, причем в i-й компоненте pi вершин. Поскольку каждая компонента дерево, число дуг в i-й компоненте равно pi-1. А тогда r(Г)= . В построенном паросочетании число дуг равно k, т.е. p(Г)³k, откуда r(Г)+p(Г)³p. Из двух полученных неравенств следует утверждение теоремы.
Заметим, что в доказательстве теоремы фактически изложены способы построения максимального паросочетания по минимальному реберному покрытию и минимального реберного покрытия по максимальному паросочетанию.