Теорема Холла (також відома як теорема про одруження)— комбінаторне твердження, що дає достатні і необхідні умови існування вибору різних елементів з деякого набору скінченних множин. Теорема названа на честь англійського математика (Філіпа Холла).
Твердження
Теорема Холла може бути сформульована кількома способами, зокрема за допомогою мови теорії графів і теорії трансверсалів.
Твердження у теорії графів
Нехай — деякий граф, і
підмножини його вершин, такі що
, і для довільного ребра
такого що
, справедливе твердження
,
тобто граф є двочастковим. Тоді для даного графа існує набір ребер, що з'єднують вершини
з різними вершинами
тоді й лише тоді коли для кожної підмножини елементів
виконується
де:
множина елементів з що з'єднані ребрами хоча б з одним елементом підмножини
Остання умова також називається умовою одружень.
Твердження у теорії трансверсалів
Нехай S = {S1, S2, … } — деяка сім'я скінченних множин. Трансверсалем для S, називається множина X = {x1, x2, …} різних елементів (де |X| = |S|) з властивістю, що для всіх i, xi∈Si.
Теорема Холла стверджує, що трансверсаль для S існує тоді й лише тоді, коли виконується умова
Доведення
Доведення 1
Доведення здійснюватимемо методом математичної індукції щодо кількості елементів S.
Теорема очевидно справедлива для . Припустимо твердження теореми справедливе для
, доведемо її для випадку
.
Спершу розглянемо випадок коли виконується для всіз власних підмножин T of S. Виберемо довільний елемент
представником
Якщо існує трансверсаль для
, тоді
є трансверсаллю для S. Але якщо взяти
то за припущенням,
. Згідно з припущенням індукції для
і як наслідок для
існує трансверсаль.
В іншому випадку для деякої виконується рівність
. Для
маємо, що для кожної
виконується
, і за припущенням індукції для
існує трансверсаль.
Для завершення доведення достатньо знайти представників для множин що не містять елементів
. Для цього достатньо довести, що для довільної множини
, виконується
і скористатися припущенням індукції.
Маємо
,
зважаючи на відсутність спільних елементів у і
, і той факт, що
. Тому за припущенням індукції,
має трансверсаль, що не містить елементів
.
Доведення 2
Позначимо через підграф графа
такий, що
- кожна вершина інцидентна деякому ребру графа
- граф
задовольняє умову одружень і є мінімальним за включенням ребер графом, що задовольняє цю вимогу.
Позначимо — степінь вершини a в графі
. Очевидно, що
. Для доведення теореми Холла достатньо довести, що
.
Для цього спершу позначимо :
Припустимо, що деяка вершини з'єднується більш ніж з однією вершиною і нехай
Тоді згідно з вибором
графи
і
не задовольняють умови одружень. Тому для
існують такі
що містять a і
де
. Звідси одержуємо:
Тобто H не задовольняє умови одружень, що суперечить припущенню і доводить теорему.
Посилання
- Теорема Холла на сайті cut-the-knot [ 3 листопада 2009 у Wayback Machine.]
- Теорема і алгоритм [ 3 червня 2010 у Wayback Machine.]
- [en]. An Introduction to the Theory of Groups. — 4th. — Springer (Graduate Texts in Mathematics), 1994. — 532 с. — .(англ.)
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет