ЧЕРЕДУЮЩАЯСЯ ЦЕПЬ

— цепь графа L = (X, U, Р) с выделенным в нем суграфом обладающая тем свойством, что ребра, принадлежащие U («жирные»), чередуются с ребрами, не принадлежащими суграфа L в Z, по Ч. ц. Q с мн-вом ребер V — это замена V новым суграфом , где , т. е. замена вдоль цепи Q всех «жирных» ребер «тонкими» и наоборот.

Суграф L, ребра которого не имеют друг с другом общих вершин, наз. паросочетанием графа L; если Q — простая Ч. ц. относительно L, такая, что ее начальная и конечная вершины не инцидентны никаким ребрам из U, то сдвиг L по Q приводит к новому паросочетанию содержащему на одно ребро больше, чем L (см. рис.); если же Ч. ц. указанного вида в L нет, то паросочетание L содержит наибольшее возможное к-во ребер. Этим пользуются в графов теории и ее

приложениях {напр., при решении задачи об сштим. назначении кандидатов на должности). Метод, основанный на сдвигах суграфов по Ч. ц., наз. еще венгерским. А. А. Зыков.