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

ТвердженняРедагувати

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

Твердження у теорії графівРедагувати

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

 ,

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

 

де:

 

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

Твердження у теорії трансверсалівРедагувати

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

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


 

ДоведенняРедагувати

Доведення 1Редагувати

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

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

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

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

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

 

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

Маємо

 

 

 ,

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

Доведення 2Редагувати

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

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

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

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

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

 
 
 

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

ПосиланняРедагувати