Изменения

Пусть дан двудольный граф <tex>G(A) = \{ (x, y) | x \in A, y \notin A, A \setminus x \cup y \in I \}</tex> — граф замен. В его правой доле можно выделить два подмножества вершин <tex>X_1 = \{z \in S \setminus I | I \cup z \in I_1 \}, тогда X_2 = \{z \in S \setminus I | I \cup z \in I_2 \}</tex>. Пусть <tex>P</tex> - кратчайший путь из <tex>X_1</tex> в его подграфе<tex>X_2</tex>. Рассмотрим сужение <tex>G'</tex> графа <tex>G</tex> на множество вершин, индуцированном кратчайшим путем лежащих в пути <tex>P</tex>.<br>Тогда в <tex>s \rightsquigarrow tG'</tex>, существует единственное полное бракосочетаниепаросочетание.