Дан полный двудольный граф с вершинами 1,2,3,4 в первой доле и a, b, c, d во второй. На графе задано паросочетание {1 ~b, 3 a, 4 c}. Укажите цепи, которые являются чередующимися относительно этого паросочетания (цепи заданы последовательностью вершин):

Рассмотрим по шагам каждую цепь. Напомним, что цепь называется чередующейся относительно данного паросочетания, если при прохождении по её ребрам они чередуются: ребро из паросочетания, ребро не из паросочетания, ребро из паросочетания и т.д. Дано паросочетание M = {1–b, 3–a, 4–c}.

Мы имеем двудольный граф с вершинами из первой доли: 1,2,3,4 и второй доли: a,b,c,d.

────────────────────────────── (1) Цепь: c – 3 – b – 1

Определим ребра цепи: • Ребро (c, 3). Заметим, что в паросочетании есть ребро (4, c), а не (3, c), значит (c,3) не принадлежит M. • Ребро (3, b). В паросочетании для вершины ...