Пример 2.7

На рис. 2.16 задан граф G, который содержит паросочетание R₁ = { 2 } (рис. 2.16,б) и паросочетание R₂ = { 1, 3 } (рис. 2.16,с).

Рис. 2.16. Граф G (а) и его возможные паросочетания: R₁ = { 2 } (б); R₂ = { 1, 3 } (в)

Одной из важных задач на графе является задача нахождения паросочетания (паросочетаний, если их несколько) с наибольшим количеством ребер. Число ребер такого паросочетания (наибольшего паросочетания) обозначается через p (G). Это число является инвариантом для графа G в том смысле, что для любого графа F, изоморфного G, имеем: p (F) = p (G). Для графа из примера 2.7 p (G) = 2.

Метод чередующихся цепей

Граф G с выделенным в нем паросочетанием R обозначают через G_R, ребра R с инцидентными им вершинами называют толстыми, а остальные ребра и вершины графа G_R – тонкими. Иначе, вершины инцидентные ребрам паросочетания, называют насыщенными.

Чередующейся цепью в графеG_R (относительно выделенного паросочетания) называется простая цепь ненулевой длины, ребра которой поочередно то тонкое, то толстое.

Чередующаяся цепь в G_R называется R - увеличителем, если она соединяет тонкие (ненасыщенные) вершины.

Из этих определений следует, что концевые ребра R -увеличителя тоже тонкие.

С помощью R -увеличителя легко переделать паросочетание R графа G в другое паросочетание _`R, содержащее на одно ребро больше, заменив в графе G_R все тонкие ребра увеличителя на толстые, а все толстые ребра – на тонкие.

Дата добавления: 2015-07-20