Изменения

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

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

132 байта добавлено, 01:58, 28 января 2016
Нет описания правки
==Определения==
Пусть <tex>G(V,E)</tex> {{---}} [[Основные_определения_теории_графов#Двудольный_граф |двудольный граф]] . <ref name="Generalizing"/> <tex>L</tex> {{---}} множество вершин первой доли. <tex>R</tex> {{---}} множество вершин правой доли.
{{Определение
|id=def1.
{{Теорема
|id=th1.
|author=Холл<ref name="Marriage"/>
|statement=Полное паросочетание существует тогда и только тогда, когда для любого <tex>A \subset L </tex> выполнено <tex>|A| \leqslant |N(A)|</tex>.
|proof=
==Примечания==
Иногда теорему называют теоремой о свадьбах.<references><ref name="Generalizing">Также теорема обобщается на граф, имеющий произвольное множество долей.</ref><ref name="Marriage">Иногда теорему называют теоремой о свадьбах.</ref></references>
==Источники информации==
27
правок

Навигация