Дискретная математика: графы и автоматы. Альпин Ю.А - 59 стр.

UptoLike

ВУЗ: 

КФУ | Казань

Составители: 

Рубрика: 

§ 3. Приложения теоремы о потоках 59
меньше, чем k − l дуг, ведущих от вершин-юношей из X к вершинам-
девушкам из
¯
X. Таким образом, |E
X
| ≥ (m − k) + l + (k − l) = m.
Равенство |E
X
| = m достигается при X = {s}. ¤
§ 3. Приложения теоремы о потоках                              59


меньше, чем k − l дуг, ведущих от вершин-юношей из X к вершинам-
девушкам из X̄. Таким образом, |EX | ≥ (m − k) + l + (k − l) = m.
Равенство |EX | = m достигается при X = {s}. ¤

Страницы