Теорема Холла — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Теорема)
(Теорема)
Строка 18: Строка 18:
 
|id=th1.  
 
|id=th1.  
 
|author=Холл
 
|author=Холл
|statement=Полное парасочетание существует тогда и только тогда, <tex> \forall A \subset  L </tex> выполнено <tex>|A| \leq |N(A)| </tex>
+
|statement=Полное паросочетание существует тогда и только тогда, когда для любого A \subset  L </tex> выполнено <tex>|A| \leq |N(A)| </tex>.
|proof=доказательство (необязательно)
+
|proof=
 +
1) Очевидно, что если существует полное паросочетание то выполнено условие.
 
}}
 
}}
  
 
==Ссылки==
 
==Ссылки==
 
==Смотри также==
 
==Смотри также==

Версия 17:45, 22 декабря 2012

Определения

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

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


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


Теорема

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

Ссылки

Смотри также