Читайте также:
|
|
На рис. 2.16 задан граф G, который содержит паросочетание R1 = { 2 } (рис. 2.16,б) и паросочетание R2 = { 1, 3 } (рис. 2.16,с).
Рис. 2.16. Граф G (а) и его возможные паросочетания: R1 = { 2 } (б); R2 = { 1, 3 } (в)
Одной из важных задач на графе является задача нахождения паросочетания (паросочетаний, если их несколько) с наибольшим количеством ребер. Число ребер такого паросочетания (наибольшего паросочетания) обозначается через p (G). Это число является инвариантом для графа G в том смысле, что для любого графа F, изоморфного G, имеем: p (F) = p (G). Для графа из примера 2.7 p (G) = 2.
Метод чередующихся цепей
Граф G с выделенным в нем паросочетанием R обозначают через GR, ребра R с инцидентными им вершинами называют толстыми, а остальные ребра и вершины графа GR – тонкими. Иначе, вершины инцидентные ребрам паросочетания, называют насыщенными.
Чередующейся цепью в графеGR (относительно выделенного паросочетания) называется простая цепь ненулевой длины, ребра которой поочередно то тонкое, то толстое.
Чередующаяся цепь в GR называется R - увеличителем, если она соединяет тонкие (ненасыщенные) вершины.
Из этих определений следует, что концевые ребра R -увеличителя тоже тонкие.
С помощью R -увеличителя легко переделать паросочетание R графа G в другое паросочетание `R, содержащее на одно ребро больше, заменив в графе GR все тонкие ребра увеличителя на толстые, а все толстые ребра – на тонкие.
Дата добавления: 2015-07-20; просмотров: 39 | Нарушение авторских прав
<== предыдущая страница | | | следующая страница ==> |
Пример 2.6 | | | Пример 2.8 |