Cтраница 2
Следующая теорема, принадлежащая Дилворту [1], была сформулирована для решеток 1), но позже ( Мирский и Перфект [1]) было установлено, что этот результат эквивалентен теореме Холла. Два элемента решетки ( см. монографию Биркгофа [1]) называются несравнимыми, если ни один из них не доминирует над другим. Под цепью в решетке понимается путь, идущий в диаграмме Хассе решетки из более верхнего элемента в более нижний. [16]
А - множество вершин а е X U У, достижимых из свободных вершин в X при помощи частичных чередующихся цепей, определенных аналогично тому, как это сделано в доказательстве теоремы Холла. [17]
Прежде чем показать, как с помощью теории матроидов можно упростить доказательство теоремы 27D о существовании общей трансверсали для двух семейств подмножеств множества Е, докажем результат, являющийся естественным обобщением на матроиды теоремы Холла. Напомним, что теорема Холла дает необходимое и достаточное условие для того, чтобы некоторое семейство подмножеств множества Л имело трансверсаль. Ответ на этот вопрос дает следующая теорема, известная как теорема Радо. [18]
Каждая - грань ( t e Na-i d - d mMn) многогранника Мп задается в форме / 7 л еМя: дг у 0 V (, j) e ate NnxNn - Условия непустоты множества Т7 дает теорема Холла ( см. следствие 4.14 гл. [19]
Теорема Фробениуса дает характеризацию двудольных графов, обладающих совершенным паросочетанием. Теорема Холла содержит характеризацию двудольных графов, имеющих паросочетание из А в В. Теорема Кенига дает формулу для числа паросочетания в двудольном графе. [20]
Если мы сможем доказать, что & имеет трансверсаль, то тем самым мы докажем теорему, поскольку элементы этой трансверсали и образуют дополнительную строку. По теореме Холла достаточно доказать, что объединение любых k множеств Si содержит по меньшей мере k различных элементов. А это очевидно, ибо любое такое объединение содержит ( п - m) k элементов ( включая повторения), и если бы в нем было менее k различных элементов, то по крайней мере один из них повторялся бы более чем п - m раз, что невозможно. [21]
Прежде чем показать, как с помощью теории матроидов можно упростить доказательство теоремы 27D о существовании общей трансверсали для двух семейств подмножеств множества Е, докажем результат, являющийся естественным обобщением на матроиды теоремы Холла. Напомним, что теорема Холла дает необходимое и достаточное условие для того, чтобы некоторое семейство подмножеств множества Л имело трансверсаль. Ответ на этот вопрос дает следующая теорема, известная как теорема Радо. [22]
Поразительно, что это очевидное необходимое условие является в то же время и достаточным. В этом и состоит теорема Холла о свадьбах; вследствие ее важности мы дадим три доказательства теоремы Холла. Первое из них принадлежит Халмошу и Вогену. [23]
Теорема 1 является аналогом теоремы об образующих конечных нильпотентных групп. Легко получить и аналог теоремы Холла о центральных рядах. Зщ что противоречит условию. [24]
Поразительно, что это очевидное необходимое условие является в то же время и достаточным. В этом и состоит теорема Холла о свадьбах; вследствие ее важности мы дадим три доказательства теоремы Холла. Первое из них принадлежит Халмошу и Вогену. [25]
Для К I условие ( 4) было получено сначала Бруком и Райзером, а затем обобщено Шрикхандом и Шюцен-бергером ( см. Райзер [ II ], гл. X), удовлетворяющих ( 2) и ( 3), в ряде случаев доказывается с помощью теоремы Холла - Коннора о вложении [ 11, стр. [26]
С его помощью воспроизведены классические результаты для диаграмм с одной петлей1); это рассмотрение аналогично приведенному для интеграла унитарности в § 7 гл. Стоит отметить, что Фотиади и Фам работают с компонентами 4-им-пульсов. Из теоремы Холла - Вайтмана следует, что при переходе к инвариантам ( Pi Pj) 2 не появляется никаких дополнительных особенностей. [27]
Часто нужно отыскивать трансверсаль семейства A ( Ai... Эта трансверсаль является независимым подмножеством матроида. Теорема Радо, частным случаем которой является теорема Холла, отвечает на вопрос о существовании такой трансверсали. [28]
Строительному управлению для выполнения работы требуются каменщик, плотник, водопроводчик и слесарь. На эти должности имеются пять претендентов: один может работать каменщиком, другой - плотником, третий - каменщиком и водопроводчиком и еще двое имеют по две специальности - водопроводчика и слесаря. Если да, то подробно проверьте выполнение условия теоремы Холла. [29]
Следовательно, эти две теоремы в некотором смысле эквивалентны. Позднее в этой главе мы докажем теорему Менгера и теорему о максимальном потоке и минимальном разрезе, каждая из которых тоже эквивалентна теореме Холла. [30]