Теорема Холла

Материал из Викиконспекты
Перейти к: навигация, поиск

Определения

Пусть [math]G(V,E)[/math] - двудольный граф.

Определение:
Полным(совершенным) паросочетанием называется паросочетание в которое входят все вершины.


Определение:
Пусть [math]X \subset V [/math]. Множeством соседей [math]N(X)= {y \in V: (x,y) \in E }[/math]


Теорема

Теорема (Холл):
Полное парасочетание существует тогда и только тогда, когда для любого [math] A \subset L [/math] выполнено [math]|A| \leq |N(A)| [/math]
Доказательство:
[math]\triangleright[/math]
доказательство (необязательно)
[math]\triangleleft[/math]

Ссылки

Смотри также