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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Теорема Холла(також відома як теорема про одруження)— комбінаторне твердження, що дає достатні і необхідні умови існування вибору різних елементів з деякого набору скінченних множин. Теорема названа на честь англійського математика Філіпа Холла.

Твердження[ред.ред. код]

Теорема Холла може бути сформульована кількома способами, зокрема за допомогою мови теорії графів і теорії трансверсалів.

Твердження у теорії графів[ред.ред. код]

Нехай — деякий граф, і підмножини його вершин, такі що , і для довільного ребра такого що , справедливе твердження

,

тобто граф є дводольним. Тоді для даного графа існує набір ребер, що з'єднують вершини з різними вершинами тоді й лише тоді коли для кожної підмножини елементів виконується

де:

множина елементів з що з'єднані ребрами хоча б з одним елементом підмножини Остання умова також називається умовою одружень.

Твердження у теорії трансверсалів[ред.ред. код]

Нехай S = {S1, S2, ... } - деяка сім'я скінченних множин. Трансверсалем для S, називається множина X = {x1, x2, ...} різних елементів (де |X| = |S|) з властивістю, що для всіх i, xiSi.

Теорема Холла стверджує, що трансверсаль для S існує тоді й лише тоді, коли виконується умова


Доведення[ред.ред. код]

Доведення 1[ред.ред. код]

Доведення здійснюватимемо методом математичної індукції щодо кількості елементів S.

Теорема очевидно справедлива для . Припустимо твердження теореми справедливе для , доведемо її для випадку .

Спершу розглянемо випадок коли виконується для всіз власних підмножин T of S. Виберемо довільний елемент представником Якщо існує трансверсаль для , тоді є трансверсаллю для S. Але якщо взяти то за припущенням, . Згідно з припущенням індукції для і як наслідок для існує трансверсаль.

В іншому випадку для деякої виконується рівність . Для маємо, що для кожної виконується , і за припущенням індукції для існує трансверсаль.

Для завершення доведення достатньо знайти представників для множин що не містять елементів . Для цього достатньо довести, що для довільної множини , виконується

і скористатися припущенням індукції.

Маємо

,

зважаючи на відсутність спільних елементів у і , і той факт, що . Тому за припущенням індукції, має трансверсаль, що не містить елементів .

Доведення 2[ред.ред. код]

Позначимо через підграф графа такий, що

  • кожна вершина інцидентна деякому ребру графа
  • граф задовольняє умову одружень і є мінімальним за включенням ребер графом, що задовольняє цю вимогу.

Позначимо — степінь вершини a в графі . Очевидно, що . Для доведення теореми Холла достатньо довести, що .

Для цього спершу позначимо :

Припустимо, що деяка вершини з'єднується більш ніж з однією вершиною і нехай Тоді згідно з вибором графи і не задовольняють умови одружень. Тому для існують такі що містять a і де . Звідси одержуємо:

Тобто H не задовольняє умови одружень, що суперечить припущенню і доводить теорему.

Посилання[ред.ред. код]