Изменения
Перенаправление на Граф замен#Лемма о единственном паросочетании в графе замен
#перенаправление [[Граф замен#Лемма о единственном паросочетании в графе замен]]
{{Утверждение
|statement=Пусть [[Двудольные_графы_и_раскраска_в_2_цвета|двудольный граф]] <tex>G</tex> содержит единственное [[Связь_максимального_паросочетания_и_минимального_вершинного_покрытия_в_двудольных_графах#Связь_максимального_паросочетания_и_минимального_вершинного_покрытия_в_двудольном_графе|полное паросочетание]] <tex>M</tex>. Тогда можно упорядочить вершины левой <tex>(a_i \in A)</tex> и правой <tex>(b_i \in B)</tex> долей таким образом, что <tex>\forall j > i : (a_i b_j) \notin G</tex>. При этом рёбра паросочетания будут иметь вид <tex>(a_i b_i)</tex>.
|about=
о единственном паросочетании в графе замен
|statement= Дан [[Определение матроида|матроид]] <tex>M = \langle X,I \rangle </tex>. Пусть двудольный граф <tex>G_M(A) = \{ (x, y) | \mid x \in A, y \notin A, A \setminus x \cup y \in I \}</tex> содержит единственное полное паросочетание на <tex>A \oplus B</tex>, где <tex>A\in I</tex> и <tex>|A| = |B|</tex>. Тогда <tex>B \in I</tex>.
|proof=
[[Файл:Graph replacement.png|thumb|left|160px|]]
== Источники информации ==
* ''Chandra Chekuri'' — [http://www.cs.illinois.edu/class/sp10/cs598csc/Lectures/Lecture16.pdf '''Chandra Chekuri — Combinatorial Optimization'''], с. 6
[[Категория:Алгоритмы и структуры данных]]
[[Категория:Матроиды]]
[[Категория:Пересечение матроидов]]
