Теорема Холла: відмінності між версіями
[неперевірена версія] | [неперевірена версія] |
Вилучено вміст Додано вміст
м Заміна застарілого математичного синтаксису відповідно до mw:Extension:Math/Roadmap |
Немає опису редагування |
||
Рядок 1:
'''Теорема Холла''' (також відома як '''теорема про одруження''')— [[комбінаторика|комбінаторне]] твердження, що дає достатні і необхідні умови існування вибору різних елементів з деякого набору скінченних множин. Теорема названа на честь англійського математика [[Філіп Холл|Філіпа Холла]].
== Твердження ==
Теорема Холла може бути сформульована кількома способами, зокрема за допомогою мови [[теорія графів|теорії графів]] і теорії трансверсалів.
=== Твердження у теорії графів ===
Нехай <math>G=(V, E)\;</math>
: <math>(v \in A \land u \in B) \lor (v \in B \land u \in A)\;</math>,
тобто граф <math>G\;</math> є [[дводольний граф|дводольним]]. Тоді для даного
: <math>|W| \geqslant |K|,\;</math>
де:
: <math>W=\{w \in B\colon (\exists k\in K) \lbrace k,w\rbrace \in E\}\;</math>
[[множина]] елементів з <math>B,\;</math> що з'єднані ребрами хоча б з одним елементом підмножини <math>K\;</math>
Остання умова також називається умовою одружень.
=== Твердження у теорії трансверсалів ===
Нехай ''S'' = {''S''<sub>''1''</sub>, ''S''<sub>''2''</sub>,
Теорема Холла стверджує, що трансверсаль для ''S'' існує тоді й лише тоді, коли виконується умова
: <math>|T| \le \Bigl|\bigcup_{t \in T} t\Bigr|</math>
== Доведення ==
=== Доведення 1 ===
Доведення здійснюватимемо [[метод математичної індукції|методом математичної індукції]] щодо кількості елементів ''S''.
Рядок 32:
Спершу розглянемо випадок коли виконується
<math> \left\vert\cup T \right\vert \ge \left\vert T\right\vert+1</math>
для всіз власних підмножин ''T'' of ''S''. Виберемо довільний елемент <math>x\in S_n</math> представником <math>S_n.</math>
<math> S' = \left\{S_1\setminus\{x\},\ldots,S_{n-1}\setminus\{x\}\right\}</math>, тоді <math>R' \cup \{x\}</math> є трансверсаллю для S.
Але якщо взяти
Рядок 47:
Для завершення доведення достатньо знайти представників для множин <math>S\setminus T</math> що не містять елементів <math>\cup T</math>. Для цього достатньо довести, що для довільної множини <math>T'\subseteq S\setminus T</math>, виконується
: <math> \left\vert\cup T' \setminus \cup T\right\vert \ge \left\vert T'\right\vert</math>
і скористатися припущенням індукції.
Рядок 60:
зважаючи на відсутність спільних елементів у <math>T</math> і <math>T'</math>, і той факт, що <math> \left\vert\cup T\right\vert=\left\vert T\right\vert</math>. Тому за припущенням індукції, <math>S\setminus T</math> має трансверсаль, що не містить елементів <math>\cup T</math>.
=== Доведення 2 ===
Позначимо через <math>H\;</math> підграф
* кожна вершина інцидентна деякому ребру
* граф <math>H\;</math> задовольняє умову одружень і є мінімальним за включенням ребер графом, що задовольняє цю вимогу.
Позначимо <math>d_H(a)\;</math>
Для цього спершу позначимо : <math>N_H(K)=\{w \in B\colon (\exists k\in K) \lbrace k,w\rbrace \in E\}\;</math>
Рядок 70:
Припустимо, що деяка вершини <math>a \in A</math> з'єднується більш ніж з однією вершиною і нехай<math>b_1,b_2 \in N_H(a).\;</math> Тоді згідно з вибором <math>H\;</math> графи <math>H-\{ab_1\}\;</math> і <math>H-\{ab_2\}\;</math> не задовольняють умови одружень. Тому для <math>i=1,2\;</math> існують такі <math>A_i \subset A</math> що містять ''a'' і <math>|A_i| > |B_i|\;</math> де <math>B_i:=N_{H-\{ab_i\}}(A_i)\;</math>.
Звідси одержуємо:
: <math>|N_H(A_1 \cap A_2 \smallsetminus \{a\} )|\leq|B_1 \cap B_2|</math>
: <math>=|B_1|+|B_2|-|B_1 \cup B_2|=|B_1|+|B_2|-|N_H(A_1 \cup A_2)</math>
: <math>\leq |A_1|-1+|A_2|-1-|A_1 \cup A_2|=|A_1 \cap A_2 \smallsetminus \{a\} |-1</math>
Тобто H не задовольняє умови одружень, що суперечить припущенню і доводить теорему.
== Посилання ==
* [http://www.cut-the-knot.org/arithmetic/elegant.shtml Теорема Холла на сайті cut-the-knot]
* [http://www.cut-the-knot.org/arithmetic/marriage.shtml Теорема і алгоритм]
[[Категорія:Парування]]
|