Лемма о единственном паросочетании в графе замен

Утверждение:

Пусть двудольный граф [math]G[/math] содержит единственное полное паросочетание [math]M[/math]. Тогда можно упорядочить вершины левой [math](a_i \in A)[/math] и правой [math](b_i \in B)[/math] долей таким образом, что [math]\forall j \gt i : (a_i b_j) \notin G[/math]. При этом рёбра паросочетания будут иметь вид [math](a_i b_i)[/math].

[math]\triangleright[/math]

Индукция по [math]|A|[/math]. При [math]|A|=1[/math] утверждение очевидно. Пусть [math]|A|=n\gt 1[/math] (для [math]|A|=n-1[/math] утверждение верно). Возьмем произвольную вершину в левой доли. Будем строить из неё чередующуюся цепь, добавляя по очереди ребро, входящее в [math]M[/math], и ребро, не входящее в [math]M[/math]. Заметим, что такой путь не содержит циклов (циклы нечётной длины невозможны, так как граф двудольный, циклы чётной длины отсутствуют из-за единственности паросочетания). Если последнее добавленное ребро не принадлежит [math]M[/math], то присоединим к цепи ребро из [math]M[/math], инцидентное последней вершине. Значит, построение цепи прервется только при добавлении ребра из [math]M[/math] при достижении вершины степени 1. Таким образом, последнее ребро в цепи имеет вид [math](ab) \in M[/math], где [math]a \in A, b \in B, \deg b = 1[/math]. Положим [math]a_n=a, b_n=b[/math]. Для [math]G \setminus \{a_n \cup b_n \}[/math] утверждение верно по предположению индукции. С другой стороны, так как [math]\deg b_n = 1[/math], то [math](a_i b_n) \notin G[/math] при [math]i\lt n[/math], поэтому для [math]j = n[/math] утверждение также верно.

[math]\triangleleft[/math]

Лемма (о единственном паросочетании в графе замен):

Дан матроид [math]M = \langle X,I \rangle [/math]. Пусть двудольный граф [math]G_M(A) = \{ (x, y) | x \in A, y \notin A, A \setminus x \cup y \in I \}[/math] содержит единственное полное паросочетание на [math]A \oplus B[/math], где [math]A\in I[/math] и [math]|A| = |B|[/math]. Тогда [math]B \in I[/math].

Доказательство:

[math]\triangleright[/math]

Упорядочим вершины левой [math](y_i \in A \setminus B)[/math] и правой [math](z_j \in B \setminus A)[/math] долей таким образом, что [math]\forall j \gt i : (y_i z_j) \notin G_M(A)[/math]. При таком упорядочивании ребра паросочетания имеют вид [math](y_i z_i)[/math]. Требуется доказать, что [math]B[/math] независимо. Предположим обратное. Пусть [math]B \notin I[/math], тогда существует цикл [math]C \subset B[/math]. Выберем минимальное [math]i[/math] такое, что [math]z_i \in C[/math]. Так как [math]\forall j \gt i : (y_i z_j) \notin G_M(A)[/math], то [math]A \setminus y_i \cup z_j \notin I[/math], следовательно, [math]C \setminus z_i \subset \langle A \setminus y_i \rangle [/math]. По свойствам замыкания 1 и 3 получаем: [math]C \setminus z_i \subset \langle A \setminus y_i \rangle \Rightarrow \langle C \setminus z_i \rangle \subset \langle \langle A \setminus y_i \rangle \rangle \Rightarrow \langle C \setminus z_i \rangle \subset \langle A \setminus y_i \rangle[/math] Так как [math]z_i \in \langle C \setminus z_i \rangle \subset \langle A \setminus y_i \rangle[/math], то [math]A \setminus y_i \cup z_i \notin I[/math], то есть в [math]G_M(A)[/math] не существует ребра [math](y_i z_i)[/math]. Но тогда, как было отмечено ранее, не существует полного паросочетания. Получили противоречие.

[math]\triangleleft[/math]

См. также

• Алгоритм Дейкстры

Источник

Chandra Chekuri — Combinatorial Optimization, с. 6