Теорема Холла — различия между версиями
(→Теорема) |
(→Теорема) |
||
| Строка 18: | Строка 18: | ||
|id=th1. | |id=th1. | ||
|author=Холл | |author=Холл | ||
| − | |statement=Полное парасочетание существует тогда и только тогда, когда для любого <tex> A \subset L </tex> | + | |statement=Полное парасочетание существует тогда и только тогда, когда для любого <tex> A \subset L </tex> выполнено <tex>|A| <= |N(A)| </tex> |
|proof=доказательство (необязательно) | |proof=доказательство (необязательно) | ||
}} | }} | ||
Версия 17:41, 22 декабря 2012
Содержание
Определения
Пусть - двудольный граф.
| Определение: |
| Полным(совершенным) паросочетанием называется паросочетание в которое входят все вершины. |
| Определение: |
| Пусть . Множeством соседей |
Теорема
| Теорема (Холл): |
Полное парасочетание существует тогда и только тогда, когда для любого выполнено |
| Доказательство: |
| доказательство (необязательно) |
