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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Определения)
(Определения)
Строка 11: Строка 11:
 
|id=def2.
 
|id=def2.
 
|nеat=1
 
|nеat=1
|definition=Пусть <tex>X \subset V </tex>. Множeством '''соседей''' <tex>N(X)= \{ y \in V: (x,y) \in E \}</tex>
+
|definition=Пусть <tex>X \subset V </tex>. Множeством '''соседей''' <tex>N(X)= \{ y \in V: (x,y) \in E \}</tex>
 
}}
 
}}
  

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

Определения

Пусть [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]

1)Очевидно, что если существует полное паросочетание, то для любого [math]A \subset L [/math] выполнено [math]|A| \leq |N(A)|[/math]. У любого подмножества вершин есть по крайней мере столько же соседей.

2)В обратную сторону будем доказывать так :
[math]\triangleleft[/math]

Ссылки

Смотри также