Изменения

Перейти к: навигация, поиск

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

3 байта убрано, 00:54, 24 декабря 2012
Теорема
|statement=Полное паросочетание существует тогда и только тогда, когда для любого <tex>A \subset L </tex> выполнено <tex>|A| \leq |N(A)|</tex>.
|proof=
<tex>/leftarrowleftar</tex> Очевидно, что если существует полное паросочетание, то для любого <tex>A \subset L </tex> выполнено <tex>|A| \leq |N(A)|</tex>. У любого подмножества вершин есть по крайней мере столько же "соседей"("соседи по парасочетанию").
*В обратную сторону докажем по индукции(будем добавлять в изначально пустое паросочетание <tex>P</tex> по одному ребру, и доказывать, что мы можем это сделать, если <tex>P</tex> не полное). Таким образом, в конце получим что <tex>P</tex> — полное паросочетание.
#База: Одна вершина соединена хотя бы с одной вершиной из <tex>R</tex>. Следовательно база верна.
Анонимный участник

Навигация